Technical report detail

Optimal Atomic Broadcast and Multicast Algorithms for Wide Area Networks

by Nicolas Schiper and Fernando Pedone

In this paper, we study the atomic broadcast and multicast problems, two fundamental abstractions for building fault-tolerant systems. As opposed to atomic broadcast, atomic multicast allows messages to be addressed to a subset of the processes in the system, each message possibly being multicast to a different subset. Our study focusses on wide area networks where groups of processes, i.e., processes physically close to each other, are inter-connected through high latency communication links. In this context, we capture the cost of our algorithms, denoted latency degree, as the number of inter-group message delays between the broadcasting (multicasting) of a message and its delivery. We present an atomic multicast algorithm with a latency degree of two and show that it is optimal. This lower bound holds even if no link nor process failure occurs. We then present an atomic broadcast algorithm with a latency degree of one. To achieve such a low latency, the algorithm is proactive, i.e., it may take actions even though no messages are broadcast. Nevertheless, it is quiescent: provided that the number of broadcast messages is finite, the algorithm eventually ceases its operation. As a consequence, in runs where the algorithm becomes quiescent too early, its latency degree is two. We show that this is unavoidable, and establish a lower bound on the quiescence of atomic broadcast algorithms. Compared to existing solutions, our algorithms either achieve a lower latency degree or equal the best latency degree but send fewer intra-group messages.

Technical report 2007/04, February 2007

BibTex entry

@techreport{07optimal, author = {Nicolas Schiper and Fernando Pedone}, title = {Optimal Atomic Broadcast and Multicast Algorithms for Wide Area Networks}, institution = {University of Lugano}, number = {2007/04}, year = 2007, month = feb }