skip to main content
10.1145/1993806.1993869acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
abstract

Scalability versus semantics of concurrent FIFO queues

Published: 06 June 2011 Publication History

Abstract

Maintaining data structure semantics of concurrent queues such as first-in first-out (FIFO) ordering requires expensive synchronization mechanisms which limit scalability. However, deviating from the original semantics of a given data structure may allow for a higher degree of scalability and yet be tolerated by many concurrent applications. We introduce the notion of a k-FIFO queue which may be out of FIFO order up to a constant k (called semantical deviation). Implementations of k-FIFO queues may be distributed and therefore be accessed unsynchronized while still being starvation-free. We show that k-FIFO queues whose implementations are based on state-of-the-art FIFO queues, which typically do not scale under high contention, provide scalability. Moreover, probabilistic versions of k-FIFO queues improve scalability further but only bound semantical deviation with high probability.

References

[1]
Y. Afek, G. Korland, and E. Yanovsky. Quasi-linearizability: Relaxed consistency for improved concurrency. In Proc. Conference on Principles of Distributed Systems (OPODIS), pages 395--410. Springer, 2010.
[2]
P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking. Balanced allocations: The heavily loaded case. SIAM Journal on Computing, 35(6):1350--1385, 2006.
[3]
C. Kirsch, H. Payer, and H. Röck. Scal: Non-linearizable computing breaks the scalability barrier. Technical Report 2010-07, Department of Computer Sciences, University of Salzburg, November 2010.
[4]
M. Michael and M. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proc. Symposium on Principles of Distributed Computing (PODC), pages 267--275. ACM, 1996.
[5]
N. Shavit. Data structures in the multicore age. Communications of the ACM, 54:76--84, March 2011.

Cited By

View all
  • (2022)Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch &Increment, Stacks and Queues with MultiplicityDistributed Computing10.1007/s00446-022-00440-y36:2(89-106)Online publication date: 7-Dec-2022
  • (2019)Extracting SIMD Parallelism from Recursive Task-Parallel ProgramsACM Transactions on Parallel Computing10.1145/33656636:4(1-37)Online publication date: 26-Dec-2019
  • (2019)HyperqueuesACM Transactions on Parallel Computing10.1145/33656606:4(1-35)Online publication date: 19-Nov-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing
June 2011
406 pages
ISBN:9781450307192
DOI:10.1145/1993806

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. concurrent data-structures
  2. multiprocessors
  3. synchronization

Qualifiers

  • Abstract

Conference

PODC '11
Sponsor:

Acceptance Rates

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

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)23
  • Downloads (Last 6 weeks)1
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch &Increment, Stacks and Queues with MultiplicityDistributed Computing10.1007/s00446-022-00440-y36:2(89-106)Online publication date: 7-Dec-2022
  • (2019)Extracting SIMD Parallelism from Recursive Task-Parallel ProgramsACM Transactions on Parallel Computing10.1145/33656636:4(1-37)Online publication date: 26-Dec-2019
  • (2019)HyperqueuesACM Transactions on Parallel Computing10.1145/33656606:4(1-35)Online publication date: 19-Nov-2019
  • (2019)Introduction to the Special Issue on Qest 2017ACM Transactions on Modeling and Computer Simulation10.1145/336378429:4(1-2)Online publication date: 18-Nov-2019
  • (2019)Faster Algorithms for Dynamic Algebraic Queries in Basic RSMs with Constant TreewidthACM Transactions on Programming Languages and Systems10.1145/336352541:4(1-46)Online publication date: 13-Nov-2019
  • (2019)Environmental Bisimulations for Probabilistic Higher-order LanguagesACM Transactions on Programming Languages and Systems10.1145/335061841:4(1-64)Online publication date: 12-Oct-2019
  • (2019)On the Impact of Programming Languages on Code QualityACM Transactions on Programming Languages and Systems10.1145/334057141:4(1-24)Online publication date: 12-Oct-2019
  • (2019)Analysis of Spatio-temporal Properties of Stochastic Systems Using TSTLACM Transactions on Modeling and Computer Simulation10.1145/332616829:4(1-24)Online publication date: 10-Dec-2019
  • (2019)Integrating Simulation and Numerical Analysis in the Evaluation of Generalized Stochastic Petri NetsACM Transactions on Modeling and Computer Simulation10.1145/332151829:4(1-25)Online publication date: 18-Nov-2019
  • (2019)Sequential Schemes for Frequentist Estimation of Properties in Statistical Model CheckingACM Transactions on Modeling and Computer Simulation10.1145/331022629:4(1-22)Online publication date: 18-Nov-2019
  • Show More Cited By

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