Gedistribueerd computergebruik

ModelsEdit

Veel taken die we met behulp van een computer zouden willen automatiseren zijn van het vraag-antwoord-type: we willen een vraag stellen en de computer moet een antwoord produceren. In de theoretische informatica worden dergelijke taken computationele problemen genoemd. Formeel bestaat een computationeel probleem uit instanties, samen met een oplossing voor elke instantie. Instanties zijn vragen die we kunnen stellen, en oplossingen zijn gewenste antwoorden op deze vragen.

De theoretische informatica probeert te begrijpen welke computationele problemen met behulp van een computer kunnen worden opgelost (computability theory) en hoe efficiënt (computational complexity theory). Traditioneel wordt gezegd dat een probleem met behulp van een computer kan worden opgelost als we een algoritme kunnen ontwerpen dat voor een gegeven instantie een correcte oplossing oplevert. Zo’n algoritme kan worden geïmplementeerd als een computerprogramma dat draait op een computer voor algemeen gebruik: het programma leest een probleemgeval van invoer, voert een berekening uit, en produceert de oplossing als uitvoer. Formalismen zoals random access machines of universele Turing machines kunnen worden gebruikt als abstracte modellen van een sequentiële computer voor algemeen gebruik die zo’n algoritme uitvoert.

Het vakgebied van concurrent en distributed computing bestudeert soortgelijke vragen in het geval van hetzij meerdere computers, hetzij een computer die een netwerk van op elkaar inwerkende processen uitvoert: welke rekenproblemen kunnen in zo’n netwerk worden opgelost en hoe efficiënt? Het is echter helemaal niet duidelijk wat wordt bedoeld met “een probleem oplossen” in het geval van een concurrent of gedistribueerd systeem: wat is bijvoorbeeld de taak van de algoritme-ontwerper, en wat is het concurrent of gedistribueerde equivalent van een sequentiële computer voor algemeen gebruik?

De bespreking hieronder richt zich op het geval van meerdere computers, hoewel veel van de kwesties hetzelfde zijn voor gelijktijdige processen die op een enkele computer draaien.

Drie gezichtspunten worden vaak gebruikt:

Parallelle algoritmen in gedeeld-geheugenmodel

• Alle processoren hebben toegang tot een gedeeld geheugen. De ontwerper van het algoritme kiest het programma dat door elke processor wordt uitgevoerd.
• Een theoretisch model is de parallelle random access machines (PRAM) die worden gebruikt. Het klassieke PRAM-model gaat echter uit van synchrone toegang tot het gedeelde geheugen.
• Gedeelde-geheugenprogramma’s kunnen worden uitgebreid tot gedistribueerde systemen als het onderliggende besturingssysteem de communicatie tussen de knooppunten inkapselt en het geheugen virtueel over alle afzonderlijke systemen verenigt.
• Een model dat dichter bij het gedrag van echte multiprocessormachines staat en rekening houdt met het gebruik van machine-instructies, zoals Compare-and-swap (CAS), is dat van asynchroon gedeeld geheugen. Er is veel werk verricht met betrekking tot dit model, waarvan een samenvatting in de literatuur is te vinden.

Parallelle algoritmen in het message-passing model

• De algoritme-ontwerper kiest de structuur van het netwerk, evenals het programma dat door elke computer wordt uitgevoerd.
• Modellen zoals Booleaanse schakelingen en sorteernetwerken worden gebruikt. Een Booleaans circuit kan worden gezien als een computernetwerk: elke poort is een computer die een uiterst eenvoudig computerprogramma uitvoert. Evenzo kan een sorteernetwerk worden gezien als een computernetwerk: elke comparator is een computer.

Gedistribueerde algoritmen in message-passing model

• De ontwerper van het algoritme kiest alleen het computerprogramma. Alle computers draaien hetzelfde programma. Het systeem moet correct werken, ongeacht de structuur van het netwerk.
• Een veelgebruikt model is een grafiek met één eindige-toestandsmachine per knooppunt.

In het geval van gedistribueerde algoritmen hebben de rekenproblemen meestal betrekking op grafieken. Vaak is de grafiek die de structuur van het computernetwerk beschrijft, de probleeminstantie. Dit wordt geïllustreerd in het volgende voorbeeld.

Een voorbeeldEdit

Overweeg het rekenprobleem van het vinden van een kleuring van een gegeven grafiek G. Verschillende gebieden kunnen de volgende benaderingen volgen:

Gecentraliseerde algoritmen

• De grafiek G wordt gecodeerd als een tekenreeks, en de tekenreeks wordt als invoer aan een computer gegeven. Het computerprogramma vindt een kleuring van de grafiek, codeert de kleuring als een tekenreeks, en geeft het resultaat weer.

Parallelle algoritmen

• Ook hier wordt de grafiek G als een tekenreeks gecodeerd. Meerdere computers kunnen echter parallel dezelfde tekenreeks benaderen. Elke computer kan zich op één deel van de grafiek richten en voor dat deel een kleuring produceren.
• Het accent ligt op krachtige berekeningen die de verwerkingskracht van meerdere computers parallel uitbuiten.

Gedistribueerde algoritmen

• De grafiek G is de structuur van het computernetwerk. Er is een computer voor elke knoop van G en een communicatieverbinding voor elke rand van G. Aanvankelijk weet elke computer alleen van zijn directe buren in de grafiek G; de computers moeten berichten met elkaar uitwisselen om meer te weten te komen over de structuur van G. Elke computer moet zijn eigen kleur als uitvoer produceren.
• Het accent ligt op het coördineren van de werking van een willekeurig gedistribueerd systeem.

Hoewel het gebied van parallelle algoritmen een andere focus heeft dan het gebied van gedistribueerde algoritmen, is er veel interactie tussen de twee gebieden. Zo werd het Cole-Vishkin-algoritme voor het inkleuren van grafieken oorspronkelijk als parallel algoritme gepresenteerd, maar dezelfde techniek kan ook direct als gedistribueerd algoritme worden gebruikt.

Een parallel algoritme kan bovendien zowel in een parallel systeem (met behulp van gedeeld geheugen) als in een gedistribueerd systeem (met behulp van message passing) worden geïmplementeerd. De traditionele grens tussen parallelle en gedistribueerde algoritmen (kies een geschikt netwerk vs. draai in een willekeurig netwerk) ligt niet op dezelfde plaats als de grens tussen parallelle en gedistribueerde systemen (gedeeld geheugen vs. message passing).

ComplexiteitsmaatstavenEdit

In parallelle algoritmen is naast tijd en ruimte nog een andere hulpbron het aantal computers. Vaak is er inderdaad een wisselwerking tussen de looptijd en het aantal computers: het probleem kan sneller worden opgelost als er meer computers parallel draaien (zie speedup). Als een beslissingsprobleem in polylogaritmische tijd kan worden opgelost door een polynomiaal aantal processoren te gebruiken, dan zegt men dat het probleem tot de klasse NC behoort. De klasse NC kan even goed worden gedefinieerd door gebruik te maken van het PRAM-formalisme of van Booleaanse circuits -RAM-machines kunnen Booleaanse circuits efficiënt simuleren en vice versa.

Bij de analyse van gedistribueerde algoritmen wordt gewoonlijk meer aandacht besteed aan communicatieoperaties dan aan rekenstappen. Het eenvoudigste model van gedistribueerd computergebruik is wellicht een synchroon systeem waarin alle knooppunten lockstep werken. Dit model staat algemeen bekend als het LOCAL-model. Tijdens elke communicatieronde ontvangen alle knooppunten parallel (1) de laatste berichten van hun buren, (2) voeren zij willekeurige lokale berekeningen uit, en (3) zenden zij nieuwe berichten naar hun buren. In dergelijke systemen is een centrale complexiteitsmaat het aantal synchrone communicatierondes dat nodig is om de taak te voltooien.

Deze complexiteitsmaat is nauw verbonden met de diameter van het netwerk. Zij D de diameter van het netwerk. Enerzijds kan elk berekenbaar probleem in een synchroon gedistribueerd systeem in ongeveer 2D communicatierondes triviaal worden opgelost: gewoon alle informatie op één plaats verzamelen (D rondes), het probleem oplossen, en elk knooppunt over de oplossing informeren (D rondes).

Aan de andere kant, als de looptijd van het algoritme veel kleiner is dan D communicatierondes, dan moeten de knooppunten in het netwerk hun output produceren zonder de mogelijkheid te hebben om informatie over verafgelegen delen van het netwerk te verkrijgen. Met andere woorden, de knooppunten moeten globaal consistente beslissingen nemen op basis van informatie die beschikbaar is in hun lokale D-buurschap. Er zijn veel gedistribueerde algoritmen bekend met een draaitijd die veel kleiner is dan D-rondes, en begrijpen welke problemen door zulke algoritmen kunnen worden opgelost is een van de centrale onderzoeksvragen van het vakgebied. Een algoritme dat een probleem in polylogaritmische tijd in de netwerkgrootte oplost, wordt in dit model als efficiënt beschouwd.

Een andere veelgebruikte maatstaf is het totale aantal bits dat in het netwerk wordt overgedragen (cf. communicatiecomplexiteit). De kenmerken van dit concept worden doorgaans gevat in het CONGEST(B)-model, dat op dezelfde wijze is gedefinieerd als het LOCAL-model, maar waarin afzonderlijke berichten slechts B bits kunnen bevatten.

Andere problemenEdit

Traditionele computationele problemen hebben als uitgangspunt dat de gebruiker een vraag stelt, een computer (of een gedistribueerd systeem) de vraag verwerkt, vervolgens een antwoord produceert en stopt. Er zijn echter ook problemen waarbij het systeem niet mag stoppen, zoals het dining philosophers problem en andere soortgelijke mutual exclusion problems. Bij deze problemen wordt van het gedistribueerde systeem verwacht dat het voortdurend het gebruik van gedeelde bronnen coördineert, zodat er geen conflicten of impasses ontstaan.

Er zijn ook fundamentele uitdagingen die uniek zijn voor gedistribueerd computergebruik, bijvoorbeeld die in verband met fouttolerantie. Voorbeelden van verwante problemen zijn consensusproblemen, Byzantijnse fouttolerantie en zelfstabilisatie.

Er wordt ook veel onderzoek gedaan naar het begrijpen van het asynchrone karakter van gedistribueerde systemen:

• Synchronisatoren kunnen worden gebruikt om synchrone algoritmen in asynchrone systemen uit te voeren.
• Logische klokken geven een causale “gebeurd-voor” ordening van gebeurtenissen.
• Kloksynchronisatiealgoritmen zorgen voor wereldwijd consistente fysieke tijdstempels.

Verkiezing

Verkiezing van een coördinator (of leider) is het proces waarbij een enkel proces wordt aangewezen als de organisator van een taak die over meerdere computers (nodes) is verdeeld. Voordat de taak begint, weten alle netwerkknooppunten niet welk knooppunt als “coördinator” (of leider) van de taak zal fungeren, of kunnen ze niet communiceren met de huidige coördinator. Nadat echter een algoritme voor de verkiezing van de coördinator is uitgevoerd, herkent elk knooppunt in het netwerk een bepaald, uniek knooppunt als de coördinator van de taak.

De knooppunten in het netwerk communiceren onderling om te beslissen wie van hen in de “coördinator”-toestand zal komen. Daartoe hebben zij een methode nodig om de onderlinge symmetrie te doorbreken. Bijvoorbeeld, als elk knooppunt unieke en vergelijkbare identiteiten heeft, dan kunnen de knooppunten hun identiteiten vergelijken, en besluiten dat het knooppunt met de hoogste identiteit de coördinator is.

De definitie van dit probleem wordt vaak toegeschreven aan LeLann, die het formaliseerde als een methode om een nieuw token te creëren in een token ring netwerk waarin het token verloren is gegaan.

Kiesalgoritmen voor een coördinator zijn ontworpen om zuinig te zijn in termen van totaal aantal verzonden bytes, en tijd. Het door Gallager, Humblet en Spira voorgestelde algoritme voor algemene ongerichte grafieken heeft een grote invloed gehad op het ontwerp van gedistribueerde algoritmen in het algemeen, en heeft de Dijkstra-prijs gewonnen voor een invloedrijk artikel in distributed computing.

Vele andere algoritmen werden voorgesteld voor verschillende soorten netwerkgrafieken, zoals ongerichte ringen, eenrichtingsringen, volledige grafieken, roosters, gerichte Euler-grafieken, en andere. Een algemene methode die de kwestie van de grafiekfamilie loskoppelt van het ontwerp van het algoritme voor de verkiezing van de coördinator werd voorgesteld door Korach, Kutten en Moran.

Om de coördinatie uit te voeren, maken gedistribueerde systemen gebruik van het concept van coördinatoren. Het probleem van de verkiezing van de coördinator is het kiezen van een proces uit een groep processen op verschillende processoren in een gedistribueerd systeem om als centrale coördinator op te treden. Er bestaan verschillende algoritmen voor de verkiezing van de centrale coördinator.

Eigenschappen van gedistribueerde systemenEdit

Tot nu toe lag de nadruk op het ontwerpen van een gedistribueerd systeem dat een gegeven probleem oplost. Een aanvullend onderzoeksprobleem is het bestuderen van de eigenschappen van een gegeven gedistribueerd systeem.

Het halteringsprobleem is een analoog voorbeeld uit het gebied van gecentraliseerde berekeningen: we krijgen een computerprogramma en de taak is te beslissen of het stopt of eeuwig doorloopt. Het halteringsprobleem is in het algemene geval onbeslisbaar, en natuurlijk is het begrijpen van het gedrag van een computernetwerk minstens zo moeilijk als het begrijpen van het gedrag van één computer.

Echter zijn er vele interessante speciale gevallen die wel te ontcijferen zijn. In het bijzonder is het mogelijk te redeneren over het gedrag van een netwerk van eindige-toestandsmachines. Een voorbeeld is te zeggen of een gegeven netwerk van op elkaar inwerkende (asynchrone en niet-deterministische) eindige-toestandsmachines een deadlock kan bereiken. Dit probleem is PSPACE-compleet, d.w.z. het is decidabel, maar het is niet waarschijnlijk dat er een efficiënt (gecentraliseerd, parallel of gedistribueerd) algoritme bestaat dat het probleem in het geval van grote netwerken oplost.