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.
NB: Om race-condities te voorkomen moet het verbinding maken een blokerende actie zijn.
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
Als een process een bericht ontvangt dat een verbinding is verbroken zijn er drie mogelijkheden:
- Het process heeft een actieve verbinding met het process in het negatieve bericht. Het process stuurt een lijst met addresses van de verbonden knopen naar de zender van het negatieve bericht.
- Het process heeft geen actieve verbinding met het process in het negatieve bericht en heeft zelf niet onlangs een negatief bericht verstuurd om het verlies van de verbinding te melden. Het process stuurt alsnog een negatief bericht naar alle verbonden knopen.
- Als het process wel al het verbinding verlies had gemeld gebeurd er niks.
<ip> ::= <number> "." <number> "." <number> "." <number>
<address> ::= <ip> ":" <number>
<addresses> ::= <address> | <address> " :" <address> | <address> " " <addresses>
, ::= " "
. ::= CR LF
"@>" , <addresses> .
"@!" , <address> .
Dit algorithme komt redelijk overeen met het klassieke tokenring algoritme maar gebruikt een volledige graaf als onderliggende netwerk architektuur. Het algorithme gaat van een initiele token ring uit met slechts een knoop waar steeds nieuwe knopen aan worden toegevoegd.
We gaan ervan uit dat de knoop al onderdeel is van een volledige graaf en dat er 1 enkele ring is waar alle andere knopen deel van uit maken. N zal naar slechts 1 andere knoop (K) een verbindingsverzoek sturen. N zal vervolgens wachten tot K actie onderneemt.
Na het ontvangen van het verzoek slaat K dit verzoek op in een interne buffer. Vervolgens wacht deze knoop tot hij het token heeft. We nemen aan dat er geen andere verzoeken zijn: K zal nu het verbindingsverzoek van N inwilligen. Mochten er wel andere verzoeken zijn dan word slechts het eerste verzoek ingewilligd; de overige verzoeken zullen steeds elk per token ronde worden behandeld.
We gaan ervan uit dat K het token heeft. Deze stuurt nu een verbindingsmelding naar alle knopen in de graaf. Ook ontvangt de beheerder van het algoritme een melding. De knoop N krijgt ook deze melding en weet dus dat deze nu onderdeel is van de ring.
De nieuwe tokenring word waargenomen door O. Omdat toevoegen van verbindingen mutual exclusief is en de ordering van de tokenring word bepaald door een lineare ordening op de node id's kan dit veilig worden gedaan. Tevens word er een teller bijgehouden die bij elke nieuwe knoop die word toegevoegd word opgehoogd. Zo kunnen telken unieke id's worden gegenereerd.
K stuurt een token-doorgeef-bericht naar alle knopen in de graaf.
Allereerst controleert O of volgens zijn interne gegevens hij nu verwacht de token te krijgen, als dit het geval is en het token-doorgeef-bericht spreekt dit niet tegen dan neemt O het token aan. Als er wel tegenspraak is kunnen er twee dingen gebeuren:
- Het token-doorgeef-bericht beweert dat O het token krijgt maar O denkt van niet: O stuurt het token direct door naar de knoop waarvan hij denkt dta deze het token moet hebben.
- Het token-doorgeef-bericht beweert dat O niet het token krijgt maar O denkt van wel: O verbreekt de verbinding.
Als O niet het token krijgt maar knoop P wel word er eerst een consistentie check gedaan. Als O geen verbinding meer heeft met knoop P verbreekt O zijn verbinding. P staat namelijk op het punt reliable berichten te sturen die de staat permanent aanpassen; als O deze mist is zij interne staat onheroepelijk inconsistent. [er moet eerst gecontrolleerd worden of er geen verlaat berichten zijn]
Vervolgens worden alle reliable berichten die P gestuurd heeft die nog in de buffer van O staan eerst naar de algoritme beheerder gestuurd. Deze berichten waren tijdelijk opgehouden omdat zij misschien verzonden waren voordat O op de hoogte werd gebracht dat P nu token-houder is. Dit bewaakt de fifo eigenschap van reliable berichten. Het is ook verboden voor knopen om na het versturen van een token-doorgeef-bericht nog reliable berichten te sturen: dit breekt de fifo eigenschap.
Als knoop O net het token heeft worden deze berichten in een buffer opgeslagen; anders worden ze kenbaar gemaakt aan de algorithme beheerder.
Als K het token heeft slaagt deze actie, anders niet.
Deze berichten zijn geheel asynchroom en hebben geen fifo eigenschap. De berichten van 1 en dezelfde afzender echter wel.
Deze knoop wacht tot hij het token heeft. Vervolgens stuurt de knoop een token-doorgeef-en-verlaat-bericht naar alle andere knopen.
De knoop voert het zelfde uit als bij een normaal doorgeef bericht maar zal de knoop uit de lijst verwijderen nadien. Ook krijgt de algoritme beheerder een melding.
Dit kan worden gezien als een token-doorgeef-en-verlaat-bericht met de node die K verwacht.
Een process kan de token niet meer loslaten en in een deadlock gaan. Dit deadlockt het hele spel dan.
"#>" .
Verbinding zoekende knoop stuurt dit naar (slechts) een verbindinghebbende knoop
"#+" , id .
"#+" , id , address .
Eerst: De verbindinghebbende knoop stuurt alle participanten van de tokenring door naar de verbinding hebbende knoop, incluis zichzelf maar in dat geval zonder address. Alle verbonden knopen ontvangen dit eenmaal voor de verbindingzoekende knoop.
"#>" , id .
De verbindinghebbende knoop termineert het protocol door het toegewezen id te sturen naar de verbindingzoekende knoop (en naar deze knoop alleen).
"##" , id .
De huidige tokenhouder geeft zijn token aan de knoop met het gegeven id.
"#!" , id .
De huidige tokenhouder geeft zijn token aan de knoop met het gegeven id en verlaat de tokenring.