The problem with two-phase commit is that it can block if the coordinator fails. One can look at fault tolerant consensus algorithms, or possibly the paxos consensus algorithm, by Lamport & Gray 2004, that guarantees termination if there is less than F-1 faults, using 2F coordinators. Fault-Tolerant consensus algorithms will iterate over F+1 all-to-all rounds, assuming there is at most F failures, to guarantee that all living processes have the same view of the system, and can return the same value. -- About the wording of this sentence: could we change the text to say "or return the same error everywhere"? Or do we want to allow returning different errors at different living processes? And why? Thomas Le 16 f�vr. 2011 � 16:16, Joshua Hursey a �crit :

It is a challenging guarantee to provide, but possible. Databases need to make decisions like this all time with transactions (commit=success, or abort=failure). Though database transaction protocols are a good place to start, we can likely loosen some of the restrictions since we are applying them to a slightly different environment.

Look at a two-phase commit protocol that includes a termination protocol (Grey), or a three-phase commit protocol (Skeen). The trick is that you really want what the literature calls a 'nonblocking' commit protocol, meaning that it will not block in an undecided state waiting for the recovery of a peer process that might be able to decide from a recovery log. There are a few other more scalable approaches out there, but are challenging to implement correctly.

-- Josh

Gray: Notes on Data Base Operating Systems (note this describes a protocol without the termination protocol, but a databases text should be able to fill in that part) - 1979

Skeen: Nonblocking commit protocols - 1981

On Feb 16, 2011, at 3:49 PM, Darius Buntinas wrote:

...

MPI_Comm_validate_all, according to the proposal at [1], must "either complete successfully everywhere or return some error everywhere." Is this possible to guarantee? What about process failures during the call? Consider the last message sent in the protocol. If the process sending that message dies just before sending it, the receiver will not know whether to return success or failure.

I think that the best we can do is say that the outcount and list of collectively-detected dead processes will be the same at all processes where the call completed successfully.

Or is there a trick I'm missing?

Thanks, -d

[1] https://svn.mpi-forum.org/trac/mpi-forum-web/wiki/ft/run_through_stabilizati... _______________________________________________ mpi3-ft mailing list [email protected] http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-ft

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

_______________________________________________ mpi3-ft mailing list [email protected] http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-ft