Efficient Player-Optimal Protocols For Strong And Differential Consensus

In this paper we consider the following two variants of the consensus problem. First, the strong consensus problem, where n players attempt to reach agreement on a value initially held by one of the correct players, despite the (malicious) behavior of up to t of them. We also formulate the delta-differential consensus problem, which specifies that the value agreed on must be of a certain plurality among the correct players -- specifically, that the plurality of any other value cannot exceed the plurality of the decision value by more than delta. In this paper we study these problems, and present efficient protocols and tight lower bounds for several standard distributed computation models -- unconditional, computational, synchronous, and asynchronous.