Abstract
Shared pools and stacks are two coordination structures with a history of applications ranging from simple producer/consumer buffers to job-schedulers and procedure stacks. This paper introduces elimination trees, a novel form of diffracting trees that offer pool and stack implementations with superior response (on average constant) under high loads, while guaranteeing logarithmic time ``deterministic'' termination under sparse request patterns.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received February 28, 1996, and in final form January 23, 1997.
Rights and permissions
About this article
Cite this article
Shavit, N., Touitou, D. Elimination Trees and the Construction of Pools and Stacks. Theory Comput. Systems 30, 645–670 (1997). https://doi.org/10.1007/s002240000072
Published:
Issue Date:
DOI: https://doi.org/10.1007/s002240000072