abstract

Brief Announcement: Fast Shared Counting using (O(n)) Compare-and-Swap Registers

Authors:

Pankaj Khanchandani,

Roger WattenhoferAuthors Info & Claims

PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

Pages 95 - 96

https://doi.org/10.1145/3087801.3087841

Published: 25 July 2017 Publication History

Get Access

Abstract

We consider the problem of building a wait-free and linearizable counter using shared registers. The counter supports a read operation, which returns the value of the counter, and an increment operation, which increments the value of the counter and returns nothing. The shared registers support read, write and compare-and-swap instructions. We show that given (n) processes and (O(n)) shared registers, the increment operation is in (O(log n)) and read operation is in (O(1)).

References

[1]

Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui. 2014. Tight Bounds for Asynchronous Renaming. Journal of the ACM (JACM) (2014).

Google Scholar

[2]

Faith Ellen and Philipp Woelfel. 2013. An Optimal Implementation of Fetch-and-Increment. In 27th International Symposium on Distributed Computing (DISC), Jerusalem, Israel.

Digital Library

Google Scholar

[3]

Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems (TOPLAS) (1990).

Google Scholar

[4]

Prasad Jayanti and Srdjan Petrovic. 2005. Efficiently Implementing a Large Number of LL/SC Objects. In 9th International Conference on Principles of Distributed Systems (OPODIS), Pisa, Italy.

Digital Library

Google Scholar

[5]

Prasad Jayanti, King Tan, and Sam Toueg. 2006. Time and Space Lower Bounds for Nonblocking Implementations. SIAM Journal on Computing (2006).

Google Scholar

Cited By

View all

Baig MHendler DMilani ATravers C(2022)Long-lived counters with polylogarithmic amortized step complexityDistributed Computing10.1007/s00446-022-00439-536:1(29-43)Online publication date: 29-Nov-2022
https://doi.org/10.1007/s00446-022-00439-5
Khanchandani PWattenhofer R(2020)Two elementary instructions make compare-and-swapJournal of Parallel and Distributed Computing10.1016/j.jpdc.2020.06.005Online publication date: Jun-2020
https://doi.org/10.1016/j.jpdc.2020.06.005
Khanchandani PWattenhofer R(2019)Two Elementary Instructions Make Compare-and-Swap2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00046(365-374)Online publication date: May-2019
https://doi.org/10.1109/IPDPS.2019.00046
Show More Cited By

Index Terms

Brief Announcement: Fast Shared Counting using (O(n)) Compare-and-Swap Registers
1. Theory of computation
  1. Design and analysis of algorithms
    1. Concurrent algorithms
    2. Parallel algorithms
      1. Shared memory algorithms

Recommendations

Brief Announcement: Persistent Multi-Word Compare-and-Swap
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

This brief announcement presents a fundamental concurrent primitive for persistent memory - a persistent atomic multi-word compare-and-swap (PMCAS).We present a novel algorithm carefully crafted to ensure that atomic updates to a multitude of words ...
Brief announcement: single-version permissive STM
PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

We present a single-version STM that satisfies a practical notion of permissiveness: it never aborts read-only transactions, and it only aborts an update transaction due to another conflicting update transaction, thereby avoiding many spurious aborts. ...
A paradox of eventual linearizability in shared memory
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

This paper compares, for the first time, the computational power of linearizable objects with that of eventually linearizable ones. We present the following paradox. We show that, unsurprisingly, no set of eventually linearizable objects can (1) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

July 2017

480 pages

ISBN:9781450349925

DOI:10.1145/3087801

General Chair:
Elad Michael Schiller
Chalmers University of Technology, Sweden
,
Program Chair:
Alexander A. Schwarzmann
University of Connecticut, USA

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2017

Check for updates

Author Tags

Qualifiers

Abstract

Conference

PODC '17

Sponsor:

PODC '17: ACM Symposium on Principles of Distributed Computing

July 25 - 27, 2017

DC, Washington, USA

Acceptance Rates

PODC '17 Paper Acceptance Rate 38 of 154 submissions, 25%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
125
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Baig MHendler DMilani ATravers C(2022)Long-lived counters with polylogarithmic amortized step complexityDistributed Computing10.1007/s00446-022-00439-536:1(29-43)Online publication date: 29-Nov-2022
https://doi.org/10.1007/s00446-022-00439-5
Khanchandani PWattenhofer R(2020)Two elementary instructions make compare-and-swapJournal of Parallel and Distributed Computing10.1016/j.jpdc.2020.06.005Online publication date: Jun-2020
https://doi.org/10.1016/j.jpdc.2020.06.005
Khanchandani PWattenhofer R(2019)Two Elementary Instructions Make Compare-and-Swap2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00046(365-374)Online publication date: May-2019
https://doi.org/10.1109/IPDPS.2019.00046
Khanchandani PWattenhofer R(2018)On the Importance of Synchronization Primitives with Low Consensus NumbersProceedings of the 19th International Conference on Distributed Computing and Networking10.1145/3154273.3154306(1-10)Online publication date: 4-Jan-2018
https://dl.acm.org/doi/10.1145/3154273.3154306

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Brief Announcement: Persistent Multi-Word Compare-and-Swap

Brief announcement: single-version permissive STM

A paradox of eventual linearizability in shared memory