4
$\begingroup$

I was reading 'Unreliable Failure Detectors for Reliable Distributed Systems' (PDF) and I was wondering if ping (with increasing timeouts in case of failure) is in class S of failure detectors:

  • strong completeness
  • weak accuracy
$\endgroup$
2
  • $\begingroup$ PDF link added. Hope you don't mind. :) $\endgroup$ Oct 12 '10 at 16:14
  • 5
    $\begingroup$ Alexandru: it would help the question if you could make it a little more self-contained: could you specify formally the model of increasing timeout (is it exponential?) and the definitions of strong completeness and weak accuracy ? $\endgroup$ Oct 12 '10 at 16:42
5
$\begingroup$

There is a lot that needs to be clarified about the model (ping) in which we want to evaluate. What are the processes IDs ? Is it IPs (IP network) ? Is the IPs permanent ? Can the IP change ? Are they connected point wise or there is a router/switch ? Can the switch fail ? Are the connections trusted or can a connection fail between two correct processes ?

I'll give counter examples assuming the TCP/IP model, where there are not permanent IPs (DHCP based IP configuration).

Strong completeness requires that every process that crashes is permanently suspected by every correct process.

Counter-example: Take process A and B, with IPs IP1 and IP2. Process A crashes permanently, releasing the IP. Process B makes a brief disconnection and acquires a new IP, which happen to be IP1.

Solution: We must assume IPs are strictly bound to each process, and can never change. Unless you identify processes with other application layer unique IDs.

Weak accuracy requires some correct processes are never suspected. Actually, if the switch/router fails for a few minutes, every process might suspect all other processes, even if all of them are correct.

The ping is delusive because it is on the IP level. To avoid these complexities and be able to reduce the needed assumptions to a minimum, think about some level of abstraction, like an application-level failure detector. However if you will really get down to the details, there is a lot to consider in the physical layer (wifi, ethernet) and on other layers as well (TCP, UDP, NAT) etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.