Source-linked AI summary
Optimal Deterministic Routing and Sorting on the Congested Clique
Christoph Lenzen
TL;DR
The paper studies communication limits in fully connected systems with O(log n)-bit bandwidth per edge per round. It develops deterministic routing and sorting techniques, solving the two problems in 16 and 37 rounds, respectively.
Problem
The paper asks what communication is required for distributed tasks in fully connected systems with O(log n) bits exchanged per edge per round.
Method
The paper uses deterministic routing schemes based on structured edge colorings and known source-destination information to distribute messages and keys.
Results
16 rounds solves the routing problem, while 37 rounds solves the sorting problem.
Takeaways & Limitations
The presented techniques handle most message and key-size ranges asymptotically optimally and support related problems such as selection and determining modes.
Takeaways & Limitations
For unknown sources and destinations, some worst-case inputs require forwarding information that prevents constant-round delivery of all messages.
Abstract
from arXiv · showhide
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.
1 Introduction & Related Work
The paper studies communication-limited distributed algorithms on fully connected systems, where bandwidth constraints make routing and sorting nontrivial despite abundant connectivity. It gives deterministic constant-round solutions for both tasks and connects sorting to related problems.
- Communication limitations remain fundamental because sending complete inputs or outputs to every node is typically too expensive.
- Constant-diameter networks can still require strong lower bounds when bandwidth limits which information nodes communicate.
- The paper studies fully connected n-node systems with O(log n) bits exchanged per round and edge.
- Routing delivers each node’s messages to their destinations, while sorting assigns globally ordered key batches to nodes.
- The deterministic approach achieves bandwidth-efficient communication using a single-level recursive-sorting style rather than random intermediate destinations.
- The results also cover local computation and memory constraints, with asymptotically optimal bounds across almost the entire parameter range.
2 Model
The model is a fully connected synchronous system in which nodes communicate independently over every edge using O(log n)-size messages. Nodes may send different messages to different neighbors in each round.
- The system is the complete graph on n uniquely identified nodes, with synchronous rounds and arbitrary finite local computation.
- Each node sends one O(log n)-bit message to every other node in each round.
- A node can send different messages along its edges, conveying Θ(n log n) bits per round rather than broadcasting one common message.
- Basic arithmetic on O(log n)-sized values counts as one computational step.
3 Routing
The paper formulates an information distribution task in which every node sends and receives n O(log n)-bit messages, then develops deterministic routing primitives and combines them into a 16-round solution. The construction uses edge-coloring, √n-sized node partitions, and constant-round subroutines, including a 4-round restricted routing scheme.
- Problem formulation: Each node is given n O(log n)-bit messages, and the goal is to deliver all messages to their destinations while minimizing rounds.The formulation assumes each node sends and receives exactly n messages; instances with at most n messages per node require no change.
- Basic communication primitives: Kőnig’s line-coloring theorem decomposes the regular bipartite multigraph of messages into matchings that determine collision-free communication patterns.The authors use these colorings to coordinate messages locally and efficiently, including a two-round routing result when source and destination information is known in advance.
- Basic communication primitives: 4 rounds suffice when messages are restricted to a node subset W of size at most √n and each node sends and receives f|W| messages.Two rounds establish the required source-destination counts, followed by two rounds that deliver the original messages.
- Information distribution algorithm: The algorithm partitions nodes into √n-sized subsets and uses intermediate routing steps to organize messages by their source and destination subsets.Messages moved to another node are stored there as copies and use that node as their subsequent source; the high-level strategy combines these moves with the restricted routing primitives.
- Round complexity: 7 rounds implement Step 2 and 4 rounds implement Step 3, while the complete information distribution task is solved deterministically within 16 rounds.The 7-round bound follows from 2+0+2+0+2+1 rounds, and the construction extends to arbitrary n without increasing the running time.
- Coordination constraint: The algorithm’s intermediate coordination is limited by initially unknown message counts across destination subsets, which are resolved using information gathered during the procedure.Nodes cannot initially determine exact message colors because they lack other nodes’ counts and therefore cannot yet know global message indices.
4 Sorting
The paper gives a deterministic sorting algorithm for distributing globally ordered keys across nodes. It sorts keys through sampled delimiters, subset-based subroutines, redistribution, and constant-round communication.
- Problem 4.1 asks node i to learn keys with indices i(n − 1) + 1 through in in the global order of all keys.
- 4.1 Sorting Fewer Keys with Fewer Nodes: The subset subroutine sorts 2n3/2 keys among √n nodes, with each node learning its keys’ global indices within the subset.
- 4.1 Sorting Fewer Keys with Fewer Nodes: The subroutine selects local samples, exchanges them, constructs delimiters, partitions keys into delimiter-defined subsets, redistributes them, and locally sorts the received keys.
- 4.1 Sorting Fewer Keys with Fewer Nodes: The delimiter partition is correct because all nodes compute the same delimiters, while local sorting and order-preserving redistribution produce the global order.
- 4.1 Sorting Fewer Keys with Fewer Nodes: The subset routine completes in 10 rounds using only edges incident to the participating subset.
- 4.2 Sorting All Keys: The full algorithm partitions nodes into √n subsets, uses the subroutine to sort redistributed keys, and solves Problem 4.1 in 37 rounds.
- 4.2 Sorting All Keys: The variant that determines each input key’s index in the global enumeration of distinct keys is solvable deterministically in a constant number of rounds.
5 Local Computations and Memory Requirements
The implementation achieves deterministic constant-round routing while keeping local computation and memory within O(n log n) per node. Bipartite edge coloring is adapted by reducing the relevant multigraphs to O(n) edges.
- Steps 3 and 4 of Algorithm 1 can be executed in 3 rounds with O(n) local computation per node.
- This 3-round implementation saves two rounds relative to Corollary 5.2 but doubles the message size in Step 4.
- Steps 3 to 5 of Algorithm 2 can be executed in 2 rounds with O(n) local computation per node.
- A variant of Algorithm 2 executes Step 2 of Algorithm 1 in 5 rounds using O(n log n) local computation and memory bits per node.
- The implementation is simultaneously efficient in running time, message size, local computation, and memory consumption.
- Problem 3.1 is solved deterministically in 12 rounds with O(n log n) computation and O(n log n) memory bits per node.
- The result transfers to Problem 4.1 and its variant, which are solvable in a constant number of rounds with O(n log n) computation and memory per node.
6 Varying Message and Key Size
The paper extends its results to varying message, key, and bandwidth sizes. Communication complexity is governed by the bits sent and received per node, while small-message routing remains constrained when destinations are unknown.
- For message or key size Θ(log n), bandwidth B ∈ O(log n) bits per edge per round suffices, while smaller B increases the required rounds.
- Values larger than O(log n) bits can be split into multiple messages when bandwidth is insufficient for one value per message.
- 6.1 Large Messages or Keys: With B ∈ Θ(log n), a Θ(log^2 n)-bit key is split into Θ(log n) messages, showing that per-node bit volume—not merely message or key count—determines complexity.
- 6.1 Large Messages or Keys: When each node must send or receive Ω(n log n) bits, the presented techniques are asymptotically optimal.
- 6.2 Small Messages: If message sources and destinations are known in advance, small messages can be routed in constant rounds under additional sender-identification assumptions.
- 6.2 Small Messages: If sources and destinations are unknown, Ω(n^2) messages may require explicit destination information totaling Ω(n^2 log n) bits, so small messages do not simplify Problem 3.1.
- 6.3 Small Keys: For o(log n)-bit keys, static node assignments and bit-level communication can order duplicate keys and support larger total key sets.