[Spread-users] Lamport timestamps?

Alaric Snell-Pym alaric at snell-pym.org.uk
Thu Aug 23 16:50:39 EDT 2007

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

For example, on every SP_receive, providing the timestamp at the
sender when the message was transmitted. Rather than change
SP_receive, I'd pack the extra information into the message sent from
the daemon to libspread, but have libspread squirrel it away in the
mbox somewhere, and provide an SP_get_timestamp_of_last_message().

Also, just finding out the 'current' timestamp would be useful.
SP_get_current_timestamp(). And, perhaps, an
SP_get_current_timestamp_and_increment() for use when you want a
stream of ascending timestamps. And, of course,
SP_notify_received_timestamp() to tell the system about a timestamp
received from another node via some means other than Spread, so the
daemon can ensure causilty by making sure its timestamp is more than
the one supplied.

As I said, I've not yet looked into the daemon to see how it handles
causality and timestamps, but I'm guessing there's a Lamport ticker
in there somewhere, that should be fairly easily exposable in a
backwards-compatible way that would save applications from having to

My application is particularly painful since I have a daemon that
runs on each node that receives update messages and writes them to a
database, and HTTP connection handling processes that write update
messages to the group, and in order to ensure that the update
messages get good timestamps, I've had to use shared memory to
implement my own per-node Lamport counter - rather than bother with
making the HTTP request handlers join a group and call SP_receive to
keep their own timestamp up to date. If they could just access an
existing one within the spread daemon, it'd save me a load of messing
around with shared memory and implementing atomic increment on
differing CPUs...

And I need access to actual timestamp values, rather than just
letting Spread order my messages for me, since I keep logs of
timestamped updates, and need to be able to merge such logs and
produce a result in a consistent ordering, so I need to record
timestamps in my log entries!



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

More information about the Spread-users mailing list