.png){kind=icon}
.png){kind=icon}
返回
An inherent bottleneck in distributed counting
.png){kind=icon}
OA
AI
DOI：10.1006/jpdc.1998.1431.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
A distributed counter allows each processor in an asynchronous message passing network to access the counter value and increment it. We study the problem of implementing a distributed counter so that no processor is a communication bottleneck. We prove a lower bound of Omega(log n/log log n) on the number of messages that some processor must exchange in a sequence of n counting operations spread over n processors. We propose a counter that achieves this bound when each processor increments the counter exactly once. Hence, the lower bound is tight. Because most algorithms and data structures count in some way, the lower bound holds for many distributed computations. We feel that the proposed concept of a communication bottleneck is a relevant measure of efficiency for a distributed algorithm and data structure, because it indicates the achievable degree of distribution. (C) 1998 Academic Press.
Keyword:
distributed data structures
distributed counting
hot-spot
bottleneck
decentralization
efficiency
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。