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



tải về 0.79 Mb.
Chế độ xem pdf
trang12/19
Chuyển đổi dữ liệu15.11.2023
Kích0.79 Mb.
#55654
1   ...   8   9   10   11   12   13   14   15   ...   19
MESSAGE ORDERING & SNAPSHOTS
c5 cacdacdiemhtttdl
move Q_e from temp_Q to delivery_Q; 
(3f) 
while (head(temp_Q)).deliverable is true do 
(3g) 
dequeue head(temp_Q) and insert in delivery_Q. 
(4) When Pi removes a message (M, tag, j, ts, deliverable) from head(delivery_Q
i
): 
(4a) clock←max(clock, ts)+1. 
Receivers 
Phase 1 
• The receiver receives the message with a tentative/proposed timestamp. 
It updates the variable priority that tracks the highest proposed timestamp, then revises 
the proposed timestamp to the priority, and places the message with its tag and the 
revised timestamp at the tail of the queue temp_Q. 
In the queue, the entry is marked as undeliverable. 
Phase 2 
• The receiver sends the revised timestamp (and the tag) back to the sender. 
• The receiver then waits in a non-blocking manner for the final timestamp (correlated 
by the message tag). 
Phase 3 
• In the third phase, the final timestamp is received from the multicaster. 
• The corresponding message entry in temp_Q is identified using the tag, and is marked 
as deliverable after the revised timestamp is overwritten by the final timestamp. 
• The queue is then resorted using the timestamp field of the entries as the key. 


CS8603:Distributed Systems Department of CSE
2020 – 2021 2. 
13
Jeppiaar Institute of Technology
• If the message entry is at the head of the temp_Q, that entry, and all consecutive 
subsequent entries that are also marked as deliverable, are dequeued from temp_Q, and 
enqueued in deliver_Q in that order. 
Complexity 
• This algorithm uses three phases, and, to send a message to n−1 processes, it uses 
3(n−1) messages and incurs a delay of three message hops. 
Example An example execution to illustrate the algorithm is given in Figure 
6.14
. Here, A and 
B multicast to a set of destinations and C and D are the common destinations for both 
multicasts. 
• Figure 6.14a. The main sequence of steps is as follows: 
1. A sends a REVISE_TS(7) message, having timestamp 7. B sends a REVISE_TS(9) 
message, having timestamp 9. 
2. C receives A’s REVISE_TS(7), enters the corresponding message in temp_Q, and marks 
it as undeliverable; priority = 7. C then sends PROPOSED_TS(7) message to A. 
3. D receives B’s REVISE_TS(9), enters the corresponding message in temp_Q, and marks 
it as undeliverable; priority = 9. D then sends PROPOSED_TS(9) message to B. 
4. 
C receives B’s REVISE_TS(9), enters the corresponding message in temp_Q, and 
marks it as undeliverable; priority = 9. C then sends PROPOSED_TS(9) message to B. 
5. D receives A’s REVISE_TS(7), enters the corresponding message in temp_Q, and marks 
it as undeliverable; priority = 10. D assigns a tentative timestamp value of 10, which is 
greater than all of the timestamps on REVISE_TSs seen so far, and then sends 
PROPOSED_TS(10) message to A. 
The state of the system is as shown in the figure. 
• Figure 

tải về 0.79 Mb.

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