Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2605.18086 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910232068751360 |
|---|---|
| author | Bai, Sirui Fu, Xinyu Wang, Yuyi Zheng, Chaodong |
| author_facet | Bai, Sirui Fu, Xinyu Wang, Yuyi Zheng, Chaodong |
| contents | In distributed computing, the renaming problem requires $n$ nodes with unique identities from a large namespace $[N]$ to acquire new, distinct identities from a smaller target namespace $[M]$. A solution is strong if $M=n$, and is order-preserving if the relative order of identities is maintained. In the synchronous message-passing model, although many fault-tolerant renaming algorithms achieve logarithmic time complexity, they universally incur a high message complexity of $Ω(n^2)$. Recent work breaks the quadratic barrier, but demands linear runtime and relies on shared randomness.
This paper addresses the challenge of designing renaming algorithms that are simultaneously time-efficient, message-efficient, and Byzantine fault-tolerant, assuming only message authentication. We present two randomized algorithms for strong and order-preserving renaming that tolerate up to $(1/3-δ)n$ Byzantine failures for any constant $δ>0$. Our first algorithm, which assumes shared randomness, terminates in $O(\text{poly-log}(n))$ rounds with $\tilde{O}(n)$ total communication cost. This matches known lower bounds within poly-logarithmic factor. Our second algorithm eliminates the shared randomness assumption and achieves $O(\text{poly-log}(n))$ runtime with $\tilde{O}(n+\min\{nf,T\})$ total communication cost, where $f$ is the actual number of faulty nodes and $T$ is the amount of messages faulty nodes sent. This gives the first Byzantine renaming algorithm that achieves both poly-logarithmic runtime and subquadratic communication cost for a wide range of parameter regimes, without shared randomness. A key technical enabler is a novel and scalable committee election primitive that could be easily integrated into other algorithms to solve various distributed computing problems with low cost and strong fault-tolerance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18086 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Distributed Renaming with Subquadratic Bits via Scalable Committee Election Bai, Sirui Fu, Xinyu Wang, Yuyi Zheng, Chaodong Distributed, Parallel, and Cluster Computing In distributed computing, the renaming problem requires $n$ nodes with unique identities from a large namespace $[N]$ to acquire new, distinct identities from a smaller target namespace $[M]$. A solution is strong if $M=n$, and is order-preserving if the relative order of identities is maintained. In the synchronous message-passing model, although many fault-tolerant renaming algorithms achieve logarithmic time complexity, they universally incur a high message complexity of $Ω(n^2)$. Recent work breaks the quadratic barrier, but demands linear runtime and relies on shared randomness. This paper addresses the challenge of designing renaming algorithms that are simultaneously time-efficient, message-efficient, and Byzantine fault-tolerant, assuming only message authentication. We present two randomized algorithms for strong and order-preserving renaming that tolerate up to $(1/3-δ)n$ Byzantine failures for any constant $δ>0$. Our first algorithm, which assumes shared randomness, terminates in $O(\text{poly-log}(n))$ rounds with $\tilde{O}(n)$ total communication cost. This matches known lower bounds within poly-logarithmic factor. Our second algorithm eliminates the shared randomness assumption and achieves $O(\text{poly-log}(n))$ runtime with $\tilde{O}(n+\min\{nf,T\})$ total communication cost, where $f$ is the actual number of faulty nodes and $T$ is the amount of messages faulty nodes sent. This gives the first Byzantine renaming algorithm that achieves both poly-logarithmic runtime and subquadratic communication cost for a wide range of parameter regimes, without shared randomness. A key technical enabler is a novel and scalable committee election primitive that could be easily integrated into other algorithms to solve various distributed computing problems with low cost and strong fault-tolerance. |
| title | Distributed Renaming with Subquadratic Bits via Scalable Committee Election |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2605.18086 |