2003 International Conference on Dependable Systems and Networks (DSN'03)
RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks
San Francisco, California
June 22-June 25
ISBN: 0-7695-1952-0
This paper presents a new algorithm implementing reconfigurable atomic read/write memory for highly dynamic environments. The original RAMBO algorithm, recently developed by Lynch and Shvartsman [15, 16], guarantees atomicity for arbitrary patterns of asynchrony, message loss, and node crashes. RAMBO II implements a different approach to establishing new configurations: instead of operating sequentially, the new algorithm reconfigures aggressively, transferring information from old configurations to new configurations in parallel. This improvement substantially reduces the time to establish a new configuration and to remove obsolete configurations. This, in turn, substantially increases fault tolerance and reduces the latency of read/write operations when the network is unstable or reconfiguration is bursty. This paper presents RAMBO II, a correctness proof, and a conditional analysis of its performance. Preliminary empirical studies illustrate the advantages of the new algorithm.
Citation:
Seth Gilbert, Nancy Lynch, Alex Shvartsman, "RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks," dsn, pp.259, 2003 International Conference on Dependable Systems and Networks (DSN'03), 2003