Introduction

The RAMBO algorithm is designed to to implement atomic, shared memory in a highly dynamic setting. The algorithm depends on a system of quorums, which provided sufficient data replication to ensure the continued availability of the data. One of the key algorithmic innovations in RAMBO is the ability for quorums to be efficiently reconfigured. This allows nodes to join and fail without disturbing the ongoing operation of the algorithm. Most importantly, a reconfiguration operation creates minimal interference with ongoing read and write operations, allowing normal operations to complete even as the quorum system is being modified.

History of the RAMBO Algorithm

The original RAMBO algorithm [1] was originally presented at DISC 2002. The algorithm was shown to be quite efficient when reconfiguration rates are not too high and the network is relatively stable. An improvement, RAMBO II [2], was presented at DSN 2003, which performed "garbage-collection" in parallel, thus recovering more rapidly from unstable network conditions.

Implementation, Optimization, and Simulation

We implemented several variants of the RAMBO algorithms on a network-of-workstations [5]. These implementations are used for comparative performance studies, and to experiment with various algorithmic optimizations. We rigorously prove the correctness of each optimization. In one such development, we augmented RAMBO with an incremental gossip algorithm and support for graceful node departure with the goal of substantially improving performance of the initial RAMBO algorithms. Although the ideas are quite intuitive, proving correctness in the presence of failure, message, and asynchrony requires subtle arguments [4].

We have also simulated the RAMBO algorithm in the context of sensor networks [3].

Ongoing Work

We are developing a new algorithm for reconfigurable quorum systems that improves on RAMBO in two ways. First, it merges the reconfiguration and the "garbage-collection" mechanisms, reducing the amoung of configuration necessary to install a new quorum configuration. Second, it takes advantage of recent advances in the Paxos consensus protocol to speed up reconfiguration in the stable case. As a result, the new algorithm has the following behavior: In the common case, reads and writes require 4 message delays, and reconfiguration requires 5 message delays. When there are no concurrent write operations, read operations require only two message delays, and when the network is stable, reconfiguration requires only three message delays. Moreover, the algorithm can recover rapidly from unstable network behavior, with old configurations being discarded as soon as new configurations are installed.

Previous RAMBO algorithms are specified so that each instance of the service is dedicated to supporting a single atomic object. Multiple objects are implemented by composing several instances of the system, one per object. This results in substantial processing and communication overheads. In a new development we introduced the notion of domains that allow the users to group related atomic objects. The implementation accesses objects and manages configurations on the basis of domains, which significantly improves the utility and the performance of the resulting service. An experimental implementation of this service has been developed.

Research Support

This work was supported in part by NSF ITR Grant CCR-0121277, NSF Grants 9804665, 9988304, CCR-0326277, 64961-CS, NSF Career Award 9984778, AFOSR Contract #F49620-00-1-0097, DARPA Contract #F33615-01-C-1896, MURI AFOSR Award Number SA2796PO 1-0000243658, DARPA/AFOSR MURI Award F49620-02-1-0325, and DARPA Air Force contract number FA9550-04-C-0084.

References:

[1] Nancy A. Lynch, and Alex A. Shvartsman. RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks. In the Proceedings of the 5th International Symposium on Distributed Computing, October, 2002.

[2] Seth Gilbert, Nancy A. Lynch, and Alex A. Shvartsman. RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks. In the Proceedings of the International Conference on Dependable Systems and Networks, June, 2003

[3] Jake Beal and Seth Gilbert. RamboNodes for the Metropolitan Ad Hoc Network. In the Proceedings of DIWANS Workshop, International Conference on Dependable Systems and Networks, July, 2004

[4] Chryssis Georgiou, Peter M. Musial, and Alex A. Shvartsman. Long-Lived RAMBO: Trading Knowledge for Communication. In the Proc. of 11'th Colloquium on Structural Information and Communication Complexity, Springer LNCS, pages 185-196, 2004

[5] Peter M. Musial and Alex A. Shvartsman. Implementing a Reconfigurable Atomic Memory Service for Dynamic Networks. In Proc. of 18'th International Parallel and Distributed Symposium -- FTPDS WS, page 208b, 2004