Message-ordered multicast by common building blocks

ABSTRACT

A message-ordered multicast service delivers messages from multiple senders to multiple receivers preserving some ordering properties among the messages such as their sending sequence or possible causality relationship. Different applications require different ordering properties. Existing message-ordered multicast protocols support only a specific ordering property.We describe a method to realize different message order multicast services using a network composed of switches and communication links with simple properties. Given these elements and their properties, we derived common building blocks which have different ordering capabilities (strong ordering or strong causal ordering). These building blocks are a very powerful and flexible tool to build more complex structures which are able to order the messages of multiple overlapping multicast groups.

REFERENCES

• 1: Brian Whetten , Todd Montgomery , Simon M. Kaplan, A High Performance Totally Ordered Multicast Protocol, Selected Papers from the International Workshop on Theory and Practice in Distributed Systems, p.33-57, September 05-09, 1994
• 2: Chris GauthierDickey , Daniel Zappala , Virginia Lo , James Marr, Low latency and cheat-proof event ordering for peer-to-peer games, Proceedings of the 14th international workshop on Network and operating systems support for digital audio and video, June 16-18, 2004, Cork, Ireland [doi>10.1145/1005847.1005877]
• 3: 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]
• 4: F. M. Kaashoek and A. S. Tanenbaum, Group communication in the Amoeba distributed operating system, IEEE International Conference on Distributed Computing Systems, pp. 222--230, May 1991
• 5: Ge-Ming Chiu , Chih-Ming Hsiao, A Note on Total Ordering Multicast Using Propagation Trees, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.217-223, February 1998 [doi>10.1109/71.663947]
• 6: Hector Garcia-Molina , AnneMarie Spauster, Ordered and reliable multicast communication, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.242-271, Aug. 1991 [doi>10.1145/128738.128741]
• 7: Ian Foster , Carl Kesselman, The Grid 2: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 8: J. C. Lin and S. Paul, RMTP: A Reliable Multicast Transport Protocol, presented at IEEE INFOCOMM96, San Francisco, California, March 1996
• 9: Jo-Mei Chang , N. F. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.251-273, Aug. 1984 [doi>10.1145/989.357400]
• 10: Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
• 11: Kenneth P. Birman , Robert V. Renesse , Robbert Van Renesse, Reliable Distributed Computing with the ISIS Toolkit, IEEE Computer Society Press, Los Alamitos, CA, 1994
• 12: M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron, Scribe: A large-scale and decentralized application-level multicast infrastructure, IEEE Journal on Selected Areas in Communication (JSAC) 20(8), October 2002
• 13: Maurice Herlihy , Srikanta Tirthapura , Roger Wattenhofer, Ordered Multicast and Distributed Swap, ACM SIGOPS Operating Systems Review, v.35 n.1, p.85-96, January 1, 2001 [doi>10.1145/371455.997810]
• 14: Michael J. Demmer , Maurice Herlihy, The Arrow Distributed Directory Protocol, Proceedings of the 12th International Symposium on Distributed Computing, p.119-133, September 24-26, 1998
• 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: R. Carr, The Tandem global update protocol, Tandem System Review, June, 1985
• 17: Richard M. Fujimoto, Parallel simulation: distributed simulation systems, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
• 18: S. E. Deering, Multicast routing in internetworks and extended LANs, Symposium proceedings on Communications architectures and protocols, p.55-64, August 16-18, 1988, Stanford, California, United States
• 19: S. Navaratnam et al, Reliable group communication in distributed systems, Proceedings, of the 8th International Conference on Distributed Computing Systems (ICDCS-8), June, 1988
• 20: W. H. Leung and S.-C. Tu, Conference Connection Method in a Multicast Packet Switching Network, U. S. Patent 5103444, April, 1992
• 21: Xavier Défago , André Schiper , Péter Urbán, Total order broadcast and multicast algorithms: Taxonomy and survey, ACM Computing Surveys (CSUR), v.36 n.4, p.372-421, December 2004 [doi>10.1145/1041680.1041682]
• 22: Xiaohua Jia, A Total Ordering Multicast Protocol Using Propagation Trees, IEEE Transactions on Parallel and Distributed Systems, v.6 n.6, p.617-627, June 1995 [doi>10.1109/71.388042]
• 23: Yair Amir , Ciprian Tutu, From Total Order to Database Replication, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.494, July 02-05, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
      C.2.3 Network Operations
          Subjects: Network management
      C.2.4 Distributed Systems

General Terms:
Algorithms, Design