2025/04/30 by Sirui Bai, Bai, Sirui, Xinyu Fu +7
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2504.21382
openalex publication_date 2025/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the renaming problem, a set of n nodes, each with a unique identity from a large namespace [N], needs to obtain new unique identities in a smaller namespace [M]. A renaming algorithm is strong if M=n. Renaming is a classical problem in distributed computing with a range of applications, and there exist many time-efficient solutions for fault-tolerant renaming in synchronous message-passing systems. However, all previous algorithms send Ω(n2) messages, and many of them also send large messages each containing Ω(n) bits. Moreover, most algorithms' performance do not scale with the actual number of failures. These limitations restrict their practical performance. We develop two new strong renaming algorithms, one tolerates up to n-1 crash failures, and the other tolerates up to (1/3-ε0)n Byzantine failures for an arbitrarily small constant ε0>0. The crash-resilient algorithm is always correct and always finishes within O(logn) rounds. It sends O((f+1)⋅ n) messages with high probability, where f is the actual number of crashes. This implies that it sends subquadratic messages as long as f=o(n/logn). The Byzantine-resilient algorithm trades time for communication: it finishes within O(max\f,1\) rounds and sends only O(f+n) messages, with high probability. Here, f is the actual number of Byzantine nodes. To obtain such strong guarantees, the Byzantine-resilient algorithm leverages shared randomness and message authentication. Both algorithms only send messages of size O(logN) bits. Therefore, our crash-resilient algorithm incurs o(n2) communication cost as long as f=o(n/(lognlogN)); and our Byzantine resilient algorithm incurs almost-linear communication cost. By deriving a lower bound, we conclude that our algorithms achieve near-optimal communication cost in many cases.