This talk will present an algorithm that emulates atomic read/write shared objects in a dynamic network setting. We call it RAMBO: Reconfigurable Atomic Memory for Basic Objects.
To ensure that the data is highly available and long-lived, each object is replicated at several network locations. To ensure atomicity, reads and writes are performed using "quorum configurations", each of which consists of a set of members plus sets of read-quorums and write-quorums. The algorithm is reconfigurable: the quorum configuration is allowed to change during computation, and such changes do not cause violations of atomicity. Any quorum configuration may be installed at any time---no intersection requirement is imposed on the sets of members or on the quorums of distinct configurations. The algorithm tolerates processor and link failures.
The algorithm performs three major activities, all concurrently: (1) reading and writing the objects, (2) choosing new configurations and notifying members, and (3) identifying and removing ("garbage-collecting") obsolete configurations. The algorithm is composed of two sub-algorithms: a main algorithm, which handles reading, writing, and garbage-collection, and a reconfiguration algorithm, which handles the selection and dissemination of new configurations.
The main safety property, atomicity, holds for arbitrary patterns of
asynchrony. Performance properties depend on particular failure and timing
assumptions. In particular, if participants gossip periodically in the
background, if garbage-collection is scheduled periodically, if reconfiguration
is not requested too frequently, and if quorums of active configurations do not
fail, then read and write operations complete within time that is proportional
to the maximum message latency.
Joint work with Alex Shvartsman