| MultiChord is a new variant of the Chord namespace management algorithm [7] that includes lightweight mechanisms
for accommodating a limited rate of change, specifically, process joins and failures. This paper describes the
algorithm formally and evaluates its performance, using both simulation and analysis. Our main result is that lookups
are provably correct—that is, each lookup returns results that are consistent with a hypothetical ideal system that differs
from the actual system only in entries corresponding to recent joins and failures—in the presence of a limited rate
of change. In particular, if the number of joins and failures that occur during a given time interval in a given region
of system are bounded, then all lookups are correct. A second result is a guaranteed upper bound for the latency of a
lookup operation in the absence of any other lookups in the system. Finally, we establish a relationship between the
deterministic assumptions of bounded joins and failures and the probabilistic assumptions (which are often used to
model large scale networks). In particular, we derive a lower bound for the mean time between two violations of the
deterministic assumptions in a steady state system where joins and failures are modeled by Poisson processes. |