MultiChord: A Resilient Namespace Management Protocol

Abstract

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