LIPIcs.OPODIS.2019.20.pdf
- Filesize: 0.5 MB
- 17 pages
Document
Consensus in Equilibrium: Can One Against All Decide Fairly?
Authors
-
Part of:
Volume:
23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-02-11
Cite AsGet BibTex
Itay Harel, Amit Jacob-Fanani, Moshe Sulamy, and Yehuda Afek. Consensus in Equilibrium: Can One Against All Decide Fairly?. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.20
https://doi.org/10.4230/LIPIcs.OPODIS.2019.20
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 n-1 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 multi-valued 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 (n-1)-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 (n-2)-resilient equilibrium for binary consensus is possible for any n. The case of (n-2)-resilient equilibrium for multi-valued consensus is left open.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
Keywords
- distributed computing
- game theory
- rational agents
- consensus
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Ittai Abraham, Lorenzo Alvisi, and Joseph Y. Halpern. Distributed computing meets game theory: combining insights from two fields. SIGACT News, 42(2):69-76, 2011. URL: https://doi.org/10.1145/1998037.1998055.
- Ittai Abraham, Danny Dolev, Rica Gonen, and Joseph Y. Halpern. Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In PODC, pages 53-62, 2006. URL: https://doi.org/10.1145/1146381.1146393.
- Ittai Abraham, Danny Dolev, and Joseph Y. Halpern. Distributed Protocols for Leader Election: A Game-Theoretic Perspective. In DISC, pages 61-75, 2013. URL: https://doi.org/10.1007/978-3-642-41527-2_5.
-
Yehuda Afek, Yehonatan Ginzberg, Shir Landau Feibish, and Moshe Sulamy. Distributed Computing Building Blocks for Rational Agents. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, 2014.
- Yehuda Afek, Shaked Rafaeli, and Moshe Sulamy. The Role of A-priori Information in Networks of Rational Agents. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1-5:18, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.5.
- Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement, Michael Dahlin, Jean-Philippe Martin, and Carl Porth. BAR fault tolerance for cooperative services. In SOSP, pages 45-58, 2005. URL: https://doi.org/10.1145/1095810.1095816.
- Dor Bank, Moshe Sulamy, and Eyal Waserman. Reaching Distributed Equilibrium with Limited ID Space. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, pages 48-51, 2018. URL: https://doi.org/10.1007/978-3-030-01325-7_9.
- Varsha Dani, Mahnush Movahedi, Yamel Rodriguez, and Jared Saia. Scalable rational secret sharing. In PODC, pages 187-196, 2011. URL: https://doi.org/10.1145/1993806.1993833.
-
John R. Douceur. The Sybil Attack. In Revised Papers from the First International Workshop on Peer-to-Peer Systems, IPTPS '01, pages 251-260, London, UK, UK, 2002. Springer-Verlag.
- Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. J. ACM, 32(2):374-382, April 1985. URL: https://doi.org/10.1145/3149.214121.
- Georg Fuchsbauer, Jonathan Katz, and David Naccache. Efficient Rational Secret Sharing in Standard Communication Networks. In TCC, pages 419-436, 2010. URL: https://doi.org/10.1007/978-3-642-11799-2_25.
- Adam Groce, Jonathan Katz, Aishwarya Thiruvengadam, and Vassilis Zikas. Byzantine Agreement with a Rational Adversary. In ICALP (2), pages 561-572, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_50.
- Joseph Y. Halpern and Vanessa Teague. Rational secret sharing and multiparty computation: extended abstract. In STOC, pages 623-632, 2004. URL: https://doi.org/10.1145/1007352.1007447.
- Joseph Y. Halpern and Xavier Vilaça. Rational Consensus: Extended Abstract. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 137-146, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2933057.2933088.
- Anna Lysyanskaya and Nikos Triandopoulos. Rationality and Adversarial Behavior in Multi-party Computation. In CRYPTO, pages 180-197, 2006. URL: https://doi.org/10.1007/11818175_11.
- Adi Shamir. How to Share a Secret. Commun. ACM, 22(11):612-613, 1979. URL: https://doi.org/10.1145/359168.359176.
- Assaf Yifrach and Yishay Mansour. Fair Leader Election for Rational Agents in Asynchronous Rings and Networks. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pages 217-226, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3212734.3212767.