2024/05/13 by Varul Srivastava, Srivastava, Varul, Sujit Gujar +1
Computer Science · #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Cryptography and Data Security #Distributed #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2405.07557
openalex publication_date 2024/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Distributed consensus protocols reach agreement among n players in the presence of f adversaries; different protocols support different values of f. Existing works study this problem for different adversary types (captured by threat models). There are three primary threat models: (i) Crash fault tolerance (CFT), (ii) Byzantine fault tolerance (BFT), and (iii) Rational fault tolerance (RFT), each more general than the previous. Agreement in repeated rounds on both (1) the proposed value in each round and (2) the ordering among agreed-upon values across multiple rounds is called Atomic BroadCast (ABC). ABC is more generalized than consensus and is employed in blockchains. This work studies ABC under the RFT threat model. We consider t byzantine and k rational adversaries among n players. We also study different types of rational players based on their utility towards (1) liveness attack, (2) censorship or (3) disagreement (forking attack). We study the problem of ABC under this general threat model in partially-synchronous networks. We show (1) ABC is impossible for n/3< (t+k)