skip to main content
10.1145/1146381.1146415acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Common2 extended to stacks and unbounded concurrency

Published: 23 July 2006 Publication History

Abstract

Common2, the family of objects that implement and are wait-free implementable from 2 consensus objects, is extended inhere in two ways: First, the stack object is added to the family --- an object that was conjectured not to be in the family. Second, Common2 is investigated in the unbounded concurrency model, whereas until now it was considered only in an n-process model.We show that fetch-and-add, test-and-set, and stack are in Common2 even with respect to this stronger notion of wait-free implementation. This necessitated the wait-free implementation of immediate snapshots in the unbounded concurrency model, which was previously not known to be possible.In addition to extending Common2, the introduction of unbounded-concurrency may help in resolving the Common2 membership problem: If, as conjectured, queue is not implementable for a-priori known concurrency n, then it is definitely not implementable for unbounded concurrency. Proving the latter should be easier than proving the former. In addition we conjecture that the swap object, that has an n-process implementation, does not have an unbounded concurrency implementation.

References

[1]
Y. Afek, E. Gafni, J. Tromp, and P. M. B. Vitányi. Wait-free test-and-set. In Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG 1992), pages 85--94, London, UK, 1992. Springer-Verlag.
[2]
Y. Afek and E. Weisberger. The instancy of snapshots and commuting objects. Journal of Algorithms, 30(1):68--105, 1999.
[3]
Y. Afek, E. Weisberger, and H. Weisman. A completeness theorem for a class of synchronization objects. In Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing (PODC 1993), pages 159--170, New York, NY, USA, 1993. ACM Press.
[4]
E. Borowsky and E. Gafni. Immediate atomic snapshots and fast renaming. In Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing (PODC 1993), pages 41--51, New York, NY, USA, 1993. ACM Press.
[5]
M. David. A single-enqueuer wait-free queue implementation. In Proceedings of the 18th International Conference on Distributed Computing (DISC 2004), pages 132--143. Springer, 2004.
[6]
M. David, A. Brodsky, and F. E. Fich. Restricted stack implementations. In Proceedings of the 19th International Conference on Distributed Computing (DISC 2005), pages 137--151. Springer, 2005.
[7]
E. Gafni. A simple algorithmic characterization of uniform solvability. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), pages 228--237, Washington, DC, USA, 2002. IEEE Computer Society.
[8]
E. Gafni, M. Merritt, and G. Taubenfeld. The concurrency hierarchy, and algorithms for unbounded concurrency. In Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing (PODC 2001), pages 161--169, New York, NY, USA, 2001. ACM Press.
[9]
D. Hendler, N. Shavit, and L. Yerushalmi. A scalable lock-free stack algorithm. In Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004), pages 206--215, New York, NY, USA, 2004. ACM Press.
[10]
M. Herlihy. Impossibility results for asynchronous pram. In Proceedings of the Third Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 1991), pages 327--336, New York, NY, USA, 1991. ACM Press.
[11]
M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124--149, 1991.
[12]
M. Herlihy and N. Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858--923, 1999.
[13]
M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463--492, 1990.
[14]
Z. Li. Non-blocking implementations of queues in asynchronous distributed shared-memory systems. Master's thesis, Department of Computer Science, University of Toronto, 2001.
[15]
M. Merritt and G. Taubenfeld. Computing with infinitely many processes. In Proceedings of the 14th International Conference on Distributed Computing (DISC 2000), pages 164--178, London, UK, 2000. Springer-Verlag.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
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: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. common2
  2. consensus number 2
  3. immediate snapshot
  4. queue
  5. stack
  6. unbounded concurrency
  7. wait-free

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

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

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)13
  • Downloads (Last 6 weeks)3
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2018)FA-Stack: A Fast Array-Based Stack with Wait-Free Progress GuaranteeIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.277012129:4(843-857)Online publication date: 1-Apr-2018
  • (2018)A Closer Look at Fault ToleranceTheory of Computing Systems10.1007/s00224-017-9779-462:5(1085-1108)Online publication date: 1-Jul-2018
  • (2012)A closer look at fault toleranceProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332484(261-270)Online publication date: 16-Jul-2012
  • (2012)The strong at-most-once problemProceedings of the 26th international conference on Distributed Computing10.1007/978-3-642-33651-5_27(386-400)Online publication date: 16-Oct-2012
  • (2011)From bounded to unbounded concurrency objects and backProceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1993806.1993823(119-128)Online publication date: 6-Jun-2011
  • (2010)On asymmetric progress conditionsProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835709(55-64)Online publication date: 25-Jul-2010
  • (2009)Non-blocking Array-Based Algorithms for Stacks and QueuesProceedings of the 10th International Conference on Distributed Computing and Networking10.1007/978-3-540-92295-7_10(55-66)Online publication date: 26-Mar-2009
  • (2006)Less is moreProceedings of the 20th international conference on Distributed Computing10.1007/11864219_15(209-223)Online publication date: 18-Sep-2006

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media