Dist Algo's
Op deze pagina worden gedistribueerde algorithmen beschreven die door de game worden gebruikt.
Dit algoritme zorgt voor een volledige graaf van FIFO communicatie tussen een aantal processen. Het gebruikt hiervoor een aantal TCP verbindingen waarbij een edge tussen process A en B word gevormd door ofwel een verbinding van A naar B ofwel een verbinding van B naar A (maar niet allebij). Elk process dient ook een luisterend socket te hebben. Een process wat verbinding wil maken met een bestaande volledige graaf probeerd actief verbinding te maken met elk process afzonderlijk. Als dit niet lukt (omdat bijvoorbeeld een van de processen geen luisterend socket heeft) slaagt de verbinding als geheel niet. Als een edge in de graaf verbroken word door welke omstandigheid dan ook probeerd het algoritme dit te herstellen. Als elk process verbinding verliest met hetzelfde andere process word dit process uit de graaf gehaald. Als echter de verbinding enkels tussen twee processen is verbroken en deze kan niet hersteld worden dan faalt de verbinding lokaal.
Het algorithme heeft de volgende invariant:
De verbonden knopen samen met de verbindende knopen in een process is een superset van de verbonden knopen van alle verbonden processen tesamen.
Een process maakt verbinding met een willekeurige knoop in het bestaande netwerk. Deze knoop stuurt een lijst met addressen van de knopen waarmee dit process is verbonden. Deze addressen worden opgeslagen in een verzameling. Er volgt een lus: zolang er nog addressen in deze verzameling zitten waarmee het process niet is verbonden probeert hij verbinding te maken meet een address uit de verzameling. Telkens als een verbinding slaagt wordt word de verzameling uitgebereid met de ontvangen lijst. Als een verbinding niet slaagt faalt de volledige verbinding.
Voorbeeld:
A->X
X >A: XYZ
A->Y
Y >A: XYZ
A->Z
Z >A: XYZ
*** A verbonden
of:
A->X
X >A: XYZ
A->Y
...
*** A niet verbonden
Als een process op zijn luisterende socket een verbinding krijgt stuurt deze een lijst met zijn verbonden knopen. Vervolgens word het inkomende process toegevoegt aan de locale verzameling van verbonden knopen.
A<-X
A >X: A
A<-Y
A >Y: AX
NB: Om race condities te voorkomen moet verbinding acceptatie en toevoegen aan de connectie verzameling atomisch zijn.
Als een process merkt dat 1 van zijn verbindingen is verbroken haalt hij deze uit de connectie verzameling en stuurt een bericht naar alle andere processen. Vervolgens wacht hij op retour berichten van andere processen. Als dit een negatief bericht is voor alle andere processen gebeurd er niks; deze knoop is simpel weg niet meer verbonden. Als een positief bericht word ontvangen herhaalt het process zoals beschreven bij "Verbinding maken".
NB: Om race-condities te voorkomen dienen alle processen eerst te controleren of verbindingen not levend zijn voordat deze berichten van andere processen behandelen.
A is verbonden met X, Y en Z:
A-!X
A >Y: !X
A >Z: !X
A <Y: !X
A <Z: !X
*** X is geen onderdeel meer
of:
A-!X
A >Y: !X
A >Z: !X
A <Y: !X
A <Z: A X Y Z
A->X
A <X: X Z
*** Verbinding herstelt
of:
A-!X
A >Y: !X
A >Z: !X
A <Y: !X
A <Z: A X Y Z
A->X
...
*** A verbreekt de verbinding
<ip> ::= <number> "." <number> "." <number> "." <number>
<address> ::= <ip> ":" <number>
<addresses> ::= <address> | <address> " :" <address> | <address> <addresses>
, ::= " "
. ::= CR LF
"@>" , <addresses> .
"@!" , <address> .