Sparsifying Congested Cliques and Core-Periphery Networks

Abstract : The \emph{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 \emph{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, i.e., 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/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\gg \sqrt{\log n/n}$, a random graph in ${\cal G}_{n,p}$ can, w.h.p., perform the all-to-all communication pattern in $O(\min\{\frac{1}{p^2},n p\})$ rounds. Finally, we show that if the core can emulate the congested clique in $t$ rounds, then there exists a distributed MST construction algorithm performing in $O(t\log n)$ rounds. Hence, for $t=O(1)$, our (deterministic) algorithm improves the best known (randomized) algorithm for constructing MST in core-periphery networks by a factor $\Theta(\log n)$.
Type de document :
Communication dans un congrès
23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2016, Helsinki, Finland. 2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01423688
Contributeur : Pierre Fraigniaud <>
Soumis le : vendredi 30 décembre 2016 - 21:55:43
Dernière modification le : jeudi 13 décembre 2018 - 15:26:38

Identifiants

  • HAL Id : hal-01423688, version 1

Collections

Citation

Pierre Fraigniaud, Balliu Alkida, Zvi Lotker, Olivetti Dennis. Sparsifying Congested Cliques and Core-Periphery Networks. 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2016, Helsinki, Finland. 2016. 〈hal-01423688〉

Partager

Métriques

Consultations de la notice

254