Vektorklokke - Vector clock

En vektorklokke er en datastruktur som brukes til å bestemme den delvise rekkefølgen av hendelser i et distribuert system og påvise kausalitetsbrudd . På samme måte som i Lamport-tidsstempler , inneholder meldinger mellom prosesser tilstanden til senderprosessens logiske klokke . En vektorklokke i et system med N -prosesser er en matrise /vektor av N logiske klokker, en klokke per prosess; en lokal "størst mulige verdier" -kopi av det globale klokkeoppsettet beholdes i hver prosess.

Betegn som vektorklokke vedlikeholdt ved prosess i, klokkeoppdateringene fortsetter som følger:

Image
Eksempel på et system med vektorklokker. Hendelser i den blå regionen er årsakene til hendelse B4, mens hendelsene i den røde regionen er effektene av hendelse B4.
  • I utgangspunktet er alle klokker null.
  • Hver gang en prosess opplever en intern hendelse, øker den sin egen logiske klokke i vektoren med en. For eksempel, ved en hendelse under prosess i, oppdateres den .
  • Hver gang en prosess sender en melding, øker den sin egen logiske klokke i vektoren med en (som i kula ovenfor, men ikke to ganger for den samme hendelsen), og deretter sender meldingen en kopi av sin egen vektor.
  • Hver gang en prosess mottar en melding, øker den sin egen logiske klokke i vektoren med en og oppdaterer hvert element i sin vektor ved å ta maksimum av verdien i sin egen vektorklokke og verdien i vektoren i den mottatte meldingen (for hvert element). For eksempel, hvis prosess Pj mottar en melding m fra Pi, oppdateres den ved å sette .

Historie

Uten å bruke det spesifikke navnet "vektorklokke", ble konseptet med en vektorklokke først nevnt i et papir fra 1986 av Rivka Ladin og Barbara Liskov der de bruker begrepet "flerstemmig tidsstempel". For å sitere fra side 31 i Liskov/Ladin -papiret:

Vi løser dette problemet ved å bruke tidsstempler med flere deler , der det er en del for hver kopi. Så hvis det er n kopier, er et tidsstempel t

t = <t1, …, tn>

hvor hver del er et positivt heltall. Siden det vanligvis vil være et lite antall kopier (f.eks. 3 til 7), er det praktisk å bruke en slik tidsstempel.

Begrepet "vektorklokke" ble først brukt uavhengig av Colin Fidge og Friedemann Mattern i 1988.

Delvis bestilling av eiendom

Vektorklokker gir mulighet for delvis ordning av hendelser. Definere følgende:

  • betegner vektorklokken for hendelsen , og angir komponenten i den klokken for prosess .
    • På engelsk: er mindre enn , hvis og bare hvis er mindre enn eller lik for alle prosessindekser , og minst ett av disse forholdene er strengt mindre (det vil si ).
  • angir at hendelsen skjedde før hendelsen . Det er definert som: if , then

Egenskaper:

  • Antisymmetri : hvis , så ¬
  • Transitivitet : hvis og , da ; eller, hvis og , da

Forholdet til andre ordre:

  • La det være sanntid når hendelsen skjer. Hvis , da
  • La oss være Lamport -tidsstempelet for hendelsen . Hvis , da

Andre mekanismer

  • I 1999 utviklet Torres-Rojas og Ahamad Plausible Clocks , en mekanisme som tar mindre plass enn vektorklokker , men som i noen tilfeller helt vil bestille hendelser som er kausalt samtidige.
  • I 2005 opprettet Agargwal og Garg Chain Clocks , et system som sporer avhengigheter ved hjelp av vektorer som er mindre enn antall prosesser, og som tilpasser seg automatisk til systemer med dynamisk antall prosesser.
  • I 2008 uttalte Almeida et al. introduserte Intervalle treklokker . Denne mekanismen generaliserer vektorklokker og tillater drift i dynamiske miljøer når identitetene og antall prosesser i beregningen ikke er kjent på forhånd.
  • I 2019 utviklet Lum Ramabaja Bloom Clocks , en sannsynlig datastruktur hvis romkompleksitet ikke er avhengig av antall noder i et system. Hvis to klokker ikke er sammenlignbare, kan blomsterklokken alltid utlede det, det vil si at falske negativer ikke er mulige. Hvis to klokker er sammenlignbare, kan blomsterklokken beregne tilliten til utsagnet, dvs. den kan beregne den falske positive frekvensen mellom sammenlignbare par klokker.

Se også

Referanser

Eksterne linker