Global States

It is often desirable to determine whether a particular property is true of a distributed system as it executes. We’d like to use logical time to construct a global view of the system state and determine whether a particular property is true. A few examples are as follows:

  • Distributed garbage collection: Are there references to an object anywhere in the system? References may exist at the local process, at another process, or in the communication channel.
  • Distributed deadlock detection: Is there a cycle in the graph of the “waits for” relationship between processes?
  • Distributed termination detection: Has a distributed algorithm terminated?
  • Distributed debugging: Example: given two processes p1 and p2 with variables x1 and x2 respectively, can we determine whether the condition |x1-x2| > δ is ever true.

In general, this problem is referred to as Global Predicate Evaluation. “A global state predicate is a function that maps from the set of global state of processes in the system ρ to {True, False}.”

  • Safety – a predicate always evaluates to false. A given undesirable property (e.g., deadlock) never occurs.
  • Liveness – a predicate eventually evaluates to true. A given desirable property (e.g., termination) eventually occurs.


Because physical time cannot be perfectly synchronized in a distributed system it is not possible to gather the global state of the system at a particular time. Cuts provide the ability to “assemble a meaningful global state from local states recorded at different times”.


  • ρ is a system of N processes pi (i = 1, 2, …, N)
  • history(pi) = hi = < e i 0 , e i 1 ,…>
  • h i k =< e i 0 , e i 1 ,…, e i k > – a finite prefix of the process’s history
  • s i k is the state of the process pi immediately before the kth event occurs
  • All processes record sending and receiving of messages. If a process pi records the sending of message m to process pj and pj has not recorded receipt of the message, then m is part of the state of the channel between pi and pj.
  • global history of ρ is the union of the individual process histories: H = h0 ∪ h1 ∪ h2 ∪…∪hN-1
  • global state can be formed by taking the set of states of the individual processes: S = (s1, s2, …, sN)
  • cut of the system’s execution is a subset of its global history that is a union of prefixes of process histories (see figure below).
  • The frontier of the cut is the last state in each process.
  • A cut is consistent if, for all events e and e’:
    • ( e ∈ C and e ‘ → e ) ⇒ e ‘ ∈ C
  • consistent global state is one that corresponds to a consistent cut.

Distributed Debugging

To further examine how you might produce consistent cuts, we’ll use the distributed debugging example. Recall that we have several processes, each with a variable xi. “The safety condition required in this example is |xi-xj| <= δ (i, j = 1, 2, …, N).”

The algorithm we’ll discuss is a centralized algorithm that determines post hoc whether the safety condition was ever violated. The processes in the system, p1, p2, …, pN, send their states to a passive monitoring process, p0. p0 is not part of the system. Based on the states collected, p0 can evaluate the safety condition.

Collecting the state: The processes send their initial state to a monitoring process and send updates whenever relevant state changes, in this case the variable xi. In addition, the processes need only send the value of xi and a vector timestamp. The monitoring process maintains a an ordered queue (by the vector timestamps) for each process where it stores the state messages. It can then create consistent global states which it uses to evaluate the safety condition.

Let S = (s1, s2, …, SN) be a global state drawn from the state messages that the monitor process has received. Let V(si) be the vector timestamp of the state si received from pi. Then it can be shown that S is a consistent global state if and only if:

V(si)[i] >= V(sj)[i] for i, j = 1, 2, …, N

Related Posts

© 2024 Basic Computer Science - Theme by WPEnjoy · Powered by WordPress