An Indulgent Uniform Total Order Algorithm with Optimistic
Delivery.
Pedro Vicente and Luís Rodrigues
Selected sections of this report were published in the Proceedings of
the 21st IEEE Symposium on Reliable Distributed Systems, pp. 92-101,
Osaka, Japan, October 2002.
Abstract
A total order algorithm is a fundamental building block in the
construction of distributed fault-tolerant applications.
Unfortunately, the implementation of such a primitive can be
expensive both in terms of communication steps and of number of
messages exchanged. This problem is exacerbated in large-scale
systems, where the performance of the algorithm may be limited by
the presence of high-latency links. Typically, the most efficient
total order algorithms do not provide uniform delivery and assume
the availability of a perfect failure detector. Such algorithms may
provide inconsistent results if the system assumptions do not hold.
On the other hand, algorithms that assume an unreliable failure
detector always provide consistent results but exhibit higher costs.
This paper presents a new algorithm that combines the advantages of
both approaches. On good periods, when the system is stable and
processes are not suspected, the algorithm operates as if a perfect
failure detector is assumed. Yet, the algorithm is indulgent, since
it never violates consistency, even in runs where processes are
suspected.
Also available extended report (gzip postscript), (pdf) .
Luís Rodrigues