The Totem multiple-ring ordering and topology maintenance protocol

ABSTRACT

The Totem multiple-ring protocol provides reliable totally ordered delivery of messages across multiple local-area networks interconnected by gateways. This consistent message order is maintained in the presence of network partitioning and remerging, and of processor failure and recovery. The protocol provides accurate topology change information as part of the global total order of messages. It addresses the issue of scalability and achieves a latency that increases logarithmically with system size by exploiting process group locality and selective forwarding of messages through the gateways. Pseudocode for the protocol and an evaluation of its performance are given. —Authors' Abstract

REFERENCES

• 1: Deborah Anne Agarwal, TOTEM: a reliable ordered delivery protocol for interconnected local-area networks, University of California at Santa Barbara, Santa Barbara, CA, 1995
• 2: D. A. Agarwal , L. E. Moser , P. M. Melliar-Smith , R. K. Budhia, A reliable ordered delivery protocol for interconnected local area networks, Proceedings of the 1995 International Conference on Network Protocols, p.365, November 07-10, 1995
• 3: ALVAREZ, G., CRISTIAN, F., AND MISHRA, S. 1998. On-demand asynchronous atomic broadcast. In Proceedings of the 5th IFIP International Working Conference on Dependable Computing for Critical Applications (Urbana-Champaign, IL, Sept. 1995), R. K. Iyer, M. Morganti, W. K. Fuchs, and V. Gligor, Eds. IEEE Computer Society Press, Los Alamitos, CA, 119-137.
• 4: AMIR, Y., DOLEV, D., KRAMER, S., AND MALKI, D. 1992. Transis: A communication subsystem for high availability. In Proceedings of the 22nd IEEE International Symposium on Fault-Tolerant Computing (Boston, MA, July). IEEE Press, Piscataway, NJ, 76-84.
• 5: Y. Amir , L. E. Moser , P. M. Melliar-Smith , D. A. Agarwal , P. Ciarfella, The Totem single-ring ordering and membership protocol, ACM Transactions on Computer Systems (TOCS), v.13 n.4, p.311-342, Nov. 1995 [doi>10.1145/210223.210224]
• 6: Kenneth P. Birman , Robert V. Renesse , Robbert Van Renesse, Reliable Distributed Computing with the ISIS Toolkit, IEEE Computer Society Press, Los Alamitos, CA, 1994
• 7: 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]
• 8: CRISTIAN, F. AND MISHRA, S. 1995. The pinwheel asynchronous atomic broadcast protocols. In Proceedings of the 2nd International Symposium on Autonomous Decentralized Systems (Phoenix, AZ, Apr.). IEEE Computer Society Press, Los Alamitos, CA, 215-221.
• 9: DOLEV, D., KRAMER, S., AND MALKI, D. 1993. Early delivery totally ordered multicast in asynchronous environments. In Proceedings of the 23rd IEEE International Symposium on Fault-Tolerant Computing (Toulouse, France, June). IEEE Computer Society Press, Los Alamitos, CA, 544-553.
• 10: P. D. Ezhilchelvan , R. A. Macedo , S. K. Shrivastava, Newtop: a fault-tolerant group communication protocol, Proceedings of the 15th International Conference on Distributed Computing Systems, p.296, May 30-June 02, 1995
• 11: Weijia Jia , Jörg Kaiser , Edgar Nett, RMP: Fault-Tolerant Group Communication, IEEE Micro, v.16 n.2, p.59-67, April 1996 [doi>10.1109/40.491463]
• 12: KAASHOEK, M. F. AND TANENBAUM, A.S. 1991. Group communication in the Amoeba distributed operating system. In Proceedings of the 11th IEEE International Conference on Distributed Computing Systems (Arlington, TX, May). IEEE Computer Society Press, Los Alamitos, CA, 436-447.
• 13: 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]
• 14: MELLIAR-SMITH, P. M. AND MOSER, L.E. 1993. Trans: A reliable broadcast protocol. IEE Trans. Commun. 140, 6 (Dec.), 481-493.
• 15: P. M. Melliar-Smith , L. E. Moser , V. Agrawala, Broadcast Protocols for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.17-25, January 1990 [doi>10.1109/71.80121]
• 16: MISHRA, S., PETERSON, L. L., AND SCHLICHTING, R. D. 1993. Consul: A communication substrate for fault-tolerant distributed programs. Distrib. Syst. Eng. 1, 2 (Dec.), 87-103.
• 17: MOSER, L. E., AMIR, Y., MELLIAR-SMITH, P. M., AND AGARWAL, D.A. 1994. Extended virtual synchrony. In Proceedings of the 14th IEEE International Conference on Distributed Computing Systems (Poznan, Poland, June). IEEE Computer Society Press, Los Alamitos, CA, 56-65.
• 18: L. E. Moser , P. M. Melliar-Smith , D. A. Agarwal , R. K. Budhia , C. A. Lingley-Papadopoulos, Totem: a fault-tolerant multicast group communication system, Communications of the ACM, v.39 n.4, p.54-63, April 1996 [doi>10.1145/227210.227226]
• 19: Louise E. Moser , P. M. Melliar-Smith , Vivek Agrawala, Asynchronous fault-tolerant total ordering algorithms, SIAM Journal on Computing, v.22 n.4, p.727-750, Aug. 1993 [doi>10.1137/0222048]
• 20: RAJAGOPALAN, B. AND MCKINLEY, P.K. 1989. A token-based protocol for reliable, ordered multicast communication. In Proceedings of the 8th IEEE Symposium on Reliable Distributed Systems (Seattle, WA, Oct.). IEEE Computer Society Press, Los Alamitos, CA, 84-93.
• 21: H. Fonseca, Totally ordered multicast in large-scale systems, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.503, May 27-30, 1996
• 22: E. Thomopoulos , L. E. Moser , P. M. Melliar-Smith, Analyzing the latency of the Totem multicast protocols, Proceedings of the 6th International Conference on Computer Communications and Networks, p.42, September 22-25, 1997
• 23: Robbert van Renesse , Kenneth P. Birman , Silvano Maffeis, Horus: a flexible group communication system, Communications of the ACM, v.39 n.4, p.76-83, April 1996 [doi>10.1145/227210.227229]
• 24: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications
      C.2.4 Distributed Systems
          Subjects: Network operating systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Algorithms, Performance, Reliability

Keywords:
Lamport timestamp, network partitioning, reliable delivery, topology maintenance, total ordering, virtual synchrony