Stabilization Time in Minority Processes

P\'al Andr\'as Papp; Roger Wattenhofer

arxiv: 1907.02131 · v1 · pith:FYTA67VAnew · submitted 2019-07-03 · 💻 cs.DM

Stabilization Time in Minority Processes

P\'al Andr\'as Papp , Roger Wattenhofer This is my paper

Pith reviewed 2026-05-25 09:10 UTC · model grok-4.3

classification 💻 cs.DM

keywords minority processesstabilization timelower boundsgraph dynamicscoloring processesdistributed algorithmsconcurrent schedulingsequential scheduling

0 comments

The pith

Some graphs force minority processes to take Ω(n^{2-ε}) steps to stabilize for any ε>0.

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

A minority process is a repeated recoloring where every node switches to whichever color appears least often among its neighbors. The authors first show a simple Ω(n²) lower bound when updates occur one at a time in the worst order. Their main result is an explicit family of graphs on which stabilization still requires nearly quadratic time even when the update order is chosen to finish as quickly as possible. The same nearly-quadratic bound continues to hold when multiple nodes may update at once under standard concurrent scheduling rules.

Core claim

The paper constructs graphs on which any minority process requires Ω(n^{2-ε}) updates to reach a stable state, for every positive ε. The construction works even when the sequence of updates is chosen to minimize the number of steps, and the same bound holds in concurrent models where multiple nodes may update simultaneously.

What carries the argument

An explicit family of graphs engineered so that color changes create long dependency chains under the minority rule, forcing many successive flips before stability.

If this is right

Stabilization time remains superlinear even under optimal ordering of updates.
The nearly quadratic lower bound applies to any reasonable concurrent scheduling model.
A simpler quadratic lower bound holds when the scheduler is fully adversarial.
Minority dynamics on these graphs cannot terminate quickly no matter how updates are arranged.

Where Pith is reading between the lines

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

The same construction technique may yield lower bounds for other local recoloring rules such as majority processes.
In very large networks the process may require many rounds before any stable partition emerges.
Additional mechanisms such as random tie-breaking or global coordination might be needed to achieve faster termination.

Load-bearing premise

Every node must always flip to the color that is strictly least frequent in its current neighborhood, and updates follow either sequential or concurrent scheduling without additional global constraints.

What would settle it

Explicit simulation or proof showing that the constructed graphs reach a stable coloring in o(n^{2-ε}) total updates for some ε>0, under either benevolent sequential or concurrent scheduling.

Figures

Figures reproduced from arXiv: 1907.02131 by P\'al Andr\'as Papp, Roger Wattenhofer.

**Figure 1.** Figure 1: Properties of the listed models However, our lower bounds extend to a range of other popular models: E. Concurrent synchronous: In every step, all switchable nodes switch simultaneously. F. Sequential random: In every step, only one node switches, chosen uniformly at random among the switchable nodes. G. Concurrent random: In every step, every switchable node switches with probability p, independently from… view at source ↗

**Figure 2.** Figure 2: Construction with an adversarial sequence of Θ( [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: Simple relay gadget (a), the steps of its operation [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 4.** Figure 4: Rechargeable relay gadget (a) and the steps of its o [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗

**Figure 5.** Figure 5: Basic (a) and generalized (b) recharging system [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗

**Figure 6.** Figure 6: and gate ... v1 v2 vp A1 (2) B1 (2) A2 (2) B2 (2) Ap (2) Bp (2) C v 2 2 2 2 [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗

**Figure 7.** Figure 7: Operation of an and gate. In the end, node D switches to black, making v switchable. gate switches, the balance of all input nodes in X will increase by 2. It would be much better to have a gadget that can perform this task without having any effect on the nodes in X. For this purpose, consider the gadget in [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗

**Figure 10.** Figure 10: Overview of the construction, with one branch sho [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗

**Figure 11.** Figure 11: Connection of a second-level recharging system t [PITH_FULL_IMAGE:figures/full_fig_p016_11.png] view at source ↗

read the original abstract

We analyze the stabilization time of minority processes in graphs. A minority process is a dynamically changing coloring, where each node repeatedly changes its color to the color which is least frequent in its neighborhood. First, we present a simple $\Omega(n^2)$ stabilization time lower bound in the sequential adversarial model. Our main contribution is a graph construction which proves a ${\Omega}(n^{2-\epsilon})$ stabilization time lower bound for any $\epsilon>0$. This lower bound holds even if the order of nodes is chosen benevolently, not only in the sequential model, but also in any reasonable concurrent model of the process.

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.

Desk Editor's Note private letter to a colleague

The paper gives a graph construction showing minority processes need nearly quadratic time even under benevolent scheduling in both sequential and concurrent models.

read the letter

The punchline is that they improve a basic quadratic lower bound to Ω(n^{2-ε}) for any ε>0 via an explicit graph family. This holds when the scheduler tries to speed things up and extends to concurrent updates. That is the actual new piece; the simple Ω(n²) bound is just setup. The construction itself is the contribution, and it targets a natural local rule where nodes flip to the minority color in their neighborhood. If the details of the graphs and the scheduling argument check out, this is useful evidence that quadratic time is close to necessary in the worst case for this process. The abstract is clear on the claim and the models, and the result is a direct existence argument rather than something circular or fitted. One soft spot is that the construction has to be delicate to block all fast stabilization paths under benevolent orderings, so the proof needs to be checked carefully for gaps in how concurrent steps are handled. Nothing in the stated claim looks internally inconsistent from the abstract. This is for researchers working on stabilization times and local dynamics on graphs. A reader already interested in distributed algorithms or graph processes will get value from the bound and the construction technique. It deserves a serious referee because the lower bound is non-routine and the model extensions are relevant, even if the paper needs revision on presentation or edge cases.

Referee Report

2 major / 1 minor

Summary. The paper analyzes stabilization time of minority processes on graphs, where each node repeatedly adopts the color that is strictly least frequent among its neighbors. It first gives a simple Ω(n²) lower bound under sequential adversarial scheduling, then presents a graph construction establishing an Ω(n^{2-ε}) lower bound for every ε>0. The latter bound is claimed to hold even when node activation order is chosen benevolently (i.e., to accelerate stabilization) and to extend from the sequential model to any reasonable concurrent model.

Significance. If the explicit graph construction is correct, the result is significant: it supplies a nearly-quadratic lower bound that survives benevolent scheduling and applies to concurrent models, thereby giving a strong worst-case characterization of minority dynamics in standard distributed-computing settings. The paper’s approach of exhibiting an explicit construction rather than a parameter-fitting argument is a methodological strength.

major comments (2)

[Main construction (presumably §3 or §4)] The central claim rests on an explicit graph construction whose details are not visible in the abstract; without the concrete vertex set, edge set, and activation schedule used to force Ω(n^{2-ε}) steps, the lower-bound argument cannot be verified. (This is load-bearing for the main contribution.)
[Model definitions (abstract and §2)] The phrase “any reasonable concurrent model” is used to extend the lower bound beyond the sequential case, yet no formal definition or list of admissible schedulers is supplied; it is therefore unclear whether the construction actually rules out all standard concurrent models (e.g., those with bounded asynchrony or fair activation).

minor comments (1)

[Abstract] The abstract states both the Ω(n²) and the Ω(n^{2-ε}) bounds but does not indicate whether the former is subsumed by the latter or serves a separate pedagogical purpose.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. The two major comments identify areas where additional clarity will strengthen the manuscript. We address each point below and will incorporate revisions to improve verifiability of the construction and precision of the model definitions.

read point-by-point responses

Referee: [Main construction (presumably §3 or §4)] The central claim rests on an explicit graph construction whose details are not visible in the abstract; without the concrete vertex set, edge set, and activation schedule used to force Ω(n^{2-ε}) steps, the lower-bound argument cannot be verified. (This is load-bearing for the main contribution.)

Authors: The full construction, including explicit vertex set, edge set, and the benevolent activation schedule, is presented in Section 3 of the manuscript. To address the concern about accessibility, we will add a high-level overview of the graph family and a schematic figure at the start of Section 3 in the revised version. These additions will make the Ω(n^{2-ε}) argument easier to verify while preserving the existing technical details. revision: yes
Referee: [Model definitions (abstract and §2)] The phrase “any reasonable concurrent model” is used to extend the lower bound beyond the sequential case, yet no formal definition or list of admissible schedulers is supplied; it is therefore unclear whether the construction actually rules out all standard concurrent models (e.g., those with bounded asynchrony or fair activation).

Authors: We agree that the informal phrasing leaves the scope of the concurrent-model claim imprecise. In the revision we will insert a formal definition in Section 2 that specifies the class of schedulers (fair activation, bounded asynchrony, and standard concurrent models from the distributed-computing literature) for which the lower bound holds. This will make the extension from the sequential case explicit and verifiable. revision: yes

Circularity Check

0 steps flagged

No significant circularity; explicit construction provides independent lower bound

full rationale

The paper's central claim is an explicit graph construction proving an Ω(n^{2-ε}) stabilization-time lower bound that holds under benevolent scheduling in both sequential and concurrent models. This is a direct existence proof against the externally defined minority process and scheduling models; no equations reduce to their own inputs by construction, no parameters are fitted and relabeled as predictions, and no load-bearing self-citations or imported uniqueness theorems are invoked. The derivation chain is therefore self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions of graphs, neighborhoods, and update rules with no fitted parameters or new entities introduced.

axioms (1)

standard math Standard definitions of undirected graphs and the minority update rule in distributed computing models.
Invoked in the abstract description of the process and models.

pith-pipeline@v0.9.0 · 5621 in / 1130 out tokens · 54647 ms · 2026-05-25T09:10:10.868882+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

Unfriendly partitions of a graph

Ron Aharoni, Eric C Milner, and Karel Prikry. Unfriendly partitions of a graph. Journal of Combinatorial Theory, Series B , 50(1):1–10, 1990

work page 1990
[2]

O n the existence and determina- tion of satisfactory partitions in a graph

Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. O n the existence and determina- tion of satisfactory partitions in a graph. In International Symposium on Algorithms and Computation, pages 444–453. Springer, 2003

work page 2003
[3]

C omplexity and approximation of satisfactory partition problems

Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. C omplexity and approximation of satisfactory partition problems. In International Computing and Combinatorics Conference , pages 829–838. Springer, 2005

work page 2005
[4]

T he satisfactory partition problem

Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. T he satisfactory partition problem. Discrete applied mathematics , 154(8):1236–1245, 2006

work page 2006
[5]

S atisfactory graph partition, vari- ants, and generalizations

Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. S atisfactory graph partition, vari- ants, and generalizations. European Journal of Operational Research, 206(2):271–280, 2010

work page 2010
[6]

C rystallization by stochastic ﬂips

Olivier Bodini, Thomas Fernique, and Damien Regnault. C rystallization by stochastic ﬂips. In Journal of Physics: Conference Series , volume 226, page 012022. IOP Publishing, 2010

work page 2010
[7]

S tochastic ﬂips on two-letter words

Olivier Bodini, Thomas Fernique, and Damien Regnault. S tochastic ﬂips on two-letter words. In 2010 Proceedings of the Seventh Workshop on Analytic Algori thmics and Com- binatorics (ANALCO) , pages 48–55. SIAM, 2010

work page 2010
[8]

Every rayless graph has an unfriendly partition

Henning Bruhn, Reinhard Diestel, Agelos Georgakopoulo s, and Philipp Spr¨ ussel. Every rayless graph has an unfriendly partition. Combinatorica, 30(5):521–532, 2010

work page 2010
[9]

The fashion game: Networ k extension of matching pennies

Zhigang Cao and Xiaoguang Yang. The fashion game: Networ k extension of matching pennies. Theoretical Computer Science , 540:169–181, 2014

work page 2014
[10]

Genetic regulation networks: circuits, regulons an d attractors

Jacques Demongeot, Julio Aracena, Florence Thuderoz, Thierry-Pascal Baum, and Olivier Cohen. Genetic regulation networks: circuits, regulons an d attractors. Comptes Rendus Biologies, 326(2):171–188, 2003

work page 2003
[11]

On non-progressive spread of inﬂuence t hrough social networks

MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Po oya Jalaly, Vahab Mirrokni, and Sina Sadeghian. On non-progressive spread of inﬂuence t hrough social networks. The- oretical Computer Science , 550:36 – 50, 2014

work page 2014
[12]

A uniﬁed framework f or strong price of anarchy in clustering games

Michal Feldman and Ophir Friedler. A uniﬁed framework f or strong price of anarchy in clustering games. In International Colloquium on Automata, Languages, and Progra mming, pages 601–613. Springer, 2015

work page 2015
[13]

Convergence in (social) in- ﬂuence networks

Silvio Frischknecht, Barbara Keller, and Roger Watten hofer. Convergence in (social) in- ﬂuence networks. In International Symposium on Distributed Computing , pages 433–446. Springer, 2013

work page 2013
[14]

Color war: Cellular automata with majority-rule

Bernd G¨ artner and Ahad N Zehmakan. Color war: Cellular automata with majority-rule. In International Conference on Language and Automata Theory and A pplications, pages 393–404. Springer, 2017

work page 2017
[15]

Majority model on ra ndom regular graphs

Bernd G¨ artner and Ahad N Zehmakan. Majority model on ra ndom regular graphs. In Latin American Symposium on Theoretical Informatics , pages 572–583. Springer, 2018

work page 2018
[16]

Algorithmic approa ch to the satisfactory graph partitioning problem

Michael U Gerber and Daniel Kobler. Algorithmic approa ch to the satisfactory graph partitioning problem. European Journal of Operational Research , 125(2):283–291, 2000. 12

work page 2000
[17]

Classes of graphs th at can be partitioned to satisfy all their vertices

Michael U Gerber and Daniel Kobler. Classes of graphs th at can be partitioned to satisfy all their vertices. Australasian Journal of Combinatorics , 29:201–214, 2004

work page 2004
[18]

Periodic behaviour of gene ralized threshold functions

Eric Goles and Jorge Olivos. Periodic behaviour of gene ralized threshold functions. Discrete Mathematics, 30(2):187–189, 1980

work page 1980
[19]

Self- stabilizing algorithms for unfriendly partitions into two disjoint dominating sets

Sandra M Hedetniemi, Stephen T Hedetniemi, KE Kennedy, and Alice A Mcrae. Self- stabilizing algorithms for unfriendly partitions into two disjoint dominating sets. Parallel Processing Letters, 23(01):1350001, 2013

work page 2013
[20]

On the voting time of the deterministic majority process

Dominik Kaaser, Frederik Mallmann-Trenn, and Emanuel e Natale. On the voting time of the deterministic majority process. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) , 2016

work page 2016
[21]

Ho w even tiny inﬂuence can have a big impact! In International Conference on Fun with Algorithms , pages 252–263

Barbara Keller, David Peleg, and Roger Wattenhofer. Ho w even tiny inﬂuence can have a big impact! In International Conference on Fun with Algorithms , pages 252–263. Springer, 2014

work page 2014
[22]

Anti-coordin ation games and stable graph col- orings

Jeremy Kun, Brian Powers, and Lev Reyzin. Anti-coordin ation games and stable graph col- orings. In International Symposium on Algorithmic Game Theory , pages 122–133. Springer, 2013

work page 2013
[23]

Local information in inﬂuence networks

Yuezhou Lv and Thomas Moscibroda. Local information in inﬂuence networks. In Inter- national Symposium on Distributed Computing , pages 292–308. Springer, 2015

work page 2015
[24]

Opinion forming in erd¨ os-r´ enyi rand om graph and expanders

Ahad N Zehmakan. Opinion forming in erd¨ os-r´ enyi rand om graph and expanders. In 29th International Symposium on Algorithms and Computation ( ISAAC 2018) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018

work page 2018
[25]

Stabilization time in weighted minority processes

P´ al Andr´ as Papp and Roger Wattenhofer. Stabilization time in weighted minority processes. In 36th International Symposium on Theoretical Aspects of Comput er Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019

work page 2019
[26]

Progresses in the analysis of stochastic 2d cellular automata: A study of asynchronous 2d minority

Damien Regnault, Nicolas Schabanel, and ´Eric Thierry. Progresses in the analysis of stochastic 2d cellular automata: A study of asynchronous 2d minority. In Ludˇ ek Kuˇ cera and Anton ´ ın Kuˇ cera, editors,Mathematical Foundations of Computer Science 2007 , pages 320–332. Springer Berlin Heidelberg, 2007

work page 2007
[27]

On the analysis of “simple” 2d stochastic cellular automata

Damien Regnault, Nicolas Schabanel, and ´Eric Thierry. On the analysis of “simple” 2d stochastic cellular automata. In International Conference on Language and Automata The- ory and Applications , pages 452–463. Springer, 2008

work page 2008
[28]

Stochastic minority on graphs

Jean-Baptiste Rouquier, Damien Regnault, and ´Eric Thierry. Stochastic minority on graphs. Theoretical Computer Science , 412(30):3947–3963, 2011

work page 2011
[29]

On satisfactory p artitioning of graphs

Khurram H Shaﬁque and Ronald D Dutton. On satisfactory p artitioning of graphs. Con- gressus Numerantium, pages 183–194, 2002

work page 2002
[30]

Graphs with no unfrien dly partitions

Saharon Shelah and Eric C Milner. Graphs with no unfrien dly partitions. A tribute to Paul Erd¨ os, pages 373–384, 1990

work page 1990
[31]

Stabili ty of certainty and opinion in inﬂuence networks

Ariel Webster, Bruce Kapron, and Valerie King. Stabili ty of certainty and opinion in inﬂuence networks. In Advances in Social Networks Analysis and Mining (ASONAM), 2016 IEEE/ACM International Conference on , pages 1309–1320. IEEE, 2016

work page 2016
[32]

Puzzled: Delightful graph theory

Peter Winkler. Puzzled: Delightful graph theory. Commun. ACM , 51(8):104–104, August 2008. 13 Appendices A Discussion of the recursive construction While the main idea of the recursive construction has been ou tlined above, there are numerous details worth discussing for completeness. Given a used recharging system, we need to restore the balanc e of M an...

work page 2008

[1] [1]

Unfriendly partitions of a graph

Ron Aharoni, Eric C Milner, and Karel Prikry. Unfriendly partitions of a graph. Journal of Combinatorial Theory, Series B , 50(1):1–10, 1990

work page 1990

[2] [2]

O n the existence and determina- tion of satisfactory partitions in a graph

Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. O n the existence and determina- tion of satisfactory partitions in a graph. In International Symposium on Algorithms and Computation, pages 444–453. Springer, 2003

work page 2003

[3] [3]

C omplexity and approximation of satisfactory partition problems

Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. C omplexity and approximation of satisfactory partition problems. In International Computing and Combinatorics Conference , pages 829–838. Springer, 2005

work page 2005

[4] [4]

T he satisfactory partition problem

Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. T he satisfactory partition problem. Discrete applied mathematics , 154(8):1236–1245, 2006

work page 2006

[5] [5]

S atisfactory graph partition, vari- ants, and generalizations

Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. S atisfactory graph partition, vari- ants, and generalizations. European Journal of Operational Research, 206(2):271–280, 2010

work page 2010

[6] [6]

C rystallization by stochastic ﬂips

Olivier Bodini, Thomas Fernique, and Damien Regnault. C rystallization by stochastic ﬂips. In Journal of Physics: Conference Series , volume 226, page 012022. IOP Publishing, 2010

work page 2010

[7] [7]

S tochastic ﬂips on two-letter words

Olivier Bodini, Thomas Fernique, and Damien Regnault. S tochastic ﬂips on two-letter words. In 2010 Proceedings of the Seventh Workshop on Analytic Algori thmics and Com- binatorics (ANALCO) , pages 48–55. SIAM, 2010

work page 2010

[8] [8]

Every rayless graph has an unfriendly partition

Henning Bruhn, Reinhard Diestel, Agelos Georgakopoulo s, and Philipp Spr¨ ussel. Every rayless graph has an unfriendly partition. Combinatorica, 30(5):521–532, 2010

work page 2010

[9] [9]

The fashion game: Networ k extension of matching pennies

Zhigang Cao and Xiaoguang Yang. The fashion game: Networ k extension of matching pennies. Theoretical Computer Science , 540:169–181, 2014

work page 2014

[10] [10]

Genetic regulation networks: circuits, regulons an d attractors

Jacques Demongeot, Julio Aracena, Florence Thuderoz, Thierry-Pascal Baum, and Olivier Cohen. Genetic regulation networks: circuits, regulons an d attractors. Comptes Rendus Biologies, 326(2):171–188, 2003

work page 2003

[11] [11]

On non-progressive spread of inﬂuence t hrough social networks

MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Po oya Jalaly, Vahab Mirrokni, and Sina Sadeghian. On non-progressive spread of inﬂuence t hrough social networks. The- oretical Computer Science , 550:36 – 50, 2014

work page 2014

[12] [12]

A uniﬁed framework f or strong price of anarchy in clustering games

Michal Feldman and Ophir Friedler. A uniﬁed framework f or strong price of anarchy in clustering games. In International Colloquium on Automata, Languages, and Progra mming, pages 601–613. Springer, 2015

work page 2015

[13] [13]

Convergence in (social) in- ﬂuence networks

Silvio Frischknecht, Barbara Keller, and Roger Watten hofer. Convergence in (social) in- ﬂuence networks. In International Symposium on Distributed Computing , pages 433–446. Springer, 2013

work page 2013

[14] [14]

Color war: Cellular automata with majority-rule

Bernd G¨ artner and Ahad N Zehmakan. Color war: Cellular automata with majority-rule. In International Conference on Language and Automata Theory and A pplications, pages 393–404. Springer, 2017

work page 2017

[15] [15]

Majority model on ra ndom regular graphs

Bernd G¨ artner and Ahad N Zehmakan. Majority model on ra ndom regular graphs. In Latin American Symposium on Theoretical Informatics , pages 572–583. Springer, 2018

work page 2018

[16] [16]

Algorithmic approa ch to the satisfactory graph partitioning problem

Michael U Gerber and Daniel Kobler. Algorithmic approa ch to the satisfactory graph partitioning problem. European Journal of Operational Research , 125(2):283–291, 2000. 12

work page 2000

[17] [17]

Classes of graphs th at can be partitioned to satisfy all their vertices

Michael U Gerber and Daniel Kobler. Classes of graphs th at can be partitioned to satisfy all their vertices. Australasian Journal of Combinatorics , 29:201–214, 2004

work page 2004

[18] [18]

Periodic behaviour of gene ralized threshold functions

Eric Goles and Jorge Olivos. Periodic behaviour of gene ralized threshold functions. Discrete Mathematics, 30(2):187–189, 1980

work page 1980

[19] [19]

Self- stabilizing algorithms for unfriendly partitions into two disjoint dominating sets

Sandra M Hedetniemi, Stephen T Hedetniemi, KE Kennedy, and Alice A Mcrae. Self- stabilizing algorithms for unfriendly partitions into two disjoint dominating sets. Parallel Processing Letters, 23(01):1350001, 2013

work page 2013

[20] [20]

On the voting time of the deterministic majority process

Dominik Kaaser, Frederik Mallmann-Trenn, and Emanuel e Natale. On the voting time of the deterministic majority process. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) , 2016

work page 2016

[21] [21]

Ho w even tiny inﬂuence can have a big impact! In International Conference on Fun with Algorithms , pages 252–263

Barbara Keller, David Peleg, and Roger Wattenhofer. Ho w even tiny inﬂuence can have a big impact! In International Conference on Fun with Algorithms , pages 252–263. Springer, 2014

work page 2014

[22] [22]

Anti-coordin ation games and stable graph col- orings

Jeremy Kun, Brian Powers, and Lev Reyzin. Anti-coordin ation games and stable graph col- orings. In International Symposium on Algorithmic Game Theory , pages 122–133. Springer, 2013

work page 2013

[23] [23]

Local information in inﬂuence networks

Yuezhou Lv and Thomas Moscibroda. Local information in inﬂuence networks. In Inter- national Symposium on Distributed Computing , pages 292–308. Springer, 2015

work page 2015

[24] [24]

Opinion forming in erd¨ os-r´ enyi rand om graph and expanders

Ahad N Zehmakan. Opinion forming in erd¨ os-r´ enyi rand om graph and expanders. In 29th International Symposium on Algorithms and Computation ( ISAAC 2018) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018

work page 2018

[25] [25]

Stabilization time in weighted minority processes

P´ al Andr´ as Papp and Roger Wattenhofer. Stabilization time in weighted minority processes. In 36th International Symposium on Theoretical Aspects of Comput er Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019

work page 2019

[26] [26]

Progresses in the analysis of stochastic 2d cellular automata: A study of asynchronous 2d minority

Damien Regnault, Nicolas Schabanel, and ´Eric Thierry. Progresses in the analysis of stochastic 2d cellular automata: A study of asynchronous 2d minority. In Ludˇ ek Kuˇ cera and Anton ´ ın Kuˇ cera, editors,Mathematical Foundations of Computer Science 2007 , pages 320–332. Springer Berlin Heidelberg, 2007

work page 2007

[27] [27]

On the analysis of “simple” 2d stochastic cellular automata

Damien Regnault, Nicolas Schabanel, and ´Eric Thierry. On the analysis of “simple” 2d stochastic cellular automata. In International Conference on Language and Automata The- ory and Applications , pages 452–463. Springer, 2008

work page 2008

[28] [28]

Stochastic minority on graphs

Jean-Baptiste Rouquier, Damien Regnault, and ´Eric Thierry. Stochastic minority on graphs. Theoretical Computer Science , 412(30):3947–3963, 2011

work page 2011

[29] [29]

On satisfactory p artitioning of graphs

Khurram H Shaﬁque and Ronald D Dutton. On satisfactory p artitioning of graphs. Con- gressus Numerantium, pages 183–194, 2002

work page 2002

[30] [30]

Graphs with no unfrien dly partitions

Saharon Shelah and Eric C Milner. Graphs with no unfrien dly partitions. A tribute to Paul Erd¨ os, pages 373–384, 1990

work page 1990

[31] [31]

Stabili ty of certainty and opinion in inﬂuence networks

Ariel Webster, Bruce Kapron, and Valerie King. Stabili ty of certainty and opinion in inﬂuence networks. In Advances in Social Networks Analysis and Mining (ASONAM), 2016 IEEE/ACM International Conference on , pages 1309–1320. IEEE, 2016

work page 2016

[32] [32]

Puzzled: Delightful graph theory

Peter Winkler. Puzzled: Delightful graph theory. Commun. ACM , 51(8):104–104, August 2008. 13 Appendices A Discussion of the recursive construction While the main idea of the recursive construction has been ou tlined above, there are numerous details worth discussing for completeness. Given a used recharging system, we need to restore the balanc e of M an...

work page 2008