Browse Prior Art Database

Atomic Broadcast Protocol for Redundant Broadcast Channels

IP.com Disclosure Number: IPCOM000100243D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 3 page(s) / 141K

Publishing Venue

IBM

Related People

Cristian, F: AUTHOR

Abstract

This article describes a protocol for atomically broadcasting messages in networks of processors connected by redundant broadcast channels.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 44% of the total text.

Atomic Broadcast Protocol for Redundant Broadcast Channels

       This article describes a protocol for atomically
broadcasting messages in networks of processors connected by
redundant broadcast channels.

      An atomic broadcast protocol is a protocol which, for some time
constant T (called the broadcast termination time), possesses the
following properties: (1) atomicity: every update whose broadcast is
initiated by some processor at time t on its clock is either
delivered to all correct processors at time t+T on their clocks or is
never delivered to any correct processor, (2) order: all updates
delivered at correct processors are delivered in the same order at
each correct processor, and (3) termination: every update whose
broadcast is initiated by a correct processor at time t on its clock
is delivered at all correct processors at time t+T on their clocks.
A broadcast channel has the following characteristic properties: 1)
when no failures occur, any message transmitted on the channel is
received by all correct processors attached to that channel 2) when
failures occur, only a subset (possibly empty) of correct processors
receive a message transmitted on the channel, but all these
processors receive the same message.  Typical examples of broadcast
channels are buses (e.g., IEEE 802.3 Ethernet or IEEE 802.4 token
bus) and rings (e.g., IEEE 802.5 token ring).

      Let R be the number of redundant broadcast channels to which
the processors involved in atomic broadcast are attached.  Let 1, 2,
..., R denote these channels.  We assume each processor is attached
to all broadcast channels. We denote E the maximum deviation between
processor clocks maintained by an underlying clock synchronization
algorithm and D the maximum real time needed for transmitting a
message on an arbitrary channel from one processor to any other
processor attached to that channel (the minimum transmission time is
assumed to be 0 for simplicity).  We assume that all processor
identifiers are distinct and a total order relation exists on them.

      If no more than F=R-1 processor and channel timing failures can
occur while a broadcast is in progress, the protocol below achieves
atomic broadcast.

      Each processor maintains a history H (initially empty) of
messages being broadcast.  Each entry in H is of type
(Time,Processor,Integer, Data,Channel).  The communication servers
which implement the atomic broadcast service are structured into four
parallel tasks: Start, Receive, Relay, and Deliver.  These tasks
access the shared variable H in mutual exclusion.  For any F, D, and
E, we let T=(F+1)(D+E) be the protocol termination time.

      To initiate the atomic broadcast of a piece of data m, a sender
on processor s passes m to the local Start task. Let t be the local
time at which the Start task receives m. To broadcast m, the Start
task 1) transmits messages (t,s,1,m) on the channels 1, 2,..., R in
this order, 2) inserts (t,s,...