In the 21st International Conference on Distributed Computing Systems (ICDCS), pages 247-254, Phoenix, Arizona, April 2001.
Previous version: Technical Memorandum MIT-LCS-TM-611 Massachusetts Institute of Technology, Laboratory for Computer Science, November 2000.
Several studies have shown that dynamic voting leads to more available solutions than other paradigms for maintaining a primary component. However, these studies have assumed that every attempt made by the algorithm to form a new primary component terminates successfully. Unfortunately, in real systems, this is not always the case: a change in connectivity can interrupt the algorithm while it is still attempting to form a new primary component; in such cases, algorithms typically block until processes can resolve the outcome of the interrupted attempt.
This paper uses simulations to evaluate the effect of interruptions on the availability of dynamic voting algorithms. We study four dynamic voting algorithms, and identify two important characteristics that impact an algorithm's availability in runs with frequent connectivity changes. First, we show that the number of communication rounds exchanged in an algorithm plays a significant role in the availability achieved, especially in the degradation of availability as connectivity changes become more frequent. Second, we show that the number of processes that need to be present in order to resolve past attempts impacts the availability, especially during long runs with numerous connectivity changes.
ICDCS talk slides (powerpoint): ppt, ppt.gz.
Technical report: ps, pdf, ps.gz.
Kyle Ingols' M.Eng thesis: ps, pdf, ps.gz.
The testing environment source code is available here.