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
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
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.