Performance Evaluation of Distributed Algortihms over the Internet.

Author: Omar M. Bakr
Supervised by: Idit Keidar.

M.Eng. Thesis, MIT department of Electrical Engineering and Computer Science, Feb 11, 2003.


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