[Resource Topic] 2010/330: Distributed Rational Consensus

Welcome to the resource topic for 2010/330

Distributed Rational Consensus

Authors: Amjed Shareef


The \textit{consensus} is a very important problem in distributed computing, where among the n players, the honest players try to come to an agreement even in the presence of t malicious players. In game theoretic environment, \textit{the group choice problem} is similar to the \textit{rational consensus problem}, where every player p_i prefers come to consensus on his value v_i or to a value which is as close to it as possible. All the players need to come to an agreement on one value by amalgamating individual preferences to form a group or social choice. In rational consensus problem, there are no malicious players. We consider the rational consensus problem in the presence of few malicious players. The players are assumed to be rational rather than honest and there exist few malicious players among them. Every rational player primarily prefers to come to consensus on his value and secondarily, prefers to come to consensus on other player’s value. In other words, if w_1, w_2 and w_3 are the payoffs obtained when p_i comes to consensus on his value, p_i comes to consensus on other’s value and p_i does not come to consensus respectively, then w_1 > w_2 > w_3. We name it as \textit{distributed rational consensus problem} DRC. The players can have two values, either 1 or 0, i.e binary consensus. The rational majority is defined as number of players, who wants to agree on one particular value, and they are more than half of the rational players. Similarly rational minority can be defined. We have considered EIG protocol, and characterized the rational behaviour, and shown that EIG protocol will not work in rational environment. We have proved that, there exists no protocol, which solves distributed consensus problem in fixed running time, where players have knowledge of other players values during the protocol. This proof is based on Maskin’s monotonicity property. The good news is, if the players do not have knowledge about other players values, then it can be solved. This can be achieved by verifiable rational secret sharing, where players do not exchange their values directly, but as pieces of it.

ePrint: https://eprint.iacr.org/2010/330

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .