CS8603:Distributed Systems Department of CSE
2020 – 2021 2.
17
Jeppiaar Institute of Technology
• The causal ordering model is useful in developing distributed algorithms and may
simplify the design of algorithms.
A consistent global state
• The global state of a distributed system is a collection of the local states of
• the processes and the channels. Notationally, global state GS is defined as
GS ={
∪
i
LS
i
,
∪
i,j
SC
ij
}.
• A global state GS is a consistent global state iff it satisfies the following two conditions:
C1: send(m
ij
)
∈LS
i
⇒ m
ij
∈SC
ij
⊕ rec(m
ij
)
∈LS
j
(
⊕ is the Ex-OR operator).
C2: send(m
ij
)
∉LS
i
⇒ m
ij
∉ SC
ij
∧ rec(m
ij
)
∉ LS
j
.
• In a consistent global state, every message that is recorded as received is also recorded
as sent. These are meaningful global states.
• The inconsistent global states are not meaningful ie., without send if receive of the
respective message exists.
Interpretation in terms of cuts
• Cuts is a zig-zag line that connects a point in the space–time diagram at some arbitrary
point in the process line.
• Cut is a powerful graphical aid for representing and reasoning about the global states
of a computation.
• Left side of the cut is referred as PAST event and right is referred as FUTURE event.
• A consistent global state corresponds to a cut in which every message received in the
PAST of the cut has been sent in the PAST of that cut. Such a cut is known as a
consistent cut. Example: Cut C2 in the above figure.
• All the messages that cross the cut from the PAST to the FUTURE are captured in the
corresponding channel state.
• If the flow is from the FUTURE to the PAST is inconsistent. Example: Cut C1.
Chia sẻ với bạn bè của bạn: |
