1
$\begingroup$

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

enter image description here

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I guess the "double union" (result of large union of X_j being united with W) is the confusing part. $\endgroup$
    – U. Windl
    Aug 9, 2021 at 7:18
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.