Optimistic Atomic Broadcast

This paper presents an Optimistic Atomic Broadcast algorithm (OPT-ABcast) that exploits the spontaneous total order message reception property experienced in local area networks, in order to allow fast delivery of messages. The OPT-ABcast algorithm is based on the Optimistic Consensus problem (OPT-Consensus) that allows processes to decide optimistically or conservatively. A process optimistically decides if it knows that the spontaneous total order message reception property holds, otherwise it decides conservatively. We evaluate the efficiency of the OPT-ABcast and the OPT-Consensus algorithms using the notion of latency degree. 1 Introduction Atomic Broadcast is a useful abstraction for the development of fault tolerant distributed applications. Understanding the conditions under which Atomic Broadcast is solvable is an important theoretical issue that has been investigated extensively. Solving Atomic Broadcast efficiently is also an important and highly relevant pragmatic issue. W..