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.
