Author:
Kyle W. Ingols
Supervised by:
Idit Keidar.
M.Eng. thesis, MIT department of Electrical Engineering
and Computer Science, May 5, 2000.
Abstract:
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.
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