Third Annual Paris Kanellakis Memorial Lecture


"Reconfigurable Atomic Memory for Dynamic Networks"

Nancy Lynch, MIT

Talk to be given by Alex Shvartsman, University of Connecticut, MIT

Thursday, December 11, 2003 at 4:00 P.M.

Lubrano Conference Room

We describe recent work on algorithms to implement atomic operations on shared objects in a dynamic network setting. A key component of this work is the RAMBO algorithm (Reconfigurable Atomic Memory for Basic Objects) that can be tailored to run in many settings including peer-to-peer networks and mobile ad hoc networks. Long-lived data availability is ensured through replication. Atomicity is ensured by performing reads and writes using ``quorum configurations,'' sets of members and set of read/write-quorums. We show that RAMBO is reconfigurable without violating atomicity and that it tolerates processor and link failures.

RAMBO concurrently
(1) reads and writes objects,
(2) chooses new configurations and notifies members, and
(3) identifies and removes (``garbage-collecting'') obsolete configurations.

Atomicity, the main safety property of RAMBO, holds for arbitrary patterns of asynchrony. RAMBO's performance depends on failure and timing assumptions. Under reasonable assumptions, we show that read and write operations complete within a time proportional to the maximum message latency.

We also discuss the ``Geoquorums algorithm'' that implements atomic memory in mobile ad hoc networks using an abstract computing platform consisting of virtual machines associated with fixed geographical locations. Mobile nodes implement the virtual machines, using a replicated state machine strategy.

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

Host: John Savage