This talk describes some of our recent work on distributed algorithms for emulating atomic read/write memory in dynamic network settings, for example, in mobile ad hoc networks or peer-to-peer networks. In such settings, processors and communication facilities may fail and recover, and may exhibit fluctuations in their timing behaviour. Participating clients may join and leave the system, and may fail. The algorithms must adapt to these changes, while maintaining the appearance of atomic memory.

We describe two approaches. The first is represented by our recent work on RAMBO and RAMBO II. (RAMBO stands for "Reconfigurable Atomic Memory for Basic Objects".) In these two algorithms, each memory object is replicated at several network locations. Reads and writes are performed using ``quorum configurations'', each consisting of a membership set and sets of read-quorums and write-quorums. These algorithms are reconfigurable: the configuration is allowed to change on-the-fly, and such changes do not cause violations of atomicity. Reconfiguration is performed using a combination of a consensus protocol and a background ``garbage-collection'' protocol. The algorithms allows reads, writes, and reconfigurations to proceed concurrently. In particular, reads and writes are not blocked or significantly delayed by reconfigurations.

The second approach, designed specifically for mobile ad hoc networks, is represented by our even more recent work on Geoquorums. In this work, a simple static network abstraction layer is defined and implemented over the mobile ad hoc network layer. Then atomic memory is implemented over the network abstraction layer using a simple static replication strategy. This approach suggests a new strategy for programming mobile ad hoc networks.

Joint work with Alex Shvartsman, Seth Gilbert, Shlomi Dolev, and Jennifer Welch.