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

This article 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 (Monte Carlo) 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 (n - polylog n). The message complexity (and also the time complexity) of our algorithms is optimal (up to a polylog n 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 sub-linear results for both the leader election and the agreement problem in the crash-fault distributed networks.