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
|
c5 cacdacdiemhtttdl
- Điều hướng trang này:
- Phase 3 • The process multicasts the final timestamp to the group members of phase 1. Algorithm: D
| Three-phase distributed algorithm
• It enforces total and causal order for closed groups. • The three phases of the algorithm are defined as follows: Sender 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 processed. • 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 i , 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. 12 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 i 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 j ) from each process P j ; (1e) ∀ j ∈ N, do temp_ts←max(temp_ts, ts j ); (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 j : (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 j . (3) When FINAL_TS(j, x, clk) arrives from P j : (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 (3e) tải về 0.79 Mb. Chia sẻ với bạn bè của bạn:
|