org.javagroups.protocols
Class CAUSAL

java.lang.Object
  |
  +--org.javagroups.stack.Protocol
        |
        +--org.javagroups.protocols.CAUSAL

public class CAUSAL
extends Protocol

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])

Version:
$Revision: 1.5 $
Author:
Vladimir Blagojevic vladimir@cs.yorku.ca

Nested Class Summary
static class CAUSAL.CausalHeader
           
 
Field Summary
 
Fields inherited from class org.javagroups.stack.Protocol
down_handler, down_prot, down_queue, down_thread, down_thread_prio, observer, props, stack, up_handler, up_prot, up_queue, up_thread, up_thread_prio
 
Constructor Summary
CAUSAL()
          default constructor
 
Method Summary
 void down(Event evt)
          Processes Event going down in the stack
 java.lang.String getName()
          Returns a name of this stack, each stackhas to have unique name
 void up(Event evt)
          Processes Event going up through the stack
 
Methods inherited from class org.javagroups.stack.Protocol
destroy, getDownProtocol, getDownQueue, getProperties, getUpProtocol, getUpQueue, init, passDown, passUp, providedDownServices, providedUpServices, receiveDownEvent, receiveUpEvent, requiredDownServices, requiredUpServices, setDownProtocol, setObserver, setProperties, setPropertiesInternal, setProtocolStack, setUpProtocol, start, startDownHandler, startUpHandler, stop, stopInternal
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

CAUSAL

public CAUSAL()
default constructor

Method Detail

down

public void down(Event evt)
Processes Event going down in the stack

Overrides:
down in class Protocol
Parameters:
evt - Event passed from the stack above Causal

up

public void up(Event evt)
Processes Event going up through the stack

Overrides:
up in class Protocol
Parameters:
evt - Event passed from the stack below Causal

getName

public java.lang.String getName()
Returns a name of this stack, each stackhas to have unique name

Specified by:
getName in class Protocol
Returns:
stack's name - CAUSAL


Copyright ? 2001,2002 www.javagroups.com . All Rights Reserved.