Optimal Deterministic Routing and Sorting on the Congested Clique

Abstract

Consider a clique of n nodes, where in each synchronous round each pair of nodes can exchange O(log n) bits. We provide deterministic constant-time solutions for two problems in this model. The first is a routing problem where each node is source and destination of n messages of size O(log n). The second is a sorting problem where each node i is given n keys of size O(log n) and needs to receive the ith batch of n keys according to the global order of the keys. The latter result also implies deterministic constant-round solutions for related problems such as selection or determining modes.

16 pages, no figures; published at PODC 2013

References in corpus (1)

• Tight Bounds for Parallel Randomized Load Balancing

Cited by in corpus (5)

• Distributed Approximation Algorithms for Weighted Shortest Paths
• MSF and Connectivity in Limited Variants of the Congested Clique
• Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique
• Super-Fast Distributed Algorithms for Metric Facility Location
• A Super-Fast Distributed Algorithm for Bipartite Metric Facility Location