Pith. sign in

REVIEW 2 major objections 4 minor 37 references

Complementary Time-Space Tradeoff for Self-Stabilizing Leader Election: Polynomial States Meet Sublinear Time

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper proves that self-stabilizing leader election in population protocols with exact population size $n$ admits a time–space tradeoff: for any $\rho$ with $2\le\rho\le\sqrt n$, there is a protocol stabilizing in…

desk verdict Genuinely new polynomial-state/sublinear-time SS-LE tradeoff with a solid Detect subprotocol, but the load-bearing FindTarget lemma is not proved and must be fixed before the main theorem is fully supported. read the letter →

arxiv 2505.23649 v3 pith:VX4YSMOR submitted 2025-05-29 cs.DC

Yuichi Sudo This is my paper
classification cs.DC MSC 68W1568M14
keywords self-stabilizingleaderelectionpopulationprotocolstime-spacetradeoffrankingcollisiondetectionphaseclockloosely-stabilizinglabeledepidemic
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

The paper proves a time–space tradeoff for self-stabilizing leader election in population protocols where every agent knows the exact population size $n$: for any integer $\rho$ with $2\le\rho\le\sqrt n$, there is a protocol that stabilizes in $O((n/\rho)\log\rho)$ expected time using $2^{2\rho\lg^2\rho+O(\log n)}$ states. Choosing $\rho=\Theta(\log n/\log^2\log n)$ makes the expected time $o(n)$ while the state count is only polynomial in $n$, which would be the first protocol in this model to combine sublinear expected time with polynomially many states. The result is obtained by solving the stronger self-stabilizing ranking problem: from any initial configuration the protocol eventually gives all agents distinct ranks in $[1,n]$, and the agent with rank $1$ serves as the leader.

What carries the argument

The load-bearing component is the collision-detection subroutine $\textsc{Detect}(r,\rho)$, which classifies agents into kings, vassals, ronins, and commoners with respect to a target rank $r$. A king recruits up to $\lfloor\rho\lg\rho\rfloor$ vassals and records their ranks in a set $\mathit{list}$; a vassal raises a suspicion flag when its list is not contained in another king's list, and suspicion spreads among vassals by a new labeled epidemic whose ordered propagation prevents outdated vassals from contaminating the king. A phase clock driven by a loosely-stabilizing leader synchronizes the cycles among $\textsc{FindTarget}$, $\textsc{Detect}(r,\rho)$, and $\textsc{Rank}$, so the whole protocol needs only polynomial state except for the $\rho$-dependent list sets.

What would settle it

From a safe configuration, create one outdated vassal with suspicion flag set whose rank list is not contained in its king's list; Lemma 4 predicts that no king ever raises the detected flag, so any interaction sequence in which the king sets $\mathit{det}=1$ would refute the safety guarantee and thus the stabilization claim.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for any positive integer $\rho$ with $2\le\rho\le\sqrt n$, the protocol $\mathcal{P}_{SSRK}(\rho)$ solves self-stabilizing ranking (and hence self-stabilizing leader election) within $O((n/\rho)\log\rho)$ expected parallel time using $2^{2\rho\lg^2\rho+O(\log n)}$ states. At the corner $\rho=\Theta(\log n/\log^2\log n)$ the expected time is $O(n\log^3\log n/\log n)=o(n)$ and the state count is polynomial, resolving the first open problem of earlier work in stronger form than sub-exponential states. The protocol runs three subroutines cyclically—find a duplicated rank, confirm the duplication, reassign unique ranks—and its collision-detection subroutine is designed so that once ranks are unique, stale information left over from past cycles can never cause a false detection; this is what makes repeated cycles safe and ultimately yields a stable assignment.

Load-bearing premise

The proof assumes that the previously known collision-detection routine, after being modified only to output a duplicate rank as the target, still detects collisions with probability $1-o(1)$ and never raises false positives from a correctly initialized configuration; if that transferred guarantee fails, the cycle cannot reliably enter the detection phase with a valid target.

Editorial extensions

If this is right

  • Setting $\rho=\lfloor\sqrt n\rfloor$ gives $O(\sqrt n\log n)$ expected time with $2^{\sqrt n\lg^2 n+O(\log n)}$ states.
  • Setting $\rho=\Theta(\log n/\log^2\log n)$ gives the claimed first polynomial-state, sublinear-time self-stabilizing leader election protocol.
  • Because the protocol assigns distinct ranks to all agents, it solves self-stabilizing ranking, not merely leader election.
  • The restriction $\rho\le\sqrt n$ implies this design cannot reach $o(\sqrt n\log n)$ expected time, a gap the paper leaves open.
  • Standard self-stabilization arguments convert the expected-time bound into an $O((n/\rho)\log\rho\cdot\log n)$ high-probability bound.

Reading between the lines

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

  • A modular reading of the cycle suggests that a faster collision-finding subroutine could be substituted into $\textsc{FindTarget}$ and improve the whole tradeoff, since the safety argument for $\textsc{Detect}$ is independent of how the target was found.
  • The $\rho\le\sqrt n$ ceiling is likely tied to the vassal-list size; allowing lists to grow with $n$ or tracking several candidate ranks at once might push the time below $\sqrt n\log n$, at the cost of more states, but the paper does not investigate this.
  • The labeled-epidemic lemma—ordered infection reaches a constant fraction of the population in $O(\log^2 n)$ expected time—could be reused as a primitive in other population protocols that need propagation biased by labels.
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.

Referee Report

2 major / 4 minor

Summary. The paper presents a self-stabilizing ranking (SS-RK) protocol, parameterized by an integer ρ with 2 ≤ ρ ≤ √n, that runs in O(n/ρ · log ρ) expected parallel time using 2^{2ρ lg^2 ρ + O(log n)} states. Since SS-RK implies self-stabilizing leader election, Theorem 1 gives a new time–space tradeoff, and choosing ρ = Θ(log n / log^2 log n) yields the claimed first poly-state protocol with sublinear expected stabilization time. The construction runs FindTarget, Detect(r, ρ), and Rank in synchronous cycles driven by a phase clock, with a loosely-stabilizing leader election protocol providing a unique leader. The core technical novelty is Detect(r, ρ), analyzed through a new 'labeled epidemic' process, together with a safety lemma showing no false-positive collision detection after the population reaches a safe configuration.

Significance. If the main theorem is correct, this is a substantial contribution: it resolves the first open problem of BCC+21a in a stronger form than the concurrent protocol of ABF+25, since it achieves polynomial states in the sublinear-time regime rather than only sub-exponential states. The paper is commendably explicit about the limitation ρ ≤ √n and about the comparison to ABF+25, and the main construction has no fitted parameters: the constants are standard protocol constants, and the state bound is derived directly from the variable domains. The proofs of the labeled-epidemic bound (Lemma 2), the Detect liveness bound (Lemma 3), and the no-false-positive safety lemma (Lemma 4) are detailed and internally consistent, and the paper correctly identifies the final-phase target epidemic as needed for agreement on a target rank. However, the proof of Lemma 9, which is the gate through which every successful stabilization cycle must pass, is not actually supplied in the manuscript; this is a load-bearing gap that must be closed before the claimed theorem is fully established.

major comments (2)
  1. [Section 8, Lemma 9, Algorithm 4, Table 3] Lemma 9 is not proved in the manuscript, and Theorem 1 relies on it in an essential way. Section 8 states that FindTarget is obtained by 'slightly modifying' the CDWB protocol of [AS25] so that agents output a duplicate rank, and that the detection guarantee transfers, but no invariant of CDWB is reproduced and no argument shows that the new output behavior in Algorithm 4, lines 47-48 and 63-64, preserves CDWB's no-false-positive and detection guarantees from a correctly initialized configuration. The cited guarantee from [AS25] concerns detecting that some collision exists; it does not by itself imply that all agents agree on a specific duplicate rank, or that the rank stored in target is in R(C). The final-phase max-epidemic in line 65 does propagate the maximum target seen, but it only helps if the value being propagated is guaranteed to be a duplicate rank. In addition, Table 3 initializes only target and parity for FindTarget, while Algorithm 4's variables gID and infectivity have no specified initial values when an agent enters mode F; CDWB's 'correctly initialized configuration' assumption is therefore not established for C_init(F). I note that the stress-test concern about Algorithm 4 omitting the final-phase target epidemic does not survive a close reading: line 65 implements exactly that max-epidemic when p2 >= T2-2. The remaining gap is nevertheless real and must be closed with a proof or a precise lemma transfer.
  2. [Section 6, Lemma 7] Lemma 7 is load-bearing and is dispatched with a one-sentence citation to three prior lemmas rather than a proof. Every successful cycle in Theorem 1 starts from a configuration in I, so without a verifiable proof that P_SSRK(ρ) reaches I from an arbitrary configuration w.h.p. within O(T4 n log n) interactions, the union-bound argument in Section 9 has no guaranteed starting point. The reset/delay mechanism in Algorithm 2, lines 9-19, is only sketched in the text, which says the details are omitted because they follow standard techniques. Please provide a complete derivation, or state precisely which conditions of Lemma 1 of [ADK+17], Lemma 5 of [SOK+20], and Lemma 6 apply to these exact update rules, including the cases where multiple agents carry reset flags and where no agent initially has a reset flag. This is likely fixable, but the current text is not sufficient for a referee to verify the self-stabilizing reset claim.
minor comments (4)
  1. [Section 8] The sentence immediately before Lemma 9 says 'we have the following theorem', but the numbered statement is Lemma 9; please change 'theorem' to 'lemma'.
  2. [Section 4, Algorithm 1] The set Rname is written as [1, ρ2] in several places, which is easy to misread as the two-element set {1, ρ2}; since the analysis uses |Rname| = ρ^2, please typeset it consistently as [1, ρ^2] throughout.
  3. [Algorithm 4, Table 3] Algorithm 4 declares gID and infectivity but gives no initial values for them at mode entry, and Table 3 lists only target and parity for FindTarget. If these variables are overwritten before CDWB uses them, say so explicitly and prove that the overwriting happens within the required initialization window; otherwise, state their initial values.
  4. [Appendix A, proof of Remark 2] The lower bound for AssignRanks_ρ assumes that the n agents are 'eventually split into ρ deputies and n−ρ recipients', but no reference or proof is given that this is an inherent property of AssignRanks_ρ rather than a property of one particular implementation. Since Remark 2 is used to argue that [ABF+25] cannot achieve the stronger O(n/ρ log ρ) bound, please cite the relevant part of [ABF+25] or make the assumption explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the claimed tradeoff is derived from independently proved lemmas and a direct state count; the self-citations are external prior work, not inputs that force the conclusion.

full rationale

The derivation chain in this paper does not reduce to its inputs. Theorem 1's space bound is a direct count of the list-variable domain in Section 9 (the sum over subsets of [1, ρ^2] of size at most floor(ρ lg ρ)), and its time bound is assembled by union bounds from Lemma 7 (reset), Lemma 9 (FindTarget), Lemma 3 (Detect), Lemma 8 (Rank), and Lemma 6 (phase clock). No parameter is fitted to the target O(n/ρ · log ρ) bound, and no equation is defined in terms of the theorem it is supposed to prove. The protocol does depend on two prior papers with overlapping authorship—[SEIM21] for the loosely-stabilizing leader and [AS25] for the CDWB collision-detection module—but these are peer-reviewed results that do not contain Theorem 1; Lemma 5 is additionally re-proved in Appendix A. The most fragile point is Lemma 9, which asserts that a 'slight modification' of CDWB makes all agents agree on one duplicate rank; the paper does not reproduce CDWB's invariants or prove the preservation of its guarantees under the modification, and agreement on a specific duplicate rank is stronger than the cited detection guarantee. This is an unproved transfer and a genuine correctness risk, but it is not circularity: the agreement property is not assumed as a premise, fitted to data, or defined in terms of the final stabilization claim. Hence no step satisfies the reduction-by-construction test, and the appropriate finding is no significant circularity.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

No new physical or mathematical entities are introduced. 'Labeled epidemic', 'kings', 'vassals', 'ronins', and 'commoners' are algorithmic roles and an analytical process, not postulated entities with independent evidence. The free parameters are design constants and the tradeoff knob ρ; none are fitted to data.

free parameters (2)
  • ρ = any integer in [2, √n]; e.g. Θ(log n / log^2 log n)
    User-chosen tradeoff parameter, not fitted to data. All time and space bounds are expressed as functions of ρ.
  • constants c_T, c_M, c_R, c_D, c_L, τ = Θ(1), chosen sufficiently large
    Standard protocol constants with no data fitting; they do not affect asymptotic bounds.
assumptions (7)
  • domain assumption Interactions are uniformly random ordered pairs; parallel time counts n interactions as one unit.
    Population protocol model, Section 1.1.
  • domain assumption Every agent knows the exact population size n.
    Stated in the abstract and Section 1; needed for the impossibility background and for setting protocol parameters.
  • domain assumption The epidemic protocol spreads a value to all agents in O(n log n) interactions w.h.p. (Lemma 1 of [AAE08]).
    Used for propagation of det, target, nonce, and reset signals.
  • domain assumption The single-leader phase clock synchronizes phases with high probability (Lemma 6 of [AAE08]).
    Used to run FindTarget, Detect, and Rank in fixed phase intervals and to obtain derandomization bits.
  • domain assumption The LS-LE protocol of [SEIM21] maintains a unique leader for poly(n) interactions w.h.p. (Lemma 5).
    Supplies the leader required by PhaseClock and Rank; proof is sketched in Appendix A.
  • domain assumption The collision-detection protocol CDWB of [AS25] detects collisions in O(n^{3/2}√log n) interactions with probability 1-(2/3)^k and has no false positives from a correct start.
    FindTarget is a modification of CDWB; the paper does not re-prove CDWB.
  • standard math Standard Chernoff, Markov, and coupon-collector bounds apply to the random scheduler.
    Used throughout the time analyses of Detect, Rank, and FindTarget.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complementary Time-Space Tradeoff for Self-Stabilizing Leader Election: Polynomial States Meet Sublinear Time." pith.science (2026). https://pith.science/paper/VX4YSMOR

@misc{pith2026250523649,
  author       = {Pith},
  title        = {Pith review of: Complementary Time-Space Tradeoff for Self-Stabilizing Leader Election: Polynomial States Meet Sublinear Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VX4YSMOR}},
  note         = {Machine review of arXiv:2505.23649}
}
abstract

We study the self-stabilizing leader election (SS-LE) problem in the population protocol model, assuming exact knowledge of the population size $n$. Burman, Chen, Chen, Doty, Nowak, Severson, and Xu [BCC+21a] (PODC) showed that this problem can be solved in $O(n)$ expected time with $O(n)$ states. Recently, G\k{a}sieniec, Grodzicki, and Stachowiak [GGS25] (PODC) proved that $n+O(\log n)$ states suffice to achieve $O(n \log n)$ time both in expectation and with high probability (w.h.p.). If substantially more states are available, sublinear time can be achieved. The authors of [BCC+21] presented a $2^{O(n^\rho\log n)}$-state SS-LE protocol with a parameter $\rho$: setting $\rho = \Theta(\log n)$ yields an optimal $O(\log n)$ time both in expectation and w.h.p., while $\rho = \Theta(1)$ results in $O(\rho\,n^{1/(\rho+1)})$ expected time. Recently, Austin, Berenbrink, Friedetzky, G\"otte, and Hintze [ABF+25] (PODC) presented a novel SS-LE protocol parameterized by a positive integer $\rho$ with $1 \le \rho < n/2$ that solves SS-LE in $O(\frac{n}{\rho}\cdot\log n)$ time w.h.p.\ using $2^{O(\rho^2\log n)}$ states. This paper independently presents yet another time--space tradeoff of SS-LE: for any positive integer $\rho$ with $2 \le \rho \le \sqrt{n}$, SS-LE can be achieved within $O\left(\frac{n}{\rho}\cdot \log\rho\right)$ expected time using $2^{2\rho\lg^2\rho + O(\log n)}$ states. The proposed protocol uses significantly fewer states than [ABF+25] for any expected stabilization time above $\Theta(\sqrt{n}\log n)$. When $\rho = \Theta\left(\frac{\log n}{\log^2 \log n}\right)$, the proposed protocol is the first to achieve sublinear time while using only polynomially many states. A limitation of our protocol is that the constraint $\rho\le\sqrt{n}$ prevents achieving $o(\sqrt{n}\log n)$ time, whereas the protocol of [ABF+25] can surpass this bound.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Time-space trade-offs in population protocols

    Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L Rivest. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2560--2579. SIAM, 2017

    work page 2017

  2. [2]

    Space-optimal majority in population protocols

    Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2221--2239. SIAM, 2018

    work page 2018

  3. [3]

    Robust detection in leak-prone population protocols

    Dan Alistarh, Bart omiej Dudek, Adrian Kosowski, David Soloveichik, and Przemys aw Uzna \'n ski. Robust detection in leak-prone population protocols. In DNA Computing and Molecular Programming: 23rd International Conference, DNA 23, Austin, TX, USA, September 24--28, 2017, Proceedings 23 , pages 155--171. Springer, 2017

    work page 2017

  4. [4]

    Recent algorithmic advances in population protocols

    Dan Alistarh and Rati Gelashvili. Recent algorithmic advances in population protocols. ACM SIGACT News , 49(3):63--73, 2018

    work page 2018

  5. [5]

    Angluin, J

    Dana. Angluin, J. Aspnes, Michael. J Fischer, and Hong. Jiang. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems , 3(4):1--28, 2008

    work page 2008

  6. [6]

    Fischer, and Ren\' e Peralta

    Dana Angluin, James Aspnes, Zo\" e Diamadi, Michael J. Fischer, and Ren\' e Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing , 18(4):235--253, 2006

    work page 2006

  7. [7]

    Fast computation by population protocols with a leader

    Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing , 21(3):183--199, 2008

    work page 2008

  8. [8]

    Sublinear-time Collision Detection with a Polynomial Number of States in Population Protocols

    Takumi Araya and Yuichi Sudo. Sublinear-time collision detection with a polynomial number of states in population protocols, 2025. URL: https://arxiv.org/abs/2411.09957, https://arxiv.org/abs/2411.09957 arXiv:2411.09957

    work page Pith review arXiv 2025

Show all 37 references
  1. [9]

    A space-time trade-off for fast self-stabilizing leader election in population protocols, 2025

    Henry Austin, Petra Berenbrink, Tom Friedetzky, Thorsten G^^c3^^b6tte, and Lukas Hintze. A space-time trade-off for fast self-stabilizing leader election in population protocols, 2025. URL: https://arxiv.org/abs/2505.01210, https://arxiv.org/abs/2505.01210 arXiv:2505.01210

    2025 arXiv

  2. [10]

    Time-space trade-offs in population protocols for the majority problem

    Petra Berenbrink, Robert Els \"a sser, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Time-space trade-offs in population protocols for the majority problem. Distributed Computing , 34:91--111, 2021

    2021

  3. [11]

    Silent self-stabilizing ranking: Time optimal and space efficient, 2025

    Petra Berenbrink, Robert Els^^c3^^a4sser, Thorsten G^^c3^^b6tte, Lukas Hintze, and Dominik Kaaser. Silent self-stabilizing ranking: Time optimal and space efficient, 2025. URL: https://arxiv.org/abs/2504.10417, https://arxiv.org/abs/2504.10417 arXiv:2504.10417

    2025 arXiv

  4. [12]

    Optimal time and space leader election in population protocols

    Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 119--129, 2020

    2020

  5. [13]

    Brief announcement: Population protocols for leader election and exact majority with O( ^2 n) states and O( ^2 n) convergence time

    Andreas Bilke, Colin Cooper, Robert Els\" a sser, and Tomasz Radzik. Brief announcement: Population protocols for leader election and exact majority with O( ^2 n) states and O( ^2 n) convergence time. In Proceedings of the 38th ACM Symposium on Principles of Distributed Comput...

    2017

  6. [14]

    Time-optimal self-stabilizing leader election in population protocols

    Janna Burman, Ho-Lin Chen, Hsueh-Ping Chen, David Doty, Thomas Nowak, Eric Severson, and Chuan Xu. Time-optimal self-stabilizing leader election in population protocols. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , pages 33--44, 2021

    2021

  7. [15]

    Time-optimal self-stabilizing leader election in population protocols, 2021

    Janna Burman, Ho-Lin Chen, Hsueh-Ping Chen, David Doty, Thomas Nowak, Eric Severson, and Chuan Xu. Time-optimal self-stabilizing leader election in population protocols, 2021. URL: https://arxiv.org/abs/1907.06068, https://arxiv.org/abs/1907.06068 arXiv:1907.06068

    2021 arXiv

  8. [16]

    How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model

    Shukai Cai, Taisuke Izumi, and Koichi Wada. How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model. Theory of Computing Systems , 50(3):433--445, 2012

    2012

  9. [17]

    Self-stabilizing leader election

    Hsueh-Ping Chen and Ho-Lin Chen. Self-stabilizing leader election. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing , pages 53--59, 2019

    2019

  10. [18]

    Self-stabilizing leader election in regular graphs

    Hsueh-Ping Chen and Ho-Lin Chen. Self-stabilizing leader election in regular graphs. In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing , pages 210--217, 2020

    2020

  11. [19]

    Dijkstra

    Edger W. Dijkstra. Self-stabilizing systems in spite of distributed control . Communications of the ACM , 17(11):643--644, 1974

    1974

  12. [20]

    Stable leader election in population protocols requires linear time

    David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Computing , 31(4):257--271, 2018

    2018

  13. [21]

    Fischer and Hong Jiang

    Michael J. Fischer and Hong Jiang. Self-stabilizing leader election in networks of finite-state anonymous agents. In International Conference on Principles of Distributed Systems , pages 395--409, 2006

    2006

  14. [22]

    Efficient assignment of identities in anonymous populations

    Leszek G a sieniec, Jesper Jansson, Christos Levcopoulos, and Andrzej Lingas. Efficient assignment of identities in anonymous populations. Information and Computation , 303:105265, 2025

    2025

  15. [23]

    Enhanced phase clocks, population protocols, and fast space optimal leader election

    Leszek G a sieniec and Grzegorz Stachowiak. Enhanced phase clocks, population protocols, and fast space optimal leader election. Journal of the ACM (JACM) , 68(1):1--21, 2020

    2020

  16. [24]

    Almost logarithmic-time space optimal leader election in population protocols

    Leszek G a sieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. In The 31st ACM on Symposium on Parallelism in Algorithms and Architectures , pages 93--102. ACM, 2019

    2019

  17. [25]

    Improving efficiency in near-state and state-optimal self-stabilising leader election population protocols, 2025

    Leszek G^^c4^^85sieniec, Tytus Grodzicki, and Grzegorz Stachowiak. Improving efficiency in near-state and state-optimal self-stabilising leader election population protocols, 2025. URL: https://arxiv.org/abs/2502.01227, https://arxiv.org/abs/2502.01227 arXiv:2502.01227

    2025 arXiv

  18. [26]

    Almost time-optimal loosely-stabilizing leader election on arbitrary graphs without identifiers in population protocols

    Haruki Kanaya, Ryota Eguchi, Taisho Sasada, and Michiko Inoue. Almost time-optimal loosely-stabilizing leader election on arbitrary graphs without identifiers in population protocols. arXiv preprint arXiv:2411.03902 , 2024

    2024

  19. [27]

    Simple and fast approximate counting and leader election in populations

    Othon Michail, Paul G Spirakis, and Michail Theofilatos. Simple and fast approximate counting and leader election in populations. In Proceedings of the 20th International Symposium on Stabilizing, Safety, and Security of Distributed Systems , pages 154--169, 2018

    2018

  20. [28]

    Time-optimal loosely-stabilizing leader election in population protocols

    Yuichi Sudo, Ryota Eguchi, Taisuke Izumi, and Toshimitsu Masuzawa. Time-optimal loosely-stabilizing leader election in population protocols. In 35nd International Symposium on Distributed Computing (DISC 2021) , pages 40:1--40:17, 2021

    2021

  21. [29]

    Leader election requires logarithmic time in population protocols

    Yuichi Sudo and Toshimitsu Masuzawa. Leader election requires logarithmic time in population protocols. Parallel Processing Letters , 30(01):2050005, 2020

    2020

  22. [30]

    Kakugawa, and Toshimitsu Masuzawa

    Yuichi Sudo, Junya Nakamura, Yukiko Yamauchi, Fukuhito Ooshita, Hirotsugu. Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election in a population protocol model. Theoretical Computer Science , 444:100--112, 2012

    2012

  23. [31]

    Time-optimal leader election in population protocols

    Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Time-optimal leader election in population protocols. IEEE Transactions on Parallel and Distributed Systems , 31(11):2620--2632, 2020

    2020

  24. [32]

    Loosely stabilizing leader election on arbitrary graphs in population protocols without identifiers or random numbers

    Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely stabilizing leader election on arbitrary graphs in population protocols without identifiers or random numbers. IEICE Transactions on Information and Systems , 103(3):489--499, 2020

    2020

  25. [33]

    Loosely-stabilizing leader election for arbitrary graphs in population protocol model

    Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. Loosely-stabilizing leader election for arbitrary graphs in population protocol model. IEEE Transactions on Parallel and Distributed Systems , 30(6):1359--1373, 2018

    2018

  26. [34]

    Loosely-stabilizing leader election with polylogarithmic convergence time

    Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. Loosely-stabilizing leader election with polylogarithmic convergence time. Theoretical Computer Science , 806:617--631, 2020

    2020

  27. [35]

    Self-stabilizing population protocols with global knowledge

    Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Self-stabilizing population protocols with global knowledge. IEEE Transactions on Parallel and Distributed Systems , 32(12):3011--3023, 2021

    2021

  28. [36]

    Time-optimal self-stabilizing leader election on rings in population protocols

    Daisuke Yokota, Yuichi Sudo, and Toshimitsu Masuzawa. Time-optimal self-stabilizing leader election on rings in population protocols. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , 104(12):1675--1684, 2021

    2021

  29. [37]

    A near time-optimal population protocol for self-stabilizing leader election on rings with a poly-logarithmic number of states

    Daisuke Yokota, Yuichi Sudo, Fukuhito Ooshita, and Toshimitsu Masuzawa. A near time-optimal population protocol for self-stabilizing leader election on rings with a poly-logarithmic number of states. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computi...

    2023

Pith tools

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