Minimum Spanning Tree and other Problems in O(1) Rounds of Congested Clique

28^th March 2019, 12:00
Tomasz Jurdzinski
Wroclaw University

Abstract

We present a distributed randomized algorithm finding Minimum Spanning Tree (MST) of a given graph in O(1) rounds, with high probability, in the Congested Clique model. The input graph in the Congested Clique model is a graph of n nodes, where each node initially knows only its incident edges. The communication graph is a clique with limited edge bandwidth: each two nodes (not necessarily neighbours in the input graph) can exchange O(log n) bits. As discovered recently, the Congested Clique model is closely connected to more realistic models of parallel and distributed computing, as MapReduce or MPC (massive
parallel computing).

We develop a new sparsification technique which reduces the connected components problem in O(1) rounds to its two restricted instances. The former instance has a graph with maximal degree O(log log n) as the input – here our sparsification technique helps. In the latter instance, a partition of the input graph into O(n/log log n) connected components is known. This gives an opportunity to apply previous results to determine connected components as well as MST in O(1) rounds.

Our result improves over previous O(log* n) algorithm of Ghaffari et al. [PODC 2016], O(log log log n) algorithm of Hegeman et al. [PODC 2015] and the O(log log n) algorithm of Lotker et al. [SICOMP 2005] It also determines Theta(1) round complexity in the congested clique for MST, as well as other graph problems, including bipartiteness, cut verification, s–t connectivity, cycle containment and O(log Delta) round complexity of the maximal independent set (MIS).