---
_id: '8534'
abstract:
- lang: eng
text: "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. \r\nSKEAP
and SEAP provide logarithmic runtimes w.h.p. on all their operations with SEAP
having to use only O(log n) bit messages."
author:
- first_name: Michael
full_name: Feldmann, Michael
id: '23538'
last_name: Feldmann
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Feldmann M, Scheideler C. Skeap & Seap: Scalable Distributed Priority
Queues for Constant and Arbitrary Priorities. In: *Proceedings of the 31st ACM
Symposium on Parallelism in Algorithms and Architectures (SPAA)*. ACM; 2019:287--296.'
apa: 'Feldmann, M., & Scheideler, C. (2019). Skeap & Seap: Scalable Distributed
Priority Queues for Constant and Arbitrary Priorities. In *Proceedings of the
31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)* (pp.
287--296). ACM.'
bibtex: '@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} }'
chicago: 'Feldmann, Michael, and Christian Scheideler. “Skeap & Seap: Scalable
Distributed Priority Queues for Constant and Arbitrary Priorities.” In *Proceedings
of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)*,
287--296. ACM, 2019.'
ieee: 'M. Feldmann and C. Scheideler, “Skeap & Seap: Scalable Distributed Priority
Queues for Constant and Arbitrary Priorities,” in *Proceedings of the 31st ACM
Symposium on Parallelism in Algorithms and Architectures (SPAA)*, 2019, pp.
287--296.'
mla: 'Feldmann, Michael, and Christian Scheideler. “Skeap & Seap: Scalable Distributed
Priority Queues for Constant and Arbitrary Priorities.” *Proceedings of the
31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)*,
ACM, 2019, pp. 287--296.'
short: 'M. Feldmann, C. Scheideler, in: Proceedings of the 31st ACM Symposium on
Parallelism in Algorithms and Architectures (SPAA), ACM, 2019, pp. 287--296.'
date_created: 2019-03-21T14:37:26Z
date_updated: 2019-07-10T10:20:08Z
department:
- _id: '79'
external_id:
arxiv:
- '1805.03472'
language:
- iso: eng
page: 287--296
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
publisher: ACM
status: public
title: 'Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary
Priorities'
type: conference
user_id: '477'
year: '2019'
...