Unit II message ordering & snapshots message ordering and group communication: Message ordering paradigms
CS8603:Distributed Systems Department of CSE
tải về 0.79 Mb. Chế độ xem pdf
|
c5 cacdacdiemhtttdl
| CS8603:Distributed Systems Department of CSE
2020 – 2021 2. 16 Jeppiaar Institute of Technology • Reason: Global state recording activities of individual components must be coordinated. 2.8 System model and definitions System model • The system consists of a collection of n processes, p 1 , p 2 ,…, p n , that are connected by channels. • There is no globally shared memory and processes communicate solely by passing messages (send and receive) asynchronously i.e., delivered reliably with finite but arbitrary time delay. • There is no physical global clock in the system. • The system can be described as a directed graph where vertices represents processes and edges represent unidirectional communication channels. • Let C ij denote the channel from process p i to process p j . • Processes and channels have states associated with them. • Process State: is the contents of processor registers, stacks, local memory, etc., and dependents on the local context of the distributed application. • Channel State of C ij : is SC ij , is the set of messages in transit of the channel. • The actions performed by a process are modeled as three types of events, • internal events – affects the state of the process. • message send events, and • message receive events. • For a message m ij that is sent by process pi to process p j , let send(m ij ) and rec(m ij ) denote its send and receive events affects state of the channel, respectively. • The events at a process are linearly ordered by their order of occurrence. • At any instant, the state of process pi, denoted by LS i , is a result of the sequence of all the events executed by p i up to that instant. • For an event e and a process state LS i , e ∈LS i iff e belongs to the sequence of events that have taken process p i to state LS i . • For an event e and a process state LS i , e ∉LS i iff e does not belong to the sequence of events that have taken process pi to state LS i . • For a channel C ij , the following set of messages will be: • Transit : transit(LS i , LS j ) = {m ij | send(m ij ) ∈ LS i ⋀ rec(m ij ) ∉ LS j } • There are several models of communication among processes. • In the FIFO model, each channel acts as a first-in first-out message queue hence, message ordering is preserved by a channel. • In the non-FIFO model, a channel acts like a set in which the sender process adds messages and the receiver process removes messages from it in a random order. • In causal delivery of messages satisfies the following property: “for any two messages m ij and m kj , if send(m ij ) → send(m kj ), then rec (m ij ) → rec(m kj ).” • Causally ordered delivery of messages implies FIFO message delivery. |