Can I read Graph Reconstruction in the Congested Clique on EtoBox?

Graph Reconstruction in the Congested Clique by Montealegre, Pedro; Perez-Salazar, Sebastian; Rapaport, Ivan; Todinca, Ioan is a scholarly article available to read on EtoBox.

What is Graph Reconstruction in the Congested Clique about?

The congested clique model is a message-passing model of distributed computation where the underlying communication network is the complete graph of $n$ nodes. In this paper we consider the situation where the joint input to the nodes is an $n$-node labeled graph $G$, i.e., the local input received by each node is the indicator function of its neighborhood in $G$. Nodes execute an algorithm, communicating with each other in synchronous rounds and their goal is to compute some function that depends on $G$. In every round, each of the $n$ nodes may send up to $n-1$ different $b$-bit messages through each of its $n-1$ communication links. We denote by $R$ the number of rounds of the algorithm. The product $Rb$, that is, the total number of bits received by a node through one link, is the cost of the algorithm. The most difficult problem we could attempt to solve is the reconstruction problem, where nodes are asked to recover all the edges of the input graph $G$. Formally, given a class of graphs $\mathcal G$, the problem is defined as follows: if $G \notin {\mathcal G}$, then every node must reject; on the other hand, if $G \in {\mathcal G}$, then every node must end up, after the $R$

Author

Montealegre, Pedro; Perez-Salazar, Sebastian; Rapaport, Ivan; Todinca, Ioan

Published

2017

Language

EN