# Algorithm notation

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

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.

• I guess the "double union" (result of large union of X_j being united with W) is the confusing part. Aug 9, 2021 at 7:18

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.