Top

Distributed Computing

Published in:

07-12-2022

Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch &Increment, Stacks and Queues with Multiplicity

Authors: Armando Castañeda, Sergio Rajsbaum, Michel Raynal

Published in: Distributed Computing | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This work consideres asynchronous shared memory systems in which any number of processes may crash. It identifies relaxations of fetch & increment, queues, sets and stacks that can be non-blocking or wait-free implemented using only Read/Write operations, without Read-After-Write synchronization patterns. Set-linearizability, a generalization of linearizability designed to specify concurrent behaviors, is used to formally express these relaxations and precisely identify the subset of executions which preserve the original sequential behavior. The specifications allow for an item to be returned more than once by different operations, but only in case of concurrency; we call such a relaxation multiplicity. Hence, these definitions give rise to new notions and new objects where concurrency explicitly appears in the specification of the objects. As far as we know, this work is the first to provide relaxations of objects with consensus number two which can be implemented using only Read/Write registers.

next article Phase transition of the k-majority dynamics in biased communication models

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

The terms “object” and “concurrent data structure” are considered as synonyms.

High contention however can make Read/Write operations slower.

Some authors use lock-free instead of non-blocking.

Although the object can be Read/Write implemented without them.

Non-blocking or wait-free implementing a (non-relaxed) set under this assumptions still requires the use of Read-Modify-Write operations.

Although the proof set-linearizes only executions with no pending operations, the example considers an execution with a pending operation to make the discussion more complete.

It is an open question if there are wait-free linearizable queue implementations using only objects with consensus number two (see [4, 11, 16, 32, 33]).

Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM 40(4), 873–890 (1993)CrossRefMATH

Afek, Y., Gafni, E., Morrison, A.: Common2 extended to stacks and unbounded concurrency. Distrib. Comput. 20(4), 239–252 (2007)CrossRefMATH

Afek, Y., Korland, G., Yanovsky, E.: Quasi-linearizability: relaxed consistency for improved concurrency. In: Proceedings of 14th International Conference on Principles of Distributed Systems, (OPODIS’10), Springer LNCS 6490, pp. 395-410 (2010)

Afek, Y., Weisberger, E., Weisman, H.: A completeness theorem for a class of synchronization objects. In: Proceedings of the 12th ACM Symposium on Principles of Distributed Computing (PODC’93), ACM Press, pp. 159–170 (1993)

Alistarh, D., Brown, T., Kopinsky, J., Li, J., Nadiradze, G.: Distributionally linearizable data structures. In: Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA’15), ACM Press, pp. 133–142 (2018)

Alistarh, D., Kopinsky, J., Li, J., Shavit, N.: The SprayList: a scalable relaxed priority queue. In: Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP’15), ACM Press, pp. 11–20 (2015)

Aspnes, J., Attiya, H., Censor-Hillel, K., Ellen, F.: Limited-use atomic snapshots with polylogarithmic step complexity. J. ACM 62(1), 3:1-3:22 (2015)MathSciNetCrossRefMATH

Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P.: The complexity of obstruction-free implementations. J. ACM, 56(4), Article 24, 33 pp (2009)

Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P., Michael, M.M., Vechev, M.T.: Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. In: Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’11), ACM Press, pp. 487-498 (2011)

10.

Attiya, H., Herlihy, M., Rachman, O.: Atomic snapshots using lattice agreement. Distrib. Comput. 8(3), 121–132 (1995)CrossRefMATH

11.

Attiya, H., Castañeda, A., Hendler, D.: Nontrivial and universal helping for wait-free queues and stacks. J. Parallel Distrib. Comput. 121, 1–14 (2018)CrossRefMATH

12.

Castañeda, A., Piña M.A.: Fully read/write fence-free work-stealing with multiplicity. In: Proceedings of the 35th International Symposium on Distributed Computing (DISC’21), LIPIcs Vol. 209, pp. 16:1–16:20 (2021)

13.

Castañeda, A., Rajsbaum, S., Raynal, M.: Unifying concurrent objects and distributed tasks: interval-linearizability. J. ACM, 65(6), Article 45, 42 pp (2018)

14.

Castañeda, A., Rajsbaum, S., Raynal, M.: Relaxed queues and stacks from read/write operations. In: Proceedings of the 24th International Conference Principles of Distributed Systems (OPODIS’20), LIPIcs Vol. 184, pp. 13:1-13:19 (2020)

15.

Castañeda, A., Rajsbaum, S., Raynal, M.: A Linearizability-based Hierarchy for Concurrent Specifications. To appear in Communications of the ACM, (2022)

16.

Eisenstat, D.: Two-enqueuer queue in Common2. arXiV:0805.O444v2, 12 pp (2009)

17.

Ellen, F., Hendler, D., Shavit, N.: On the inherent sequentiality of concurrent objects. SIAM J. Comput. 41(3), 519–536 (2012)MathSciNetCrossRefMATH

18.

Goubault, E., Ledent, J., Mimram S.: Concurrent specifications beyond linearizability. In: Proceedings of the 22nd International Conference on Principles of Distributed Systems (OPODIS’18), LIPIcs Vol. 125, pp. 28:1-28:16 (2018)

19.

Haas, A., Henzinger, T.A., Holzer, A., Kirsch, Ch.M, Lippautz, M., Payer, H., Sezgin, A., Sokolova, A., Veith, H.: Local linearizability for concurrent set-type data structures. In: Proceedings of the 27th International Conference on Concurrency Theory (CONCUR’16), LIPIcs Vol. 59, pp. 6:1–6:15 (2016)

20.

Haas, A., Lippautz, M., Henzinger, T.A., Payer, H., Sokolova, A., Kirsch, C.M., Sezgin, A.: Distributed queues in shared memory: multicore performance and scalability through quantitative relaxation. In: Computing Frontiers Conference (CF’13), ACM Press, pp. 17:1–17:9 (2013)

21.

Hemed, N., Rinetzky, N., Vafeiadis, V.: Modular verification of concurrent-aware linearizability. In: Proceedings of the 29th International Conference on Distributed Computing (DISC’15), Springer LNCS 9363, pp. 371–387 (2015)

22.

Hendler, D., Shavit, N., Yerushalmi, L.: A scalable lock-free stack algorithm. J. Parallel Distrib. Comput. 70(1), 1–12 (2010)CrossRefMATH

23.

Henzinger, T.A., Kirsch, C.M., Payer, H., Sezgin, A., Sokolova, A.: Quantitative relaxation of concurrent data structures. In: Proceedings of the 40th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’13), ACM Pres, pp. 17:1–17:9 (2013)

24.

Herlihy, M.P.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)CrossRef

25.

Herlihy, M.P., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann, 508 pp, ISBN 978-0-12-370591-4 (2008)

26.

Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)

27.

Imbs, D., Raynal, M.: Help when needed, but no more: efficient read/write partial snapshot. J. Parallel Distrib. Comput. 72(1), 1–13 (2012)CrossRefMATH

28.

Kirsch, C.M., Lippautz, Payer, H.: Fast and scalable lock-free FIFO queues. In: Proceedings of the 12th International Conference on Parallel Computing Technologies (PaCT’13), Springer LNCS 7979, pp. 208–223 (2013)

29.

Kirsch, C.M., Payer, H., Röck, H., Ana Sokolova, A.: Performance, scalability, and semantics of concurrent FIFO queues. In: Proceedings of 12th International Conference on Algorithms and Architectures for Parallel Processing (ICAAPP’12), Springer LNCS 7439, pp. 273–287 (2012)

30.

Lamport, L.: On interprocess communication, Part I: basic formalism. Distrib. Comput. 1(2), 77–85 (1986)MathSciNetCrossRefMATH

31.

Li, Z.: Non-blocking implementations of queues in asynchronous distributed shared-memory systems. Tech Report, Department of Computer Science, University of Toronto (2001)

32.

Matei, D.: A single-enqueuer wait-free queue implementation. In: Proceedings of the 18th International Conference on Distributed Computing (DISC’04), Springer LNCS 3274, pp. 132–143 (2004)

33.

Matei, D., Brodsky, A., Ellen, F.: Restricted stack implementations. In: 19th International Conference on Distributed Computing (DISC’05), Springer LNCS 3724, pp. 137–151 (2005)

34.

Michael, M.M., Vechev, M.T., Saraswat, S.A.: Idempotent work stealing. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP’09), ACM Press, pp. 45–54 (2009)

35.

Moir, M., Shavit, N.: Concurrent data structures. Handbook of Data Structures and Applications, chapter 47, Chapman and hall/CrC Press, 33 pp (2007)

36.

Morrison, A., Afek, Y.: Fence-free work stealing on bounded TSO processors. In: Proceedings of the 19th ACM Architectural Support for Programming Languages and Operating Systems (ASPLOS’14), ACM Press, pp. 413–426 (2014)

37.

Neiger, G.: Brief announcement: Set linearizability. In: Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC’94), ACM Press, p. 396 (1994)

38.

Nguyen, D., Lenharth, A., Pingali, K.: A lightweight infrastructure for graph analytics. In: Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP’13), ACM Press, pp. 456–471 (2013)

39.

Payer, H., Röck, H., Kirsch, M.M., Sokolova, A.: Brief announcement: Scalability versus semantics of concurrent FIFO queues. In: Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC’11), ACM Press, pp. 331–332 (2011)

40.

Rajsbaum, S., Raynal, M.: Mastering concurrent computing through sequential thinking. Commun. ACM 63(1), 78–87 (2020)CrossRef

41.

Raynal, M.: Concurrent Programming: Algorithms, Principles and Foundations. Springer, 515 pp, ISBN 978-3-642-32026-2 (2013)

42.

Rihani, H., Sanders, P., Dementiev, R.: Brief Announcement: MultiQueues: simple relaxed concurrent priority queues. In: Proceedings of the 327th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA’12), ACM Press, pp. 80–82 (2015)

43.

Shavit, N.: Data structures in the multicore age. Commun. ACM 54(3), 76–84 (2011)CrossRef

44.

Shavit, N., Taubenfeld, G.: The computability of relaxed data structures: queues and stacks as examples. Distrib. Comput. 29(5), 395–407 (2016)MathSciNetCrossRefMATH

45.

Talmage, E., Welch, J.L.: Relaxed data types as consistency conditions. Algorithms 11(5), 61 (2018)

46.

Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Pearson Education/Prentice Hall, 423 pp, ISBN 0-131-97259-6 (2006)

47.

Zhou, T., Michael, M.M., Spear, M.F.: A practical, scalable, relaxed priority queue. In: Proceedings of the 48th International Conference on Parallel Processing (ICPP’19), pp. 57:1–57:10 (2019)

Title: Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch &Increment, Stacks and Queues with Multiplicity
Authors: Armando Castañeda
Sergio Rajsbaum
Michel Raynal
Publication date: 07-12-2022
Publisher: Springer Berlin Heidelberg
Published in: Distributed Computing / Issue 2/2023
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI: https://doi.org/10.1007/s00446-022-00440-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2023

The canonical amoebot model: algorithms and concurrency control

Phase transition of the k-majority dynamics in biased communication models

Termination of amnesiac flooding

Cross-chain payment protocols with success guarantees

Premium Partner