view release on metacpan or  search on metacpan

lib/Algorithm/VectorClocks.pm  view on Meta::CPAN

        elsif ($res != $r) { return 0  } # independent
    }
    $res;
}

sub _list_ids { uniq map { keys %{ $_->clocks } } @_ }

1; # Magic true value required at end of module
__END__

=head1 NAME

Algorithm::VectorClocks - Generating a partial ordering of events in a distributed system


=head1 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'


=head1 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.


=head1 METHODS

=head2 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.


=head2 Algorithm::VectorClocks->new([$vc])

Creates a new object of Algorithm::VectorClocks.
Arguments can be any one of the following:

=over 4

=item * Algorithm::VectorClocks object

An Algorithm::VectorClocks object.
In this case, this method returns the passed argument $vc.

=item * 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.

=back


=head2 $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"

=head2 $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++;

=head2 $vc->merge($other_vc)