Metadata only
Date
1997Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
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 such that no processor is a communication bottleneck. We prove a lower bound of !2(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. Show more
Publication status
publishedExternal links
Book title
PODC '97: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed ComputingPages / Article No.
Publisher
Association for Computing MachineryEvent
Organisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger
Related publications and datasets
Is previous version of: http://hdl.handle.net/20.500.11850/99203
More
Show all metadata
ETH Bibliography
yes
Altmetrics