Communication oblivious algorithms achieve tight bounds for sorting and permutation
Communication-Oblivious Permutation and Sorting
Data Structures and Algorithms
Summary
When computers process secret data on cloud servers, the way they communicate can unintentionally leak information. The authors study how to perform fundamental tasks like rearranging or sorting data so that the communication patterns do not depend on the data itself, keeping it more secure. They establish exact minimum communication amounts needed to do this across multiple processors and show differences between sorting just zeros and ones versus general sorting. This helps improve privacy when running computations on untrusted hardware.
What this means in practice
- •For cloud infrastructure engineers: Design cloud computing systems that perform private data sorting with guaranteed data-independent communication patterns for enhanced privacy.
- •For distributed system architects: Develop parallel sorting algorithms that minimize communication while hiding data-dependent patterns, improving security on multiprocessor platforms.
A theory result. No direct application yet.
Authors
Qi Dong, Yilei Wang, Ke Yi
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.