arXiv preprint ·
Communication-Oblivious Permutation and Sorting
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
With the help of secure hardware such as trusted execution environments (TEEs), private data can be uploaded and computed in untrusted cloud clusters, so that an adversary controlling the cloud can only see the data in encrypted form. However, the communication pattern between the processors may still reveal sensitive information about the data, so it is important to develop parallel algorithms in the BSP model whose communication pattern is independent of the input data, a property known as \textit{communication obliviousness}. In this paper, we study such algorithms for three fundamental problems: permutation, sorting, and 0-1 sorting. For the first two problems, we prove a tight (up to lower-order terms) communication complexity of $(2-2/p)n\pm o(n)$. Here, $p$ is the number of processors and $n$ is the input size, assuming $2\le p$ and $p=o(n^{1/3})$. Our lower bound holds regardless of the number of rounds and local memory size, while for balanced permutation and sorting the upper bound is achieved in a constant number of rounds with load at most $n/p+o(n/p)$. For 0-1 sorting, we also derive a tight communication complexity of $C_{\mathrm{cut}}(p) \cdot n \pm o(n)$, where $C_{\mathrm{cut}}(p)$ is the optimal value of a linear program parameterized by $p$. Although there appears to be no closed-form for $C_{\mathrm{cut}}(p)$, we show that it is strictly smaller than $2-2/p$ for all $p\ge 3$, thus separating 0-1 sorting from general sorting in terms of their communication complexity.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.