Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch &Increment, Stacks and Queues with Multiplicity
Tóm tắt
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.
Tài liệu tham khảo
Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM 40(4), 873–890 (1993)
Afek, Y., Gafni, E., Morrison, A.: Common2 extended to stacks and unbounded concurrency. Distrib. Comput. 20(4), 239–252 (2007)
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)
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)
Attiya, H., Herlihy, M., Rachman, O.: Atomic snapshots using lattice agreement. Distrib. Comput. 8(3), 121–132 (1995)
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)
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)
Castañeda, A., Rajsbaum, S., Raynal, M.: Unifying concurrent objects and distributed tasks: interval-linearizability. J. ACM, 65(6), Article 45, 42 pp (2018)
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)
Castañeda, A., Rajsbaum, S., Raynal, M.: A Linearizability-based Hierarchy for Concurrent Specifications. To appear in Communications of the ACM, (2022)
Eisenstat, D.: Two-enqueuer queue in Common2. arXiV:0805.O444v2, 12 pp (2009)
Ellen, F., Hendler, D., Shavit, N.: On the inherent sequentiality of concurrent objects. SIAM J. Comput. 41(3), 519–536 (2012)
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)
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)
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)
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)
Hendler, D., Shavit, N., Yerushalmi, L.: A scalable lock-free stack algorithm. J. Parallel Distrib. Comput. 70(1), 1–12 (2010)
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)
Herlihy, M.P.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)
Herlihy, M.P., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann, 508 pp, ISBN 978-0-12-370591-4 (2008)
Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)
Imbs, D., Raynal, M.: Help when needed, but no more: efficient read/write partial snapshot. J. Parallel Distrib. Comput. 72(1), 1–13 (2012)
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)
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)
Lamport, L.: On interprocess communication, Part I: basic formalism. Distrib. Comput. 1(2), 77–85 (1986)
Li, Z.: Non-blocking implementations of queues in asynchronous distributed shared-memory systems. Tech Report, Department of Computer Science, University of Toronto (2001)
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)
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)
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)
Moir, M., Shavit, N.: Concurrent data structures. Handbook of Data Structures and Applications, chapter 47, Chapman and hall/CrC Press, 33 pp (2007)
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)
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)
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)
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)
Rajsbaum, S., Raynal, M.: Mastering concurrent computing through sequential thinking. Commun. ACM 63(1), 78–87 (2020)
Raynal, M.: Concurrent Programming: Algorithms, Principles and Foundations. Springer, 515 pp, ISBN 978-3-642-32026-2 (2013)
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)
Shavit, N.: Data structures in the multicore age. Commun. ACM 54(3), 76–84 (2011)
Shavit, N., Taubenfeld, G.: The computability of relaxed data structures: queues and stacks as examples. Distrib. Comput. 29(5), 395–407 (2016)
Talmage, E., Welch, J.L.: Relaxed data types as consistency conditions. Algorithms 11(5), 61 (2018)
Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Pearson Education/Prentice Hall, 423 pp, ISBN 0-131-97259-6 (2006)
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)