|
Implements casual ordering layer using vector clocks.
Causal protocol layer guarantees that if message m0 multicasted
by a process group member p0 causes process group member
p1 to multicast message p1 then all other remaining process group
members in a current view will receive messages in order m0
followed by m1.
First time encountered, causal order seems very similar to FIFO order but
there is an important distinction. While FIFO order gurantees that
if process group member p0 multicasts m0 followed by m1 the messages
will be delivered in order m0,m1 to all other group members, causal
order expands this notion of an order from a single group member "space"
to a whole group space i.e if p0 sends message m0 which causes member
p1 to send message m1 then all other group members are guaranteed to
receive m0 followed by m1.
Causal protocol layer achieves this ordering type by introducing sense of
a time in a group using vector clocks. The idea is very simple. Each message
is labeled by a vector, contained in a causal header, representing the number of
prior causal messages received by the sending group member. Vector time of [3,5,2,4] in
a group of four members [p0,p1,p2,p3] means that process p0 has sent 3 messages
and has received 5,2 and 4 messages from a member p1,p2 and p3 respectively.
Each member increases its counter by 1 when it sends a message. When receiving
message mi from a member pi , (where pi != pj) containing vector time VT(mi),
process pj delays delivery of a message mi until:
for every k:1..n
VT(mi)[k] == VT(pj)[k] + 1 if k=i,
VT(mi)[k] <= VT(pj)[k] otherwise
After the next causal message is delivered at process group pj, VT(pj) is
updated as follows:
for every k:1...n VT(pj)[k] == max(VT(mi)[k],VT(pj)[k])
author:
Vladimir Blagojevic vladimir@cs.yorku.ca
version:
$Revision: 1.8 $ | 