Evaluating the Running Time of a Communication Round over the Internet.

Authors: Omar Bakr and Idit Keidar

In the 21st ACM Symposium on Principles of Distributed Computing (PODC '02), Monterey, CA, USA, pages 243-252, July 2002.


We study the running time of distributed algorithms deployed in a widely distributed setting over the Internet using TCP. We consider a simple primitive that corresponds to a communication round in which every host sends information to every other host; this primitive occurs in numerous distributed algorithms. We experiment with four algorithms that typically implement this primitive. We run our experiments on ten 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.

Download PODC 2002 paper: ps, ps.gz, pdf.
Download talk slides: pps, pps.gz, ppt, ppt.gz.

Last modified: Mon Jul 1 13:56:59 EDT 2002