Efficient distributed algorithms for holistic aggregation functions on random regular graphs

In this paper, we propose efficient distributed algorithms for three holistic aggregation functions on random regular graphs that are good candidates for network topology in next-generation data centers. The three holistic aggregation functions include SELECTION (select the k-th largest or smallest element), DISTINCT (query the count of distinct elements), MODE (query the most frequent element). We design three basic techniques — Pre-order Network Partition, Pairwise-independent Random Walk, and Random Permutation Delivery, and devise the algorithms based on the techniques. The round complexity of the distributed SELECTION is Θ(log N) which meets the lower bound where N is the number of nodes and each node holds a numeric element. The round complexity of the distributed DISTINCT and MODE algorithms are O(log3N / log log N) and O(log2N log log N) respectively. All of our results break the lower bounds obtained on general graphs and our distributed algorithms are all based on the $${\cal C}{\cal O}{\cal N}{\cal G}{\cal E}{\cal S}{\cal T}$$ model, which restricts each node to send only O(log N) bits on each edge in one round under synchronous communications.