[Spread-users] Adding info to Transitional EVS messages

[John Schultz]

Nilo,

> Let M be a safe message delivered in a transitional membership.  Can we 
> know if M did meet total order?  Then, we know that M was delivered in a 
> transitional only because "I don't know if everybody knows".

Spread does know whether or not a message meets no-holes total (AGREED) 
order within a view.  So, in theory, for a SAFE message that was delivered 
after a transitional, yes, a user COULD differentiate between the cases 
where the msg (1) didn't meet no-holes total order delivery due to a hole 
or (2) if the daemon just couldn't meet SAFE delivery due to not 
collecting all the necessary ACKs.  Note that in Spread, case (1) being 
true automatically also implies case (2) is true.

Currently, Spread does not provide this differentiating information to 
clients (it is never sent to the client side) and I'm not sure how easy it 
would be to alter Spread to provide this info.

> If a message does not meet total-order, then for sure the message was 
> not received by anyone in a regular membership (since I had a hole and 
> no member could have ever establish safe delivery).  If a transitional 
> message is in total order, then we know that other members could have 
> safely received the message in a regular membership

I think your understanding is correct but I would say it this way:

In Spread, if a SAFE message does not locally meet no-holes total (AGREED) 
order, then the message could not have been delivered to anyone before a 
transitional signal.  If a SAFE message does locally meet no-holes total 
order, then the message could have been delivered to someone before a 
transitional signal.

> After a transitional membership, if the primary knows the set of 
> messages that could have been applied by the secondary

Using this extra information the primary would know a superset of which 
messages *COULD* have been applied by the secondary (i.e. - delivered as 
SAFE before a transitional signal at the secondary).

> and applying those updates would result in an idempotent operation from 
> the last checkpointed state, then the primary knows for sure the state 
> of the secondary after the partition.

By idempotent operation do you mean an operation that "has no persistant 
side effects" such as a read operation?

Are you saying that all operations within the view, before and after the 
transitional signal, are idempotent or only the ones after the 
transitional signal at the primary that meet no-holes total order?

> (there could be other messages that are not in-order in the transitional 
> ... but now we know the secondary would have never applied those).

That is true.

> If totally-ordered messages result in a non-idempotent operation, we can 
> know the complete set of states that could have been reached from the 
> last checkpoint by ignoring non-ordered messages.

To some extent, yes.  If you somehow persistantly synchronized the primary 
and secondary to equivalent states before processing any update msgs in 
the view, then the primary can know which of several states the secondary 
could have reached as it subsequently applied each of the msgs.  But, the 
primary cannot know at the time of seperation which of those states the 
secondary actually did reach.  For example, the secondary could have 
crashed or seperated immediately after your synchronization point, or the 
secondary could have applied all of the msgs the primary has as meeting 
no-holes total order, or it could have only applied some prefix of those 
messages.

Generally, the primary could not correctly choose between these various 
possibilities without further communication with the secondary.

Also, you should be careful about simply ignoring messages that do not 
meet no-holes total order.  Do you really want your system to lose
messages that could cause updates or do you have some other form of 
recovery mechanism to reinject those updates into the system later?

Finally, are you aware that Yair's PhD thesis describes an elegant 
algorithm for persistant state replication between N parties using SAFE 
msgs in extended virtual synchrony (i.e. - Spread)?  If so, then why are 
you "reinventing the wheel?" :)

Cheers!

---
John Schultz
Spread Concepts
Phn: 443 838 2200