Harel, Itay ;
JacobFanani, Amit ;
Sulamy, Moshe ;
Afek, Yehuda
Consensus in Equilibrium: Can One Against All Decide Fairly?
Abstract
Is there an equilibrium for distributed consensus when all agents except one collude to steer the decision value towards their preference? If an equilibrium exists, then an n1 size coalition cannot do better by deviating from the algorithm, even if it prefers a different decision value. We show that an equilibrium exists under this condition only if the number of agents in the network is odd and the decision is binary (among two possible input values). That is, in this framework we provide a separation between binary and multivalued consensus. Moreover, the input and output distribution must be uniform, regardless of the communication model (synchronous or asynchronous). Furthermore, we define a new problem  Resilient Input Sharing (RIS), and use it to find an iff condition for the (n1)resilient equilibrium for deterministic binary consensus, essentially showing that an equilibrium for deterministic consensus is equivalent to each agent learning all the other inputs in some strong sense. Finally, we note that (n2)resilient equilibrium for binary consensus is possible for any n. The case of (n2)resilient equilibrium for multivalued consensus is left open.
BibTeX  Entry
@InProceedings{harel_et_al:LIPIcs:2020:11806,
author = {Itay Harel and Amit JacobFanani and Moshe Sulamy and Yehuda Afek},
title = {{Consensus in Equilibrium: Can One Against All Decide Fairly?}},
booktitle = {23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
pages = {20:120:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771337},
ISSN = {18688969},
year = {2020},
volume = {153},
editor = {Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11806},
URN = {urn:nbn:de:0030drops118065},
doi = {10.4230/LIPIcs.OPODIS.2019.20},
annote = {Keywords: distributed computing, game theory, rational agents, consensus}
}
11.02.2020
Keywords: 

distributed computing, game theory, rational agents, consensus 
Seminar: 

23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Issue date: 

2020 
Date of publication: 

11.02.2020 