Nancy Lynch and Ion Stoica

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1306
2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1306.pdf

MultiChord is a new variant of the Chord namespace management algorithm 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.

BibTeX citation:

@techreport{Lynch:CSD-04-1306,
    Author = {Lynch, Nancy and Stoica, Ion},
    Title = {MultiChord: A Resilient Namespace Management Protocol},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5371.html},
    Number = {UCB/CSD-04-1306},
    Abstract = {MultiChord is a new variant of the Chord namespace management algorithm 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.}
}

EndNote citation:

%0 Report
%A Lynch, Nancy
%A Stoica, Ion
%T MultiChord: A Resilient Namespace Management Protocol
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1306
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5371.html
%F Lynch:CSD-04-1306