Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.21382 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915267261497344 |
|---|---|
| author | Bai, Sirui Fu, Xinyu Wang, Yuheng Wang, Yuyi Zheng, Chaodong |
| author_facet | Bai, Sirui Fu, Xinyu Wang, Yuheng Wang, Yuyi Zheng, Chaodong |
| contents | 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 $Ω(n^2)$ 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 $\tilde{O}((f+1)\cdot 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: it finishes within $\tilde{O}(\max\{f,1\})$ rounds and sends only $\tilde{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(\log{N})$ bits. Therefore, our crash-resilient algorithm incurs $o(n^2)$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21382 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Robust and Scalable Renaming with Subquadratic Bits Bai, Sirui Fu, Xinyu Wang, Yuheng Wang, Yuyi Zheng, Chaodong Distributed, Parallel, and Cluster Computing 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 $Ω(n^2)$ 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 $\tilde{O}((f+1)\cdot 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: it finishes within $\tilde{O}(\max\{f,1\})$ rounds and sends only $\tilde{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(\log{N})$ bits. Therefore, our crash-resilient algorithm incurs $o(n^2)$ 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. |
| title | Robust and Scalable Renaming with Subquadratic Bits |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2504.21382 |