<p>I'm assuming that you mean the Flood Set algorithm for solving the agreement problem in Section 6.2 of [1]. The Flood Set algorithm proceeds in rounds and requires every process $u$ to forward all received values, which it stores in a set $W$; initially $W$ contains $u$'s input value. We assume that $f$ processes can be faulty. After $f+1$ rounds, every alive process $u$ checks if its set $W$ is a singleton. If so, $u$ decides on the singleton value, otherwise $u$ decides on a default value $x$. It can easily be shown that after $f+1$ rounds, all correct processes have the same set $W$. </p>

<p>For a general graph, the answer is obviously no: Suppose that the network is cut by a faulty process $u$ into parts $C_0$ and $C_1$ and processes in $C_0$ start with $0$ whereas processes in $C_1$ start with $1$. If $u$ crashes initially, the following happens in round $f+1$: all processes in $C_0$ will decide on $0$ and all processes in $C_1$ will decide on $1$.</p>

<p>Note that this impossibility argument holds for <em>any</em> agreement algorithm.</p>

<p>[1] Nancy Lynch. Distributed Computing. Publisher: Morgan Kaufmann</p>

CC BY-SA 3.0
2012-03-13T04:44:34.537Z
2012-03-13T04:44:34.537Z
Peter
<p>I would like to ask how could someone modify FloodSet algorithm to work in a general network,
where process failures happen..Is it possible for it to work if a "crucial" [1] failure happens?</p>

<p>[1]: As crucial i mean a failure in a process that "cuts" the network in two separate pieces</p>

CC BY-SA 3.0
2012-03-12T12:40:29.203Z
Care to explain what the “FloodSet algorithm” is?
Tsuyoshi Ito
<dc.distributed-comp>
FloodSet in general networks
George Tseres
# FloodSet in general networks

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

I would like to ask how could someone modify FloodSet algorithm to work in a general network,
where process failures happen..Is it possible for it to work if a "crucial" [1] failure happens?

[1]: As crucial i mean a failure in a process that "cuts" the network in two separate pieces

**Tags:** dc.distributed-comp
> **Comments:**
> **username_1**: Care to explain what the “FloodSet algorithm” is?  

---

## 1 answers

### Answer by username_2 on 2012-03-13. Score: 3

I'm assuming that you mean the Flood Set algorithm for solving the agreement problem in Section 6.2 of [1]. The Flood Set algorithm proceeds in rounds and requires every process $u$ to forward all received values, which it stores in a set $W$; initially $W$ contains $u$'s input value. We assume that $f$ processes can be faulty. After $f+1$ rounds, every alive process $u$ checks if its set $W$ is a singleton. If so, $u$ decides on the singleton value, otherwise $u$ decides on a default value $x$. It can easily be shown that after $f+1$ rounds, all correct processes have the same set $W$.

For a general graph, the answer is obviously no: Suppose that the network is cut by a faulty process $u$ into parts $C\_0$ and $C\_1$ and processes in $C\_0$ start with $0$ whereas processes in $C\_1$ start with $1$. If $u$ crashes initially, the following happens in round $f+1$: all processes in $C\_0$ will decide on $0$ and all processes in $C\_1$ will decide on $1$.

Note that this impossibility argument holds for *any* agreement algorithm.

[1] Nancy Lynch. Distributed Computing. Publisher: Morgan Kaufmann


---

