Consensus times for monotone aggregation dynamics
Abstract
We study an asynchronous consensus dynamics on N agents: at each step a uniformly chosen agent replaces its state by f(Y1,…,Yr), where f is a fixed monotone aggregation rule and Y1,…,Yr are the states of r agents sampled uniformly with replacement. Let T be the first time at which all agents agree. Let f:{0,1}r→{0,1} be monotone and non-constant. The expected consensus time is governed by the two \emph{endpoint degrees} D0(f)=#{i:f(ei)=1} and D1(f)=#{i:f(1−ei)=0}, where ei is the ith standard basis vector and 1 the all-ones vector. If D0(f)≠ 1 and D1(f)≠ 1, then E[T]=Θ(N(1+log df)), where df counts the agents that must change state before the nearest attracting consensus is reached, so that E[T]=O(Nlog N) uniformly over initial states. If f is a dictator, E[T] is given by a voter-model formula and equals Θ(N2 Ent(p0)) with absolute constants, uniformly over the initial state, where Ent is the binary entropy and p0 the initial fraction of agents in state $1$. Otherwise exactly one of D0(f),D1(f) equals $1$ and the other equals $0$. The worst-case expected consensus time is then Θ(N2−1/m), where m≥ 2 is the least number of coordinates that force the value $1$ in the {\em residual rule} of f, defined in the paper (of its dual, when D1(f)=1).
Related
- Measuring Learned Monotone Temporal Aggregation at Matched Admissibility
- Monotone Mixing and Distribution Dynamics
- On Fixed-Time Stability of Continuous Dynamics for Non-Monotone Variational Inequalities
- Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus
- Input-to-Output Stability and Consensus Control of Opinion Dynamics on Graph State-Space
BibTeX
@misc{mossel2026consensus,
title = {{Consensus times for monotone aggregation dynamics}},
author = {Elchanan Mossel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04468},
eprint = {2609.04468},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04468},
}
RIS
TY - UNPB
TI - Consensus times for monotone aggregation dynamics
AU - Elchanan Mossel
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.04468
UR - https://arxiv.org/abs/2609.04468
AB - We study an asynchronous consensus dynamics on N agents: at each step a uniformly chosen agent replaces its state by f(Y_1,…,Y_r), where f is a fixed monotone aggregation rule and Y_1,…,Y_r are the states of r agents sampled uniformly with replacement. Let T be the first time at which all agents agree. Let f:{0,1}^r→{0,1} be monotone and non-constant. The expected consensus time is governed by the two \emph{endpoint degrees} D_0(f)=#{i:f(e_i)=1} and D_1(f)=#{i:f(1−e_i)=0}, where e_i is the ith standard basis vector and 1 the all-ones vector. If D_0(f)≠ 1 and D_1(f)≠ 1, then E[T]=Θ(N(1+log d_f)), where d_f counts the agents that must change state before the nearest attracting consensus is reached, so that E[T]=O(Nlog N) uniformly over initial states. If f is a dictator, E[T] is given by a voter-model formula and equals Θ(N^2 Ent(p_0)) with absolute constants, uniformly over the initial state, where Ent is the binary entropy and p_0 the initial fraction of agents in state $1$. Otherwise exactly one of D_0(f),D_1(f) equals $1$ and the other equals $0$. The worst-case expected consensus time is then Θ(N^2−1/m), where m≥ 2 is the least number of coordinates that force the value $1$ in the {\em residual rule} of f, defined in the paper (of its dual, when D_1(f)=1).
ER -