Consensus with Bounded Space and Minimal Communication

MaRDI QIDQ6357344zbMATH OpenFDO

Authors Simina Brânzei, Yuval Peres

Publication date 31 December 2020

Abstract: Population protocols are a fundamental model in distributed computing, where many nodes with bounded memory and computational power have random pairwise interactions over time. This model has been studied in a rich body of literature aiming to understand the tradeoffs between the memory and time needed to perform computational tasks. We study the population protocol model focusing on the communication complexity needed to achieve consensus with high probability. When the number of memory states is $s=O(loglogn)$, the best upper bound known was given by a protocol with $O(nlogn)$ communication, while the best lower bound was $Omega(nlog(n)/s)$ communication. We design a protocol that shows the lower bound is sharp. When each agent has $s=O(log{n}^{heta})$ states of memory, with $hetain(0,1/2)$, consensus can be reached in time $O(log(n))$ with $O(nlog(n)/s)$ communications with high probability.

This page was built for publication: Consensus with Bounded Space and Minimal Communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6357344)