Sparsifying congested cliques and core-periphery networks Conference Paper uri icon


  • The core-periphery network architecture proposed by Avin et al. ICALP 2014 was shown to support fast computation for many distributed algorithms, while being much sparser than the congested clique. For being efficient, the core-periphery architecture is however bounded to satisfy three axioms, among which is the capability of the core to emulate the clique, ie, to implement the all-to-all communication pattern, in O (1) rounds in the CONGEST model. In this paper, we show that implementing all-to-all communication in k rounds can be done in n- node networks with roughly n^ 2/kn 2/k edges, and this bound is tight. Hence, sparsifying the core beyond just saving a fraction of the edges requires to relax the constraint on the time to simulate the congested clique. We show that, for p ≫\log n/np≫ log n/n, a random graph in G _ n, p G n, p can, whp, perform the all-to-all communication pattern in O (\min {1 p^ 2 …

publication date

  • January 1, 2016