Optimal deterministic routing and sorting on the congested clique
Consider a clique of <i>n</i> nodes, where in each synchronous round each pair of nodes can exchange <i>O(log n)</i> 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 <i>n</i> messages of size <i>O(log n)</i>. The second is a sorting problem where each node <i>i</i> is given <i>n</i> keys of size <i>O(log n)</i> and needs to receive the <i>i<sup>th</sup></i> batch of <i>n</i> 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.