Fault-tolerant distributed systems are becoming more important, but in existing systems, maintaining the consistency of replicated data is quite expensive. The Totem single-ring protocol supports consistent concurrent operations by placing a total order on broadcast messages. This total order is derived from the sequence number in a token that circulates around a logical ring imposed on a set of processors in a broadcast domain. The protocol handles reconfiguration of the system when processors fail and restart or when the network partitions and remerges. Extended virtual synchrony ensures that processors deliver messages and configuration changes to the application in a consistent, systemwide total order. An effective flow control mechanism enables the Totem single-ring protocol to achieve message-ordering rates significantly higher than the best prior total-ordering protocols.

Introduction The development of communication protocols is significantly more difficult than the development of sequential programs. Communication protocols are harder to develop because of the many possible executions and ordering of events, the difficulty of recording the history of an execution, the inability to stop the system so that its state can be examined, the difficulty of injecting a stimulus or fault at exactly the right moment, and the lack of reproducibility. Fault-tolerance presents additional problems, particularly the need to recover correctly from rare failure modes and the appearance of correct operation even though the system contains serious defects. The protocol development environment presented here was designed to aid in the development of the Totem reliable ordered broadcast protocol, but its concepts are also applicable to other communication protocols. The development environment is a distributed discrete-event simulator designed to provide a testbed

The Totem protocol supports consistent concurrent operations by placing a total order on broadcast messages. This total order is achieved by including a sequence number in a token circulated around a logical ring that is imposed on a set of processors in a broadcast domain. A membership algorithm handles reconfiguration, including restarting of a failed processor and remerging of a partitioned network. Effective flow-control allows the protocol to achieve message ordering rates two to three times higher than the best prior protocols. The single-ring total ordering protocol of Totem provides fault-tolerant agreed and safe delivery of messages within a broadcast domain.>