miniatura|Exemple d'un sistema de rellotges vectorials. Els esdeveniments de la regió blava són les causes que condueixen a l'esdeveniment B4, mentre que els de la regió vermella són els efectes de l'esdeveniment B4. Un rellotge vectorial és una estructura de dades que s'utilitza per determinar l'ordre parcial dels esdeveniments en un sistema distribuït i detectar violacions de causalitat. Igual que en les marques de temps de Lamport, els missatges entre processos contenen l'estat del rellotge lògic del procés emissor. Un rellotge vectorial d'un sistema de N processos és una matriu /vector de N rellotges lògics, un rellotge per procés; es guarda una còpia local de "valors més grans possibles" de la matriu de rellotge global a cada procés.
Denota com el rellotge vectorial mantingut pel procés , les actualitzacions del rellotge es duen a terme de la següent manera:
Inicialment tots els rellotges són a zero. Cada vegada que un procés experimenta un esdeveniment intern, incrementa el seu propi rellotge lògic en el vector en una unitat. Per exemple, en un esdeveniment al procés , s'actualitza . Cada vegada que un procés envia un missatge, incrementa el seu propi rellotge lògic en el vector en un (com en el punt anterior, però no dues vegades per al mateix esdeveniment), després emparella el missatge amb una còpia del seu propi vector i finalment envia el parell. Cada vegada que un procés rep un parell de rellotge missatge-vector, incrementa el seu propi rellotge lògic en el vector en un i actualitza cada element del seu vector prenent el màxim del valor del seu propi rellotge vectorial i el valor del vector en el parell rebut (per a cada element). Per exemple, si el procés rep un missatge de , primer incrementa el seu propi rellotge lògic en el vector en un i després actualitza tot el seu vector establint .
Història Lamport va originar la idea dels rellotges lògics de Lamport el 1978. Tanmateix, els rellotges lògics d'aquell article eren escalars, no vectors. La generalització al temps vectorial va ser desenvolupada diverses vegades, aparentment de forma independent, per diferents autors a principis dels anys vuitanta. Almenys 6 articles contenen el concepte. Els articles citats canònicament en referència als rellotges vectorials són els treballs de Colin Fidge i Friedemann Mattern de 1988, ja que (independentment) van establir el nom "rellotge vectorial" i les propietats matemàtiques dels rellotges vectorials.
Propietat d'ordenació parcial Els rellotges vectorials permeten l'ordenació causal parcial dels esdeveniments. Definint el següent:
denotes the vector clock of event , and denotes the component of that clock for process .
In English: is less than , if and only if is less than or equal to for all process indices , and at least one of those relationships is strictly smaller (that is, ). denotes that event happened before event . It is defined as: if , then
Antisimetria: si , aleshores ¬ Transitivitat: si i , aleshores ; o, si i , aleshores
Relació amb altres comandes Sigui el moment real en què es produeix l'esdeveniment passa. Si , aleshores Sigui la marca de temps de Lamport de l'esdeveniment Si , aleshores
Limitacions sota els fracassos bizantins Els rellotges vectorials poden detectar de manera fiable la causalitat en sistemes distribuïts subjectes a errors de bloqueig. Tanmateix, quan els processos es comporten de manera arbitrària o maliciosa, com en el model de fallada bizantí, la detecció de la causalitat esdevé fonamentalment impossible, cosa que fa que els rellotges vectorials siguin ineficaços en aquests entorns. Aquest resultat d'impossibilitat es vàlid per a totes les variants dels rellotges vectorials, ja que prové de les limitacions bàsiques inherents al problema de la detecció de la causalitat en fallades bizantines.
Altres mecanismes El 1999, Torres-Rojas i Ahamad van desenvolupar els rellotges plausibles, un mecanisme que ocupa menys espai que els rellotges vectorials però que, en alguns casos, ordenarà totalment esdeveniments que són causalment concurrents.
El 2005, Agarwal i Garg van crear Chain Clocks, un sistema que rastreja les dependències mitjançant vectors amb una mida més petita que el nombre de processos i que s'adapta automàticament a sistemes amb un nombre dinàmic de processos. El 2008, Almeida et al. van introduir els rellotges d'arbre d'intervals. Aquest mecanisme generalitza els rellotges vectorials i permet el funcionament en entorns dinàmics quan les identitats i el nombre de processos del càlcul no es coneixen per endavant.
El 2019, Lum Ramabaja va proposar els rellotges de Bloom, una estructura de dades probabilística basada en filtres de Bloom. En comparació amb un rellotge vectorial, l'espai utilitzat per node és fix i no depèn del nombre de nodes d'un sistema. La comparació de dos rellotges produeix un veritable negatiu (els rellotges no són comparables), o bé un suggeriment que un rellotge precedeix l'altre, amb la possibilitat d'un fals positiu on els dos rellotges no estan relacionats. La taxa de falsos positius disminueix a mesura que es permet més emmagatzematge.
Referències
Categoria:Algorismes Categoria:Lògica