Open access
Date
1997Type
- Report
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 k on the number of messages that some processor must exchange in a sequence of n counting operations spread over n processors where kkk n We propose a counter that achieves this bound for the situation it is derived for namely 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 eciency for a distributed algorithm and data structure because it indicates the achievable degree of distribution. Show more
Permanent link
https://doi.org/10.3929/ethz-a-006651923Publication status
publishedJournal / series
Technical report / Department Informatik, ETH ZürichVolume
Publisher
ETH Zürich, Institut für Theoretische InformatikSubject
DISTRIBUTED ALGORITHMS + PARALLEL ALGORITHMS (PROGRAMMING METHODS); PARALLELVERARBEITUNG + NEBENLÄUFIGKEIT (BETRIEBSSYSTEME); VERTEILTE ALGORITHMEN + PARALLELE ALGORITHMEN (PROGRAMMIERMETHODEN); PROCESS MANAGEMENT (OPERATING SYSTEMS); PROZESSVERWALTUNG + PROZESSMANAGEMENT (BETRIEBSSYSTEME); PARALLEL PROCESSING + CONCURRENCY (OPERATING SYSTEMS)Organisational unit
02150 - Dep. Informatik / Dep. of Computer Science
Notes
Technical Reports D-INFK.More
Show all metadata
ETH Bibliography
yes
Altmetrics