From spontaneous total order to uniform total order

Abstract

A total order protocol 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.Optimistic total order protocols have been proposed to alleviate this problem. However, different optimistic protocols offer quite distinct services. This paper makes an overview of different optimistic approaches and shows how they can be combined in a single adaptive protocol.