[Spread-users] Lamport timestamps?

[John Schultz]

On Fri, 24 Aug 2007, Alaric Snell-Pym wrote:
>
> Interesting; I think I'm going to have to put some time aside to read
> those papers on spread's implementation...

Please note that Spread is still using protocols similar to the RING 
protocol of Totem.  The experimental versions of Spread that did fancy 
0wide area stuff have never gone into production.

> It sounds like my current approach (implementing lamport timestamps
> on top of RELIABLE_MESS) is probably the way to go for now, then!

I'm not sure how UNRELIABLE_MESS, RELIABLE_MESS and FIFO_MESS are 
implemented currently, although I believe they are NOT simply AGREED_MESS. 
I do not know, for example, if the daemon waits for the token to send 
these messages or not, which is not strictly needed for these weaker 
types (although possibly necessary for flow control).

> 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!

> Is that worth the tracking overhead, though, compared to a lamport
> timestamp, which after all encodes that the state of the system
> sending the message with timestamp K depeneds on all the message it's
> received with timestamps less than K?
>
> I know that suggests dependencies on messages that the recipient has
> never itself received, which might perhaps cause more to be replayed
> than needs be, but does that outweigh the simplicity of the
> algorithm? ;-)

A lamport timestamp alone is not sufficient to be able to deliver causal 
messages.  In order to deliver a causal message you need to know that all 
causally previous messages in the system have already been delivered.  In 
effect, this means you need to collect an acknowlegement from EACH OF THE 
OTHER PARTICIPANTS that they didn't send any messages causally prior to 
that message.  All the LTS tells you is that if you have two messages then 
the one with the lesser LTS can't be causally dependent upon the one with 
the higher LTS.

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.

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

Cheers!

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