[Spread-users] Lamport timestamps?

[Alaric Snell-Pym]

On 24 Aug 2007, at 8:53 pm, John Schultz wrote:

>> So does choosing CAUSAL_MESS over AGREED_MESS actually gain one?
>
> Right now, no.
>
>> Nothing for now, but future implementations may implement CAUSAL_MESS
>> more efficiently?
>

> Exactly!

That's fine. I've noticed that with all sorts of performance-critical
systems, the more information about the client's intentions you can
grab the better; even if you're not using it yet, you'll probably be
able to find uses for it later, in the endless tradeoff between
semantics and speed :-)

> For example, let's say I'm server A and I'm connected with two
> other servers, B and C.  I have a causal message from C with a
> lamport timestamp on it.  I need to somehow know that there are no
> outstanding messages from either B or C with lesser timestamps on
> them before I can deliver this message.  So somehow I must collect
> this knowledge (e.g. - ACK from B and index # of origination from
> C) from those servers.

Ah, good point, I'm being blinkered by my own application domain; out-
of-order delivery of messages matters not to me, since I can discard
an update to a record if the update is timestamped earlier than the
last-modified timestamp in the record.

> The vector timestamp and DAG methods reverse the issue of
> discovering dependency.  When a sender sends a message it knows
> exactly which messages upon which it depends.  So it simply
> attaches that knowledge to the message.  Then when a receiver gets
> the message it knows immediately which messages it has to deliver
> prior to delivering this one.  This method is superior (latency-
> wise) to gathering implicit or explicit ACKs from ALL other
> participating servers before delivering.  It is also more precise
> and introduces no unnecessary dependencies (particularly if it is
> client generated).

Quite!

Thanks for the insights :-)

ABS

--
Alaric Snell-Pym
Work: http://www.snell-systems.co.uk/
Play: http://www.snell-pym.org.uk/alaric/
Blog: http://www.snell-pym.org.uk/?author=4