Global state and snapshot recording Algorithms

CS8603:Distributed Systems Department of CSE
2020 – 2021 2. 
15
Jeppiaar Institute of Technology
• Each component of a distributed system has a local state. The state of a process is the 
state of its local memory and a history of its activity. 
• The state of a channel is the set of messages in the transit. 
• The global state of a distributed system is the collection of states of the process and the 
channel. 
• Applications that use the global state information are : 
• deadlocks detection 
• failure recovery, 
• for debugging distributed software 
• If shared memory is available then an up-to-date state of the entire system is available 
to the processes sharing the memory. 
• The absence of shared memory makes difficult to have the coherent and complete view 
of the system based on the local states of individual processes. 
• A global snapshot can be obtained if the components of distributed system record their 
local states at the same time. This is possible if the local clocks at processes were 
perfectly synchronized or a global system clock that is instantaneously read by the 
processes. 
• However, it is infeasible to have perfectly synchronized clocks at various sites as the 
clocks are bound to drift. If processes read time from a single common clock 
(maintained at one process), various indeterminate transmission delays may happen. 
• In both cases, collection of local state observations is not meaningful, as discussed 
below. 
• Example: 
o Let S1 and S2 be two distinct sites of a distributed system which maintain bank 
accounts A and B, respectively. Let the communication channels from site S1 to 
site S2 and from site S2 to site S1 be denoted by C12 and C21, respectively. 
• Consider the following sequence of actions, which are also illustrated in the timing 
• diagram of Figure 
4.1
: 
• Time t0: Initially, Account A=$600, Account B=$200, C12 =$0, C21=$0. 
• Time t1: Site S1 initiates a transfer of $50 from A to B. Hence, 
A= $550, B=$200, C12=$50, C21=$0. 
• Time t2: Site S2 initiates a transfer of $80 from Account B to A. Hence, 
A= $550,B=$120, C12 =$50, C21=$80. 
• Time t3: Site S1 receives the message for a $80 credit to Account A. Hence, 
A=$630, B=$120, C12 =$50, C21 =$0. 
• Time t4: Site S2 receives the message for a $50 credit to Account B. Hence, 
A=$630, B=$170, C12=$0, C21=$0. 
• Suppose the local state of Account A is recorded at time t0 which is $600 and the local 
state of Account B and channels C12 and C21 are recorded at time t2 are $120, $50, 
and $80, respectively. 
• Then the recorded global state shows $850 in the system. An extra $50 appears in the 
system. 

tải về 0.79 Mb.

Chia sẻ với bạn bè của bạn: