Communication cost of consensus for nodes with limited memory
Communication cost of consensus for nodes with limited memory
复制标题
内存有限的节点共识的通信成本
DOI：
10.1073/pnas.1912980117
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ranade, Gireeja
中科院分区：
文献类型：
--
作者：
Fanti, Giulia;Holden, Nina;Peres, Yuval;Ranade, Gireeja
受无线网络和物联网应用的启发，我们考虑了一个节点试图在其多数比特上以高概率达成共识的模型。每个节点在时间0被分配一个比特，并且是具有比特存储器(即，状态)和泊松时钟的有限自动机。当时钟响起时，可以选择通信，然后匹配到统一选择的节点。节点可以基于另一节点的状态来更新它们的状态。以前的工作侧重于最小化达成共识的时间和出错的概率，而我们的目标是最小化沟通的数量。我们证明了，当m&t；3logloglog(N)时，可以以线性通信代价达成共识，而当m<；logloglog(N)时，这是不可能的。一个关键的步骤是区分节点何时能够意识到知道多数位并停止通信。我们证明，如果他们的内存太低，这是不可能的。
Motivated by applications in wireless networks and the Internet of Things, we consider a model ofnodes trying to reach consensus with high probability on their majority bit. Each nodeis assigned a bit at time 0 and is a finite automaton withbits of memory (i.e.,states) and a Poisson clock. When the clock ofrings,can choose to communicate and is then matched to a uniformly chosen node. The nodesandmay update their states based on the state of the other node. Previous work has focused on minimizing the time to consensus and the probability of error, while our goal is minimizing the number of communications. We show that, when m>3logloglog(n), consensus can be reached with linear communication cost, but this is impossible if m<logloglog(n). A key step is to distinguish when nodes can become aware of knowing the majority bit and stop communicating. We show that this is impossible if their memory is too low.
登录
查看更多内容
影响因子：
4.6
作者：
Cardelli, Luca;Csikasz-Nagy, Attila
通讯作者：
Csikasz-Nagy, Attila
DOI：
--
发表时间：
2012
期刊：
2013 Proceedings IEEE INFOCOM
影响因子：
--
作者：
Shang Shang;P. Cuff;Pan Hui;S. Kulkarni
通讯作者：
S. Kulkarni
通过图表上的本地多数投票得出全球多数共识
DOI：
--
发表时间：
2012
期刊：
International Conference on Network Games, Control and Optimization
影响因子：
--
作者：
Mohammed Abdullah;M. Draief
通讯作者：
M. Draief
影响因子：
1.9
作者：
Mossel, Elchanan;Neeman, Joe;Tamuz, Omer
通讯作者：
Tamuz, Omer
具有最佳通信复杂度的分布式协议
DOI：
--
发表时间：
2010
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Seth Gilbert;D. Kowalski
通讯作者：
D. Kowalski