Exercise 21: failure detector implementation and its properties.

[dag7dev]

Exercise 21: Show a possible implementation of a failure detector and discuss its properties.

[simonesestito]

Can we use the naive approach where a FD always says that everyone is dead? It's easier, but idk if too easy

[susannacifani]

Can we recycle this question-solution from Drive? Because our question seems quite open to me

[Tommaso-Sgroi]

There are various possible solutions for implementing a failure detector, all solutions may be transformed into strong failure detectors. A simple and strong way to do it is to force all nodes to send an “im alive” message to all other nodes. When a node doesn't receive the “im alive” message in a time ΔT + 𝛅 it suppose that node is dead. After time ΔT + 𝛅 (the same as timeout) all processes exchange their suspect set and update their. The update must work as follow:

• if node i is suspected by other node but not me: ignore.
• if node is not suspected by other node but from me: remove node from suspected and increase 𝛅.
• if all nodes suspect a node dead: add it to the suspected list.

Properties:

• Strong completeness, all processes that crash will be detected by all other correct processes; that’s because. If a process suspects another process after time ΔT + 𝛅 (because it didn't receive the live message), receiving the table of suspects from all other processes, it can assume that it is alive if another process doesn't suspect it because it received the live message before its timeout.
• Strong accuracy: there is a time after which correct processes are not suspected by any correct process. In the update step when a process receives the other table, if there is a conflict for a process, the process table is updated with the “alive” value. So even the process that suspected the dead of a process that’s alive won’t suspect it anymore.