Simultaneity is harder than agreement

Abstract

We prove a strong lower bound on the number of rounds of message exchange required to achieve simultaneity (i.e., action in the same round) in certain synchronous fault-tolerant distributed systems. Specifically, our bound holds for any randomized protocol which solves either the simultaneous agreement problem or the distributed firing squad problem. It is known that any protocol that solves either of these problems and that is resilient to t processor faults has at least one execution that lasts at least t + 1 rounds. We strengthen that bound by showing that all normal executions of such a protocol last at least t + 1 rounds. The restriction to normal executions is a technical one that excludes certain executions in which a fortuitous pattern of processor faults enables early termination. The lower bounds proved in this paper contrast with known protocols that achieve agreement on a value (without simultaneity) in fewer than t + 1 rounds in some normal executions. Our results are proved for randomized protocols, for a benign failure model (crash faults), and for a weak adversary. They apply a fortiori to deterministic protocols, more malicious failure models, and stronger adversaries. © 1991.