Author: Omar M. Bakr
Supervised by:
Idit Keidar.
M.Eng. Thesis, MIT department of Electrical Engineering
and Computer Science, Feb 11, 2003.
Abstract:
We study the running time of distributed algorithms deployed in a
widely distributed setting over the Internet using TCP. We consider
two simple primitives. Both primitives corresponds to a
communication round which is employed by many different
algorithms and systems. In the first primitive, every host sends
information to every other host. The second primitive propagates
information from a quorum of hosts to a quorum of hosts. Both
primitives occur in numerous distributed algorithms. We experiment
with four algorithms that typically implement the first primitive and
two that implement the second. We run our experiments on twenty-eight
hosts at geographically disperse locations over the Internet. We
observe that message-loss has a large impact on algorithm running
times, which causes leader-based algorithms to usually outperform
decentralized ones. We also observe that algorithms, in which hosts
need only to hear from a quorum, are more reliable, efficient, and
tolerant to bad links than algorithms where every host is required to
hear from every other host in the system.
Download thesis (postscript or pdf):
ps,
pdf,
ps.gz.
Part of the thesis material has been published in:
Evaluating the Running Time of a Communication Round over the
Internet, PODC 2002.
Last modified: Wed Mar 5 09:33:59 IST 2003