I am reading Nancy Lynch's Distributed Algorithms.
In page 103, there is the FloodSet algorithm. Can anyone please explain what Uj mean in W := W U Uj xj (line 3 of transition function)?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
⋃ is the n-ary union operator, similar to how ∑ is the n-ary addition operator.
So, in the same way that ∑j someExpressionDependingOnJ means "add the values of all the different instances of someExpressionDependingOnJ ranging over all js together", ⋃j someExpressionDependingOnJ means "union the values of all the different instances of someExpressionDependingOnJ ranging over all js together".
X here is the dictionary of all messages indexed by the message sender, Xj is the message from sender j in the dictionary.
Putting all of that together, ⋃j Xj is the union of all messages.
-
$\begingroup$ I guess the "double union" (result of large union of X_j being united with W) is the confusing part. $\endgroup$– U. WindlAug 9, 2021 at 7:18
$\begingroup$
$\endgroup$
Possibly suitable is also to bring general formal definition of union with respect to indexed family:
Suppose we have set $X$, called indices set, and for each $\alpha \in X$ is defined some $U_\alpha$ set. Then, by definition, set
$$\bigcup\limits_{\alpha \in X}U_\alpha=\{x\colon \exists \alpha \in X, x\in U_\alpha\}$$
is called union with respect to indexed family $\{U_\alpha\}_{\alpha \in X}$. If, for example, we take $X=\{1,2\}$, then we obtain usual union of two sets. For $X=\{1, \cdots, n\}$ it is union with respect to $n$ sets asked OP.
