AMp: a highly parallel atomic multicast protocol

ABSTRACT

This paper deals with the problem of reliable group communication for distributed applications, in the context of the Reliable Broadcast class of protocols. An atomic multicast protocol for token passing Lans is presented. The actual implementation is on an 8802/4 Token-bus, although it is applicable to 8802/5 Token-rings and the FDDI Fibre-Optic network. The simplicity and efficiency of reliable broadcast protocols may be considerably improved, if the system fault model is restricted or convenient architectures are used. Fail-controlled communication components are used here to build an efficient reliable multicast protocol on top of the exposed MAC interface of a VLSI Lan controller. The architecture is built on standard Lans, in view of taking advantage of the availability of communications hardware and the possibility of coexistence with standard stations, in the same network. The service offered allows transparent multicasting inside logical groups, which are dynamically created and updated. The primitive is highly parallel and provides atomic agreement and consistent delivery order, respecting logical precedence. These features are an important contribution for the implementation of high performance distributed computing systems.

REFERENCES

• Babaoglu 85: Oza.lp Babao~lu and Rog~rio Drummond. Streets of byzantium: network architectures for fast reliable broadcasts. IEEE Transactions on Software E~zgineering, (6), June 1985.
• Berglund 85: E.J. Berglund and D. Cheriton. A distributed multi-player game program using the distributed v kernel. IEEE, (2):, May 1985.
• Birman 87: 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]
• Cart 87: Mich~le Cart, Jean Ferric, and Sukrisno Mardyanto. Atomic broadcast protocol, preserving concurrency for an unreliable broadcast network. Local communication systems: LAN and PBX, 1987.
• Chang 84: 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]
• Cheriton 85: David R. Cheriton , Willy Zwaenepoel, Distributed process groups in the V Kernel, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.77-107, May 1985 [doi>10.1145/214438.214439]
• Cristian 85: F. Cristian, Aghili. H., R. Strong, and D. Dolev. Atomic Broadcast: From simple message diffusion to Byzantine Agreement. In FTCS15- Ann Arbor- USA, june 1985.
• Cristian 86: F. Cristian, Aghili. H., and R. Strong. Clock synchronization in the presence of omission and performance faults. In FTCS16- Viena- A ttstria, July 1986.
• Gray 78: J. Gray. Notes on database operating systems. Lecture Notes in Computer Science, 1978.
• Hadzilacos 84: Vassos Hadzilacos, Issues of fault tolerance in concurrent computations (databases, reliability, transactions, agreement protocols, distributed computing), 1985
• Lamport 78: 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]
• Lamport 82: 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]
• Martin 85: P. Martin, C. Guerin, and T. Muntean. Specification and implementation of protocols' reliabte broadcast protocols. Geneve, Switzerland, January 1985.
• Navaratnam 88: S. Navaratnam, S. Chanson, and G. Neufeld. Reliable group communication in distributed systems, pages 428-437, IEEE, San Jose - USA, June 1988.
• Peterson 88: Larry L. Peterson, Nick C. Buchholdz, and Richard D. Schlichting. Preserving and Using Contezt Information in Interyrocess Commanication. Technical Report 88-23, Departement of Computer Science, The University of Arizona, Tucson, Arizona 85721, May 1988.
• Powell 88: D. Powell, D. Seaton, G. Bonn, P. Verissimo, and F. Waeselynk. The Delta-4 approach to dependability in open distributed computing systems. In FTC$18 - Tokyo- Japan, June 1988.
• Schneider 84: Fred B. Schneider , David Gries , Richard D. Schlichting, Fault-tolerant broadcasts, Science of Computer Programming, v.4 n.1, p.1-15, April 1984 [doi>10.1016/0167-6423(84)90009-1]
• Schneider 86: Fred B. Schneider, The State Machine Approach: A Tutorial, Cornell University, Ithaca, NY, 1986
• Verissimo 87: Paulo Verissimo, Luis Rodrigues, and Jo~ Marques. Atomic Multicast Extensions for 802.4 Token-Bus. In FOC/LAN 87, Conference, Anaheim-USA, October 1987.
• Verissimo 88a: Paulo Verissimo. Redundant media mechanisms for dependable communication in token-bus lans. In Local Computer Network Conference, IEEE, Minneapolis-USA, October 1988.
• Verissimo 88b: Paulo Verissimo, Lufs Rodrigues, and Mario Baptista. AMP: A highly parallel atomic multicast primiiive. Technical Report RT/139, Delta4 Proj., INESC, Lisboa, Portugal, September 1988.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)
      C.2.5 Local and Wide-Area Networks
          Subjects: Buses; Access schemes

General Terms:
Design, Reliability