[Spread-users] Lamport timestamps?

John Schultz jschultz at spreadconcepts.com
Fri Aug 24 11:49:24 EDT 2007


Spread currently implements causal ordering as a total ordering that is 
causal.  Rather than a lamport timestamp, each Spread daemon updates a 
shared sequence number that defines the IDs and total order of messages. 
Only one daemon can update this sequence number at a time (within a given 
membership) when it holds the token and sends messages.

Exposing this counter would buy users very little, as they can easily 
reconstruct the counter upon delivery.  The first delivered message is #1, 
the second is #2 and so on.  Simply reset the counter to zero on any 
membership change (and associate it with the membership ID).  The only 
tricky thing would be after transitional messages where there can be holes 
in the total order.  Anyway, let us know if this helps with your problem 
or not.

Because total order is a stronger service than causal order, this 
implementation can cause higher latencies, both in message origination and 
in delivery dependencies, than if causal ordering was directly 
implemented.

If one were to implement causal ordering directly in Spread, then we most 
likely would use a Directed Acyclic Graph (DAG) of causal dependency 
rather than vector timestamps.  Essentially, the DAG is an optimized 
version of vector timestamps where only the minimum necessary causality 
information is attached to each message.

For example, if a daemon were to send two messages with no intervening 
receives, then the first one might have several dependencies listed but 
the second message would simply say it depends on the first message it 
just sent.  When you have losses you may need to recover some of the 
messages in the dependency chain, but this is true for either 
implementation.

Cheers!

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

On Thu, 23 Aug 2007, Peter A. Friend wrote:

> On Aug 23, 2007, at 1:50 PM, Alaric Snell-Pym wrote:
>> 
>> Hi there,
>> 
>> Implementing a replicated data storage system using Spread, I've had
>> to implement my own Lamport timestamps for various reasons, but it
>> occurs to me that there's probably one ticking away inside my local
>> Spread daemon anyway. I've not yet looked in the source, but I'm
>> considering the feasibility of exposing that time to the users of the
>> daemon.
>
> And this is also related to a question I posted earlier about how causal 
> orders are currently implemented. From the book by Birman it seems you can 
> use a logical timestamp but it takes a lot of messages to support a causal 
> order. With vector timestamps there is more per-message overhead but fewer 
> messages are needed to provide a causal order.




More information about the Spread-users mailing list