Low-Latency Atomic Broadcast in the Presence of Contention

摘要

The Atomic Broadcast algorithm described in this paper can deliver messages in two communication steps, even if multiple processes broadcast at the same time. It tags all broadcast messages with the local real time, and delivers all messages in order of these timestamps. The Ω-elected leader simulates processes it suspects to have crashed (◇S). For fault-tolerance, it uses a new cheap Generic Broadcast algorithm that requires only a majority of correct processes (n ＞ 2f) and, in failure-free runs, delivers all non-conflicting messages in two steps. The main algorithm satisfies several new lower bounds.