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

  1. $\bigcup _i S'(v _i) = S$
  2. 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:

  1. Are there similar problems to this problem (note that the sets are not processors !)
  2. 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.

  • 1
    $\begingroup$ Thank you, but I still don't understand the dependence on $E$. Seems that we can set $S'(i)=S(i)\setminus\bigcup_{j<i}S'(j)$. $\endgroup$ – Alex Golovnev Dec 13 '12 at 3:46
  • 3
    $\begingroup$ @Peter: If you set and $S(v_i) = S = \{1\}$ for all $i$, then the problem is equal to leader election; precisely one node has to announce $S'(v_i) = \{1\}$. But of course whether the lower bound applies depends on the model of computation. $\endgroup$ – Jukka Suomela Dec 13 '12 at 15:08
  • 1
    $\begingroup$ @JukkaSuomela: thanks. AJed: The following paper might be of interest to you: Imbs, Rajsbaum, Raynal: The Universe of Symmetry Breaking Tasks. (SIROCCO 2011) hal.inria.fr/inria-00560453 However, I don't think it's possible to capture your requirement 1 in this framework. $\endgroup$ – Peter Dec 13 '12 at 18:03
  • 4
    $\begingroup$ I think the problem could be rephrased so that the connection with the leader election problem is even more clear. In essence, we are running here $k$ leader election processes in parallel: As input, we have $i \in S(v)$ if node $v$ participates in the leader election process number $i$. As output, we have $i \in S'(v)$ if node $v$ wins the leader election process $i$. We cannot solve this problem faster than leader election; a trivial upper bound is $k$ parallel executions of a leader election algorithm; but the key question is whether this can be solved as fast as single leader election. $\endgroup$ – Jukka Suomela Dec 13 '12 at 18:48
  • 1
    $\begingroup$ @JukkaSuomela to be more precise, it would be enough to do one election + (k - 1) traversals. If the msg size is big enough (i.e. $O(k)$) then it we would need $\Theta(1)$ traversal. $\endgroup$ – AJed Dec 13 '12 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.