More Web Proxy on the site http://driver.im/

Article

Collective asynchronous reading with polylogarithmic worst-case overhead

Authors:

Bogdan S. Chlebus,

Dariusz R. Kowalski,

Alexander A. ShvartsmanAuthors Info & Claims

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

Pages 321 - 330

https://doi.org/10.1145/1007352.1007406

Published: 13 June 2004 Publication History

Abstract

The Collect problem for an asynchronous shared-memory system has the objective for the processors to learn all values of a collection of shared registers, while minimizing the total number of read and write operations. First abstracted by Saks, Shavit, and Woll [37], Collect is among the standard problems in distributed computing, The model consists of $n$ asynchronous processes, each with a single-writer multi-reader register of a polynomial capacity. The best previously known deterministic solution performs O(n^3/2log n) reads and writes, and it is due to Ajtai, Aspnes, Dwork, and Waarts [3]. This paper presents a new deterministic algorithm that performs O(n log⁷ n) read/write operations, thus substantially improving the best previous upper bound. Using an approach based on epidemic rumor-spreading, the novelty of the new algorithm is in using a family of expander graphs and ensuring that each of the successive groups of processes collect and propagate sufficiently many rumors to the next group. The algorithm is adapted to the Repeatable Collect problem, which is an on-line version. The competitive latency of the new algorithm is O(log⁷ n) vs. the much higher competitive latency O(√nlog n) given in [3]. A result of independent interest in this paper abstracts a gossiping game that is played on a graph and that gives its payoff in terms of expansion.

References

[1]

Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit, Atomic snapshots of shared memory, J. ACM, 40 (1993) 873--890.]]

Digital Library

[2]

Y. Afek, G. Stupp, and D. Touitou, Long-lived and adaptive collect with applications, Proc., 40th IEEE Symp. on Found. of Comp. Science, 1999, pp. 262--272.]]

Digital Library

[3]

M. Ajtai, J. Aspnes, C. Dwork, and O. Waarts, A theory of competitive analysis of distributed algorithms, Proc., 35th IEEE Symp. of Foundations of Computer Science, 1994, pp. 401--411.]]

Digital Library

[4]

J. Anderson, Composite registers, Distributed Computing, 6 (1993) 141--154.]]

Digital Library

[5]

R. J. Anderson, and H. Woll, Algorithms for the certified write-all problem, SIAM J. Computing, 26 (1997) 1277--1283.]]

Digital Library

[6]

J. Aspnes, and M. Herlihy, Wait-free data structures in the asynchronous PRAM model, in Proc., 2nd ACM Symp. on Parallel Alg. and Arch., 1990, pp. 340--349.]]

Digital Library

[7]

J. Aspnes, and W. Hurwood, Spreading rumors rapidly despite an adversary, J. Algorithms, 26 (1998) 386--411.]]

Digital Library

[8]

H. Attiya, A. Fouren, and E. Gafni, An adaptive collect algorithm with applications, Distributed Computing, 15 (2002) 87--96.]]

Digital Library

[9]

H. Attiya, M. Herlihy, and O. Rachman, Atomic snapshots using lattice agreement, Distributed Computing, 8 (1995) 121--132.]]

Digital Library

[10]

H. Attiya, and O. Rachman, Atomic snapshots in O(n log n) operations, SIAM J. Computing, 27 (1998) 319--340.]]

Digital Library

[11]

B. Awerbuch, S. Kutten, and D. Peleg, Competitive distributed job scheduling, in Proc., 24th ACM Symp. on Theory of Computing, 1992, pp. 571--580.]]

Digital Library

[12]

N. T. J. Bailey, The Mathematical Theory of Infectious Diseases and its Applications, Charles Griffin, London, 1975.]]

[13]

Y. Bartal, A. Fiat, and Y. Rabani, Competitive algorithms for distributed data management, in Proc., 24th ACM Symp. on Theory of Comp, 1992, pp. 39--50.]]

Digital Library

[14]

J. Buss, P. C. Kanellakis, P. L. Ragde, and A. A. Shvartsman, Parallel algorithms with processor failures and delays, J. Algorithms, 20 (1996) 45--86.]]

Digital Library

[15]

B. S. Chlebus, L. Gasieniec, D. R. Kowalski, and A. A. Shvartsman, Bounding work and communication in robust cooperative computation, in Proc., 16th Int. Symposium on Distributed Computing, 2002, Springer LNCS 2508, pp. 295--310.]]

Digital Library

[16]

B. S. Chlebus, and D. R. Kowalski, Gossiping to reach consensus, in Proc., 14th ACM Symp. on Parallel Algorithms and Architectures, 2002, pp. 220--229.]]

Digital Library

[17]

B. S. Chlebus, S. Dobrev, D. R. Kowalski, G. Malewicz, A. A. Shvartsman, and I. Vrto, Towards practical deterministic write-all algorithms, in Proc., 13th ACM Symp. on Parallel Algorithms and Arch., 2001, pp. 271--280.]]

Digital Library

[18]

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swineheart, and D. Terry, Epidemic algorithms for replicated database maintenance, in Proc., 6th ACM Symp. on Principles of Distributed Computing, 1987, pp. 1--12.]]

Digital Library

[19]

D. Dolev and N. Shavit, Bounded concurrent time-stamping, SIAM J. Computing, 26 (1997) 418--455.]]

Digital Library

[20]

C. Dwork, M. Herlihy, and O. Waarts, Bounded round numbers, in Proc., 12th ACM Symp. on Principles of Distributed Computing, 1993, pp. 53--64.]]

Digital Library

[21]

C. Dwork and O. Waarts, Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible!, Proc., 24th ACM Symp. on the Theory of Comp., 1992, pp. 655--666.]]

Digital Library

[22]

C. Georgiou, D. R. Kowalski, and A. A. Shvartsman, Efficient gossip and robust distributed computation, in Proc., 17th Int. Symp. on Distributed Computing, 2003, pp. 224--238.]]

[23]

C. Georgiou, A. Russell, and A. A. Shvartsman, Work-competitive scheduling for cooperative computing with dynamic groups, in Proc., 35th ACM Symposium on Theory of Computing, 2003, pp. 251--258.]]

Digital Library

[24]

M. Harchol-Balter, T. Leighton, and D. Lewin, Resource discovery in distributed networks, in Proc., 18th ACM Symp. on Principles of Distributed Computing, 1999, pp. 229--238.]]

Digital Library

[25]

A. Israeli and M. Li, Bounded time stamps Proc., 28th IEEE Symp. Found. of Computer Science, 1987, pp. 371--382.]]

[26]

P. C. Kanellakis, and A. A. Shvartsman, Efficient parallel algorithms can be made robust, Distributed Computing, 5 (1992) 201--217.]]

[27]

P. C. Kanellakis, and A. A. Shvartsman, Fault-Tolerant Parallel Computation, Kluwer Academic Pub., 1997.]]

Digital Library

[28]

R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking, Randomized rumor spreading, in Proc., 41st IEEE Symp. on Foundations of Computer Science, 2000, pp. 565--574.]]

Digital Library

[29]

D. Kempe, J. Kleinberg, and A. Demers, Spatial gossip and resource location protocols, in Proc., 33rd ACM Symp. on Theory of Computing, 2001, pp. 163--172.]]

Digital Library

[30]

M. Li, J. Tromp, and P. M. B. Vitanyi, How to share concurrent wait-free variables, J. ACM, 43 (1996) 723--746.]]

Digital Library

[31]

N. A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996.]]

Digital Library

[32]

G. Malewicz, A work-optimal deterministic algorithm for the asynchronous certified write-all problem, in Proc., 22nd ACM Symposium on Principles of Distributed Computing, 2003, pp. 255--264.]]

Digital Library

[33]

C. Martel, A. Park, and R. Subramonian, Work-optimal asynchronous algorithms for shared memory parallel computers, SIAM J. Computing, 21 (1992) 1070--1099.]]

Digital Library

[34]

M. S. Pinsker, On the complexity of a concentrator, in Proc., 7th Annual Teletraffic Conference, 1973, pp. 318/1--318/4.]]

[35]

N. Pippenger, Sorting and selecting in rounds, SIAM J. Computing, 16 (1987) 1032--1038.]]

Digital Library

[36]

O. Reingold, S. P. Vadhan, and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors, Ann. Mathematics, 155 (2002) 157--187.]]

[37]

M. Saks, N. Shavit, and H. Woll, Optimal time randomized consensus--making resilient algorithms fast in practice, in Proc. 2nd SIAM--ACM Symp. Discrete Algorithms, 1991, pp. 351--362.]]

Digital Library

[38]

N. Shavit, "Concurrent Timestamping," Ph. D. Thesis, The Hebrew University, 1989.]]

[39]

A. A. Shvartsman, Achieving optimal CRCW PRAM fault-tolerance, Information Processing Letters, 39 (1991) 59--66.]]

Digital Library

[40]

D. Sleator and R. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, 28 (1985) 202--208.]]

Digital Library

[41]

A. Ta-Shma, C. Umans, and D. Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, in Proc., 33rd ACM Symp. on Theory of Computing, 2001, pp. 143--152.]]

Digital Library

[42]

E. Upfal, Tolerating a linear number of faults in networks of bounded degree, Information and Computation, 115 (1994) 312--320.]]

Digital Library

[43]

P. M. B. Vitanyi and B. Awerbuch, Atomic shared register access by asynchronous hardware, in Proc., 27th Symp. on Foundations of Computer Science, 1986, pp. 233--243.]]

Digital Library

[44]

R. van Renesse, Y. Minsky, and M. Hayden, A gossip-style failure detection service, in Proc., IFIP Int. Conf. on Distributed Systems Platforms and Open Distributed Processing, 1998, pp. 55--70.]]

Digital Library

[45]

A. Wigderson, and D. Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Combinatorica, 19 (1999) 125--138.]]

Cited By

Georgiou CKowalski D(2015)On the competitiveness of scheduling dynamically injected tasks on processes prone to crashes and restartsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.07.00784:C(94-107)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.jpdc.2015.07.007
Georgiou CKowalski D(2011)Performing dynamically injected tasks on processes prone to crashes and restartsProceedings of the 25th international conference on Distributed computing10.5555/2075029.2075049(165-180)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2075029.2075049
Georgiou CGilbert SKowalski D(2011)Meeting the deadlineDistributed Computing10.1007/s00446-011-0144-624:5(223-244)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1007/s00446-011-0144-6
Show More Cited By

Index Terms

Collective asynchronous reading with polylogarithmic worst-case overhead
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Polylogarithmic-time deterministic network decomposition and distributed derandomization
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated 2^O(√logn)-time algorithm of Panconesi and Srinivasan [STOC’92] and settles a central and long-standing question in ...
Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

A recent work by Christiansen, Nowicki, and Rotenberg [STOC’23] provides dynamic algorithms for coloring sparse graphs, concretely as a function of the graph’s arboricity α. They give two randomized algorithms: O(α logα) implicit coloring in poly(logn) ...
Asynchronous exclusive selection
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing

The distributed setting of this paper is an asynchronous system consisting of n processes prone to crashes and a number of shared read-write registers. We consider problems regarding assigning integer values to processes in an exclusive way, in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

June 2004

660 pages

ISBN:1581138520

DOI:10.1145/1007352

Program Chair:
László Babai
University of Chicago, Chicago, IL

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC04

Sponsor:

STOC04: Symposium of Theory of Computing 2004

June 13 - 16, 2004

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
247
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Georgiou CKowalski D(2015)On the competitiveness of scheduling dynamically injected tasks on processes prone to crashes and restartsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.07.00784:C(94-107)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.jpdc.2015.07.007
Georgiou CKowalski D(2011)Performing dynamically injected tasks on processes prone to crashes and restartsProceedings of the 25th international conference on Distributed computing10.5555/2075029.2075049(165-180)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2075029.2075049
Georgiou CGilbert SKowalski D(2011)Meeting the deadlineDistributed Computing10.1007/s00446-011-0144-624:5(223-244)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1007/s00446-011-0144-6
Georgiou CKowalski D(2011)Performing Dynamically Injected Tasks on Processes Prone to Crashes and RestartsDistributed Computing10.1007/978-3-642-24100-0_15(165-180)Online publication date: 2011
https://doi.org/10.1007/978-3-642-24100-0_15
Gilbert SKowalski D(2010)Trusted computing for fault-prone wireless networksProceedings of the 24th international conference on Distributed computing10.5555/1888781.1888826(359-373)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.5555/1888781.1888826
Georgiou CGilbert SKowalski DRicha AGuerraoui R(2010)Meeting the deadlineProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835759(247-256)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835759
Gilbert SKowalski D(2010)Trusted Computing for Fault-Prone Wireless NetworksDistributed Computing10.1007/978-3-642-15763-9_33(359-373)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15763-9_33
Kowalski DStrojnowski M(2007)On the Communication Surplus Incurred by Faulty ProcessorsDistributed Computing10.1007/978-3-540-75142-7_26(328-342)Online publication date: 2007
https://doi.org/10.1007/978-3-540-75142-7_26
Chlebus BKowalski D(2006)Time and communication efficient consensus for crash failuresProceedings of the 20th international conference on Distributed Computing10.1007/11864219_22(314-328)Online publication date: 18-Sep-2006
https://dl.acm.org/doi/10.1007/11864219_22
Chlebus BKowalski DGabow HFagin R(2005)Cooperative asynchronous update of shared memoryProceedings of the thirty-seventh annual ACM symposium on Theory of computing10.1145/1060590.1060698(733-739)Online publication date: 22-May-2005
https://dl.acm.org/doi/10.1145/1060590.1060698

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents