[Spread-users] Adding info to Transitional EVS messages

John Lane Schultz jschultz at spreadconcepts.com
Sun Aug 28 20:36:18 EDT 2005

Nilo Rivera wrote:
> Consider the following scenario:
> 1. Clients X and Y (Cx and Cy) are members of groups A and B, each 
> running on its own daemon.
> 2. Cx sends a safe message Ma to group A, followed by another safe 
> message Mb to group B.
> 3. Cy receives Mb, followed by a partition which leaves him alone. 4. Cy 
> established "I know that everybody knows" for Mb before the partition. 
> (may not be the case in Spread)
> 5. Cy delivers Mb in a transitional membership because it does not have 
> Ma..

Within a heavy-weight daemon membership/view, a control token is 
circulated to assign sequence numbers to messages sent within that view. 
  This token/sequence assignment establishes a total order on the 
messages sent within that view.  Similiarly, safe messages are also 
noted on this token through a single ARU (Acknowledge Receipt & 
Understanding) counter.  This ARU basically notes the minimum message 
sequence number up through which all daemons in the view have received ...

> First, can (4) above happen in Spread?....If not, is it implementation 
> dependent (a vector or fined-grained-token could do it)?.

As such, I don't believe that (4) can be achieved in Spread as the ARU 
will still be stuck on trying to make message Ma safe and Mb is later in 
the total order (needs a higher ARU than Ma).  This mechanism is 
implementation dependent as an all-ACK (inefficient) or similiar 
algorithm could locally achieve such knowledge for Mb but not Ma, which 
I don't believe can occur in Spread.

> Here is the reason: If group A and B are independent state machines, 
> then group B gets penalized for a message unrelated to his state (cannot 
> apply Mb). However, Mb could have been safely applied if we know that is 
> in order and everyone in the group received it.  We have such a case 
> where an application is a member of hundreds of groups with a few 
> independent state machines.   I guess each state machine could use a 
> different spread network to solve the above, but is not possible as some 
> events are sent to multiple state machines.

The different Spread process groups are "simulated" through the use of a 
single daemon "group."  Because we do not run independent state machines 
per group but rather 1 per daemon membership, Spread can efficiently run 
with thousands of process groups running inside it.  It also allows 
Spread to easily make guarantees across groups and to give well-defined 
meaning to open group semantics.

It is true that in edge cases like the one you describe a different 
algorithm could be slightly more optimal in some senses, but that 
optimization would come at a too heavy performance and capability cost.


John Schultz
Spread Concepts LLC

More information about the Spread-users mailing list