Limit Laws for Consensus Protocols on the Complete Graph
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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.19131
curl -X POST /api/v1/records/arxiv/2605.19131/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.19131/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'