{"id":"arxiv/2605.19131","url":"https://arxiv.org/abs/2605.19131","tags":["math.CO","math.PR"],"score":0,"title":"Limit Laws for Consensus Protocols on the Complete Graph","domain":"math.CO","source":"arxiv","authors":["Julian Becker","Konstantinos Panagiotou"],"reviews":0,"subject":"math.CO","summary":"We study a distributed consensus problem on a complete communication network of $n$ vertices, each holding one of two opinions. The vertices communicate in rounds, possibly in the presence of adversarial noise, and exchange information until they all agree on a single opinion. We consider a general class of protocols, where the vertices randomly sample neighbors and update their own opinion according to an update function $f$ depending on the sampled opinions. A prominent example is the $k$-maj protocol, where every vertex adopts the majority opinion of $k$ randomly sampled neighbors,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-18","reactions":{}}