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.

cpanm Algorithm::VectorClocks

perl -MCPAN -e shell
install Algorithm::VectorClocks