2015/12/19 by Zohir Bouzid, Bouzid, Zohir, Damien Imbs +3
Computer Science · Engineering · #Cryptography and Data Security #Distributed #Distributed systems and fault tolerance #Electrochemical sensors and biosensors #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1512.06227
openalex publication_date 2015/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This short paper presents a necessary condition for Byzantine k-set agreement in (synchronous or asynchronous) message-passing systems and asynchronous shared memory systems where the processes communicate through atomic single-writer multi-reader registers. It gives a proof, which is particularly simple, that k-set agreement cannot be solved t-resiliently in an n-process system when n ≤ 2t + (t)/(k). This bound is tight for the case k=1 (Byzantine consensus) in synchronous message-passing systems.