Multiprocess time queue
2001 (English)In: Algorithms and Computation: 12th International Symposium, ISAAC 2001, Christchurch, New Zealand, December 19-21, 2001. / [ed] Peter Eades; Tadao Takaoka, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2001, 599-609 p.Conference paper (Refereed)
We show how to implement a bounded time queue for two different processes. The time queue is a variant of a priority queue with elements from a discrete universe. The bounded time queue has elements from a discrete bounded universe. One process has time constraints and may only spend constant worst case time on each operation while the other process may spend more time. The time constrained process only has to be able to perform some of the time queue operations while the other process has to be able to perform all operations. We show how to do a deamortization of the deleteMin cost and to provide mutual exclusion for the parts of the data structure that both processes maintain.
Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2001. 599-609 p.
Lecture Notes in Computer Science, ISSN 0302-9743 ; 2223
Research subject Dependable Communication and Computation Systems
IdentifiersURN: urn:nbn:se:ltu:diva-38256DOI: 10.1007/3-540-45678-3_51Local ID: c98690e0-a0ac-11db-8975-000ea68e967bOAI: oai:DiVA.org:ltu-38256DiVA: diva2:1011755
International Symposium on Algorithms and Computation : 19/12/2001 - 21/12/2001
Godkänd; 2001; 20060922 (ysko)2016-10-032016-10-03Bibliographically approved