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

<ol>
<li>$\bigcup _i S'(v _i) = S$</li>
<li>For each $v_i$ and $v _j$ such that $i \neq j$, $S'(v _i) \cap S'(v _j) = \emptyset$. </li>
</ol>

<p>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)$. </p>

<p>The problem is quite simple as you notice. The problem is at least as costly as election. My questions though:</p>

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

<p>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. </p>

CC BY-SA 3.0
2012-12-13T02:49:44.153Z
Could you please explain what is $E$?
Alex Golovnev
CC BY-SA 3.0
2012-12-13T03:05:43.180Z
E is the set of edges between the vertices.
AJed
CC BY-SA 3.0
2012-12-13T03:36:42.390Z
Probably, you forgot to describe how the problem depends on $E$. It seems, that $S'(1)=S, \forall i \neq 1, S'(i)=\emptyset$ is a solution.
Alex Golovnev
CC BY-SA 3.0
2012-12-13T03:42:02.453Z
Oh, no. the set $S'(v_i)$ must be a subset of $S(v_i)$. We dont control how the values in $S(v _i)$ are given. - I edited the question
AJed
CC BY-SA 3.0
2012-12-13T03:46:21.910Z
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)$.
Alex Golovnev
CC BY-SA 3.0
2012-12-13T03:52:07.467Z
Yup, this is a sequential algorithm - we are looking for a distributed algorithm better than election somehow (message complexity below $\Omega(n \log n + m)$ perhaps. There is no dependence on $E$ (if i understand u well - other than that you will need to use them for communication - and $G$ is arbitrary since we didnt specify it)
AJed
CC BY-SA 3.0
2012-12-13T06:27:41.937Z
So, it would be probably better to describe the problem more straightforwardly (without referring to graphs). You have a $n$ sets whose union is $S$ and would like to pick a subset of each set, such that your selections partition $S$ (except you allow empty selections). And you are interested in distributed and/or randomized algorithms for the problem. Or is it that the sets are located at nodes and can only communicate along edges?
usul
CC BY-SA 3.0
2012-12-13T09:13:02.973Z
Could you explain why the leader election lower bound for asynchronous networks (i.e. $\Omega(n \log n + m)$ messages) is also a lower bound here?
Peter
CC BY-SA 3.0
2012-12-13T12:43:34.067Z
I think this is a good question, but you need to specify the model of computation. For example, are you interested in synchronous or asynchronous systems? Do you have unique identifiers for your nodes? What is the "cost" here; are you only interested in the message complexity? Also note that if you only allow communication along the edges of $G$, then graph $G$ needs to be connected; otherwise the problem cannot be solved.
Jukka Suomela
CC BY-SA 3.0
2012-12-13T15:08:36.543Z
@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.
Jukka Suomela
CC BY-SA 3.0
2012-12-13T18:03:29.773Z
@JukkaSuomela: thanks.
AJed: The following paper might be of interest to you: Imbs, Rajsbaum, Raynal: *The Universe of Symmetry Breaking Tasks*. (SIROCCO 2011) http://hal.inria.fr/inria-00560453/
However, I don't think it's possible to capture your requirement 1 in this framework.
Peter
CC BY-SA 3.0
2012-12-13T18:19:42.687Z
All: question edited. Peter R: Thank you, I will have a look
AJed
CC BY-SA 3.0
2012-12-13T18:48:13.037Z
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.
Jukka Suomela
CC BY-SA 3.0
2012-12-13T22:02:36.643Z
@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.
AJed
<reference-request><randomized-algorithms><dc.distributed-comp>
Distributed algorithms on sets
AJed
# Distributed algorithms on sets

(Asked by: username_0 on 2012-12-12)

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.

**Tags:** reference-request, randomized-algorithms, dc.distributed-comp
> **Comments:**
> **username_1**: Could you please explain what is $E$?  
> **username_0**: E is the set of edges between the vertices.  
> **username_1**: Probably, you forgot to describe how the problem depends on $E$. It seems, that $S'(1)=S, \forall i \neq 1, S'(i)=\emptyset$ is a solution.  
> **username_0**: Oh, no. the set $S'(v_i)$ must be a subset of $S(v_i)$. We dont control how the values in $S(v _i)$ are given. - I edited the question  
> **username_1**: 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)$.  
> **username_0**: Yup, this is a sequential algorithm - we are looking for a distributed algorithm better than election somehow (message complexity below $\Omega(n \log n + m)$ perhaps. There is no dependence on $E$ (if i understand u well - other than that you will need to use them for communication - and $G$ is arbitrary since we didnt specify it)  
> **username_2**: So, it would be probably better to describe the problem more straightforwardly (without referring to graphs). You have a $n$ sets whose union is $S$ and would like to pick a subset of each set, such that your selections partition $S$ (except you allow empty selections). And you are interested in distributed and/or randomized algorithms for the problem. Or is it that the sets are located at nodes and can only communicate along edges?  
> **username_3**: Could you explain why the leader election lower bound for asynchronous networks (i.e. $\Omega(n \log n + m)$ messages) is also a lower bound here?  
> **username_4**: I think this is a good question, but you need to specify the model of computation. For example, are you interested in synchronous or asynchronous systems? Do you have unique identifiers for your nodes? What is the "cost" here; are you only interested in the message complexity? Also note that if you only allow communication along the edges of $G$, then graph $G$ needs to be connected; otherwise the problem cannot be solved.  
> **username_4**: @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.  
> **username_3**: @JukkaSuomela: thanks. AJed: The following paper might be of interest to you: Imbs, Rajsbaum, Raynal: *The Universe of Symmetry Breaking Tasks*. (SIROCCO 2011) http://hal.inria.fr/inria-00560453/ However, I don't think it's possible to capture your requirement 1 in this framework.  
> **username_0**: All: question edited. Peter R: Thank you, I will have a look  
> **username_4**: 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.  
> **username_0**: @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.  

---

## 0 answers

