I am reading Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process." Journal of the ACM (JACM) 32.2 (1985): 374-382, available here, the paper in which the well known FLP Theorem was proved.

I am having trouble understanding the notion of an "applicable event" used in this paper. Here's a quote from the paper (Section 2):

Since processes are deterministic, the step is completely determined by the pair $e = (p,m)$, which we call an event. (This "event" should be thought of as the receipt of $m$ by $p$.) $e(C)$ denotes the resulting configuration, and we say that $e$ can be applied to $C$.

I can't understand this definition. When is an event applicable? When is it not applicable?


An event $e$ is applicable in configuration $C$ if it could happen at configuration $C$. Since $e = (p,m)$ means that message $m$ arrives at processor $p$, $e$ is applicable at $C$ if the message queue at $C$ contains the message $m$ directed at $p$. If there is no message directed at $p$ with contents $m$ then $e$ is not applicable at $C$.

| cite | improve this answer | |
  • $\begingroup$ Ah, I see. This makes sense. I'll wait a few more hours before accepting your answer just in case an even better answer shows up. $\endgroup$ – Jacopo Notarstefano Nov 15 '14 at 23:18

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.