Availability Study of Dynamic Voting Algorithms.

Author: Kyle W. Ingols
Supervised by: Idit Keidar.

M.Eng. thesis, MIT department of Electrical Engineering and Computer Science, May 5, 2000.


Fault tolerant distributed systems often select a primary component to allow a subset of the processes to function when failures occur. Several studies have examined algorithms for selecting primary components. 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: if a change in connectivity occurs while the algorithm is still running, algorithms typically block until processes can resolve the outcome of the interrupted attempt.

This thesis first presents a framework for the implementation of primary component algorithms. This framework is used to implement several algorithms based on the dynamic voting principle. The thesis then shows, using simulations, that an algorithm's performance is highly affected by interruptions; availability degrades as more connectivity changes occur, and as these changes become more frequent.

The testing environment source code is available here.

Download (postscript or pdf): ps, pdf, ps.gz.

Part of the thesis material has been published in:
Availability Study of Dynamic Voting Algorithms, ICDCS 2001.

Last modified: Wed Mar 5 09:36:14 IST 2003