Abstract
We present an efficient wait-free implementation of a concurrent priorityqueue in the asynchronous shared memory computational model. In this model each process runs at different speed and might be subject to arbitrarily long delays. The new implementation is based on the heap data structure in which the Insert and DeleteMin operations are long — they take more than one atomic instruction to complete and they leave the heap inconsistent until completed. The previous implementation requires copying the entire data-structure by each processes every time it tries to perform an operation. Consequently its space and time complexity are linear in the number of processes — p and in the size of the data-structure — n. In the new implementation all processes operate directly on the shared copy of the data structure. Its time complexity is O(p log n) and its space complexity is O(n). Moreover, the new implementation is effectively parallel, meaning that all processes can operate effectively on the object, such that the throughput increases as the number of processes increases.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. V. Aho, J.E. Hopcroft, J. D. Ullman. Data Structures and Algorithms. pages 139–145.
J. Alemany, E. W. Felten. Performance Issues in Non-blocking Synchronization on Shared-memory Multiprocessors. In Proceedings of the 11th ACM Symposium on Principles of Distributed Computing, pages 124–134, August 1992.
Aspnes J. and M. Herlihy, Fast Randomized Consensus Using Shared Memory, Jour. of Algorithms, Vol. 11, pages 441–461, September 1990.
J. Aspnes, Time-and Space-Efficient Randomized Consensus, Proceedings of the 9th ACM Conference on Principles of Distributed Computing, August 1990, pages 325–331.
R. J. Anderson, H. Woll. Wait-Free parallel algorithms for the union-find problem. In Proceedings of the 23rd ACM Symposium on Theory of Computation, pages 370–380, May 1991.
B. Chor, A. Israeli, and M. Li, “On Processors Coordination Using Asynchronous Hardware, Proceedings of the 6th ACM Conference on Principles of Distributed Computing, pages 86–97, August 1987.
M. P. Herlihy. Impossibility and universality results for wait-free synchronization. In Seventh ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 1988.
M. P. Herlihy. A methodology for implementing highly concurrent data structures. DEC Cambridge Research Lab Technical report 91/10.
M. P. Herlihy, J. E. B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. DEC Cambridge Research Lab Technical report 92/7.
M. Herlihy and J. Wing. Linearizability: A correctness condition for concurrent objects. In ACM TOPLAS, 12(3):463–492, 1990.
A. Israeli and L. Rappoport, Efficient Wait-Free Implementation of a Concurrent Priority Queue. Tehnion, Faculty of Computer Science, Technical report 781.
Loui M. C. and H. H. Abu-Amara, Memory Requirements for Agreement among Unreliable Asynchronous Processes, Advances in Computing Research, JAI press, 1987, pages 163–183.
L. Lamport, “On Interprocess Communication. Part I: Basic Formalism”, Distributed Computing 1, 2 1986, pages 77–85.
L. Lamport, “On Interprocess Communication. Part II: Algorithms”, Distributed Computing 1, 2 1986, pages 86–101.
G.L. Peterson, Concurrent reading while writing, ACM Transactions on Programming Languages and Systems, Vol. 5, No. 1, pages 46–55.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Israeli, A., Rappoport, L. (1993). Efficient wait-free implementation of a concurrent priority queue. In: Schiper, A. (eds) Distributed Algorithms. WDAG 1993. Lecture Notes in Computer Science, vol 725. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57271-6_23
Download citation
DOI: https://doi.org/10.1007/3-540-57271-6_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57271-8
Online ISBN: 978-3-540-48029-7
eBook Packages: Springer Book Archive