On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement

Our paper investigates the message complexity of two fundamental problems, leader election and agreement, in the crash-fault synchronous and fully-connected distributed network. We present randomized algorithms for both the problems and also show non-trivial lower bounds on the message complexity. Our algorithms achieve sublinear message complexity in the so-called implicit version of the two problems when tolerating more than a constant fraction of the faulty nodes. In comparison to the state-of-art, our results improved and extended the works of [Gilbert-Kowalski, SODA’10] (which studied only the agreement problem) in several directions. Specifically, our algorithms tolerate any number of faulty nodes up to . The message complexity (and also the time complexity) of our algorithms is optimal (up to a factor). Further, our algorithm works in anonymous networks, where nodes do not know each other. To the best of our knowledge, these are the first sublinear results for both the leader election and the agreement problem in the crash-fault distributed networks.

A full version of the paper is available at [3]