[Mpi3-ft] Eventually Perfect Failure Detector

[Josh Hursey]

So we have been working under a modified definition of a 'Perfect
Failure Detector' for a while. Recently we have been encouraged to
revisit and clarify this assumption and definition (1) to make it
clearer without the academic jargon (2) to be more precise as far as
the detector we actually semantically require.

It should be noted that a truly Perfect Detector can only be
implemented in a synchronous system, which makes it an unsafe
assumption for the MPI standard. In the RTS proposal we weakened the
definition slightly to handle transient failures (an therefor a nod to
partially synchronous systems), but we still talk about it as a
Perfect Detector which has been getting us in trouble.

After a few conversations with folks and some additional (re-)reading
I started to reformulate the text in the RTS proposal. At bottom I
included the new text that I am suggesting to replace the 'Perfect
Detector' language in the RTS proposal.

At its core is the movement to what is called an 'Eventually Perfect'
failure detector with a terminate-upon-mistake constraint for
mistakenly identified failed processes (previously we called them
transitent failures). So to the local process the failure detector
seems perfect, but in the system as a whole it is only eventually so.

The front part of the text below is meant to be the clearer language,
and I pushed the more precise stuff into the rationale.

Take a read through the text below and let me know what you think. I
suspect it will require some iteration to get just right, but
hopefully it starts us out on better footing going forward.

Thanks,
Josh


---------------------------------------------
17.2 MPI Terms and Conventions

Fail-Stop process failure is one in which the process stops executing,
and its internal state is lost [5].

17.3 Detection of Process Failure

MPI will provide the ability to detect process failures. MPI will
guarantee that eventually all alive processes will be able to know
about the failure. The state management and query operations defined
in this chapter allow the application to query for the failed set of
processes in a communication group. Additional semantics regarding
communication involving failed processes are defined later in this
chapter.

It is possible that MPI mistakenly identifies a process as failed when
it is not failed. In this situation the MPI library will exclude the
mistakenly identified failed process from the MPI universe, and
eventually all alive processes will see this process as failed.

------------------
Rationale.
MPI provides an eventually perfect failure detector for fail-stop
process failures [1]. An eventually perfect failure detector is both
strongly complete and eventually strongly accurate.

Strong completeness is defined as: "Eventually every process that
crashes is permanently suspected by every correct process" [1]. In
essence this means that eventually every failed process will be able
to be known to all alive processes. Without strong completeness some
alive process that depends on a failed process is not guaranteed to
ever receive an error, which can lead to a deadlock.

Eventual strong accuracy is defined as: "There is a time after which
correct processes are not suspected by any correct process" [1].
Depending on the system architecture, it may be impossible to
correctly determine if a process is failed or slow [3]. Eventual
strong accuracy allows for unreliable failure detectors that may
mistakenly suspect a process as failed when it is not failed [1].

If a process failure was reported to the application and the process
is later found to be alive then MPI will exclude the process from the
MPI universe. Resolving the mistake by excluding the process from the
MPI universe is similar to the technique used by the group membership
protocol in [4]. This additional constraint allows for consistent
reporting of error states to the local process. Without this
constraint the application would not be able to trust the MPI
implementation when it reports process failure errors. Once an alive
process receives notification of a failed peer process, then it may
continue under the assumption that the process is failed.

End of rationale.
------------------

------------------
Advice to users.
The strong completeness condition of the failure detector allows the
MPI implementation some flexibility in managing the performance costs
involved with process failure detection and notification. As such, it
is possible that some alive processes in the MPI universe know of
process failures that other alive processes do not for a period of
time. Additionally, if a process was mistakenly reported as failed it
is possible that for some period of time a subset of processes
interact with the process normally, while others see it as failed.
Eventually all processes in the MPI universe will be able to be aware
of the process failure.

End of advice to users.
------------------

------------------
Advice to implementors.
An MPI implementation may choose to provide a stronger failure
detector (i.e., perfect failure detector), but is not required to do
so. This may be possible for MPI implementations targeted at
synchronous systems [2].

End of advice to implementors.
------------------

Citations:
----------
[1] Chandra, T. and Toueg, S. Unreliable Failure Detectors for
Reliable Distributed Systems. Journal of the ACM (1996).
[2] Dwork, C., Lynch, N., and Stockmeyer, L. Consensus in the Presence
of Partial Synchrony. Journal of the ACM (1988).
[3] Fischer, M., Lynch, N., and Paterson, M. Impossibility of
distributed consensus with one faulty process. Journal of the ACM
(1985).
[4] Ricciardi, A. and Birman, K. Using process groups to implement
failure detection in asynchronous environments. In Proceedings of the
Eleventh ACM Symposium on Principles of Distributed Computing (1991).
[5] Schlichting, R.D. and Schneider, F.B. Fail-stop processors: An
approach to designing fault-tolerant computing systems. ACM
Transactions on Computer Systems (1983).

---------------------------------------------

-- 
Joshua Hursey
Postdoctoral Research Associate
Oak Ridge National Laboratory
http://users.nccs.gov/~jjhursey