RECORD
Determining Majority in Networks with Local Interactions and very Small Local Memory
Distributed, Parallel, and Cluster Computing · Submitted 30 Apr 2014
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim As we prove, this protocol is optimal, in the sense that there is no population protocol that always computes majority with fewer than 4 states per vertex.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may have a few additional possible states and can interact in pairs only if they share an edge. Any (population) protocol is required to stabilize in the initial majority. We first present and analyze a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler. As we prove, this protocol is optimal, in the sense that there is no population protocol that always computes majority with fewer than 4 states per vertex. However this does not rule out the existence of a protocol with 3 states per vertex that is correct with high probability. To this end, we examine a very natural majority protocol with 3 states per vertex, introduced in [Angluin et al. 2008] where its performance has been analyzed for the clique graph. We study the performance of this protocol in arbitrary networks. We prove that, when the two initial states are put uniformly at random on the vertices, this protocol converges to the initial majority with probability higher than the probability of converging to the initial minority. In contrast, we present an infinite family of graphs, on which the protocol can fail whp, even when the difference between the initial majority and the initial minority is $n - \Theta(\ln{n})$. We also present another infinite family of graphs in which the protocol of Angluin et al. takes an expected exponential time to converge. These two negative results build upon a very positive result concerning the robustness of the protocol on the clique. Surprisingly, the resistance of the clique to failure causes the failure in general graphs. Our techniques use new domination and coupling arguments for suitably defined processes whose dynamics capture the antagonism between the states involved.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. | background 0.87 | 0.30 | 0.03 | asserted 0.78 |
| s1 | The vertices may have a few additional possible states and can interact in pairs only if they share an edge. | background 0.94 | 0.13 | 0.02 | hedged possibility 0.92 |
| s2 | Any (population) protocol is required to stabilize in the initial majority. | background 0.97 | 0.08 | 0.06 | asserted 0.98 |
| s3 | We first present and analyze a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler. | contribution 0.91 | 0.95 | 0.28 | asserted 1.00 |
| s4 | As we prove, this protocol is optimal, in the sense that there is no population protocol that always computes majority with fewer than 4 states per vertex. | result 0.91 | 0.86 | 0.35 | asserted 1.00 |
| s5 | However this does not rule out the existence of a protocol with 3 states per vertex that is correct with high probability. | gap 0.85 | 0.26 | 0.07 | hedged possibility 0.90 |
| s6 | To this end, we examine a very natural majority protocol with 3 states per vertex, introduced in [Angluin et al. 2008] where its performance has been analyzed for the clique graph. | background 0.48 | 0.11 | 0.04 | asserted 0.94 |
| s7 | We study the performance of this protocol in arbitrary networks. | contribution 0.98 | 0.81 | 0.03 | asserted 0.57 |
| s8 | We prove that, when the two initial states are put uniformly at random on the vertices, this protocol converges to the initial majority with probability higher than the probability of converging to the initial minority. | result 1.00 | 0.90 | 0.13 | asserted 1.00 |
| s9 | In contrast, we present an infinite family of graphs, on which the protocol can fail whp, even when the difference between the initial majority and the initial minority is $n - \Theta(\ln{n})$. | result 0.97 | 0.94 | 0.18 | asserted 0.99 |
| s10 | We also present another infinite family of graphs in which the protocol of Angluin et al. takes an expected exponential time to converge. | result 0.97 | 0.93 | 0.07 | asserted 1.00 |
| s11 | These two negative results build upon a very positive result concerning the robustness of the protocol on the clique. | interpretation 0.79 | 0.64 | 0.08 | asserted 0.99 |
| s12 | Surprisingly, the resistance of the clique to failure causes the failure in general graphs. | interpretation 0.93 | 0.78 | 0.15 | asserted 1.00 |
| s13 | Our techniques use new domination and coupling arguments for suitably defined processes whose dynamics capture the antagonism between the states involved. | method 0.99 | 0.87 | 0.04 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may have a few additional possible states and can interact in pairs only if they share an edge. Any (population) protocol is required to stabilize in the initial majority. We first present and analyze a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler. As we prove, this protocol is optimal, in the sense that there is no population protocol that always computes majority with fewer than 4 states per vertex. However this does not rule out the existence of a protocol with 3 states per vertex that is correct with high probability. To this end, we examine a very natural majority protocol with 3 states per vertex, introduced in [Angluin et al. 2008] where its performance has been analyzed for the clique graph. We study the performance of this protocol in arbitrary networks. We prove that, when the two initial states are put uniformly at random on the vertices, this protocol converges to the initial majority with probability higher than the probability of converging to the initial minority. In contrast, we present an infinite family of graphs, on which the protocol can fail whp, even when the difference between the initial majority and the initial minority is $n - \Theta(\ln{n})$. We also present another infinite family of graphs in which the protocol of Angluin et al. takes an expected exponential time to converge. These two negative results build upon a very positive result concerning the robustness of the protocol on the clique. Surprisingly, the resistance of the clique to failure causes the failure in general graphs. Our techniques use new domination and coupling arguments for suitably defined processes whose dynamics capture the antagonism between the states involved.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.