Next: Checkpointing for Recovery Up: Figures in the book Previous: Failure Detectors

Solvable Problems in Asynchronous Systems

**Figure:** Implementation of an IO detector using a $\Diamond\;\cal{W}$ detector
$\fbox{\begin{minipage}{\textwidth}\sf \begin{tabbing} x\=xxxx\=xxxx\=xxxx\=xxxx\... ...$;\\ \> \> $IO.suspects := EW.suspects - \{ i \}$; \end{tabbing}\end{minipage}}$

**Figure:** Implementation of an IO detector
$\fbox{\begin{minipage}{\textwidth}\sf \begin{tabbing} x\=xxxx\=xxxx\=xxxx\=xxxx\... ...\> \> $IO.suspects := IO.suspects \cup \{ i \}$;\\ \end{tabbing}\end{minipage}}$

**Figure:** A detector that does not satisfy IO accuracy
$\fbox{\begin{minipage}{\textwidth}\sf \begin{tabbing} x\=xxxx\=xxxx\=xxxx\=xxxx\... ... $P_i$\\ \> \> send \lq\lq I am alive'' to $P_i$\\ \\ \end{tabbing}\end{minipage}}$

**Figure:** An algorithm for the alive token problem
$\fbox{\begin{minipage}{\textwidth}\sf \begin{tabbing} x\=xxxx\=xxxx\=xxxx\=xxxx\... ...i)$ {\bf then}\\ \> \> $token := f\!alse;$\\ \\ \end{tabbing}\end{minipage}}$

**Figure:** An algorithm that eventually guarantees a single token
$\fbox{\begin{minipage}{\textwidth}\sf \begin{tabbing} x\=xxxx\=xxxx\=xxxx\=xxxx\... ...cket[j] > ticket[i])) \wedge \neg suspected[i]$\par \end{tabbing}\end{minipage}}$

**Figure:** An algorithm for solving the -set consensus problem
$\fbox{\begin{minipage}{\textwidth}\sf \begin{tabbing} x\=xxxx\=xxxx\=xxxx\=xxxx\... ...roposals;\\ \> \> $decision$ := $min$(proposals); \end{tabbing}\end{minipage}}$

**Figure:** An algorithm for reliable broadcast of message
$\fbox{\begin{minipage}{\textwidth}\sf \begin{tabbing} x\=xxxx\=xxxx\=xxxx\=xxxx\... ...ll processes;\\ \> \> $notdone := f\!alse$;\\ \\ \end{tabbing}\end{minipage}}$

Next: Checkpointing for Recovery Up: Figures in the book Previous: Failure Detectors

Vijay K. Garg 2005-02-08