2023/12/22 by Ivan Geffner, Joseph Y. Halpern, Geffner, Ivan +1
Computer Science · Engineering · #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Multiagent Systems (cs.MA) #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2312.14775
openalex publication_date 2023/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Protocols for tossing a common coin play a key role in the vast majority of implementations of consensus. Even though the common coins in the literature are usually fair (they have equal chance of landing heads or tails), we focus on the problem of implementing a biased common coin such that the probability of landing heads is p ∈ [0,1]. Even though biased common coins can be implemented using fair common coins, we show that this can require significant inter-party communication. In fact, we show that there is no bound on the number of messages needed to generate a common coin of bias p in a way that tolerates even one malicious agent, even if we restrict p to an arbitrary infinite subset of [0,1] (e.g., rational numbers of the form 1/2n) and assume that the system is synchronous. By way of contrast, if we do not require the protocol to tolerate a faulty agent, we can do this. Thus, the cause of the message complexity is the requirement of fault tolerance.