Programming Research Group Technical Monograph PRG-87

A W Roscoe

October 1990, 55 pages, ISBN 0-902928-66-X

We introduce, and prove correct, two novel algorithms for preserving a form of consistency in distributed databases arranged as rings. The first uses as its model databases with a fixed number of fields with updates which assign known constant values to one of these "slots". The proof of this relies on a moderately complex combinatorial argument. The second algorithm, which can be viewed as generalising the first, takes a wider view and simply assumes that the set of updates have an operation analogous to the conjunction of group theory: given any u,v we can find u^v such that u;v=v;u^v, which satisfies some natural algebraic properties. Its proof relies on an algebraic argument based on partial orders, which may well have applications outside databases, for example in the field of "true concurrency". We indicate how the algorithm can be generalised to a number of other network topologies, and give guidelines for further generalisations. If combined with timestamping, the algorithms provide highly concurrent methods of ensuring that the sequence of updates executed at all nodes corresponds to the order implied by these timestamps.