LCS Publication Details
Publication Title: MultiChord: A Resilient Namespace Management Protocol
Publication Author: Lynch, Nancy
Additional Authors: Ion Stoica
LCS Document Number: MIT-LCS-TR-936
Publication Date: 2-19-2004
LCS Group: Theory of Computation
Additional URL:
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.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.