Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
201 lines (69 sloc) 4.68 KB

#Module unsplit_vclock#

A simple Erlang implementation of vector clocks as inspired by Lamport logical clocks.

Copyright (c) 2007-2008 Basho Technologies

Authors: Justin Sheehy (justin@basho.com), Andy Gross (andy@basho.com).

References* Leslie Lamport (1978). "Time, clocks, and the ordering of events in a distributed system". Communications of the ACM 21 (7): 558-565.

  • Friedemann Mattern (1988). "Virtual Time and Global States of Distributed Systems". Workshop on Parallel and Distributed Algorithms: pp. 215-226

##Data Types##

###counter()##

counter() = integer()

###node()##

node() = term()

Nodes can have any term() as a name, but they must differ from each other.

###timestamp()##

timestamp() = integer()

###vc_entry()##

vc_entry() = {node(), {counter(), timestamp()}}

The timestamp is present but not used, in case a client wishes to inspect it.

###vclock()##

vclock() = [vc_entry]

##Function Index##

all_nodes/1Return the list of all nodes that have ever incremented VClock.
descends/2Return true if Va is a direct descendant of Vb, else false -- remember, a vclock is its own descendant!
equal/2Compares two VClocks for equality.
fresh/0Create a brand new vclock.
get_counter/2Get the counter value in VClock set from Node.
get_timestamp/2Get the timestamp value in a VClock set from Node.
increment/2Increment VClock at Node.
merge/1Combine all VClocks in the input list into their least possible common descendant.
prune/3Possibly shrink the size of a vclock, depending on current age and size.

##Function Details##

###all_nodes/1##

all_nodes(VClock::vclock()) -> [node()]



Return the list of all nodes that have ever incremented VClock.

###descends/2##

descends(Va::vclock(), Vb::vclock()) -> bool()



Return true if Va is a direct descendant of Vb, else false -- remember, a vclock is its own descendant!

###equal/2##

equal(VClockA::vclock(), VClockB::vclock()) -> true | false



Compares two VClocks for equality. Not very fast.

###fresh/0##

fresh() -> vclock()



Create a brand new vclock.

###get_counter/2##

get_counter(Node::node(), VClock::vclock()) -> counter()



Get the counter value in VClock set from Node.

###get_timestamp/2##

get_timestamp(Node::node(), VClock::vclock()) -> timestamp()



Get the timestamp value in a VClock set from Node.

###increment/2##

increment(Node::node(), VClock::vclock()) -> vclock()



Increment VClock at Node.

###merge/1##

merge(VClocks::[vclock()]) -> vclock()



Combine all VClocks in the input list into their least possible common descendant.

###prune/3##

prune(V::vclock(), Now::integer(), BucketProps::term()) -> vclock()



Possibly shrink the size of a vclock, depending on current age and size.