<p>The model studied in the following work should be a fairly close match with the model that you described (see in particular graph problems "without edge duplication"):</p>

<ul>
<li>Woodruff &amp; Zhang: "When Distributed Computation is Communication Expensive" <a href="http://arxiv.org/abs/1304.4636" rel="nofollow">http://arxiv.org/abs/1304.4636</a></li>
</ul>

<p>See also this work for closely related models:</p>

<ul>
<li>Klauck et al.: "Distributed Computation of Large-scale Graph Problems" <a href="http://arxiv.org/abs/1311.6209" rel="nofollow">http://arxiv.org/abs/1311.6209</a></li>
</ul>

<p>You may also be interested in the "congested clique" model, which is the special case such that $k = |V|$ and computer number $i$ is aware of the edges incident to node number $i$.</p>

CC BY-SA 3.0
2016-01-10T11:55:12.330Z
2016-01-10T11:55:12.330Z
Jukka Suomela
<p>I have a problem on distributed graph, with the following model: <br>
1. There is a Global Graph $G=(V,E)$ <br>
2. There are $k$ computers. <br>
3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the graph, i.e. $V$, and subset of the edges, i.e. computer $i$ knows $V_i \subseteq V$. <br>
4. Each computer observes different subset of edges, i.e., for all $i,j$ : $V_i \cap V_j = \emptyset$. <br></p>

<p>I searched for papers which handle the same model, but I didn't find anything. Do you know if such model is being studied?</p>

CC BY-SA 3.0
2016-01-10T15:24:16.933Z
Should $V_i \subseteq V$ be $E_i \subseteq E$? Similarly, for part 4.
Denis Pankratov
<graph-theory><graph-algorithms><dc.distributed-comp><dc.parallel-comp><network-modeling>
Does such model exists?
Guest Y
# Does such model exists?

(Asked by: username_0 on 2016-01-10)

I have a problem on distributed graph, with the following model:   
1. There is a Global Graph $G=(V,E)$   
2. There are $k$ computers.   
3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the graph, i.e. $V$, and subset of the edges, i.e. computer $i$ knows $V\_i \subseteq V$.   
4. Each computer observes different subset of edges, i.e., for all $i,j$ : $V\_i \cap V\_j = \emptyset$.

I searched for papers which handle the same model, but I didn't find anything. Do you know if such model is being studied?

**Tags:** graph-theory, graph-algorithms, dc.distributed-comp, dc.parallel-comp, network-modeling

> **Comments:**
> **username_1**: Should $V_i \subseteq V$ be $E_i \subseteq E$? Similarly, for part 4.  

---

## 1 answers

### Answer by username_2 on 2016-01-10. Score: 3

The model studied in the following work should be a fairly close match with the model that you described (see in particular graph problems "without edge duplication"):

* Woodruff & Zhang: "When Distributed Computation is Communication Expensive" <http://arxiv.org/abs/1304.4636>

See also this work for closely related models:

* Klauck et al.: "Distributed Computation of Large-scale Graph Problems" <http://arxiv.org/abs/1311.6209>

You may also be interested in the "congested clique" model, which is the special case such that $k = |V|$ and computer number $i$ is aware of the edges incident to node number $i$.


---

