Pith. sign in

REVIEW 3 major objections 5 minor 2 cited by

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

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper answers the open question of whether collision detection in population protocols can be solved in sublinear parallel time with a polynomial number of states per agent, presenting a protocol that does so with probability one.

desk verdict Solid CDWB core, but Theorem 1's integration argument has a genuine hole that blocks the claimed main result. read the letter →

arxiv 2411.09957 v2 pith:VBQRPN7P submitted 2024-11-15 cs.DC

Takumi Araya , Yuichi Sudo This is my paper · ORCID
classification cs.DC MSC 68W15
keywords populationprotocolscollisiondetectionsublinearparalleltimephaseclocksquare-rootdecompositionnonce-basedidentifiersanonymousagentspolynomialstates
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 studies collision detection in the population protocol model, where $n$ anonymous state-machine agents, each holding a rank in $[1,n]$, must all output whether any two ranks coincide, while one pair of agents is chosen uniformly at random to interact at each step. It claims that the task can be solved in sublinear parallel time with a polynomial state count: $O(n^{3/2}\log^{3/2} n)$ interactions with high probability and $O(n^{3/2}\sqrt{\log n})$ in expectation, using $\tilde{O}(n)$ states per agent. This answers an open question posed in 2021, and it is the first protocol to achieve sublinear parallel time with polynomially many states. The algorithm synchronizes the population into the same epoch with a phase clock, splits the rank range into segments of length about $\sqrt{n\log n}$, and proliferates nonce-tagged group identifiers so that two agents with the same rank but different nonces meet and raise a collision flag. A slower backup protocol guarantees correctness with probability 1 even when the fast stage misses a collision.

What carries the argument

The load-bearing mechanism is the proliferation of nonce-tagged group identifiers inside synchronized epochs. Each epoch is dedicated to one segment of the rank range; agents in that segment generate $({\rm offset}, \chi)$ identifiers with a uniform random nonce $\chi$, and an infectivity counter caps how many times an identifier can be copied, so that the set of non-null agents stays below $n/2$. A collision is registered exactly when two agents with the same offset carry different nonces, and the phase clock supplies the synchronized windows that make each epoch long enough for proliferation to complete while short enough that the total time stays $O(n^{3/2}\log^{3/2} n)$.

What would settle it

Run the phase clock alone with $F = \Theta(\sqrt{n}\log^{3/2}n)$ and a constant $m$, and record the first epoch where some agent's epoch value differs from the leader's for a full $d_1 n\log n$ window. If such a desynchronization occurs with non-negligible probability for large $n$, Lemma 2 is false and the $O(n^{3/2}\log^{3/2}n)$ stabilization bound no longer follows from the proof as written.

Watch

Extended reading notes

Core claim

The central claim is that the collision detection problem no longer forces a linear-time lower bound when only polynomially many states are allowed. In the leader-assisted protocol CDWB, the rank range is divided into $z = \lceil n_U/\ell\rceil$ segments of length $\ell = \lceil\sqrt{n_L\log n_L}\rceil$, and a modified phase clock makes all agents progress through $F = r z + 1$ epochs together, with $r=\Theta(\log n)$ epochs devoted to each segment. In an epoch for a segment, every agent whose rank lies in that segment generates a group identifier consisting of its rank offset inside the segment and a random nonce; these identifiers spread to null agents with a capped infectivity counter. Two agents with the same rank offset but different nonces prove a collision and raise a flag. Since at most $2\ell$ agents can enter a segment when the number of colliding pairs is small, the proliferation completes in $O(n\log n)$ steps per epoch, and the $r$ repetitions drive the failure probability below $n^{-\eta}$. The full protocol runs the size-estimation procedure Approximate in parallel to elect a leader and learn $\log n$, then executes CDWB, with a direct-interaction backup ensuring that correctness holds with probability 1.

Load-bearing premise

The whole speedup rests on an unproved lemma: that a global synchronization timer (the phase clock) keeps every agent in the same round for at least $d_1 n\log n$ and at most $d_2 n\log n$ steps, across $F=\Theta(\sqrt{n}\log^{3/2}n)$ consecutive rounds; if that synchronization fails, the round-based detection and the sublinear time bound collapse.

Editorial extensions

If this is right

  • Collision detection is now solvable in $\tilde{O}(\sqrt{n})$ parallel time with $\tilde{O}(n)$ states per agent, replacing the previous situation where the fastest polynomial-state protocols needed linear parallel time.
  • The protocol is always correct with probability 1: the fast stage only decides how quickly stabilization happens, and the backup protocol eventually raises the flag in every colliding configuration.
  • The square-root decomposition reduces detection over the full $[1,n]$ range to $\Theta(\sqrt{n\log n})$ independent segment subproblems, each solved within $O(n\log n)$ interactions with high probability.
  • Running the size-estimation procedure Approximate in parallel removes the need for a pre-elected leader and for exact knowledge of $n$, so the same bounds hold from any initialized configuration.

Reading between the lines

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

  • Beyond the paper's stated results, the segment-and-nonce proliferation looks reusable for other multiset predicates, such as estimating the number of duplicated ranks, at a similar state cost.
  • A natural next step is to turn this collision detector into a ranking subroutine inside a self-stabilizing or loosely-stabilizing leader-election protocol; if that works, sublinear-time self-stabilizing ranking with polynomial states would follow.
  • The derandomization remark suggests the protocol can run without internal random bits by using the initiator/responder role of each interaction as the nonce source, a variant worth testing in scheduler models with less explicit randomness.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper presents a population protocol, CollisionDetection, for the collision detection problem, in which every agent starts with an input rank in [1,n] and must eventually output whether any two agents share the same rank. The protocol first runs the Approximate counting/leader-election protocol of Berenbrink et al., and once agents have matching level and logNum values and countFin=1, it runs a subprotocol CDWB that uses a phase clock and a square-root decomposition over segments of the rank space. The paper claims that the integrated protocol stabilizes within O(n^{3/2} log^{3/2} n) time steps with high probability and O(n^{3/2} sqrt(log n)) in expectation, using tilde-O(n) states per agent excluding the input rank, and that this is the first polynomial-state sublinear-time solution to the open problem raised by Burman et al.

Significance. If the main theorem were established, the paper would resolve an open question affirmatively: it would give the first sublinear parallel time, polynomial-state population protocol for collision detection. The core CDWB subprotocol is a serious algorithmic contribution: the square-root decomposition, the phase-clock epoch structure, and the virtual-agent analysis of the bounded-proliferation process are well-motivated and the internal lemmas (Lemmas 4 and 5) are argued in detail with Chernoff bounds and a branching-process interpretation. However, the integration of CDWB with Approximate in Section 4.2 contains a load-bearing gap: the suffix of the integrated execution is claimed to be exactly a CDWB execution, but the protocol only invokes CDWB on pairs of agents that both have countFin=1. As written, this invalidates the application of the standalone CDWB analysis to the main protocol. The significance of the result is therefore conditional on a correct integration argument.

major comments (3)
  1. [§4.1, Algorithm 3 line 16, Lemma 5] The proof of Theorem 1 claims that the suffix Ct, Ct+1, ... 'exactly corresponds to the execution of CDWB'. This is not correct. Lemma 6 gives a time t at which only the leader aL and one other agent u have countFin=1; all other agents have countFin=0. Algorithm 4 executes CDWB only when both interacting agents have countFin=1 (lines 32-33), so for interactions involving a countFin=0 agent the PhaseClock and the rest of CDWB are skipped. During the subsequent one-way epidemic that sets countFin=1 for the remaining agents, the active agents' phase clock advances only through their pairwise meetings, which occur with probability Theta(1/n^2) per step, not through the full-population process analyzed in CDWB. Inactive agents remain frozen at their initial timer and epoch values. Moreover, the assertion that 'in an execution of CDWB, no agent changes its state before the unique leader aL has its first interaction' is false even for standalone CDWB: Algorithm 2 lines 6-7 update a non-leader responder's timer on any interaction, including interactions between two non-leaders. Therefore Lemma 2 and Lemmas 4-5 cannot be applied to the integrated protocol, and the claimed O(n^{3/2} log^{3/2} n) high-probability bound and O(n^{3/2} sqrt(log n)) expectation bound are unsupported. A separate argument is needed to show either that the partial-participation prefix leaves the configuration within O(1) CDWB updates of the initial configuration, or the integration must be redesigned so that all agents start CDWB from a synchronized initial configuration.
  2. [§3.2, Lemma 2] There is an inconsistency in the nonce range. The text in Section 4.1 says that x (the nonce) is chosen uniformly at random in [0, ceil(n_U eta / r) - 1], but Algorithm 3 line 16 selects x uniformly from {0,1}. Lemma 5's probability 1/2 that two colliding agents choose different nonces relies on the binary range. If the intended range is the larger set, then the probability of a different nonce is much higher, but the domain of gid becomes Theta(ell * n_U eta / r), which is Theta(n^{3/2} / sqrt(log n)) for the parameter choices in the paper, contradicting the claim in Lemma 5 that 'gid uses O(sqrt(n)) states'. The paper must choose one nonce range and adjust the probability and state-count arguments accordingly.
  3. [§3.2, Lemma 2] Lemma 2 is stated without proof and is attributed to Angluin et al. [6], but it is used for a non-constant number of epochs: in CDWB, F = r*z + 1 = Theta(log n * n / sqrt(n log n)) = Theta(sqrt(n) log^{3/2} n). The cited phase clock analysis in [6] is for a constant number of phases, and it is not immediate that the same constants d1 and d2, and the same high-probability bound, hold uniformly for every epoch index up to a non-constant F. Since Lemma 2 is the basis for the epoch-synchronization argument that underlies the round-based collision detection in CDWB, the paper should either prove the lemma for this parameter range or cite a specific theorem in [6] that explicitly covers non-constant F. Without this, the time bound of Lemma 5 is not fully supported.
minor comments (5)
  1. [Algorithm 4, line 33] The call 'CDWB(r, 2a.logNum-1, 2a.logNum+1)' appears to pass three arguments, while CDWB is defined with two parameters (nL, nU) in Algorithm 3. It should probably be 'CDWB(2a.logNum-1, 2a.logNum+1)', and the role of r needs to be clarified or removed.
  2. [Lemma 5] The statement that 'gid uses O(sqrt(n)) states' is inaccurate: with ell = ceil(sqrt(n_L log n_L)), the domain of gid has size Theta(ell) = Theta(sqrt(n log n)). The final tilde-O(n) state bound is unaffected if the tilde is applied, but the sentence should be corrected for precision.
  3. [Section 4.1, page 8] The text says 'all agents enter the final epoch r * ell + 1', but the phase clock argument is F = r*z + 1; the symbol ell appears to be a typo for z.
  4. [Lemma 5] The inequality '1/2 - epsilon >= 1/3' requires epsilon <= 1/6. Since d1 can be chosen arbitrarily large, this is fixable, but the proof should state a concrete small constant rather than 'any constant epsilon'.
  5. [Section 4.2, paragraph before Algorithm 4] The description of the 'straightforward' integration says CDWB would be executed 'if either a.countFin = 0 or b.countFin = 0', which is the opposite of the condition used in Algorithm 4 lines 32-33. The text and the pseudocode should be aligned.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the claimed time bounds and correctness follow from explicit probabilistic analyses, and the load-bearing external lemmas are not self-citations.

full rationale

The derivation chain in this paper is not circular. The main result, Theorem 1, is obtained by combining (a) CDWB's own probabilistic analysis (Lemma 4 and the repeated-epoch argument with success probability 1/3), (b) the external one-way epidemic and phase clock results of Angluin, Aspnes, and Eisenstat [6], and (c) the external Approximate counting/leader-election protocol of Berenbrink, Kaaser, and Radzik [10]. None of these load-bearing ingredients is fitted to the paper's own output, and none is a renamed version of the collision-detection claim. Lemma 2, the phase-clock synchronization lemma for a non-constant number of epochs, is stated as 'directly follows' from [6] and is not proved in this paper, but this is an omitted/supporting external proof, not a circular dependency. The only self-citation used in a technical proof is [26] for the 'virtual agents' concept in Lemma 4; the proof in this paper defines the virtual agents explicitly and gives its own Chernoff-bound argument, so the citation is a proof technique, not a load-bearing unverified premise. No uniqueness theorem is imported from the authors' prior work, and no fitted parameter is renamed as a prediction. The Theorem 1 claim that the suffix after Approximate stabilization 'exactly corresponds to the execution of CDWB' is a substantive correctness assertion; whether it is actually valid given the partial participation of CDWB is a legitimate correctness risk, but it is not circularity because it does not reduce the theorem to its own assumptions by definition. Overall, the paper's central derivation is self-contained apart from standard external lemmas, so the circularity score is 0.

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

The algorithm's central claim rests on standard tools (epidemic, phase clock, counting) and chooses parameters ℓ, r, z, m to balance time and state count. No fitted constants or invented physical entities.

free parameters (4)
  • ℓ (segment length) = ⌈√(n_L log n_L)⌉
    Chosen to balance segment size against number of segments, yielding sublinear time; affects state count and detection probability.
  • r (epochs per segment) = ⌈3η log n_U⌉
    Set to make detection failure probability ≤ n^{-η}; affects total time O(r z n log n).
  • z (number of segments) = ⌈n_U/ℓ⌉
    Determined by ℓ and n_U; number of epochs per full cycle.
  • m (phase clock modulus) = constant (choice via Lemma 2)
    Must be sufficiently large constant to satisfy Lemma 2's synchronization guarantees.
assumptions (5)
  • standard math Epidemic propagation reaches all agents in O(n log n) steps w.h.p. (Lemma 1)
    Cited from [6]; used throughout for flag and epoch propagation.
  • standard math Phase clock with one leader synchronizes all agents' epochs, each epoch lasting Θ(n log n) steps (Lemma 2)
    Stated without proof as a consequence of [6]; central to the round structure of CDWB.
  • standard math Counting protocol Approximate elects a leader and estimates log n in O(n log^2 n) steps w.h.p. (Lemma 6)
    Cited from [10]; used to remove leader and size-knowledge assumptions.
  • domain assumption Uniformly random scheduler; ordered pairs chosen uniformly
    Model definition in Section 2.1; central to all probabilistic analyses.
  • domain assumption Input ranks are fixed and do not change
    Model assumption in Section 2.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sublinear-time Collision Detection with a Polynomial Number of States in Population Protocols." pith.science (2026). https://pith.science/paper/VBQRPN7P

@misc{pith2026241109957,
  author       = {Pith},
  title        = {Pith review of: Sublinear-time Collision Detection with a Polynomial Number of States in Population Protocols},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VBQRPN7P}},
  note         = {Machine review of arXiv:2411.09957}
}
abstract

This paper addresses the collision detection problem in population protocols. The network consists of state machines called agents. At each time step, exactly one pair of agents is chosen uniformly at random to have an interaction, changing the states of the two agents. The collision detection problem involves each agent starting with an input integer between $1$ and $n$, where $n$ is the number of agents, and requires those agents to determine whether there are any duplicate input values among all agents. Specifically, the goal is for all agents to output false if all input values are distinct, and true otherwise. In this paper, we present an algorithm that requires a polynomial number of states per agent and solves the collision detection problem with probability one in sub-linear parallel time, both with high probability and in expectation. To the best of our knowledge, this algorithm is the first to solve the collision detection problem using a polynomial number of states within sublinear parallel time, affirmatively answering the question raised by Burman, Chen, Chen, Doty, Nowak, Severson, and Xu [PODC 2021] for the first time.

Figures

Figures reproduced from arXiv: 2411.09957 by the authors.

Figure 1
Figure 1. Segments of the second part of CDWB(nL, nU ) [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

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

    cs.DC 2025-05 conditional novelty 8.0 of 10

    For any 2≤ρ≤√n, a new protocol solves self-stabilizing ranking in O(n/ρ·logρ) expected time with 2^{2ρlg^2ρ+O(logn)} states, the first to combine sublinear time with polynomial states.

  2. A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols

    cs.DC 2025-05 conditional novelty 8.0 of 10

    A parametrized population protocol solves self-stabilizing leader election in O(n log n / r) time with 2^{O(r^2 log n)} states, yielding O(log n) time with 2^{O(n^2 log n)} states and sublinear time with 2^{O(log^3 n)...

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · cited by 2 Pith papers

  1. [6]

    Fast computation by population pro- tocols with a leader.Distributed Computing, 21(3):183–199, 2008

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

    work page 2008

  2. [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. InProceedings of the Twenty-Eighth Annual ACM- SIAM Symposium on Discrete Algorithms, pages 2560–2579. SIAM, 2017

    work page 2017

  3. [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

  4. [3]

    Polylogarithmic-time leader election in population pro- tocols

    Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population pro- tocols. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, pages 479–491, 2015

    work page 2015

  5. [4]

    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. [5]

    Fischer, and René Peralta

    Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Compu- tation in networks of passively mobile finite-state sensors.Distributed Computing, 18(4):235– 253, 2006

    work page 2006

  7. [7]

    Self-stabilizing leader election in population protocols over arbitrary communication graphs

    Joffroy Beauquier, Peva Blanchard, and Janna Burman. Self-stabilizing leader election in population protocols over arbitrary communication graphs. InInternational Conference on Principles of Distributed Systems, pages 38–52, 2013. 13

    work page 2013

  8. [8]

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

    Petra Berenbrink, Robert Elsä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

    work page 2021

Show all 34 references
  1. [9]

    Optimal time and space leader elec- tion in population protocols

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

    2020

  2. [10]

    On counting the population size

    Petra Berenbrink, Dominik Kaaser, and Tomasz Radzik. On counting the population size. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 43–52, 2019

    2019

  3. [11]

    Time-optimal self-stabilizing leader election in population protocols

    JannaBurman, Ho-LinChen, Hsueh-PingChen, DavidDoty, ThomasNowak, EricSeverson, 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

  4. [12]

    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

  5. [13]

    Potop-Butucaru

    Davide Canepa and Maria G. Potop-Butucaru. Stabilizing leader election in population protocols. http://hal.inria.fr/inria-00166632, 2007

    2007

  6. [14]

    Passively mobile communicating machines that use restricted space

    Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Andreas Pavlogiannis, and Paul G Spirakis. Passively mobile communicating machines that use restricted space. In Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foun- dations of Mobile Computin...

    2011

  7. [15]

    Self-stabilizing leader election

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

    2019

  8. [16]

    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

  9. [17]

    Efficient size estimation and impossibility of termination in uniform dense population protocols

    David Doty and Mahsa Eftekhari. Efficient size estimation and impossibility of termination in uniform dense population protocols. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, page 34–42, 2019

    2019

  10. [18]

    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

  11. [19]

    Fischer and Hong Jiang

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

    2006

  12. [20]

    Fast space optimal leader election in population protocols

    Leszek Gąsieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2653–2667. SIAM, 2018

    2018

  13. [21]

    Almostlogarithmic-time space optimal leader election in population protocols

    LeszekGąsieniec, GrzegorzStachowiak, andPrzemyslawUznanski. Almostlogarithmic-time space optimal leader election in population protocols. InThe 31st ACM on Symposium on Parallelism in Algorithms and Architectures, pages 93–102. ACM, 2019. 14

    2019

  14. [22]

    On space and time complexity of loosely-stabilizing leader election

    Taisuke Izumi. On space and time complexity of loosely-stabilizing leader election. In International Colloquium on Structural Information and Communication Complexity, pages 299–312, 2015

    2015

  15. [23]

    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 Sympo- sium on Distributed Computing (DISC 2021), pages 40:1–40:17, 2021

    2021

  16. [24]

    Leader election requires logarithmic time in popu- lation protocols

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

    2020

  17. [25]

    The same speed timer in population protocols

    Yuichi Sudo, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. The same speed timer in population protocols. In the 36th IEEE International Conference on Dis- tributed Computing Systems, pages 252–261, 2016

    2016

  18. [26]

    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

  19. [27]

    Time-optimal leader election in population protocols.IEEE Transactions on Par- allel and Distributed Systems, 31(11):2620–2632, 2020

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

    2020

  20. [28]

    Loosely- stabilizing leader election on arbitrary graphs in population protocols

    Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely- stabilizing leader election on arbitrary graphs in population protocols. In International Conference on Principles of Distributed Systems, pages 339–354, 2014

    2014

  21. [29]

    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

  22. [30]

    Loosely-stabilizing leader election for arbitrary graphs in popu- lation protocol model.IEEE Transactions on Parallel and Distributed Systems, 30(6):1359– 1373, 2018

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

    2018

  23. [31]

    Loosely-stabilizing leader election with polylogarithmic conver- gence time

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

    2020

  24. [32]

    Self-stabilizing population protocols with global knowledge.IEEE Transactions on Parallel and Distributed Systems, 32(12):3011–3023, 2021

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

    2021

  25. [33]

    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

  26. [34]

    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. InProceedings of the 2023 ACM Symposium on Principles of Distributed Computi...

    2023

Pith tools

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