Mohsen Ghaffari and Hsin-Hao Su: Generalizing the Congested Clique

Abstract: The congested clique model of distributed computing has received increasingly more attention in the past few years. In this model, the system is composed of n processors/nodes which are connected via a complete communication graph K_n, where per round, each two nodes can exchange O(log n) bits. With the goal of generalizing this communication model, we study the following two questions: 

1. Given an arbitrary n-node network G, how can we efficiently simulate one round of the congested clique K_n in G, i.e., how can we deliver one O(log n)-bit message from each node to each other node? This would provide a black-box method for transforming congested clique algorithms to algorithms for more general networks.
    
2. How can we design efficient graph algorithms for networks that are sparse approximations of the clique (expanders), e.g., networks with edge-expansion at least 1/polylog n and maximum degree at most polylog n. We specifically show distributed algorithms with round complexity of 2^{O(sqrt{log n log log n})} for problems such as Minimum Spanning Trees and Minimum Cut.