Distributed Systems

How to find global states in a distributed system


Problems in distributed systems

  • Many problems in distributed systems can be cast in terms of the problem of detecting global states.
  • For instance, the global state detection algorithm helps to solve an important class of problems: stable property detection
  • A stable property is one that persists: once a stable property becomes true it remains true thereafter.
  • Examples of stable properties are “computation has terminated,” “ the system is deadlocked” and “all tokens in a token ring have disappeared.
  • The stable property detection problem is that of devising algorithms to detect a given stable property.

.   Assumptions of Distributed Systems

  • Processes in a distributed system communicate by sending and receiving messages
  • A process can record its own state and the messages it sends and receives; it can record nothing else
  • To determine a global system state, a process p must enlist the cooperation of other processes that must record their own local states and send the recorded local states to p
  • All processes cannot record their local states at precisely the same instant unless they have access to a common clock.
  • We assume that processes do not share clocks or memory
  • The problem is to devise algorithms by which processes record their own states and the states of communication channels so that the set of process and channel states recorded form a global system state.
  • The global-state-detection algorithm is to be superimposed on the underlying computation: it must run concurrently with, but not alter, this underlying computation.

How does global state recording algorithm work

The global-state recording algorithm works as follows:

  • Each process records its own state, and the two processes that a channel is incident on cooperate in recording the channel state.
  • We cannot ensure that the states of all processes and channels will be recorded at the same instant because there is no global clock; however, we require that the recorded process and channel states form a “meaningful” global system state.
  • The global-state recording algorithm is to be superimposed on the underlying computation, that is, it must run concurrently with, but not alter, the underlying computation
  • The algorithm, may send messages and require processes to carry out computations; however, the messages and computation required to record the global state must not interfere with the underlying computation.


How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

0 0 votes
Article Rating
Notify of
Inline Feedbacks
View all comments