NAME
Algorithm::VectorClocks - Generating a partial ordering of events in a distributed system
SYNOPSIS
use Algorithm::VectorClocks;
### in server A ###
Algorithm::VectorClocks->id('A');
my $vc_a = Algorithm::VectorClocks->new;
$vc_a->increment; # same as $vc_a++
my $serialized_a = $vc_a->serialize; # same as "$vc_a"
# send a message with $serialized_a to server B
### in server B ###
Algorithm::VectorClocks->id('B');
my $vc_b = Algorithm::VectorClocks->new;
# receive the message with $serialized_a from server A
$vc_b->merge($serialized_a); # same as $vc_b += $serialized_a
$vc_b->increment;
my $serialized_b = $vc_b->serialize;
### in client ###
# retrieves $serialized_a and $serialized_b
my @res = order_vector_clocks({ A => $serialized_a, B => $serialized_b });
$res[0]; # 'B' is the latest
$res[1]; # 'A'DESCRIPTION
Description, shamelessly stolen from Wikipedia:
Vector Clocks is an algorithm for generating a partial ordering of
events in a distributed system. Just as in Lamport timestamps,
interprocess messages contain the state of the sending process's
logical clock. Vector clock of a system of N processes is an array
of N logical clocks, one per process, a local copy of which is kept
in each process with the following rules for clock updates:
* initially all clocks are zero
* each time a process experiences an internal event, it increments
its own logical clock in the vector by one
* each time a process prepares to send a message, it increments its
own logical clock in the vector by one and then sends its entire
vector along with the message being sent
* each time a process receives a message, it increments its own
logical clock in the vector by one and updates each element in its
vector by taking the maximum of the value in its own vector clock
and the value in the vector in the received message (for every
element).You're encouraged to read the original paper, linked below.
METHODS
Algorithm::VectorClocks->id([$id])
Returns the ID (name) of a server which manages the vector clocks. Sets the server ID if $id is passed.
The default ID is your hostname.
Algorithm::VectorClocks->new([$vc])
Creates a new object of Algorithm::VectorClocks. Arguments can be any one of the following:
Algorithm::VectorClocks object
An Algorithm::VectorClocks object. In this case, this method returns the passed argument $vc.
Serialized object of Algorithm::VectorClocks
A serialized form of Algorithm::VectorClocks object, which can be obtained by method serialize(). In this case, this method behaves like a copy constructor.
$vc->serialize
Returns a serialized form of $vc, which is intended to be exchanged with the other servers.
This module overloads a string conversion operator, and the following code does the same thing:
"$vc"$vc->increment
Increments its own clock in $vc, and returns the object itself.
This module overloads an increment operator, and the following code does the same thing:
$vc++;$vc->merge($other_vc)
Merges $other_vc into $vc itself, and returns the object itself.
This module overloads an assignment forms of additional operator, and the following code does the same thing:
$vc += $other_vc;$vc->equal($other_vc)
Returns true if $vc equals $other_vc.
This module overloads a comparison operator, and the following code does the same thing:
$vc == $other_vc;
$vc eq $other_vc;$vc->not_equal($other_vc)
Returns true unless $vc equals $other_vc.
This module overloads a comparison operator, and the following code does the same thing:
$vc != $other_vc;
$vc ne $other_vc;$vc->clocks
Returns the vector of clocks.
order_vector_clocks({ $id => $vc, ... })
Returns the list of server IDs in order (the latest comes first). The arguments can be a HASH reference of server IDs and their vector clocks.
If some vector clocks are same or independently updated (cannot be ordered), they are packed into single element as an array reference. In the following example, vector clocks of A and C are independent with each other, and B is older than them:
@res = order_vector_clocks({ A => $vc_a, B => $vc_b, C => $vc_c });
$res[0][0]; # is 'A' or 'C'
$res[0][1]; # is 'A' or 'C'
$res[1]; # is 'B'INTERNAL METHODS
_pack_independent_vector_clocks
Packs independent clocks into a single element in a array.
are_independent($vc, ...)
Returns true if any pair of $vc's are independent with each other.
$vc->_is_independent($other_vc)
Returns true if $vc and $other_vc are independent with each other.
$vc->_compare($other_vc)
Compares $vc with $other_vc, which can be an Algorithm::VectorClock object or a serialied one.
Returns a negative value if $vc is a cause of $other_vc. Returns a positive value if $vc is an effect of $other_vc. Returns zero if $vc and $other_vc are same or independent.
_list_ids(@vcs)
SEE ALSO
Friedemann Mattern, "Virtual Time and Global States of Distributed Systems," Proc. Workshop on Parallel and Distributed Algorithms, 1989.
AUTHOR
Takeru INOUE <takeru.inoue _ gmail.com>
LICENCE AND COPYRIGHT
Copyright (c) 2008, Takeru INOUE <takeru.inoue _ gmail.com>. All rights reserved.
This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself. See perlartistic.
DISCLAIMER OF WARRANTY
BECAUSE THIS SOFTWARE IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE SOFTWARE, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE SOFTWARE "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE SOFTWARE IS WITH YOU. SHOULD THE SOFTWARE PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR CORRECTION.
IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE SOFTWARE AS PERMITTED BY THE ABOVE LICENCE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE SOFTWARE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE SOFTWARE TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.