Abstract

The 2-Choices rule is a well-studied distributed consensus protocol in which nodes, each holding a binary opinion, rapidly converge to the opinion initially supported by the majority. Under the classic version of this rule, nodes update their opinions at the ticks of independent Poisson clocks by sampling two neighbours uniformly at random and adopting the majority opinion among themselves and the sampled neighbours. In this talk, I shall explore a slightly modified version of the 2-Choices dynamics in the presence of node failures. Specifically, each node independently fails to follow the update rule with constant probability $\alpha$; upon failure, it instead selects one of the two opinions uniformly at random. This constitutes a strong failure model, generating $\mathrm{\Theta }(n)$ failures per unit time on average. Surprisingly, we show that the system remains robust: for failure probabilities below a critical threshold, the dynamics resemble the classical (failure-free) 2-Choices process. However, once the failure probability exceeds this threshold, the system loses robustness and rapidly mixes to a stationary distribution. Our results apply to both complete graphs and to expander graphs with sufficiently large spectral gaps and sufficiently homogeneous degree distributions. This talk is based on work that has appeared at SIGMETRICS 2026 and is joint with Luke Meredith (Warwick).

Bio

Prof. Arpan Mukhopadhyay, Associate Professor, University of Warwick

Arpan Mukhopadhyay is currently an Associate Professor with the Department of Computer Science, University of Warwick, U.K. His research interests include applied probability, stochastic processes, algorithm design, and optimization with applications to computer, communication, and distributed systems. He has received several Best Paper Awards, including those at the IFIP Performance 2015 and ACM Mobihoc 2024, and he received the 2018 Rising Scholar Award at the International Teletraffic Congress for his contributions to mean field analysis of large heterogeneous networks.