Skeap & Leap: Scalable Distributed Priority Queues for constant and arbitrary Priorities

Abstract

We propose two protocols for distributed priority queues (denoted by 'heap' for simplicity in this paper) called SKEAP and LEAP. SKEAP realizes a distributed heap for a constant amount of priorities and LEAP 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 LEAP we provide a novel distributed protocol for the \(k\)-selection problem that runs in time \(\mathcal O(\log n)\) w.h.p. SKEAP guarantees sequential consistency for its heap operations, while LEAP guarantees linearizability. SKEAP and LEAP provide logarithmic runtimes w.h.p. on all their operations.