2012/03/20 by Xiaohui Bei, Wei Chen, Bei, Xiaohui +3 · 1 citation
Computer Science · Decision Sciences · #Computer Science and Game Theory (cs.GT) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Game Theory and Applications #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.GT
paper · pdf · doi:10.48550/arxiv.1203.4324
openalex publication_date 2012/03/20 · arxiv created 2012/06/06 · arxiv updated 2012/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study distributed consensus in synchronous systems subject to both unexpected crash failures and strategic manipulations by rational agents in the system. We adapt the concept of collusion-resistant Nash equilibrium to model protocols that are resilient to both crash failures and strategic manipulations of a group of colluding agents. For a system with n distributed agents, we design a deterministic protocol that tolerates 2 colluding agents and a randomized protocol that tolerates n - 1 colluding agents, and both tolerate any number of failures. We also show that if colluders are allowed an extra communication round after each synchronous round, there is no protocol that can tolerate even 2 colluding agents and 1 crash failure.