Browse Prior Art Database

Trans: A Broadcast Protocol for Distributed Systems

IP.com Disclosure Number: IPCOM000128375D
Original Publication Date: 1988-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 13 page(s) / 46K

Publishing Venue

Software Patent Institute

Related People

P.M. Melliar-Smith: AUTHOR [+4]

Abstract

Many distributed computer systems use a communication mechanism that is physically a broadcast medium, such as an Ethernet, 1553 bus, or packet ra-dio system. Other common communication media, such as a token ring, could function as broadcast media, even though they are not normally so used. The advantage of a broadcast communication medium is that it is physically possible to distribute a message simultaneously to several destinations. There are important activities in a distributed system that involve many pro-cessors simultaneously and that would benefit from broadcast or multicast com-munication. Among these are scheduling and load balancing, synchronization, process migration, remote procedure calls, nested atomic transactions, access to distributed information, locking, update and commitment, and transaction log--' ging. Recent work in distributed operating systems.. has made extensive use 'Of. broadcast and multicast communication [2,41. Existing communication protocols do not allow distributed systems to use this broadcast capability, but rather require messages to be point-to-point, from a single source to a single destination. They, therefore, require that many in-dividual messages and corresponding individual acknowledgments be sent. In a network of n nodes a total of 2 * n - 2 messages are required, when perhaps a single broadcast message would suffice. Broadcast communication simulated by point-to-point protocols is not only wasteful of the communication resource, but limits the size of the distributed system by saturating the communication medium and discourages the use of truly distributed algorithms because of their unnecessaxily high communication cost. Reliable transmission of a message requires the ability to retransmit the mes-sage because of damage or loss in transit. Within the ISO protocol hierarchy, the primary responsibility for ensuring this reliable transmission across the communi-cation medium lies with the data link layer communication protocol. Our broad-cast protoZo'l, Trans, is directed towards that layer of the hierarchy. Trans pro-vides only services appropriate to the data link layer, in contrast to other atomic broadcast protocols that ignore the hierarchy and are entirely self-contained. Trans can determine whether a processor has acknowledged receiving a message, but it has no responsibility for network membership or network reconfiguration following a failure. Most existing data link layer protocols use a positive-acknowledgment strat-egy, in which the recipient of a message explicitly transmits an acknowledgment of its receipt, either as a separate message or as a part of another message. The sender of the original message uses a timeout to trigger retransmission if no acknowledgment is received from the recipient. In a broadcast context such protocols require individual acknowledgments from each recipient, even if it is possible (which usually it is not) to take advantage of the broadcast medium to disseminate the message to all recipients. Thus, broadcasting with positive acknowledgments can reduce the number of messages from 2 * n - 2 to n, but this still does not take full advantage of the broadcast medium. To eliminate this overhead Trans uses a negative-acknowledgment strategy,--in which most processors transmit no acknowledgment if they receive a message.~,', successfully, but rather transmit a negative acknowledgment if they become aware-that they have not received a message. Trans ensures that a processor is able to determine that its message has been received by all of the intended recipients. There is a possibility that continued progress in communication technology, such as 100 MHz fiber links, will eliminate communication bottlenecks and the need for more efficient broadcast protocols, but techniques applicable to commu-nication axe also effective in enhancing the performance of processors. Further-more, for many systems the limiting factor is not so much the bandwidth of the communication medium but the operating system overhead associated with send-ing each message. Consequently, we anticipate that communication will continue to be a limiting resource and that broadcast protocols will become an important aspect of distributed systems. Given a reliable and efficient broadcast protocol, it is possible to take ad-vantage of it to construct efficient distributed application algorithms. We are investigating such algorithms for distributed mutual exclusion, locking, and syn-chronizati,5ii, as well as for update and commitment in a distributed database. Based on an algorithm for placing a total order on the sequence of broadcast messages, even in the presence of noisy communication and of processor fail-stop faults, remarkable improvements in efficiency are possible. Distributed opera-tions can be accomplished with on the order of a single broadcast message, one to two orders of magnitude less than the best existing algorithms for fault-tolerant distributed systems 18).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Trans: A Broadcast Protocol for Distributed Systems

P.M. Melliar-Smith, L.E. Moser

Department of Computer Science

December 1988

1. Introduction

Many distributed computer systems use a communication mechanism that is physically a broadcast medium, such as an Ethernet, 1553 bus, or packet ra-dio system. Other common communication media, such as a token ring, could function as broadcast media, even though they are not normally so used. The advantage of a broadcast communication medium is that it is physically possible to distribute a message simultaneously to several destinations. There are important activities in a distributed system that involve many pro-cessors simultaneously and that would benefit from broadcast or multicast com-munication. Among these are scheduling and load balancing, synchronization, process migration, remote procedure calls, nested atomic transactions, access to distributed information, locking, update and commitment, and transaction log--' ging. Recent work in distributed operating systems.. has made extensive use 'Of. broadcast and multicast communication [2,41. Existing communication protocols do not allow distributed systems to use this broadcast capability, but rather require messages to be point-to-point, from a single source to a single destination. They, therefore, require that many in- dividual messages and corresponding individual acknowledgments be sent. In a network of n nodes a total of 2 * n - 2 messages are required, when perhaps a single broadcast message would suffice. Broadcast communication simulated by point-to-point protocols is not only wasteful of the communication resource, but limits the size of the distributed system by saturating the communication medium and discourages the use of truly distributed algorithms because of their unnecessaxily high communication cost. Reliable transmission of a message requires the ability to retransmit the mes-sage because of damage or loss in transit. Within the ISO protocol hierarchy, the primary responsibility for ensuring this reliable transmission across the communi-cation medium lies with the data link layer communication protocol. Our broad- cast protoZo'l, Trans, is directed towards that layer of the hierarchy. Trans pro-vides only services appropriate to the data link layer, in contrast to other atomic broadcast protocols that ignore the hierarchy and are entirely self-contained. Trans can determine whether a processor has acknowledged receiving a message, but it has no responsibility for network membership or network reconfiguration following a failure. Most existing data link layer protocols use a positive- acknowledgment strat-egy, in which the recipient of a message explicitly transmits an acknowledgment of its receipt, either as a separate message or as a part of another message. The sender of the original message uses a timeout to trigger retransmission if no acknowledgment...