pith. sign in

arxiv: 2605.18086 · v1 · pith:TJLJRMLYnew · submitted 2026-05-18 · 💻 cs.DC

Distributed Renaming with Subquadratic Bits via Scalable Committee Election

Sirui Bai , Xinyu Fu , Yuyi Wang , Chaodong Zheng This is my paper

Pith reviewed 2026-05-20 00:44 UTC · model grok-4.3

classification 💻 cs.DC
keywords renamingByzantine fault tolerancedistributed computingcommittee electionmessage complexityrandomized algorithmssynchronous modelorder-preserving renaming
0
0 comments X

The pith

Two algorithms solve Byzantine renaming in poly-log rounds with subquadratic total communication, one without shared randomness.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The renaming problem asks n nodes with unique large IDs to pick distinct small IDs while preserving order. The paper gives randomized solutions that tolerate nearly one-third Byzantine faults in the synchronous authenticated model. Both versions finish in poly-logarithmic rounds. The first uses shared randomness to keep total bits exchanged near linear in n. The second removes the shared-randomness assumption and still stays subquadratic, with communication scaling as n plus the minimum of faults times n or the actual faulty traffic. A new committee-election building block supplies the fault tolerance and efficiency.

Core claim

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(poly-log(n)) rounds with Õ(n) total communication cost. Our second algorithm eliminates the shared randomness assumption and achieves O(poly-log(n)) runtime with Õ(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.

What carries the argument

A novel scalable committee election primitive that elects a small, reliable subset of nodes to coordinate renaming while tolerating a constant fraction of Byzantine faults at low communication cost.

If this is right

  • The algorithms match known lower bounds on time and communication up to poly-log factors.
  • The second version gives the first poly-log-time, subquadratic-communication Byzantine renaming solution without shared randomness across wide parameter ranges.
  • The committee election primitive can be plugged into other distributed tasks to obtain similar efficiency gains.
  • Communication cost improves automatically when fewer faults occur or faulty nodes send fewer messages.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The committee primitive may reduce communication in other primitives such as reliable broadcast or leader election under the same fault bound.
  • Removing the synchrony assumption while keeping subquadratic cost would require new techniques for handling timing uncertainty.
  • The approach could be tested in large-scale simulations to measure practical bit savings when f is much smaller than n.

Load-bearing premise

The system runs in synchronous rounds, messages carry unforgeable authentication, and the number of Byzantine nodes stays below one-third by a fixed positive margin.

What would settle it

A run in which the algorithm either exceeds poly-log rounds or sends more than Õ(n) bits in total when the actual number of faults is less than (1/3−δ)n and shared randomness is unavailable.

Figures

Figures reproduced from arXiv: 2605.18086 by Chaodong Zheng, Sirui Bai, Xinyu Fu, Yuyi Wang.

Figure 1
Figure 1. Figure 1: Pseudocode of Bouncing. examining following critical aspects: whether all nodes in the local list receive assignments, whether identity collisions occur, whether all identities fall within [n], and whether all identities are order preserving. The verification culminates in a two-tier consensus process: committee members first reach agreement on the assignments’ validity, followed by global consensus among … view at source ↗
Figure 2
Figure 2. Figure 2: Pseudocode of Sampling. (1) u is in Src; (2) the total number of fragments that v has forwarded for u is not too large; and (3) node u is “accepted” by v, where each node in Src is “accepted” by v with a probability specified when invoking Bouncing. Note that the last two criteria are introduced to allow us further tweak the total communication cost of Bouncing, and to counter the behavior that Byzantine n… view at source ↗
Figure 3
Figure 3. Figure 3: Pseudocode of the renaming algorithm with shared random bits. (1 − ϵ)(2/3 + δ)C log n correct nodes; and (3) the committee contains less than com b = com all−com g Byzantine nodes. Here, ϵ > 0 is a sufficiently small constant, and C > 0 is a sufficiently large constant. (ϵ and C will be specified in the analysis.) Then, we utilize this committee to distributed new identities. Committee election. With share… view at source ↗
Figure 4
Figure 4. Figure 4: The procedure SharedRenaming contains multiple iterations. In each iteration, a committee member becomes the leader and coordinates with the rest of the committee to assign new identities to all nodes. Following this assignment process, the committee further conducts a validity assessment and reach agreement on whether to halt execution (in case the assignment is valid) or continue into next iteration (in … view at source ↗
Figure 4
Figure 4. Figure 4: Pseudocode of SharedRenaming. The leader of iteration j is the node with the j-th smallest identity in the committee. (Recalled that above committee election process ensures all nodes obtain identical committee lists, hence nodes agree on identical leader in each iteration.) At the start of each iteration, each node broadcasts its original identity to the committee. Each committee member v adds these ident… view at source ↗
Figure 4
Figure 4. Figure 4: Take a union bound over at most n 2 choices of x and ID(y), we conclude that with probability at least 1 − n −10c , every identity in S v∈G Listv is forwarded to lead∗ during the execution of Bouncing in Line 10 of [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Pseudocode of CommitteeElection. 6 Renaming Algorithm without Shared Random Bits 6.1 Committee Election Similar to the setting when shared randomness is available, to accomplish renaming, we begin with electing a committee of bounded size. However, without shared randomness, this process becomes much more complicated. Moreover, after this process, all nodes may have different views on the constitution of t… view at source ↗
Figure 6
Figure 6. Figure 6: Pseudocode of CommitteeBuild. (recall [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Pseudocode of CommitteeConsensus. RedoConsensus(electedv, S′ v , com outv, com all) executed at node v. 1: redov ← 0. 2: if (electedv == 1) then Send ⟨COM, com outv⟩ to all nodes. 3: if (|S ′ v| < com all) then redov ← the majority value of com out among all received COM messages from S ′ v. 4: redo′ v ← Run Sampling(1|S′ v |≥com all, 1|S′ v |<com all, {redov}, 1/2). 5: if (|S ′ v| ≥ com all and 0 ∈/ redo′… view at source ↗
Figure 8
Figure 8. Figure 8: Pseudocode of RedoConsensus. members in S ′ v as follows: upon receiving at least com g INIT messages with identical values (either 1 or 0), the node echos this value to the nodes in S ′ v via ECHO messages. At this point, for a node v with input com readyv = 0, it initializes strongv to 0. (If v has com readyv = 1, then it is confident that all nodes’ eventual agreed value will be identical to v’s input, … view at source ↗
Figure 9
Figure 9. Figure 9: Pseudocode of Renaming. other hand, if node v detects an oversized committee (i.e., |S ′ v | ≥ com all), then it triggers an execution of the Sampling primitive. In this invocation, nodes with oversized committees act as querying nodes, issu￾ing queries with data item 0, while nodes with proper-size committees act as responding nodes, using their local redo as the data item. By setting proper threshold for… view at source ↗
Figure 10
Figure 10. Figure 10: Pseudocode of LeaderElection. in another variable com lead′ v . Then, committee member v broadcasts an INIT message containing the identity of com lead′ v to the committee S ′ v . Upon receiving com g INIT messages with identical leader identity from nodes in S ′ v , node v sends an ECHO message containing this leader identity to the committee S ′ v . Once com b ECHO messages are received from the committ… view at source ↗
Figure 11
Figure 11. Figure 11: Pseudocode of OldNameGather. NewNameScatter(electedv, S′ v , leadv, Listv, List′ v ) executed at node v. 1: if (ID(v) == leadv) then 2: RankMsgv ← ∅. 3: for (every ID(u) ∈ List′ v) do 4: ranku ← the rank order of ID(u) in List′ v. 5: RankMsgv ← RankMsgv ∪ {⟨NewID, ID(v), ID(u), ranku⟩}. 6: RankMsg′ v ← Run Bouncing(1ID(v)==leadv , {leadv}, S′ v, RankMsgv, 1). 7: if (electedv == 1) then 8: com redov ← 0, M… view at source ↗
Figure 12
Figure 12. Figure 12: Pseudocode of NewNameScatter. with probability (C log n)/com all, avoiding excessive message complexity. The leader aggregates all received P reListMsg into P reListMsg′ and then extracts the identities contained within P reListMsg′ to construct a comprehensive list List′ . OldNameGather ultimately returns a local identity list List for each committee member, and a comprehensive identity list List′ for th… view at source ↗
Figure 13
Figure 13. Figure 13: Pseudocode of NewNameValidate. The NewNameScatter procedure. This procedure combines leader-driven identity assignment with committee-based verification to ensure reliable new identity allocation, as formalized in [PITH_FULL_IMAGE:figures/full_fig_p025_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Pseudocode of the vector consensus algorithm. Appendix A Vector Consensus Algorithm We summarize the guarantees of our vector consensus algorithm in the following lemma. Lemma A.1. Assume all nodes’ identities are in [N]. Let G denote the set of correct committee nodes. For each node v ∈ G, let Sv denote the committee in its view. Let cˆ denote an upper bound of | S v∈G Sv| and let ˆb denote an upper boun… view at source ↗
read the original abstract

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 $\Omega(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-\delta)n$ Byzantine failures for any constant $\delta>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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper presents two randomized algorithms for strong and order-preserving renaming in the synchronous authenticated message-passing model that tolerate up to (1/3-δ)n Byzantine failures for constant δ>0. The first algorithm assumes shared randomness, runs in O(polylog n) rounds, and uses Õ(n) total communication. The second removes the shared-randomness assumption while retaining O(polylog n) runtime and achieving Õ(n + min{nf, T}) communication, where f is the actual number of faults and T counts messages sent by faulty nodes. Both rely on a new scalable committee-election primitive whose local renaming subroutines aggregate to the claimed global bounds.

Significance. If the central claims hold, the work is significant: it supplies the first Byzantine renaming algorithms that simultaneously achieve polylogarithmic time and subquadratic (or adaptive) communication without shared randomness, matching known lower bounds up to polylog factors in the shared-randomness case. The committee-election primitive is presented as a reusable building block and the adaptive min{nf,T} term provides a clean way to charge extra cost only to actual misbehavior. These features would be of broad interest to the distributed-computing community.

major comments (2)
  1. [§4] §4 (Committee Election): the proof that elected committees remain small and well-distributed with high probability under (1/3-δ)n faults must be checked for the precise concentration bounds used; any looseness here directly affects whether the subsequent renaming subroutines truly aggregate to Õ(n) total bits rather than Õ(n log n).
  2. [§5.2] §5.2 (Second algorithm): the definition and charging argument for the min{nf,T} term needs an explicit lemma showing that T cannot grow faster than O(n) in the worst case when f is linear; otherwise the subquadratic claim fails for the regime f=Θ(n).
minor comments (3)
  1. [Preliminaries] The Õ notation is used throughout but never expanded; a single sentence in the preliminaries clarifying the hidden polylog factors would improve readability.
  2. [Figure 1] Figure 1 (high-level overview) would benefit from explicit arrows or labels indicating where the committee-election primitive is invoked inside each renaming phase.
  3. [Introduction] A short paragraph comparing the new primitive's fault-tolerance threshold (1/3-δ) with the classic 1/3 bound for Byzantine agreement would help readers assess novelty.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The feedback highlights areas where additional precision in the proofs will strengthen the presentation. We address each major comment below and will incorporate the suggested clarifications in the revised version.

read point-by-point responses

  1. Referee: [§4] §4 (Committee Election): the proof that elected committees remain small and well-distributed with high probability under (1/3-δ)n faults must be checked for the precise concentration bounds used; any looseness here directly affects whether the subsequent renaming subroutines truly aggregate to Õ(n) total bits rather than Õ(n log n).

    Authors: We thank the referee for this observation. In the analysis of the committee election primitive (Theorem 4.1), we apply Chernoff bounds to the binomial vote counts for each candidate, setting the failure probability per candidate to 1/n^3. With the bias parameter δ, this yields committees of size O(log n / δ) with high probability. A union bound over the n nodes then ensures that all committees satisfy the size bound simultaneously. Because each local renaming subroutine on a committee of size s incurs O(s log s) bits and there are Θ(n / log n) such committees, the aggregate cost is Õ(n). We will insert the explicit Chernoff parameters, deviation thresholds, and union-bound calculation into the proof of Theorem 4.1 to make the aggregation transparent. revision: yes

  2. Referee: [§5.2] §5.2 (Second algorithm): the definition and charging argument for the min{nf,T} term needs an explicit lemma showing that T cannot grow faster than O(n) in the worst case when f is linear; otherwise the subquadratic claim fails for the regime f=Θ(n).

    Authors: We agree that an explicit supporting lemma will clarify the charging argument. In Section 5.2, T counts all messages originated by faulty nodes. The authenticated-message model together with the committee-election filter limits each faulty node to O(log n) messages per round before its messages are ignored by honest nodes in subsequent phases. Summing over O(polylog n) rounds and f ≤ n faulty nodes produces T = O(n polylog n) in the worst case. Consequently, when f = Θ(n) we have min{nf, T} = Õ(n), preserving the overall Õ(n + min{nf, T}) bound. We will add this argument as a new Lemma 5.3 with a formal potential-function proof. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript introduces two new randomized algorithms for strong order-preserving renaming under Byzantine faults, supported by a novel scalable committee-election primitive. The polylogarithmic runtime and subquadratic communication bounds are derived from explicit algorithmic constructions and standard synchronous authenticated message-passing analysis with an explicit (1/3-δ)n fault bound; these steps do not reduce to self-definitions, fitted inputs renamed as predictions, or load-bearing self-citations. The argument is self-contained against external benchmarks and does not rely on renaming known results or smuggling ansatzes via prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper relies on standard distributed-computing model assumptions and introduces one new algorithmic primitive whose correctness is not independently evidenced in the abstract.

axioms (1)
  • domain assumption Synchronous message-passing model with message authentication
    Invoked as the setting for all complexity claims in the abstract.
invented entities (1)
  • Scalable committee election primitive no independent evidence
    purpose: To coordinate renaming with low communication cost and strong fault tolerance
    Presented as the key technical enabler that enables the claimed bounds and is reusable in other algorithms.

pith-pipeline@v0.9.0 · 5853 in / 1270 out tokens · 58854 ms · 2026-05-20T00:44:06.402462+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    Asynchronous algorand: Reaching agreement with near linear communication and constant expected time

    Ittai Abraham, Eli Chouatt, Yossi Gilad, Gilad Stern, and Sophia Yakoubov. Asynchronous algorand: Reaching agreement with near linear communication and constant expected time. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 28–38. ACM, 2025

    work page 2025

  2. [2]

    The renaming problem: Recent developments and open questions.http:// bulletin.eatcs.org/index.php/beatcs/article/view/381/361, 2015

    Dan Alistarh. The renaming problem: Recent developments and open questions.http:// bulletin.eatcs.org/index.php/beatcs/article/view/381/361, 2015

    work page 2015

  3. [3]

    Randomized loose renaming in o(log log n) time

    Dan Alistarh, James Aspnes, George Giakkoupis, and Philipp Woelfel. Randomized loose renaming in o(log log n) time. InProceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, pages 200–209. ACM, 2013

    work page 2013

  4. [4]

    The complexity of renaming

    Dan Alistarh, James Aspnes, Seth Gilbert, and Rachid Guerraoui. The complexity of renaming. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, pages 718–727. IEEE, 2011

    work page 2011

  5. [5]

    Balls-into-leaves: Sub-logarithmic renaming in synchronous message-passing systems

    Dan Alistarh, Oksana Denysyuk, Lu ´ıs Rodrigues, and Nir Shavit. Balls-into-leaves: Sub-logarithmic renaming in synchronous message-passing systems. InProceedings of the 2014 ACM symposium on Principles of distributed computing, PODC ’14, pages 232–241. ACM, 2014

    work page 2014

  6. [6]

    How to elect a leader faster than a tournament

    Dan Alistarh, Rati Gelashvili, and Adrian Vladu. How to elect a leader faster than a tournament. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, pages 365–374. ACM, 2015

    work page 2015

  7. [7]

    Renaming in an asynchronous environment.Journal of the ACM, 37(3):524–548, 1990

    Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and R ¨udiger Reischuk. Renaming in an asynchronous environment.Journal of the ACM, 37(3):524–548, 1990

    work page 1990

  8. [8]

    Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols

    John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols. InProceed- ings of the 34th International Symposium on Distributed Computing, DISC ’20, pages 31:1–31:19. Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik, 2020

    work page 2020

  9. [9]

    Awake complexity of distributed mini- mum spanning tree

    John Augustine, William K Moses Jr, and Gopal Pandurangan. Awake complexity of distributed mini- mum spanning tree. InInternational Colloquium on Structural Information and Communication Com- plexity, SIROCCO ’24, pages 45–63. Springer, 2024

    work page 2024

  10. [10]

    Brief announcement: Robust and scalable renaming with subquadratic bits

    Sirui Bai, Xinyu Fu, Yuheng Wang, Yuyi Wang, and Chaodong Zheng. Brief announcement: Robust and scalable renaming with subquadratic bits. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 264–267. ACM, 2025

    work page 2025

  11. [11]

    Morgan & Claypool Publishers, 2013

    Leonid Barenboim and Michael Elkin.Distributed graph coloring: Fundamentals and recent devel- opments. Morgan & Claypool Publishers, 2013

    work page 2013

  12. [12]

    Byzantine agreement with predictions

    Naama Ben-David, Muhammad Ayaz Dzulfikar, Faith Ellen, and Seth Gilbert. Byzantine agreement with predictions. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 3–14. ACM, 2025. 41

    work page 2025

  13. [13]

    Bender, Jeremy T

    Michael A. Bender, Jeremy T. Fineman, Mahnush Movahedi, Jared Saia, Varsha Dani, Seth Gilbert, Seth Pettie, and Maxwell Young. Resource-competitive algorithms.SIGACT News, 46(3):57–71, 2015

    work page 2015

  14. [14]

    Leader election with poly-logarithmic communication per party

    Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, Kartik Nayak, and Sravya Yandamuri. Leader election with poly-logarithmic communication per party. InAdvances in Cryptology - CRYPTO 2025: 45th Annual International Cryptology Conference, CRYPTO ’25, pages 37–68. Springer, 2025

    work page 2025

  15. [15]

    In- ternet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile

    Sharon Boeyen, Stefan Santesson, Tim Polk, Russ Housley, Stephen Farrell, and David Cooper. In- ternet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile. RFC 5280, 2008

    work page 2008

  16. [16]

    Sok: Research perspectives and challenges for bitcoin and cryptocurrencies

    Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A Kroll, and Edward W Felten. Sok: Research perspectives and challenges for bitcoin and cryptocurrencies. InProceedings of the 2015 IEEE Symposium on Security and Privacy, S&P ’15, pages 104–121. IEEE, 2015

    work page 2015

  17. [17]

    An o (log n)) expected rounds randomized byzantine generals protocol.Journal of the ACM, 34(4):910–920, 1987

    Gabriel Bracha. An o (log n)) expected rounds randomized byzantine generals protocol.Journal of the ACM, 34(4):910–920, 1987

    work page 1987

  18. [18]

    Asynchronous consensus and broadcast protocols.Journal of the ACM, 32(4):824–840, 1985

    Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols.Journal of the ACM, 32(4):824–840, 1985

    work page 1985

  19. [19]

    The renaming problem in shared memory systems: An introduction.Computer Science Review, 5(3):229–251, 2011

    Armando Casta ˜neda, Sergio Rajsbaum, and Michel Raynal. The renaming problem in shared memory systems: An introduction.Computer Science Review, 5(3):229–251, 2011

    work page 2011

  20. [20]

    Fast perfect-information leader-election protocol with linear immu- nity

    Jason Cooper and Nathan Linial. Fast perfect-information leader-election protocol with linear immu- nity. InProceedings of the 25th Annual ACM symposium on Theory of Computing, STOC ’93, pages 662–671. ACM, 1993

    work page 1993

  21. [21]

    Byzantine renaming in synchronous systems witht < n

    Oksana Denysyuk and Lu ´ıs Rodrigues. Byzantine renaming in synchronous systems witht < n. In Proceedings of the 2013 ACM symposium on Principles of distributed computing, PODC ’13, pages 210–219. ACM, 2013

    work page 2013

  22. [22]

    Order-preserving renaming in synchronous systems with byzantine faults

    Oksana Denysyuk and Lu ´ıs Rodrigues. Order-preserving renaming in synchronous systems with byzantine faults. InIEEE 33rd International Conference on Distributed Computing Systems, ICDCS ’13, pages 276–285. IEEE, 2013

    work page 2013

  23. [23]

    Raymond Strong

    Danny Dolev and H. Raymond Strong. Polynomial algorithms for multiple processor agreement. In Proceedings of the fourteenth annual ACM symposium on theory of computing, STOC ’82, pages 401–

    work page

  24. [24]

    Raymond Strong

    Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement.SIAM Journal on Computing, 12(4):656–666, 1983

    work page 1983

  25. [25]

    Improved byzantine agreement under an adaptive adversary

    Fabien Dufoulon and Gopal Pandurangan. Improved byzantine agreement under an adaptive adversary. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 173–180. ACM, 2025

    work page 2025

  26. [26]

    On the number of synchronous rounds sufficient for authenti- cated byzantine agreement

    Matthias Fitzi and Jesper Buus Nielsen. On the number of synchronous rounds sufficient for authenti- cated byzantine agreement. InInternational Symposium on Distributed Computing, DISC ’09, pages 449–463. Springer Berlin Heidelberg, 2009

    work page 2009

  27. [27]

    Subconsensus tasks: Renaming is weaker than set agreement

    Eli Gafni, Sergio Rajsbaum, and Maurice Herlihy. Subconsensus tasks: Renaming is weaker than set agreement. InInternational Symposium on Distributed Computing, DISC ’06, pages 329–338. Springer Berlin Heidelberg, 2006

    work page 2006

  28. [28]

    Improved deterministic network decompo- sition

    Mohsen Ghaffari, Christoph Grunau, and V ´aclav Rozhoˇn. Improved deterministic network decompo- sition. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, pages 2904–2923. SIAM, 2021

    work page 2021

  29. [29]

    Kowalski

    Seth Gilbert and Dariusz R. Kowalski. Distributed agreement with optimal communication complexity. InProceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pages 42 965—977. SIAM, 2010

    work page 2010

  30. [30]

    Scalable leader election

    Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Scalable leader election. InProceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, SODA ’06, pages 990–999. SIAM, 2006

    work page 2006

  31. [31]

    Towards secure and scalable computation in peer-to-peer networks

    Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Towards secure and scalable computation in peer-to-peer networks. InProceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’06, pages 87–98. IEEE, 2006

    work page 2006

  32. [32]

    Sublinear message bounds of authenticated implicit byzantine agreement

    Manish Kumar and Anisur Rahaman Molla. Sublinear message bounds of authenticated implicit byzantine agreement. InProceedings of the 25th International Conference on Distributed Comput- ing and Networking, ICDCN ’24, pages 124–133. ACM, 2024

    work page 2024

  33. [33]

    The byzantine generals problem.ACM Trans- actions on Programming Languages and Systems, 4(3):382–401, 1982

    Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem.ACM Trans- actions on Programming Languages and Systems, 4(3):382–401, 1982

    work page 1982

  34. [34]

    A recursive early-stopping phase king protocol

    Christoph Lenzen and Sahar Sheikholeslami. A recursive early-stopping phase king protocol. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, pages 60–69. ACM, 2022

    work page 2022

  35. [35]

    Morgan Kaufmann Publishers, 1996

    Nancy Lynch.Distributed Algorithms. Morgan Kaufmann Publishers, 1996

    work page 1996

  36. [36]

    Cambridge University Press, 1995

    Rajeev Motwani and Prabhakar Raghavan.Randomized algorithms. Cambridge University Press, 1995

    work page 1995

  37. [37]

    Renaming in message passing systems with byzantine failures

    Michael Okun and Amnon Barak. Renaming in message passing systems with byzantine failures. In International Symposium on Distributed Computing, DISC ’06, pages 16–30. Springer, 2006

    work page 2006

  38. [38]

    Renaming in synchronous message passing systems with byzantine failures.Distributed Computing, 20(6):403–413, 2008

    Michael Okun, Amnon Barak, and Eli Gafni. Renaming in synchronous message passing systems with byzantine failures.Distributed Computing, 20(6):403–413, 2008

    work page 2008

  39. [39]

    Simple and efficient leader election in the full information model

    Rafail Ostrovsky, Sridhar Rajagopalan, and Umesh Vazirani. Simple and efficient leader election in the full information model. InProceedings of the 26th Annual ACM symposium on Theory of Computing, STOC ’94, pages 234–242. ACM, 1994

    work page 1994

  40. [40]

    Perfect information leader election in log*(n) + o(1) rounds

    Alexander Russell and David Zuckerman. Perfect information leader election in log*(n) + o(1) rounds. Journal of Computer and System Sciences, 63(4):612–626, 2001. 43

    work page 2001