Giter VIP home page Giter VIP logo

vector-clock's Introduction

Vector Clock and Lamport timestamp PHP library

This project is a PHP implementation of the concept of Vector Clock and Lamport timestamp as defined in the paper : Timestamps in Message-Passing Systems That Preserve the Partial Ordering (paper/vector-clock-paper.pdf).

This library provides :

  • Lamport timestamp
  • Asynchrone vector clock
  • Synchrone vector clock

These implementations carefully follow the research paper and all classes are fully tested (100% coverage).

Every example present in the paper is transcribed as a Phpunit test.

Installation

composer require dynamophp/vector-clock

Lamport timestamp

Usage

<?php

$lt1 = new LamportTimestamp(76);
$lt2 = new LamportTimestamp(59);

assertEquals(76, lt1->getValue());
assertEquals(59, lt2->getValue());
assertTrue($lt1->happenAfter($lt2)); // lt2 -> lt1
assertTrue($lt2->happenBefore($lt1));


$lt1->applyLocalEvent();
$lt2->applyLocalEvent();

assertEquals(77, lt1->getValue());
assertEquals(60, lt2->getValue());
assertTrue($lt1->happenAfter($lt2)); // lt2 -> lt1
assertTrue($lt2->happenBefore($lt1));


$lt1ToSend = clone $lt1->applySendEvent();
$lt2->applyLocalEvent();

assertEquals(78, lt1->getValue());
assertEquals(78, $lt1ToSend->getValue());
assertEquals(61, lt2->getValue());
assertTrue($lt1->isIdenticalTo($lt1ToSend)); // lt1 == lt1ToSend
assertFalse($lt2->isIdenticalTo($lt1ToSend)); // lt2 != lt1ToSend

$lt2->applyReceiveEvent($lt1ToSend);

assertEquals(78, lt1->getValue());
assertEquals(79, lt2->getValue());
assertTrue($lt1->happenBefore($lt2)); // lt1 -> lt2
assertTrue($lt2->happenAfter($lt1));

In the test case : LamportTimestampScenarioTest::testPaperFigure1A and LamportTimestampScenarioTest::testPaperFigure1B you can see the full scenario of the paper :

fig1.png

Asynchrone vector clock

Usage

<?php

// We create three clocks, one for each node in our system
$clockNode1 = new AsyncVectorClock('NODE-1');
$clockNode2 = new AsyncVectorClock('NODE-2');
$clockNode3 = new AsyncVectorClock('NODE-3');

// Then, for each clock, we add the others nodes in the current vector 

$clockNode1->addNode('NODE-2');
$clockNode1->addNode('NODE-3');

$clockNode2->addNode('NODE-1');
$clockNode2->addNode('NODE-3');

$clockNode3->addNode('NODE-1');
$clockNode3->addNode('NODE-2');

// All clocks must look like [0, 0, 0]
// After the initialization part, we can play with our clocks

$a = (clone $clockProcess1)->applySendEvent(); // [1, 0, 0]
$l = (clone $clockProcess2)->applyLocalEvent(); // [0, 1, 0]
$v = (clone $clockProcess3)->applyLocalEvent(); // [0, 0, 1]


$b = (clone $a)->applyLocalEvent(); // [2, 0, 0]
$m = (clone $l)->applyReceiveEvent($a); // [2, 2, 0]
$w = (clone $v)->applyLocalEvent(); // [0, 0, 3]

// And one more important thing, we can compare clocks

assertTrue($l->canBeComparedWith($v)); 

assertTrue($a->isIdenticalTo($a)); // a == a
assertTrue($l->isConcurrentWith($v)); // l <-> v

assertTrue($m->happenAfter($a)); // a -> m
assertTrue($a->happenBefore($m)); // a -> m
assertTrue($l->happenBefore($m)); // l -> m

In the test case : AsyncVectorScenarioTest::testPaperFigure3 you can see the full scenario of the paper :

fig3.png

Synchrone vector clock

Usage

<?php

// We create three clocks, one for each node in our system
$clockNode1 = new SyncVectorClock('NODE-1');
$clockNode2 = new SyncVectorClock('NODE-2');
$clockNode3 = new SyncVectorClock('NODE-3');

// Then, for each clock, we add the others nodes in the current vector 

$clockNode1->addNode('NODE-2');
$clockNode1->addNode('NODE-3');

$clockNode2->addNode('NODE-1');
$clockNode2->addNode('NODE-3');

$clockNode3->addNode('NODE-1');
$clockNode3->addNode('NODE-2');

// All clocks must look like [0, 0, 0] and are idle (i.e. not in communication with another node)
// After the initialization part, we can play with our clocks

assertTrue($clockNode1->isIdle());
assertTrue($clockNode2->isIdle());
assertTrue($clockNode3->isIdle());

$a = (clone $clockNode1)->applyLocalEvent(); // [1, 0, 0]
$t = (clone $clockNode3)->applyLocalEvent(); // [0, 0, 1]

// Then we want to make a synchrone communication between node1 and node2

$b = clone $a; // [1, 0, 0]
$l = clone $clockNode2; // [0, 0, 0]

$b->applySendEvent($l->getNode());
assertTrue($b->isCommunicating());
assertEquals('NODE-2', $b->getCommunicatingNode());

// $b sends its clock and is in a communicating state
// This means that, if you try to modify the clock you will get a ClockIsNotIdleException
// The only way for $b to become idle again is to receive a clock from NODE-2 (the current node is communicating with)
// As soon as $b receive a clock from NODE-2, it will merge it and go back to idle state and can be modified again

$l->applyReceiveEvent($b); // [2, 1, 0]
$b->applyReceiveEvent($l); // [2, 1, 0]

assertTrue($b->isIdle());

// And one more important thing, we can compare clocks

assertTrue($a->canBeComparedWith($t)); 

assertTrue($a->isIdenticalTo($a)); // a == a
assertTrue($l->isIdenticalTo($b)); // l == b

assertTrue($a->isConcurrentWith($t)); // a <-> t

assertTrue($l->happenAfter($a)); // a -> l
assertTrue($a->happenBefore($b)); // a -> b
assertTrue($a->happenBefore($l)); // a -> l

In the test case : SyncVectorScenarioTest::testPaperFigure7 you can see the full scenario of the paper :

fig7.png

How to contribue

Dev environment

You can launch the project locally, either using an old fashion PHP installation or Docker.

If you use Docker, there is a docker-compose file for you in the docker directory.

cd docker && docker-compose up -d

Installing dependencies

Using composer in you dev env :

composer install

Code quality

Your code must be passed through PhpCsFixer :

Fix src/

php vendor/bin/php-cs-fixer fix src --rules=@Symfony

Fix tests/

php vendor/bin/php-cs-fixer fix tests --rules=@Symfony

And be analyzed by Phpstan

php vendor/bin/phpstan analyse src -c /app/phpstan.neon

Tests

The project use PhpUnit

Here is the command to launch the test suite

php vendor/phpunit/phpunit/phpunit --configuration phpunit.xml.dist tests

Note: You need Xdebug for the coverage. If you're using the Docker env provided in this project, it's already installed and configured.

Commit convention

Your commits message musts follow this convention

vector-clock's People

Contributors

baptistecontreras avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar

Forkers

wecomingtoyou

vector-clock's Issues

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.