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

Three-phase distributed algorithm

tải về 0.79 Mb.
Chế độ xem pdf
Chuyển đổi dữ liệu15.11.2023
Kích0.79 Mb.
1   ...   7   8   9   10   11   12   13   14   ...   19
c5 cacdacdiemhtttdl
Three-phase distributed algorithm 
• It enforces total and causal order for closed groups. 
• The three phases of the algorithm are defined as follows: 
Phase 1 
• A process multicasts the message M to the group members with the 
➢ a locally unique tag and 
➢ the local timestamp 
Phase 2 
• Sender process awaits for the reply from all the group members who respond with a 
tentative proposal for a revised timestamp for that message M. 
it is an non-blocking await i.e., any other messages received in the meanwhile are 
• Once all expected replies are received, the process computes the maximum of proposed 
timestamps for M, and uses the maximum as final timestamp. 
Phase 3 
• The process multicasts the final timestamp to the group members of phase 1. 
Algorithm: Distributed algorithm to implement total order & causal order of messages. Code 
at P
, 1 ≤ i ≤ n. 
record Q_entry 
M: int; // the application message 
tag: int
// unique message identifier 
sender_id: int
// sender of the message 
timestamp: int
// tentative timestamp assigned to message 
deliverable: boolean; // whether message is ready for delivery 
(local variables) 
queue of Q_entry: temp_Q_ delivery_Q 
int: clock 
// Used as a variant of Lamport’s scalar clock 
int: priority 
// Used to track the highest proposed timestamp 

CS8603:Distributed Systems Department of CSE
2020 – 2021 2. 
Jeppiaar Institute of Technology
(message types) 
REVISE_TS(M, i, tag, ts) 
// Phase 1 message sent by Pi, with initial timestamp ts 
PROPOSED_TS(j, i, tag, ts) // Phase 2 message sent by Pj , with revised timestamp, to P

FINAL_TS(i, tag, ts) 
// Phase 3 message sent by Pi, with final timestamp 
(1) When process Pi wants to multicast a message M with a tag tag: 
(1a) clock←clock+1; 
(1b) send REVISE_TS(M, i, tag, clock) to all processes
(1c) temp_ts←0; 
(1d) await PROPOSED_TS(j, i, tag, ts
) from each process P

∀ j ∈ N, do temp_ts←max(temp_ts, ts
(1f) send FINAL_TS(i, tag, temp_ts) to all processes; 
(1g) clock←max(clock, temp_ts). 
(2) When REVISE_TS(M, j, tag, clk) arrives from P

(2a) priority←max_priority+1(clk); 
(2b) insert (M, tag, j, priority, undeliverable) in temp_Q; 
// at end of queue 
(2c) send PROPOSED_TS(i, j, tag_ priority) to P

(3) When FINAL_TS(j, x, clk) arrives from P

(3a) Identify entry Q_e in temp_Q, where Q_e.tag = x; 
(3b) mark Q_e.deliverable as true; 
(3c) Update Q_e.timestamp to clk and re-sort temp_Q based on the timestamp field; 
(3d) if (head(temp_Q)).tag = Q_e.tag then 

tải về 0.79 Mb.

Chia sẻ với bạn bè của bạn:
1   ...   7   8   9   10   11   12   13   14   ...   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