An Inherent Bottleneck in Distributed Counting
| العنوان: | An Inherent Bottleneck in Distributed Counting |
|---|---|
| المؤلفون: | Peter Widmayer, Roger Wattenhofer |
| المصدر: | Technical report / Department Informatik, ETH Zürich, 259 PODC |
| بيانات النشر: | Elsevier BV, 1998. |
| سنة النشر: | 1998 |
| مصطلحات موضوعية: | Computational complexity theory, Computer Networks and Communications, Computer science, Distributed computing, PARALLEL PROCESSING + CONCURRENCY (OPERATING SYSTEMS), Parallel computing, DISTRIBUTED ALGORITHMS + PARALLEL ALGORITHMS (PROGRAMMING METHODS), Upper and lower bounds, Bottleneck, Theoretical Computer Science, Data processing, computer science, Artificial Intelligence, PARALLELVERARBEITUNG + NEBENLÄUFIGKEIT (BETRIEBSSYSTEME), Sequence, Degree (graph theory), PROZESSVERWALTUNG + PROZESSMANAGEMENT (BETRIEBSSYSTEME), VERTEILTE ALGORITHMEN + PARALLELE ALGORITHMEN (PROGRAMMIERMETHODEN), Message passing, PROCESS MANAGEMENT (OPERATING SYSTEMS), Data structure, Hardware and Architecture, Asynchronous communication, Distributed algorithm, ddc:004, Software |
| الوصف: | 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. Technical report / Department Informatik, ETH Zürich, 259 |
| وصف الملف: | application/application/pdf |
| تدمد: | 0743-7315 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::21b8604f3bf6488dfd6126efaebc698d https://doi.org/10.1006/jpdc.1998.1431 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi.dedup.....21b8604f3bf6488dfd6126efaebc698d |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 07437315 |
|---|