conference paper
Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary Priorities
Michael
Feldmann
author 23538
Christian
Scheideler
author 20792
79
department
SFB 901
project
SFB 901 - Project Area A
project
SFB 901 - Subproject A1
project
We propose two protocols for distributed priority queues (denoted by 'heap' for simplicity in this paper) called SKEAP and SEAP. SKEAP realizes a distributed heap for a constant amount of priorities and SEAP one for an arbitrary amount. Both protocols build on an overlay, which induces an aggregation tree on which heap operations are aggregated in batches, ensuring that our protocols scale even for a high rate of incoming requests. As part of SEAP we provide a novel distributed protocol for the k-selection problem that runs in time O(log n) w.h.p. SKEAP guarantees sequential consistency for its heap operations, while SEAP guarantees serializability. SKEAP and SEAP provide logarithmic runtimes w.h.p. on all their operations.
SKEAP and SEAP provide logarithmic runtimes w.h.p. on all their operations with SEAP having to use only O(log n) bit messages.
ACM2019
eng
Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
1805.03472
287--296
M. Feldmann, C. Scheideler, in: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, 2019, pp. 287--296.
M. Feldmann and C. Scheideler, “Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary Priorities,” in <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2019, pp. 287--296.
Feldmann, M., & Scheideler, C. (2019). Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary Priorities. In <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i> (pp. 287--296). ACM.
Feldmann M, Scheideler C. Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary Priorities. In: <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. ACM; 2019:287--296.
@inproceedings{Feldmann_Scheideler_2019, title={Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary Priorities}, booktitle={Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, publisher={ACM}, author={Feldmann, Michael and Scheideler, Christian}, year={2019}, pages={287--296} }
Feldmann, Michael, and Christian Scheideler. “Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary Priorities.” <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, ACM, 2019, pp. 287--296.
Feldmann, Michael, and Christian Scheideler. “Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary Priorities.” In <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 287--296. ACM, 2019.
85342019-03-21T14:37:26Z2019-07-10T10:20:08Z