Given a connected arbitrary network $G = (V,E)$, where $V$ is a set of nodes (processors) and $E$ is the set of edges between the nodes. Each node $v _i$ is assigned a non-empty set $S(v _i)$, where $\bigcup _i S(v _i) = S$. The set $S$ is a universe of size $k$. The objective is to let each node $v _i$ find a subset $S'(v _i) \subseteq S(v _i)$ such that (by simply communicating with each other).
- $\bigcup _i S'(v _i) = S$
- For each $v_i$ and $v _j$ such that $i \neq j$, $S'(v _i) \cap S'(v _j) = \emptyset$.
The idea is that no two set $S'(v_i)$ and $S'(v _j)$ share any common elements, while a set $S'(v _i)$ may be empty. Yet, every element of $S$ must be in a set $S'(v _i)$.
The problem is quite simple as you notice. The problem is at least as costly as election. My questions though:
- Are there similar problems to this problem (note that the sets are not processors !)
- Do you think there are efficient randomized distributed algorithms for this problem ? Any hints for some techniques that may help break the election bound. (By randomized: I mean I may relax the Req2. such that some nodes have intersecting sets, but not many of them).
Note: any computational model would be accepted (I m just looking for hints). But asynchronous computational model with unique ID's is perhaps the most preferred.
