Unit II message ordering & snapshots message ordering and group communication: Message ordering paradigms

Global state and snapshot recording Algorithms

tải về 0.79 Mb.
Chế độ xem pdf
Chuyển đổi dữ liệu15.11.2023
Kích0.79 Mb.
1   ...   11   12   13   14   15   16   17   18   19
c5 cacdacdiemhtttdl
Global state and snapshot recording Algorithms 
2.7 Introduction 
distributed computing system consists of spatially separated processes that do not 
share a common memory and communicate asynchronously with each other by 
message passing over communication channels. 

CS8603:Distributed Systems Department of CSE
2020 – 2021 2. 
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 
• 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 
• 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 
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 

• 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 

tải về 0.79 Mb.

Chia sẻ với bạn bè của bạn:
1   ...   11   12   13   14   15   16   17   18   19

Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2023
được sử dụng cho việc quản lý

    Quê hương