Efficient player-optimal protocols for strong and differential consensus

Abstract

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. (Recall that in the standard version of the problem, the players are also required to decide on one of the correct players' input values, but only when they all start with the same value; otherwise, they can decide on a default.) Although the problem is closely related to the standard problem, the only known solution with the optimal number of players requires exponential computation and communication in the unconditional setting.Even though the decision would be a value originally held by a correct player, strong consensus allows for a decision value that is the least common among the correct players. We also formulate the δ-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 δ.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.