Inevitable Global Predicates
- 88 Downloads
In previous chapters we have discussed the class of predicates that are weak. As explained earlier, a weak predicate p holds in a distributed computation if there exists a consistent global state in which p is true. In this chapter, we discuss a different class of unstable predicates called strong predicates. Intuitively, a strong predicate p is true if it is true for all observers of the distributed computation. These predicates are generally useful in verifying that a desirable predicate was indeed true in a distributed computation. For example, consider the distributed computation shown in Fig. 7.1(a). Processes P1 and P2 set their flags, flag1 and flag2 and send messages to each other. On receiving a message from the other process, each process resets its own flag. It is easy to see that no matter what the execution speeds of processes are, the system will always go through a global state in which both flags are set. Similarly, computations in Fig. 7.1(b) and (c) also go through a global state in which both flag1 and flag2 are set.
KeywordsGlobal State Execution Speed Checker Process Global Sequence Local Predicate
Unable to display preview. Download preview PDF.