Brief Announcement: Robust and Scalable Renaming with Subquadratic Bits

Abstract

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. There exist many time-efficient solutions for fault-tolerant renaming in synchronous message-passing systems. However, all previous algorithms send Ω(n²) 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(log n) rounds. It sends Õ((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/log n). The Byzantine-resilient algorithm trades time for communication cost: it finishes within Õ(max{f, 1}) rounds and sends only Õ(f + n) messages, with high probability. Here, f is the actual number of Byzantine nodes. Both algorithms only send messages of size O(log N) bits. Therefore, our crash-resilient algorithm incurs o(n²) communication cost as long as f = o(n/(log n log N)); 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.