Inevitable Global Predicates

  • Vijay K. Garg


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.


Global State Execution Speed Checker Process Global Sequence Local Predicate 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Copyright information

© Kluwer Academic Publishers 1996

Authors and Affiliations

  • Vijay K. Garg
    • 1
  1. 1.Department of Electrical and Computer EngineeringUniversity of Texas at AustinAustinUSA

Personalised recommendations