# Does such model exists?

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?

• Should $V_i \subseteq V$ be $E_i \subseteq E$? Similarly, for part 4. – Denis Pankratov Jan 10 '16 at 15:24

## 1 Answer

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"):

See also this work for closely related models:

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$.