this is the generic discussion about week 9's material, which is group communication, summaries and other general questions/comments.
Group (of nodes)
Group:
Collection of nodes that act together for some purpose.
A message to the group is received by all those nodes
Multicast:
Delivery to all nodes in a group
Two scenarios:
A client solicits a service from any one node in a group
Requires best-effort multicast:
Guaranteed delivery to reachable, non-faulty nodes
A client requests a service from each and all members of a group of nodes
Requires reliable (a k a “atomic”) multicast:
A guarantee that the message has been received and delivered by all
Example: A request to back up a database on multiple nodes
Broadcast:
Delivery to all nodes in “the system”
11/25/2019
1
Message ordering in multicast
“The trick:” Each receiving node can buffer messages before delivering them to the application layer
Each node can adjust the order in which messages are delivered.
Possible order requirements:
Causal order:
Causally related messages from any senders are delivered in their causal order
Total order:
All messages are delivered in the same order to each recipient
But not necessarily in the order they were sent (by different senders)
The messages may be alarm notices from different originators
All group members must receive the notices in the same order
A reliable and total-order multicast is called atomic multicast
6/4/2020
2
Causal order example: Messages on a bulletin board [Coulouris (2012), 15.4.3]
Messages on each topic should be delivered at each node in the order they were sent
If user X reads Msg1 and then posts a reply, all users should see Msg1 first and then the reply
This is called causal ordering (not “casual”)
Messages that are not causally dependent are called concurrent
Causal order is implemented as a kind of chronological ordering:
It will deliver all messages, that might be causally dependent, in the correct sequence
A message, m, sent from a node is considered causally dependent on any message that the node (sent or) delivered before sending m.
Examples:
Chat application
Someone sends a message and some recipients reply.
With causal ordering, all will see the replies after the message replied to.
Real-time multimedia; online video call (Adelstein & Sighal 1997)
Twitter: Proprietary protocol
Commercial-pilot safety checks before takeoff
6/3/2020
3
3
Causal order protocol
Assumes multicast in a closed group, 1 .. n.
The source is a member of the group.
Multicast cannot span across different groups.
Each group member, i, maintains a vector L = L1 .. Ln
Each vector element (Lk): Number of messages delivered at node i, so far, from member k, except that:
The group member i’s own vector element, Li, is the number of messages i has sent
The vector with one element per node is similar to the vector clock, but they do not work the same way.
When member i sends a multicast message
It increments Li
It sets V = L and includes V with the message
Note that this protocol needs no global clock
10/19/2020
4
Causal order: Receive
Member j receives a multicast message, m, from member i including the vector V = [ V1 .. Vn ]
Member j compares V with its own vector L:
Deliver m if j has delivered all messages that member i had delivered when sending m
That is, Lk ≥ Vk for all k i.
If so, set Li = Vi (updating j ’s count of messages received from sender i and delivered.)
Otherwise, delay m until Lk ≥ Vk for all k i.
At that point, set Li = Vi and deliver the message.
Note: A lower-level protocol ensures that j receives all messages sent by i in order
11/26/2019
5
Causal order: Example
x,x,x,x is the vector L of each node, for example 0,0,0,0 or 2,1,0,1. The vector is copied into any send.
Node 1 Node 2 Node 3 Node 4
0,0,0,0 0,0,0,0 0,0,0,0 0,0,0,0
send A 1,0,0,0
send B 0,0,0,1
send C 2,0,0,0
receive A; deliver A; 1,0,0,0
send D; 1,1,0,0 receive B; deliver B; 0,0,0,1
receive C; deliver C; 2,1,0,0
receive D; delay D
receive B; deliver B; 2,1,0,1
receive A; deliver A; 1,0,0,1
receive C; deliver C; 2,0,0,1
receive D; deliver D; 2,1,0,1
receive A; deliver A; 1,0,0,1
deliver D; 1,1,0,1
receive C; deliver C; 2,1,0,1
receive B; deliver B; 2,0,0,1
receive D; deliver D; 2,1,0,1
A and B are concurrent. Node 2 delivers first A then B. Node 3 delivers first B then A.
Same for C and D. Same for B and C.
D is causally dependent on A so Node 4 must delay D until A is delivered to Node 4.
4/20/2020
6
Explanation of casual order example using message D
When message D is sent from Node 2, D has the vector 1,1,0,0.
The ‘1’ in the leftmost position means that Node 2 had delivered exactly one message from Node 1 before sending D.
When message D arrives at Node 3, Node 3 can deliver D only if it has already delivered at least 1 message from Node 1.
Node 3’s vector just before D arrives is 2,0,0,1.
Because the leftmost position is 2, it has indeed delivered (at least) one message from Node 1 and can deliver D.
When message D arrives at Node 4, Node 4’s vector is 0,0,0,1.
The leftmost position shows that Node 4 has not delivered any message from Node 1.
For this reason, Node 4 must delay message D.
It delivers D as soon as it delivers message A so that D’s vector is 1,0,0,1.
Note: It is misleading to say that the causal order delivers all messages in the order they were sent (Sisson, 1995).
This does hold for causally ordered messages: primary, response, response …
But there are also concurrent messages, where we cannot know the order.
Perhaps the statement is true for those messages where we can determine the order?
10/19/2020
7
7
2-phase total-order multicast
All recipients deliver messages to their application layers in the same order
Not necessarily the order they were sent
The group communication layer determines the correct order of delivery
This multicast can be used in file replication.
Replicas are typically held at multiple nodes for fault tolerance.
After the updates in each message have been made to the replicas at all nodes, the replicas would be identical.
The basic implementation of Lamport’s clock is sufficient
We use an example with two originators, S1 and S2, and two group members, G1 and G2
6/3/2020
8
Delivery of 2-phase total-order messages
Before delivery to the application layer:
The multicast of a message must be committed, and
The messages must be ordered by their commit times.
Phase 1: Originator (S1 or S2) sends a message and collects an ack with a suggested delivery time from each group member (G1 and G2).
Phase 2: Originator broadcasts a commit message with the agreed commit time
The commit time is the greatest suggested delivery time
Each group member determines locally when to deliver each message to the application layer.
A message is delivered as soon as:
its official commit time has been established, and
there are no pending messages that could turn out to have earlier commit times
We shall see an example of this
10/19/2020
9
2-phase total-order multicast scenario
10
Comm. handler buffer at node G1:
Msg Suggested time Commit time
m0 2 Delivered
m1 7 15
m2 9 13
m3 20 Pending
4/20/2020
On this particular slide:
Messages are black
Acks are red (suggested time)
Commit messages are blue (agreed
time)
Protocol monitors (chat 3)
Recap: A semaphore safe object safeguards a shared domain resource (such as a forklift)
A thread operating on a semaphore safe object is obligated to follow a simple protocol:
First acquire and then release the shared resource.
To enforce this obligation, we used a protocol monitor that encapsulates:
the semaphore safe object and
all operations that need exclusive access to the shared resource
A procedure (such as Use_Forklift, for example), includes an acquire call and a release call
Those calls bracket some other statements in between (i.e., the critical section)
A protocol monitor encapsulates that procedure as well as the semaphore safe object
10/19/2020
11
11
10/19/2020
12
Protocol monitor for the forklift (from chat 3, the forklift is the safe object here)
package Forklift_Monitor is -- package specification
procedure Use_Forklift; -- operation that a job calls
end Forklift_Monitor;
package body Forklift_Monitor is -- package body
protected Forklift_Semaphore is … -- spec and
protected body Forklift_Semaphore is … -- body of semaphore PO
procedure Use_Forklift is
begin
Forklift_Semaphore.Acquire;
… -- Critical section: Operate the forklift
Forklift_Semaphore.Release;
end Use_Forklift;
end Forklift_Monitor;
The multicast “machinery” regarded as a safe object
At each node, at most one thread at a time can perform a multicast
If the node has more than one thread wanting to multicast:
Only one thread can perform a multicast at once
So we need a state-machine safe object controlling access to the multicast “machinery”
We encapsulate it in protocol monitors
Total_Order_Sender for sending
Total_Order_Receiver for receiving
10/19/2020
13
Protocol monitor for sender
Total_Order_Sender is an object (a package in Ada) -- not a safe object
Inside Total_Order_Sender, the state-machine safe object Sending keeps the protocol state:
Free, Phase1, Waiting, Phase2, Free, ….
From within Total_Order_Sender, app threads and comm threads call Sending to update the state data
Once the app thread is cleared to send, it does this outside Sending
While this is happening, comm threads report acks to Ack_Received
If we did the sending inside the safe object Sending, we would lock out the comm threads from calling Sending
Total_Order_Sender ensures that the protocol is followed
11/26/2019
14
Protocol monitor for sender
package Total_Order_Sender
protected Sending State-machine safe object for the total-order (sender) protocol
entry Start_Send Application thread gets exclusive access to sending machinery
entry Commit The sending application thread blocks until all acks received
and then computes the agreed commit time
procedure Done App thread releases exclusive access to sending machinery
procedure Ack_Received Ack with suggested delivery time received
private
State : statetype := Free
end Sending;
procedure Send Application thread wants to send
Sending.Start_Send Block until State = Phase1
-- Here: Send message to each recipient
Sending.Commit Messages sent. Block until State = Phase2
-- Here: Send a commit message with the agreed commit time to each recipient
Sending.Done Release exclusive access. State = Free
end Send;
procedure Ack_Received Comm thread reports that an ack was received
“Patch through” the call to Sending.Ack_Received
end Total_Order_Sender
11/25/2019
15
The safe object Sending as a “receptionist”
The previous slide shows two units:
The protected object Sending
The procedure Send
Couldn’t Send be part of the protected object?
Protected object Sending serves as a kind of receptionist:
Any thread wanting to multicast can call Total_Order_Sender.Send at any time and potentially be queued up on Sending.Start_Send
Another thread, which is also executing code in Send, may have exclusive access to Sending and the sending machinery
10/19/2020
16
Conclusion
We looked at two multicast protocols:
The causal protocol useful for a bulletin board:
Each “thread” of messages arrives in the same order at each node:
Initial post
Response1 to initial
Response1B to initial
Response2B to response1B
Response2 to response1
Response3 to response2
Response4 to response3
The 2-phase total-order multicast
All group members get the messages in the same order
But not necessarily the order they were sent.
4/21/2020
17
Ungraded homework exercise 1
Four distributed nodes, P1 – P4, communicate by means of a causal order protocol.
Initially, node P1 has the vector 0, 0, 0, 0.
The messages F, G, H, J arrive at node P1 in the following order:
Arrival seq. no. Message From node Vector in message
1 J P4 0, 0, 1, 1
2 G P2 0, 1, 0, 0
3 H P3 0, 0, 2, 0
4 F P3 0, 0, 1, 0
In which order are the messages delivered?
What is the vector at P1 after each message is delivered?
11/25/2019
18
Solution for ungraded clock homework exercise 1
11/25/2019
19
Solution for ungraded clock homework exercise 2
20
11/25/2019
S1G1G2S22175 67 8989 1011 12 15 16 1713 1410 17 18 1915 16m1 (7)m1(15)m2m2(9)(13)171819(13) 20(15)
S1 G1 G2 S2 2 1 7 5 6 7 8 9 8 9 10 11 12 15 16 17 13 14 10 17 18 19 15 16 m1 (7) m1 (15) m2 m2 (9) (13) 17 18 19 (13) 20 (15)
P1P2P3P4100020003000400055006542010022002300240025002600001000222332234223520001000240034004
P1
P2
P3
P4
1000
2000
3000
4000
5500
6542
0100
2200
2300
2400
2500
2600
0010
0022
2332
2342
2352
0001
0002
4003
4004
P1P2P3P41000200030004502010002020302040205020634073400100020003003422352236200010002003300340035
P1
P2
P3
P4
1000
2000
3000
4502
0100
0202
0302
0402
0502
0634
0734
0010
0020
0030
0342
2352
2362
0001
0002
0033
0034
0035
Solution for ungraded clock homework exercise 2
P1
P2
P3
P4
1000 2000 3000 4502
0100 0202 0302 0402 0502 0634 0734
0010 0020 0030 0342 2352 2362
0001 0002 0033 0034 0035
203/4/2019
Solution for ungraded clock homework
exercise 2
P1
P2
P3
P4
1000 2000
3000
4502
0100
0202 0302
0402
0502
0634
0734
0010
0020
0030
0342
2352
2362
0001
0002
0033
0034
0035
203/4/2019