Evaluating the running time of a communication round over the internet

ABSTRACT

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.

REFERENCES

• 1: D. A. Agarwal , L. E. Moser , P. M. Melliar-Smith , R. K. Budhia, The Totem multiple-ring ordering and topology maintenance protocol, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.93-132, May 1998 [doi>10.1145/279227.279228]
• 2: Y. Amir , A. Wool, Evaluating quorum systems over the Internet, Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96), p.26, June 25-27, 1996
• 3: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 4: Chandra, B., Dahlin, M., Gao, L., and Nayate, A. End-to-end WAN service availability. In Third Usenix Symposium on Internet Technologies and Systems (USITS01) (Mar. 2001).
• 5: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 6: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 7: Sally Floyd , Vern Paxson, Difficulties in simulating the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.4, p.392-403, August 2001 [doi>10.1109/90.944338]
• 8: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 9: R. Guerraoui , A. Schiper, The Decentralized Non-Blocking Atomic Commitment Protocol, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.2, October 25-28, 1995
• 10: Katherine Guo , Werner Vogels , Robbert van Renesse, Structured virtual synchrony: exploring the bounds of virtual synchronous group communication, Proceedings of the 7th workshop on ACM SIGOPS European workshop: Systems support for worldwide applications, September 09-11, 1996, Connemara, Ireland [doi>10.1145/504450.504488]
• 11: Idit Keidar , Danny Dolev, Increasing the resilience of distributed and replicated database systems, Journal of Computer and System Sciences, v.57 n.3, p.309-324, Dec. 1998 [doi>10.1006/jcss.1998.1566]
• 12: Idit Keidar , Sergio Rajsbaum, On the cost of fault-tolerant consensus when there are no faults: preliminary version, ACM SIGACT News, v.32 n.2, June 2001 [doi>10.1145/504192.504195]
• 13: Idit Keidar , Jeremy Sussman , Keith Marzullo , Danny Dolev, Moshe: A group membership service for WANs, ACM Transactions on Computer Systems (TOCS), v.20 n.3, p.191-238, August 2002 [doi>10.1145/566340.566341]
• 14: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 15: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 16: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 17: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 18: S. Rajsbaum , M. Sidi, On the Performance of Synchronized Programs in Distributed Networks with Random Processing Times and Transmission Delays, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.939-950, September 1994 [doi>10.1109/71.308532]
• 19: Stefan Savage , Thomas Anderson , Amit Aggarwal , David Becker , Neal Cardwell , Andy Collins , Eric Hoffman , John Snell , Amin Vahdat , Geoff Voelker , John Zahorjan, Detour: Informed Internet Routing and Transport, IEEE Micro, v.19 n.1, p.50-59, January 1999 [doi>10.1109/40.748796]
• 20: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 22: Sergent, N. Evaluating latency of distributed algorithms using Petri nets. In 5th Euromicro Workshop on Parallel and Distributed Processing (London, UK, Jan. 1997), pp. 437-442.
• 23: Dale Skeen, Nonblocking commit protocols, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582339]
• 24: W. Richard Stevens, TCP/IP illustrated (vol. 1): the protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 25: Urbán, P., Défago, X., and Schiper, A. Contention-aware metrics for distributed algorithms: Comparison of atomic broadcast algorithms. In 9th IEEE International Conference on Computer Communications and Networks (IC3N 2000) (Oct. 2000).
• 26: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]