CSE 223a Homework 3

Due 10 March 2009

The ◊S failure detector provides each process p with a set suspects(p). These are the processes that p suspects as being faulty. The failure detector guarantees that there is some correct process c such that eventually all correct processes p never have c in suspects(p).

The Ω failure detector provides each process p with a single process identifier trusts(p). The failure detector guarantees that there is some correct process c such that eventually all correct processes p have trusts(p) = c.

Show that these two failure detectors are equivalent. You can do this by showing if you have ◊S then you can implement Ω, and if you have Ω then you can implement ◊S.

27 February 2009 by kam