2025/04/14 by Xing Hu, Sam Toueg, Hu, Xing +1
Computer Science · #Advanced Database Systems and Queries #Distributed #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Natural Language Processing Techniques #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2504.09805
openalex publication_date 2025/04/14 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
We define and show how to implement SWMR registers that provide properties of unforgeable digital signatures - without actually using such signatures - in systems with Byzantine processes. Intuitively, processes can use these registers to write values as if they are ``signed'', such that these ``signed values'' can be ``verified'' by any process and ``relayed'' to any process. All our register implementations are from SWMR registers, and they work in systems with n > 3f processes, f of which can be Byzantine. We show that these implementations are optimal in the number of Byzantine processes they can tolerate: more precisely, we prove that if 3 ≤ n ≤ 3f, the registers that we propose cannot be implemented from SWMR registers without using signatures. The registers that we introduce in this paper can also be implemented without signatures in message-passing systems with n > 3f processes, f of which can be Byzantine: this is because SWMR registers can be implemented in such systems (Mostéfaoui, Petrolia, Raynal, and Jard 2017).