Sublinear Message Bounds for Randomized Agreement
John E. Augustine, Anisur Rahaman Molla, Gopal Pandurangan · 2018
This paper focuses on understanding the message complexity of randomized agreement in synchronous distributed networks. We focus on the so-called implicit agreement problem where each node starts with an input value (0 or 1) and at the end one or more nodes should decide on a common input value which should be equal to some node's input value (there can be undecided nodes). Implicit agreement is a generalization of the fundamental agreement and leader election problems.