Content-Oblivious Leader Election in 2-Edge-Connected Networks

Giuseppe A. Di Luna; Haoran Zhou; J\'er\'emie Chalopin; Lyuting Chen; Yi-Jun Chang

Content-Oblivious Leader Election in 2-Edge-Connected Networks

T0 review · 0 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Two algorithms show that leaders can be elected by pulse counting alone in fully defective networks, refuting the conjecture that a preselected leader is always required.

desk verdict Strong paper that closes the content-oblivious leader election question on rings and, under a modest size bound, on general 2-edge-connected graphs; the proofs are long but the delicate points hold up. read the letter →

arxiv 2507.08348 v3 pith:XRDTLY32 submitted 2025-07-11 cs.DC

Jérémie Chalopin , Yi-Jun Chang , Lyuting Chen , Giuseppe A. Di Luna , Haoran Zhou This is my paper · ORCID

classification cs.DC MSC 68M1468W15

keywords content-obliviouscomputationfully-defectivenetworksleaderelectionquiescenttermination2-edge-connectedgraphsunorientedringspulsecommunicationasynchronousdistributedalgorithms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

In the fully-defective communication model, every message may be arbitrarily corrupted, so nodes are left with only the timing of arrivals—pulses—as information. Earlier work proved that any noiseless algorithm can be simulated in such a network, but only if a leader is chosen in advance, and it conjectured that this preselected leader is unavoidable. This paper refutes that conjecture: it presents a pulse-only leader election algorithm that quiescently terminates in any 2-edge-connected network, given only an upper bound on the number of nodes, and a second algorithm that needs no such bound on unoriented rings. Because the elected leader is the last node to stop, the earlier simulation can be composed with the election, so any noiseless algorithm becomes simulable without a preselected leader. The ring result also matches the best known message bound, showing that orientation of the ring is not needed after all.

What carries the argument

The engine of Theorem 1 is a near-synchronized counter: each node broadcasts a pulse after each increment and its counter equals the minimum number of pulses received on any port, so neighboring counters differ by at most one. Identifiers are first multiplied by $N$ so that only the smallest-ID node can ever reach its own counter value. The leader then announces itself by a DFS notification that sends a fixed surplus of $\mathsf{ID}(r) + N + 2$ pulses along each edge; the surplus defeats the counter's bounds and forces each neighbor to detect an anomaly. The proof rests on a chain-and-anchor argument along shortest paths in the strongly connected orientation of the graph built from a DFS tree, which keeps every unvisited node's counter below its own identifier until the announcement arrives. For Theorem 2 the mechanism is a solitude check followed by transparency: a node that fails its check sends two balancing pulses and then relays every pulse to the opposite port, behaving as an asynchronous link; the induction deletes such nodes one at a time until only the maximum-ID node remains, whose termination pulse travels around the ring and is recognized by a three-pulse imbalance.

What would settle it

Run the ring algorithm on a three-node unoriented ring with adversarial pulse scheduling and identifiers spaced by two; if any non-maximum node ever terminates as Leader, or if any relaying node's Diff counter reaches 3 before the maximum-ID node sends its termination pulse, Theorem 2 fails. Equivalently, for the general algorithm, exhibit a 2-edge-connected graph and a delivery order in which some node's counter reaches $\mathsf{ID}(v)$ before the DFS notification arrives, since the chain-and-anchor invariant guarantees $\mathsf{Count}(v) \leq \mathsf{ID}(r) + N - 1 < \mathsf{ID}(v)$ for every non-leader at all times.

Watch

Extended reading notes

Core claim

The paper's central claim is that quiescently terminating content-oblivious leader election is possible without a preselected leader. Theorem 1 constructs an algorithm that works in every 2-edge-connected network when the nodes share an upper bound $N$ on the network size, electing the node with the smallest identifier using $O(m \cdot N \cdot \mathsf{ID}_{\min})$ pulses, where $m$ is the number of edges and $\mathsf{ID}_{\min}$ the smallest identifier; the leader is the last node to terminate, which is exactly the property that lets a following simulation algorithm run safely. Theorem 2 removes the need for $N$ on unoriented rings: a uniform algorithm elects the largest identifier with $O(n \cdot \mathsf{ID}_{\max})$ pulses, matching the previous bound for oriented rings and refuting the claim that orientation is required for termination detection. Together the theorems imply that fully-defective and noiseless communication are computationally equivalent on rings, and equivalent whenever a size bound is known in general 2-edge-connected topologies.

Load-bearing premise

The general-topology result collapses if the shared upper bound $N$ on the number of nodes is wrong, since identifiers are spaced $N$ apart so that only the smallest-ID node can reach its own counter value; the ring result instead collapses if a node that fails its solitude check cannot be made perfectly transparent, because its neighbors must never detect it through an off-by-one pulse imbalance.

Editorial extensions

If this is right

Whenever an upper bound on the number of nodes is known, every algorithm designed for a noiseless 2-edge-connected network can be executed in a fully-defective network with no preselected leader: run the election, then run the known simulation from the elected leader.
On unoriented rings, no bound on the network size and no consistent orientation are needed; quiescent termination is achieved with $O(n \cdot \mathsf{ID}_{\max})$ messages, the same bound previously attainable only with orientation.
The standing conjectures—that a preselected leader is necessary for any non-trivial content-oblivious computation, and that terminating election is impossible in unoriented rings—are both false.
The dependency on identifiers improves from the maximum identifier to the minimum identifier in general topologies, at the price of the size bound $N$.
Since the leader terminates last, the election composes cleanly with subsequent algorithms: nodes can tell which pulses belong to which phase.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The surplus-pulse notification suggests a general recipe: in a 2-edge-connected network, a node can force recognition of any event by sending more pulses than any untouched counter can plausibly accumulate; the same trick may yield other content-oblivious primitives, such as broadcast or renaming, without a leader.
The ring algorithm's transparency argument hints that uniform election might extend to general 2-edge-connected graphs: if a non-leader can always be made indistinguishable from a deleted node while the maximum-ID node keeps competing, the inductive deletion may not need the size bound $N$ at all—a question the paper leaves open.
The paper's own remark that a node cannot notify all neighbors at once, because that would break the chain-and-anchor guarantee, suggests that any speedup of the DFS notification must find a different anchor structure rather than simply flooding.
The Diff-threshold idea used for the ring's termination signal could serve as a generic content-oblivious 'end of computation' marker when composing multiple tasks, since every non-leader terminates only after relaying the leader's third pulse.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this is a strong paper, and my verdict agrees with the reader's ACCEPT at moderate confidence. It gives the first quiescently terminating content-oblivious leader election for general 2-edge-connected networks (with a known size bound N) and for unoriented rings, and the ring result is uniform and matches the prior O(n·IDmax) bound. When combined with CCG+23, the first result removes the preselected-leader assumption under non-uniformity; the second refutes the FGG+24 conjecture that orientation is needed for termination. The algorithms are genuinely new, not modifications of the oriented-ring trick: the general case uses an Awerbuch-style synchronized counter plus a DFS notification phase, and the ring case uses a solitude check followed by transparent relaying, with the maximum-ID node as the last one standing.

What the paper does well: the proof structure is explicit, with complete pseudocode. I checked the two places that looked most likely to break. The chain-and-anchor argument in Lemma 22 survives because the DFS orientation prevents the single in-flight edge from appearing on the chain. The transparency argument behind Proposition 26 is delicate, but Lemma 33 fixes the sent/received counts at ID2+2 after rebalancing, and Lemma 28's synchronization bound prevents a neighbor from creating a spurious three-pulse imbalance before the max-ID node's termination group. The off-by-one risks are addressed.

Soft spots, in proportion: Theorem 1's need for a known N is a real limitation, and the paper says so honestly—the general conjecture is refuted only in the non-uniform setting, and the uniform case remains open. The ring proof has a sketched local-min variant of Lemma 30; it is not fully expanded, and a referee should ask for that to be written out. It does not seem load-bearing, because the induction in Corollary 37 can apply the global-min version to successively reduced rings. The proofs are long and not machine-checked, so a human referee will have to invest real time, but I did not find a gap. Citations are appropriate, including the self-citations; nothing looks inflated.

Who should read it: anyone working on content-oblivious or beeping-style computation, and the distributed computing community generally. It deserves a serious referee, not a desk reject. I would send it out and ask for expansion of the local-min case plus a careful check of the ring induction.

Referee Report

0 major / 5 minor

Summary. The paper studies content-oblivious leader election in asynchronous fully-defective networks, where communication is reduced to pulses. It proves two main results. Theorem 1 gives a quiescently terminating leader election algorithm for every 2-edge-connected network, assuming a known upper bound N on the number of nodes, with message complexity O(m * N * IDmin); combined with the simulation of Censor-Hillel, Cohen, Gelles, and Sela, this removes the preselected-leader assumption from that simulation. Theorem 2 gives a uniform, quiescently terminating leader election algorithm for unoriented rings with message complexity O(n * IDmax), requiring neither orientation nor knowledge of N. The proofs are organized around a counting phase with near-synchronization, a DFS notification phase justified by a chain-and-anchor invariant, and, for rings, an inductive node-deletion argument based on transparency of relaying nodes.

Significance. If the results stand, they close two open problems in the content-oblivious model: the conjecture that a preselected leader is necessary for nontrivial computation in fully-defective networks is refuted under a known size bound, and the conjecture that quiescently terminating leader election is impossible on unoriented rings is refuted. The paper is careful and unusually detailed: the main invariants (small counter property, chain-and-anchor, node-deletion indistinguishability, no-early-termination) are stated precisely and the induction skeletons are explicit. The composition argument with prior simulation results is correctly aligned with the quiescent-termination and leader-last requirements. I checked the central proof skeleton and found no load-bearing gap; the delicate transparency argument behind Proposition 26 is closed by the exact count in Lemma 33 and the synchronization bound in Lemma 28. The paper does not provide machine-checked proofs or code, but the hand proofs are sufficiently detailed for a theory venue.

minor comments (5)

[Section 5.1, Lemma 30] The weaker local-minimum variant of Lemma 30 is stated only as a sketch ('it is still possible to adapt the proof'), and the formal induction in Corollary 37 iterates over global minima, so this does not affect the main theorem; nevertheless, the remark should either be proved or explicitly marked as non-essential, since as written it leaves the impression that a case distinction is being deferred.
[Section 4.1, Lemma 14] In the proof of Lemma 14, the quantity x = min_{u in V\S} Count(u) is infinite when S = V, and the instruction 'by choosing x = ...' is only meaningful for nonempty V\S; the edge case is handled separately in Lemma 15, but the lemma statement or proof should state this convention explicitly.
[Section 4.2, Algorithm 2 and event definitions] The event SendExplore_j(v) is triggered before the 'wait until rho_j >= LeaderID + 1' on line 7, whereas the prose describes it as the moment a node 'starts sending' an explore-notification; this conflation of intention and actual first pulse should be clarified, because the timing of t^Send is used in the induction hypothesis H1.
[Section 5.1, Observation 27] Observation 27 says a node 'has received i pulses' from each neighbor after i iterations, but in the asynchronous buffered model a node may have received additional pulses that it has not yet consumed; the statement should say 'has consumed i pulses in RcvPulse actions,' which is what Lemma 28 actually uses.
[Section 5, proof of Theorem 2] The complexity calculation says vmax sends 4*IDmax + 3 pulses and attributes the factor 4 to doubling the identifiers, but this is only correct if IDmax denotes the original, predoubling identifier; the text should state explicitly whether IDmax in this calculation is the original or the doubled value.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: core algorithms are proved directly from model assumptions, and the only overlapping self-citation appears in a non-load-bearing related-work list.

full rationale

The central claims of the paper are self-contained derivations rather than re-statements of assumptions. Theorem 1 is established by an induction over the DFS traversal sequence (Lemma 19 and the IH conditions H1-H3), with the counter and pulse-count invariants proved from the algorithm's own definitions (Observations 10-11, Lemmas 12-14, Lemma 22, Lemma 25). The 'chain-and-anchor' argument is not imported from prior work; it is derived in Lemma 22 using the paper's own strongly-connected orientation. Theorem 2 likewise rests on internally proved invariants: the local synchronization bound (Lemma 28), the rebalancing count identities (Lemma 33), and the pulse-difference characterization (Lemma 35), culminating in Corollary 37 and Lemma 38. The composition with the [CCG+23] simulation is an external result used as a theorem, not as an input to the correctness proof; the required properties of quiescent termination and leader-last termination are proved in the paper (Proof of Theorem 1 and Lemma 38). The only overlapping self-citation is [CKP+19], which appears solely in the Related Work sentence 'Leader election has been extensively studied in these models [ARV22; BGK20; CD19; CD21; CKP+19; DS18; EK21; GH13; SM20; VZ25].' That citation is not load-bearing: no theorem, lemma, or construction depends on it, and it does not supply a uniqueness result or ansatz. The paper also explicitly notes its own limitation that N must be known for general topologies, which is an honest assumption rather than a hidden circularity. No fitted input is renamed as a prediction, and no known result is repackaged under new coordinates. Accordingly, the derivation chain does not reduce to its own inputs, and the correct circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper does not fit any constants to data and introduces no new entities. The central claims rest on standard model assumptions (fair asynchronous delivery, port numbering, unique IDs), the known size bound N for the non-uniform theorem, and standard graph theory (Robbins' theorem, DFS properties). The most paper-specific element is the doubling of IDs in the ring algorithm, which is a design choice with a mathematical justification rather than a free parameter.

assumptions (5)

domain assumption The network is 2-edge-connected, and for Theorem 1 every node is given the same upper bound N >= n on the number of nodes.
Section 2.1 states these as model and input assumptions; the algorithm multiplies IDs by N and uses N to set pulse thresholds.
domain assumption The asynchronous scheduler is fair: every pulse is delivered after finite delay, and node actions triggered by a pulse are instantaneous.
Section 2.1; all liveness results (Lemmas 14, 25, 30) rely on eventual delivery.
domain assumption Nodes have unique integer identifiers and incident edges are locally distinguished by port numbers.
Section 2.1; used to define the DFS tree and the strongly connected orientation in Section 2.3, and to set ID-based counting thresholds.
standard math Robbins' theorem: every 2-edge-connected undirected graph admits a strongly connected orientation.
Cited in Section 2.3 as [Rob39]; the paper's own Observation 9 gives a constructive version from a DFS tree. Used to define the directed graph G-tilde for the chain-and-anchor analysis.
standard math After doubling identifiers in Algorithm 3 (Line 1), no two identifiers in the network are consecutive, giving a gap of at least 2.
Consequence of distinct integers being doubled into even integers; used in Lemma 29 and Lemma 30 to ensure neighbors remain in the competing phase long enough.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Content-Oblivious Leader Election in 2-Edge-Connected Networks." pith.science (2026). https://pith.science/paper/XRDTLY32

@misc{pith2026250708348,
  author       = {Pith},
  title        = {Pith review of: Content-Oblivious Leader Election in 2-Edge-Connected Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XRDTLY32}},
  note         = {Machine review of arXiv:2507.08348}
}

abstract

Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may suffer an extreme form of alteration errors, rendering messages completely corrupted. The model is equivalent to content-oblivious computation, where nodes communicate solely via pulses. They showed that if the network is 2-edge-connected, then any algorithm for a noiseless setting can be simulated in the fully-defective setting; otherwise, no non-trivial computation is possible in the fully-defective setting. However, their simulation requires a predesignated leader, which they conjectured to be necessary for any non-trivial content-oblivious task. In this work, we present two results: General 2-edge-connected topologies: First, we show an asynchronous content-oblivious leader election algorithm that quiescently terminates in any 2-edge-connected network with message complexity $O(m \cdot N \cdot \mathsf{ID}_{\min})$, where $m$ is the number of edges, $N$ is a known upper bound on the number of nodes, and $\mathsf{ID}_{\min}$ is the smallest $\mathsf{ID}$. Combined with the above simulation, this result shows that whenever a size bound $N$ is known, any noiseless algorithm can be simulated in the fully-defective model without a preselected leader, fully refuting the conjecture. Unoriented rings: We then show that the knowledge of $N$ can be dropped in unoriented ring topologies by presenting a quiescently terminating election algorithm with message complexity $O(n \cdot \mathsf{ID}_{\max})$ that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous leader election in oriented rings by Frei, Gelles, Ghazy, and Nolin (DISC 2024) and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Computing in Anonymous Dynamic Networks with One-Bit Communications
cs.DC 2026-07 accept novelty 7.0 of 10

One-bit broadcast-counting in anonymous dynamic networks supports general multiset computation in O(n³ log² n) rounds, nearly matching the congested O(n³) bound, with a matching Ω(n³) lower bound for large input universes.

Reference graph

Works this paper leans on

19 extracted references · 13 canonical work pages · cited by 1 Pith paper

[12]

4230 / LIPICS

doi: 10 . 4230 / LIPICS . DISC . 2021

work page 2021
[18]

url: https://doi.org/10.1145/3293611.3331620

doi: 10.1145/3293611.3331620. url: https://doi.org/10.1145/3293611.3331620. [Ray18] Michel Raynal. Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach. Springer, Cham, 2018.doi: 10.1007/978-3-319-94141-7. [Rob39] Herbert Ellis Robbins. A theorem on graphs, with an application to a problem of traffic control. The American Mathematic...

work page arXiv 2018
[23]

[HP21b] Yael Hitron and Merav Parter

url: https://doi.org/10.4230/LIPIcs.DISC.2021.23. [HP21b] Yael Hitron and Merav Parter. General CONGEST compilers against adversarial edges. In Seth Gilbert, editor,Proceedings of the 35th International Symposium on Distributed Computing (DISC), volume 209 of LIPIcs, 24:1–24:18. Schloss Dagstuhl - Leibniz- Zentrum für Informatik,

doi:10.4230/lipics.disc.2021.23 2021
[24]

33 [HPY22] Yael Hitron, Merav Parter, and Eylon Yogev

url: https : //doi.org/10.4230/LIPIcs.DISC.2021.24. 33 [HPY22] Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST algorithms against eavesdroppers. In Christian Scheideler, editor, Proceedings of the 36th International Symposium on Distributed Computing (DISC),volume246of LIPIcs,27:1–27:19.Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022...

work page doi:10.4230/lipics.disc.2021.24 2021
[102]

Secure distributed computing made (nearly) optimal

[PY19b] Merav Parter and Eylon Yogev. Secure distributed computing made (nearly) optimal. In Peter Robinson and Faith Ellen, editors,Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 107–116. ACM,

work page 2019
[1985]

Distributed CONGEST algorithms against mobile ad- versaries

[FP23] Orr Fischer and Merav Parter. Distributed CONGEST algorithms against mobile ad- versaries. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors,Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC), pages 262–273. ACM,

work page 2023
[1992]

Distributed algorithms made secure: A graph theoretic approach

[PY19a] Merav Parter and Eylon Yogev. Distributed algorithms made secure: A graph theoretic approach. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 1693–1710. SIAM, 2019.doi: 10.1137/1.9781611975482.102. url: https://doi.org/10.1137/1.9781611975482

work page doi:10.1137/1.9781611975482.102
[1993]

Coding for interactive communication

[Sch96] Leonard J Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 42(6):1745–1756, 1996.doi: 10.1109/18.556671. [SM20] Yuichi Sudo and Toshimitsu Masuzawa. Leader election requires logarithmic time in population protocols.Parallel Processing Letters, 30(01):2050005,

work page doi:10.1109/18.556671 1996

Show all 19 references

[2003]

Deploying wireless networks with beeps

[CK10] Alejandro Cornejo and Fabian Kuhn. Deploying wireless networks with beeps. In Pro- ceedings of the 24th International Conference on Distributed Computing, DISC’10, pages 148–162, Cambridge, MA. Springer-Verlag, 2010.isbn: 3642157629. [CKP+19] Yi-Jun Chang, Tsvi Kopelowi...

2010 doi
[2006]

Near-optimal leader election in pop- ulation protocols on graphs

[ARV22] Dan Alistarh, Joel Rybicki, and Sasha Voitovych. Near-optimal leader election in pop- ulation protocols on graphs. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC), pages 246–256,

2022
[2013]

Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

[FGG+24] FabianFrei,RanGelles,AhmedGhazy,andAlexandreNolin.Content-ObliviousLeader ElectiononRings.InDanAlistarh,editor, 38th International Symposium on Distributed Computing (DISC 2024), volume 319 ofLeibniz International Proceedings in Informat- ics (LIPIcs), 26:1–26:20, Dag...

2024
[2015]

Mani Krishna, editors

[KK20] Israel Koren and C. Mani Krishna, editors. Fault-Tolerant Systems. Morgan Kaufmann, San Francisco, 2nd edition, 2020.doi: 10.1016/B978-0-12-818105-8. [Par22] MeravParter.Agraphtheoreticapproachforresilientdistributedalgorithms.InAlessia Milani and Philipp Woelfel, edito...

2020 doi
[2018]

Fault-Tolerant Design

32 [Dub13] Elena Dubrova. Fault-Tolerant Design. Springer, Berlin, 2013.doi: 10.1007/978-1- 4614-2113-9. [EK21] Yuval Emek and Eyal Keren. A thin self-stabilizing asynchronous unison algorithm with applications to fault tolerant biological networks. InProceedings of the 2021 A...

2013 doi
[2019]

doi: 10.1016/j.tcs

issn: 0304-3975. doi: 10.1016/j.tcs. 2019.02.027. url: https://doi.org/10.1016/j.tcs.2019.02.027. [CD21] Artur Czumaj and Peter Davies. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks.Journal of the ACM (JACM), 68(2):1–22,

2019 doi
[2020]

Time is not a healer

[SW89] Nicola Santoro and Peter Widmayer. Time is not a healer. InSTACS 1989, volume 349 of Lecture Notes in Comput. Sci.Pages 304–313. Springer,

1989
[2021]

[EW13] YuvalEmekandRogerWattenhofer.Stoneagedistributedcomputing.In Proceedings of the 2013 ACM symposium on Principles of distributed computing (PODC), pages 137– 146,

2013
[2022]

1145 / 3519270

doi: 10 . 1145 / 3519270 . 3538453. url: https://doi.org/10.1145/3519270.3538453. [Pel92] Andrzej Pelc. Reliable communication in networks with byzantine link failures. Net- works, 22(5):441–459,
[2023]

1145 / 3583668

doi: 10 . 1145 / 3583668 . 3594578. url: https://doi.org/10.1145/3583668.3594578. [FSW14] Klaus-Tycho Förster, Jochen Seidel, and Roger Wattenhofer. Deterministic leader elec- tion in multi-hop beeping networks. InProceedings of 28th International Symposium on Distributed Comp...
[2024]

doi: 10.4230/LIPIcs.DISC.2024.26

isbn: 978-3-95977-352-2. doi: 10.4230/LIPIcs.DISC.2024.26. url: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.26. [FLP85] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process.Journal of ...

2024 doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [12]

4230 / LIPICS

doi: 10 . 4230 / LIPICS . DISC . 2021

work page 2021

[2] [18]

url: https://doi.org/10.1145/3293611.3331620

doi: 10.1145/3293611.3331620. url: https://doi.org/10.1145/3293611.3331620. [Ray18] Michel Raynal. Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach. Springer, Cham, 2018.doi: 10.1007/978-3-319-94141-7. [Rob39] Herbert Ellis Robbins. A theorem on graphs, with an application to a problem of traffic control. The American Mathematic...

work page arXiv 2018

[3] [23]

[HP21b] Yael Hitron and Merav Parter

url: https://doi.org/10.4230/LIPIcs.DISC.2021.23. [HP21b] Yael Hitron and Merav Parter. General CONGEST compilers against adversarial edges. In Seth Gilbert, editor,Proceedings of the 35th International Symposium on Distributed Computing (DISC), volume 209 of LIPIcs, 24:1–24:18. Schloss Dagstuhl - Leibniz- Zentrum für Informatik,

doi:10.4230/lipics.disc.2021.23 2021

[4] [24]

33 [HPY22] Yael Hitron, Merav Parter, and Eylon Yogev

url: https : //doi.org/10.4230/LIPIcs.DISC.2021.24. 33 [HPY22] Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST algorithms against eavesdroppers. In Christian Scheideler, editor, Proceedings of the 36th International Symposium on Distributed Computing (DISC),volume246of LIPIcs,27:1–27:19.Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022...

work page doi:10.4230/lipics.disc.2021.24 2021

[5] [102]

Secure distributed computing made (nearly) optimal

[PY19b] Merav Parter and Eylon Yogev. Secure distributed computing made (nearly) optimal. In Peter Robinson and Faith Ellen, editors,Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 107–116. ACM,

work page 2019

[6] [1985]

Distributed CONGEST algorithms against mobile ad- versaries

[FP23] Orr Fischer and Merav Parter. Distributed CONGEST algorithms against mobile ad- versaries. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors,Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC), pages 262–273. ACM,

work page 2023

[7] [1992]

Distributed algorithms made secure: A graph theoretic approach

[PY19a] Merav Parter and Eylon Yogev. Distributed algorithms made secure: A graph theoretic approach. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 1693–1710. SIAM, 2019.doi: 10.1137/1.9781611975482.102. url: https://doi.org/10.1137/1.9781611975482

work page doi:10.1137/1.9781611975482.102

[8] [1993]

Coding for interactive communication

[Sch96] Leonard J Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 42(6):1745–1756, 1996.doi: 10.1109/18.556671. [SM20] Yuichi Sudo and Toshimitsu Masuzawa. Leader election requires logarithmic time in population protocols.Parallel Processing Letters, 30(01):2050005,

work page doi:10.1109/18.556671 1996