pith. sign in

arxiv: 1907.06855 · v1 · pith:MST3S62Snew · submitted 2019-07-16 · 💻 cs.MA · cs.DC

Broadcast Distributed Voting Algorithm in Population Protocols

Hamidreza Bandealinaeini , Saber Salehkaleybar This is my paper

Pith reviewed 2026-05-24 20:54 UTC · model grok-4.3

classification 💻 cs.MA cs.DC
keywords population protocolsmajority votingbroadcastingdistributed algorithmstime complexitymessage complexitymulti-choice votingwireless networks
0
0 comments X

The pith

Two algorithms in a broadcasting population protocol model solve multi-choice majority voting with reduced time and message costs compared to pairwise protocols.

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

The paper introduces broadcasting population protocols, in which each agent can send one message to all its current neighbors simultaneously rather than interacting pairwise. It presents two distributed algorithms that allow n agents, each initially holding one of K choices, to converge on the majority choice through these local broadcasts. The authors prove correctness and derive improved bounds on time until consensus and total messages exchanged. Experiments demonstrate that the gains hold relative to earlier algorithms designed for conventional population protocols. The approach is positioned for settings such as wireless networks where simultaneous transmission to multiple recipients occurs naturally.

Core claim

In the broadcasting population protocol model, where each agent transmits a single message simultaneously to all its current neighbors, two new distributed algorithms correctly solve the multi-choice majority voting problem for n agents and K choices, achieving better time and message complexity than previous algorithms that rely on pairwise interactions in standard population protocols.

What carries the argument

The broadcasting population protocol model, which replaces pairwise interactions with simultaneous neighbor broadcasts to carry the voting process.

If this is right

  • Majority voting can be performed with lower communication overhead in networks supporting broadcasts.
  • The algorithms apply directly to wireless settings where simultaneous transmission to subsets of agents is possible.
  • Convergence time for distributed decision tasks decreases when broadcast replaces pairwise steps.
  • Existing population-protocol results for voting may require re-derivation under the broadcast assumption.

Where Pith is reading between the lines

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

  • The broadcast model could be tested on related tasks such as leader election or data aggregation to check for similar gains.
  • In mobile or dynamic networks the ability to reach multiple neighbors at once might reduce sensitivity to topology changes.
  • Scaling behavior for very large K relative to n could be examined experimentally beyond the reported cases.

Load-bearing premise

The communication model must allow each agent to transmit one message simultaneously to all its current neighbors.

What would settle it

A direct comparison simulation in which the new algorithms are restricted to pairwise messages only, showing either failure to reach the correct majority or no reduction in time and message counts.

Figures

Figures reproduced from arXiv: 1907.06855 by Hamidreza Bandealinaeini, Saber Salehkaleybar.

Figure 1
Figure 1. Figure 1: Time and message complexities of B-DMV algorithm and pairwise version (DMVR algorithm) in a mesh network with [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Results for analysis of the first phase. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Runtime and transmitted messages for different algorithms in a mesh network topology with [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Runtime of Accelerated B-DMV 2 algorithm until convergence [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
read the original abstract

We consider the problem of multi-choice majority voting in a network of $n$ agents where each agent initially selects a choice from a set of $K$ possible choices. The agents try to infer the choice in majority merely by performing local interactions. Population protocols provide a framework for designing pairwise interactions between agents in order to perform tasks in a coordinated manner. In this paper, we propose ``Broadcasting Population Protocol" model as a counterpart model of conventional population protocols for the networks that each agent can send a message to all its neighbors simultaneously. We design two distributed algorithms for solving the multi-choice majority voting problem in the model of broadcasting population protocols. We prove the correctness of these algorithms and analyze their performance in terms of time and message complexities. Experiments show that the proposed algorithm improves both time and message complexities significantly with respect to previous algorithms proposed in conventional population protocols and they can be utilized in networks where messages can be transmitted to a subset of agents simultaneously such as wireless networks.

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 introduces the Broadcasting Population Protocol model, in which each agent can transmit a single message simultaneously to all its current neighbors. It designs two distributed algorithms for the multi-choice majority voting problem in this model, proves their correctness, derives time and message complexity bounds, and presents simulation experiments claiming significant improvements over prior algorithms in conventional population protocols.

Significance. If the broadcasting model is accepted for the target setting, the work supplies a new protocol class together with correctness proofs and explicit complexity expressions that improve on the standard pairwise-interaction model. The experimental validation of the analytic bounds is a positive feature.

major comments (2)
  1. [Model Definition] Model section: the claimed complexity gains rest entirely on the broadcasting assumption; the paper must state whether the model permits concurrent broadcasts from multiple agents or assumes a collision-free medium, because this directly determines whether the stated time and message bounds remain valid in wireless networks.
  2. [Complexity Analysis] Complexity analysis: the time-complexity derivation for the second algorithm appears to count only successful broadcasts; an explicit accounting for the probability of message loss or retransmission under the broadcasting rule is needed to support the 'significant improvement' claim relative to the O(n log n) baseline of standard protocols.
minor comments (3)
  1. [Abstract] Abstract: the phrase 'improves both time and message complexities significantly' should be replaced by the concrete asymptotic bounds obtained.
  2. [Experiments] Experiments: simulation parameters (network size range, number of independent runs, exact topologies) are not listed in the figure captions or text, making it impossible to assess statistical reliability of the reported speed-ups.
  3. [Algorithm Description] Notation: the distinction between the two proposed algorithms is introduced only informally; a short table comparing their state spaces and broadcast rules would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive comments and the recommendation for minor revision. We address each major comment below.

read point-by-point responses

  1. Referee: [Model Definition] Model section: the claimed complexity gains rest entirely on the broadcasting assumption; the paper must state whether the model permits concurrent broadcasts from multiple agents or assumes a collision-free medium, because this directly determines whether the stated time and message bounds remain valid in wireless networks.

    Authors: We agree that the model assumptions should be stated more explicitly. The Broadcasting Population Protocol model extends the standard population protocol framework by allowing an agent to transmit a single message to all its current neighbors simultaneously. As in conventional population protocols, interactions are governed by a scheduler that selects one agent at a time to perform its action; thus, the model assumes a collision-free medium with no concurrent broadcasts. We will revise the model section to clarify this assumption and add a note that the complexity bounds are derived under this idealization, which may not directly hold in real wireless networks without additional collision-avoidance mechanisms. revision: yes

  2. Referee: [Complexity Analysis] Complexity analysis: the time-complexity derivation for the second algorithm appears to count only successful broadcasts; an explicit accounting for the probability of message loss or retransmission under the broadcasting rule is needed to support the 'significant improvement' claim relative to the O(n log n) baseline of standard protocols.

    Authors: The time- and message-complexity bounds are derived under the abstract model in which scheduled broadcasts succeed. The analysis does not incorporate probabilities of message loss or retransmissions because the model definition excludes collisions. We acknowledge that an explicit probabilistic accounting would strengthen claims about practical wireless settings, but deriving such bounds requires introducing a specific channel model (e.g., collision probability as a function of density), which lies outside the paper's scope. We will add a clarifying remark in the complexity section stating the assumptions and noting that the reported improvements hold in the idealized collision-free case. revision: partial

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper defines a new broadcasting population protocol model as an explicit counterpart to conventional population protocols, then designs two algorithms for multi-choice majority voting, provides correctness proofs, and derives time/message complexity bounds directly from the model assumptions and interaction rules. These bounds and the claimed improvements are obtained analytically from the broadcasting capability and are validated by simulation; no equation reduces a claimed result to a fitted parameter, self-citation, or renamed input by construction. The central claims rest on the independent model definition and algorithmic construction rather than on any self-referential step.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper rests on standard population-protocol assumptions plus the new broadcast communication primitive; no free parameters or invented physical entities are visible from the abstract.

axioms (1)
  • domain assumption Agents interact according to a population protocol model (pairwise or broadcast) on an underlying communication graph
    Invoked as the framework for designing the algorithms
invented entities (1)
  • Broadcasting Population Protocol model no independent evidence
    purpose: To capture simultaneous one-to-many message transmission to neighbors
    New model introduced to enable the algorithms

pith-pipeline@v0.9.0 · 5693 in / 1249 out tokens · 21843 ms · 2026-05-24T20:54:20.641159+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 1 internal anchor

  1. [1]

    N. A. Lynch, Distributed algorithms. Elsevier, 1996

    work page 1996

  2. [2]

    Distributed information process- ing in biological and computational systems,

    S. Navlakha and Z. Bar-Joseph, “Distributed information process- ing in biological and computational systems,” Communications of the ACM, vol. 58, no. 1, pp. 94–102, 2015

    work page 2015

  3. [3]

    Deterministic function computation with chemical reaction networks,

    H.-L. Chen, D. Doty, and D. Soloveichik, “Deterministic function computation with chemical reaction networks,” Natural computing, vol. 13, no. 4, pp. 517–534, 2014

    work page 2014

  4. [4]

    Polylogarithmic-time leader elec- tion in population protocols,

    D. Alistarh and R. Gelashvili, “Polylogarithmic-time leader elec- tion in population protocols,” in International Colloquium on Au- tomata, Languages, and Programming. Springer, 2015, pp. 479–491

    work page 2015

  5. [5]

    Stable leader election in population protocols requires linear time,

    D. Doty and D. Soloveichik, “Stable leader election in population protocols requires linear time,” Distributed Computing , vol. 31, no. 4, pp. 257–271, 2018

    work page 2018

  6. [6]

    Self-stabilizing population protocols,

    D. Angluin, J. Aspnes, M. J. Fischer, and H. Jiang, “Self-stabilizing population protocols,” in International Conference On Principles Of Distributed Systems. Springer, 2005, pp. 103–117

    work page 2005

  7. [7]

    Simple and efficient leader election,

    P . Berenbrink, D. Kaaser, P . Kling, and L. Otterbach, “Simple and efficient leader election,” in 1st Symposium on Simplicity in Algorithms (SOSA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018

    work page 2018

  8. [8]

    Time and Space Optimal Counting in Population Protocols

    J. Aspnes, J. Beauquier, J. Burman, and D. Sohier, “Time and space optimal counting in population protocols,” arXiv preprint arXiv:1611.07238, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  9. [9]

    Space-optimal counting in population protocols,

    J. Beauquier, J. Burman, S. Clavi `ere, and D. Sohier, “Space-optimal counting in population protocols,” in International Symposium on Distributed Computing. Springer, 2015, pp. 631–646

    work page 2015

  10. [10]

    Space-efficient self-stabilizing counting population protocols on mobile sensor networks,

    T. Izumi, K. Kinpara, T. Izumi, and K. Wada, “Space-efficient self-stabilizing counting population protocols on mobile sensor networks,” Theoretical Computer Science, vol. 552, pp. 99–108, 2014

    work page 2014

  11. [11]

    Self- stabilizing counting in mobile sensor networks,

    J. Beauquier, J. Clement, S. Messika, L. Rosaz, and B. Rozoy, “Self- stabilizing counting in mobile sensor networks,” in Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. ACM, 2007, pp. 396–397

    work page 2007

  12. [12]

    A simple population pro- tocol for fast robust approximate majority,

    D. Angluin, J. Aspnes, and D. Eisenstat, “A simple population pro- tocol for fast robust approximate majority,” Distributed Computing, vol. 21, no. 2, pp. 87–102, 2008

    work page 2008

  13. [13]

    The distributed multiple voting problem,

    F. B ´en´ezit, P . Thiran, and M. Vetterli, “The distributed multiple voting problem,” IEEE Journal of Selected Topics in Signal Processing, vol. 5, no. 4, pp. 791–804, 2011. 9

    work page 2011

  14. [14]

    Dis- tributed voting/ranking with optimal number of states per node,

    S. Salehkaleybar, A. Sharif-Nassab, and S. J. Golestani, “Dis- tributed voting/ranking with optimal number of states per node,” IEEE Transactions on Signal and Information Processing over Networks, vol. 1, no. 4, pp. 259–267, 2015

    work page 2015

  15. [15]

    Deterministic population protocols for exact major- ity and plurality,

    L. Gasieniec, D. Hamilton, R. Martin, P . G. Spirakis, and G. Sta- chowiak, “Deterministic population protocols for exact major- ity and plurality,” Leibniz International Proceedings in Informatics, LIPIcs, vol. 70, pp. 14–1, 2017

    work page 2017

  16. [16]

    Space-optimal majority in population protocols,

    D. Alistarh, J. Aspnes, and R. Gelashvili, “Space-optimal majority in population protocols,” in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM, 2018, pp. 2221–2239

    work page 2018

  17. [17]

    Fast and exact ma- jority in population protocols,

    D. Alistarh, R. Gelashvili, and M. Vojnovi ´c, “Fast and exact ma- jority in population protocols,” in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing . ACM, 2015, pp. 47–56

    work page 2015

  18. [18]

    Interval consensus: from quantized gossip to voting,

    F. B ´en´ezit, P . Thiran, and M. Vetterli, “Interval consensus: from quantized gossip to voting,” in 2009 IEEE International Conference on Acoustics, Speech and Signal Processing . IEEE, 2009, pp. 3661– 3664

    work page 2009

  19. [19]

    Time-space trade-offs in population protocols,

    D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, and R. L. Rivest, “Time-space trade-offs in population protocols,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2017, pp. 2560–2579

    work page 2017

  20. [20]

    Applied probability and queues, (2003),

    S. Asmussen, “Applied probability and queues, (2003),” 2003

    work page 2003

  21. [21]

    Epidemic processes in complex networks,

    R. Pastor-Satorras, C. Castellano, P . Van Mieghem, and A. Vespig- nani, “Epidemic processes in complex networks,” Reviews of mod- ern physics, vol. 87, no. 3, p. 925, 2015

    work page 2015