September 2011 - mpiwg-ft - mailman3.cels.anl.gov

Re: [Mpi3-ft] Eventually Perfect Failure Detector
by Josh Hursey 02 Sep '11

02 Sep '11

I added the current text to the wiki: https://svn.mpi-forum.org/trac/mpi-forum-web/wiki/ft/rts_failure_detector More below... On Fri, Sep 2, 2011 at 3:04 PM, Darius Buntinas <buntinas(a)mcs.anl.gov> wrote: > I think this sounds very good. ï¿½Some comments: > > Fail-Stop: ï¿½Shouldn't it say that the process doesn't recover, or stops executing permanently? I think adding the work 'permanently' helps drive this home. > > Mistakenly failed processes: ï¿½I think we should say that we allow the implementation to kill the process. I added the sentence: The MPI implementation is allowed to terminate the process that was mistakenly identified as failed. > > Paragraph starting with "Strong completeness": ï¿½Technically it's more likely that the process will _hang_ (in a blocking communication operation) than result in a "deadlock". ï¿½Maybe: "...which may result in a process stuck in, e.g., a blocking communication operation." How about: Without strong completeness some alive process that depends on a failed process is not guaranteed that communication with the failed process will ever complete with an error (e.g., may wait indefinitely in a blocking receive operation). > > Advice to users: ï¿½Maybe change the sentence starting with "As such..." to "As such, it is possible that for a period of time, some alive processes in the MPI universe know of process failures that other alive processes do not." Changed. Thanks, Josh > > -d > > On Sep 1, 2011, at 10:34 AM, Josh Hursey wrote: > >> 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 >> _______________________________________________ >> mpi3-ft mailing list >> mpi3-ft(a)lists.mpi-forum.org >> http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-ft > > > _______________________________________________ > mpi3-ft mailing list > mpi3-ft(a)lists.mpi-forum.org > http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-ft > > -- Joshua Hursey Postdoctoral Research Associate Oak Ridge National Laboratory http://users.nccs.gov/~jjhursey

1 0

Re: [Mpi3-ft] Eventually Perfect Failure Detector
by Darius Buntinas 02 Sep '11

02 Sep '11

I think this sounds very good. Some comments: Fail-Stop: Shouldn't it say that the process doesn't recover, or stops executing permanently? Mistakenly failed processes: I think we should say that we allow the implementation to kill the process. Paragraph starting with "Strong completeness": Technically it's more likely that the process will _hang_ (in a blocking communication operation) than result in a "deadlock". Maybe: "...which may result in a process stuck in, e.g., a blocking communication operation." Advice to users: Maybe change the sentence starting with "As such..." to "As such, it is possible that for a period of time, some alive processes in the MPI universe know of process failures that other alive processes do not." -d On Sep 1, 2011, at 10:34 AM, Josh Hursey wrote: > 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 > _______________________________________________ > mpi3-ft mailing list > mpi3-ft(a)lists.mpi-forum.org > http://lists.mpi-forum.org/mailman/listinfo.cgi/mpi3-ft

1 0

[Mpi3-ft] Eventually Perfect Failure Detector
by Josh Hursey 01 Sep '11

01 Sep '11

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

1 0

Re: [Mpi3-ft] MPI_Comm_validate_all vs MPI_Comm_reenable_collectives vs ...
by Howard Pritchard 01 Sep '11

01 Sep '11

Hi Josh, I vote for MPI_COMM_VALIDATE. Howard Josh Hursey wrote: > While preparing the EuroMPI poster last night, I noticed that the > naming of the agreement protocol collective is still somewhat > problematic. I think this is what Darius mentioned in a previous > email, but I did not get it until I was converting some of the > examples. > > The semantics of the agreement protocol collective are pretty solid: > Uniform agreement of the set of failures in a communicator, and > re-enable collective operations excluding the agreed upon set of > failures. > > However the new function name (MPI_Comm_reenable_collectives) only > addresses the latter part of the semantics. Commonly people will be > using this routine to answer questions like: > "Are there any failures in this communicator?" > "Are there any new failures in this communicator?" > "Is Rank X failed in this communicator?" > > Those questions focus more on the first part of the semantic. So it > seems to me that we need to adjust the name of this function to > reflect the full semantics of the operation. > > ----- A rough example ----- > MPI_Comm_reenable_collectives(comm, &group[0]); > do { > .. Do work .. > MPI_Comm_reenable_collectives(comm, &group[1]); > if( group[0] != group[1] ) { /* New failures detected */ > group[0] = group[1]; > continue; /* retry) > } else { > break; /* no new failures - recovery block OK */ > } > } while( 1 ); > ----- A rough example ----- > > I don't have a good suggestion at this point, but it is something we > should address. Darius previous suggested the following: > MPI_COMM_VALIDATE > MPI_COMM_REPAIR > MPI_COMM_RESTORE > MPI_COMM_RECONCILE > MPI_COMM_CORRELATE > MPI_COMM_NORMALIZE > > I would like to reserve 'Repair' and 'Restore' for the process > recovery proposal. I am leading towards MPI_Comm_validate. > > Validate implies that we are making a declaration of the accuracy or > soundness of something (in this case the communicator and failed set). > So that seems to give us 'agreement' and to some degree implies 'ok > for collectives'. > > What to folks think? > > -- Josh > -- Howard Pritchard Software Engineering Cray, Inc.

1 0

[Mpi3-ft] MPI_Comm_validate_all vs MPI_Comm_reenable_collectives vs ...
by Josh Hursey 01 Sep '11

01 Sep '11

While preparing the EuroMPI poster last night, I noticed that the naming of the agreement protocol collective is still somewhat problematic. I think this is what Darius mentioned in a previous email, but I did not get it until I was converting some of the examples. The semantics of the agreement protocol collective are pretty solid: Uniform agreement of the set of failures in a communicator, and re-enable collective operations excluding the agreed upon set of failures. However the new function name (MPI_Comm_reenable_collectives) only addresses the latter part of the semantics. Commonly people will be using this routine to answer questions like: "Are there any failures in this communicator?" "Are there any new failures in this communicator?" "Is Rank X failed in this communicator?" Those questions focus more on the first part of the semantic. So it seems to me that we need to adjust the name of this function to reflect the full semantics of the operation. ----- A rough example ----- MPI_Comm_reenable_collectives(comm, &group[0]); do { .. Do work .. MPI_Comm_reenable_collectives(comm, &group[1]); if( group[0] != group[1] ) { /* New failures detected */ group[0] = group[1]; continue; /* retry) } else { break; /* no new failures - recovery block OK */ } } while( 1 ); ----- A rough example ----- I don't have a good suggestion at this point, but it is something we should address. Darius previous suggested the following: MPI_COMM_VALIDATE MPI_COMM_REPAIR MPI_COMM_RESTORE MPI_COMM_RECONCILE MPI_COMM_CORRELATE MPI_COMM_NORMALIZE I would like to reserve 'Repair' and 'Restore' for the process recovery proposal. I am leading towards MPI_Comm_validate. Validate implies that we are making a declaration of the accuracy or soundness of something (in this case the communicator and failed set). So that seems to give us 'agreement' and to some degree implies 'ok for collectives'. What to folks think? -- Josh -- Joshua Hursey Postdoctoral Research Associate Oak Ridge National Laboratory http://users.nccs.gov/~jjhursey

1 0