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

tải về 0.79 Mb.

Chế độ xem pdf

trang	10/19
Chuyển đổi dữ liệu	15.11.2023
Kích	0.79 Mb.
	#55654

1 ... 6 7 8 9 10 11 12 13 ... 19

MESSAGE ORDERING & SNAPSHOTS
c5 cacdacdiemhtttdl

Centralized algorithm for total order
Algorithm

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
i
and P
j
and for each pair of messages M
x
and M
y
that are
delivered to both the processes, P
i
is delivered M
x
before M
y
if and only if P
j
is delivered M
x
before M
y
.
Example
• The execution in Figure
6.11
(b) does not satisfy total order. Even
• if the message m did not exist, total order would not be satisfied. The execution
• in Figure
6.11
(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.
11
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.
Complexity
Each message transmission takes two message hops and exactly n messages
in a system of n processes.
Drawbacks
• 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