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

tải về 0.79 Mb.
Chế độ xem pdf
Chuyển đổi dữ liệu15.11.2023
Kích0.79 Mb.
1   ...   6   7   8   9   10   11   12   13   ...   19
c5 cacdacdiemhtttdl
2.6 Total order 
• For example of updates to replicated data would be logical only if all replicas see the 
updates in the same order. 
Definition 6.14 (Total order) 
For each pair of processes P

and P

and for each pair of messages M

and M

that are 
delivered to both the processes, P

is delivered M

before M

if and only if P

is delivered M

before M

The execution in Figure 
(b) does not satisfy total order. Even 
• if the message m did not exist, total order would not be satisfied. The execution 
• in Figure 
(c) satisfies total order. 
Centralized algorithm for total order 
• Algorithm Assumes all processes broadcast messages. 
• It enforces total order and also the causal order in a system with FIFO channels. 
• Each process sends the message it wants to broadcast to a centralized process. 
• The centralized process relays all the messages it receives to every other process over 
FIFO channels. 
Algorithm : centralized algorithm to implement total order & causal order of messages. 
(1) When process Pi wants to multicast a message M to group G: 

CS8603:Distributed Systems Department of CSE
2020 – 2021 2. 
Jeppiaar Institute of Technology
(1a) send M(i,G) to central coordinator. 
(2) When M(i,G) arrives from Pi at the central coordinator: 
(2a) send M(i,G) to all members of the group G. 
(3) When M(i,G) arrives at Pj from the central coordinator: 
(3a) deliver M(i,G) to the application. 
Each message transmission takes two message hops and exactly n messages 
in a system of n processes. 
• A centralized algorithm has a single point of failure and congestion 

tải về 0.79 Mb.

Chia sẻ với bạn bè của bạn:
1   ...   6   7   8   9   10   11   12   13   ...   19

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

    Quê hương