Gedistribueerde algoritmen

Een gedistribueerd systeem is een softwaresysteem dat bestaat uit meerdere componenten die op verschillende machines worden uitgevoerd en berichten met elkaar uitwisselen via een netwerk. Gedistribueerde systemen zijn niet meer weg te denken uit de moderne samenleving: webapplicaties, cloudtechnologie, en blockchains zijn slechts enkele voorbeelden van gedistribueerde systemen waar zowel IT-professionals als ‘de gewone burger’ dagelijks mee geconfronteerd worden. De vraag naar gedistribueerde systemen zal in de toekomst bovendien alleen maar toenemen, gevoed door nieuwe ontwikkelingen en innovaties zoals internet of things en smart cities.

Gedistribueerde systemen hebben een aantal kenmerken die hun ontwikkeling uiterst uitdagend maakt. Een belangrijke bron van complicaties is het feit dat het berichtenverkeer tussen de componenten van een gedistribueerd systeem niet instantaan verloopt, maar asynchroon: er zit altijd wat tijd tussen het versturen en het ontvangen van een bericht, en de verstuurder weet bovendien niet wanneer de ontvanger het bericht daadwerkelijk heeft verwerkt. Om de situatie nog complexer te maken, is het daarnaast mogelijk dat berichten in een andere volgorde worden ontvangen dan dat ze zijn verstuurd, zelfs als er slechts één verstuurder is. De kunst is om, ondanks deze onzekerheden, er toch voor te zorgen dat alle componenten op een juiste manier informatie met elkaar uitwisselen en gezamenlijk de gewenste functionaliteit realiseren.

In dit vak bestuderen we grondbeginselen van gedistribueerde systemen vanuit een algoritmisch perspectief: we nemen kennis van een aantal gedistribueerde algoritmen, wier executie is verspreid over de componenten van een gedistribueerd systeem, en waarbij communicatie tussen de componenten een essentiële rol speelt.

Een voorbeeld van een fundamenteel probleem is het volgende. Stel dat één van de componenten van een gedistribueerd systeem een kopie wil maken van de globale toestand van het hele systeem (namelijk, de waarden van alle variabelen in alle componenten). Het probleem lijkt misschien eenvoudig: de component stuurt simpelweg een bericht naar alle andere componenten om hen te vragen om een kopie van hun lokale toestand, waarna die andere componenten zo’n kopie maken en terugsturen. Het probleem is de timing: de tijd tussen het versturen en het ontvangen van de kopieerverzoeken is voor elk van de componenten anders, waardoor de kopieën niet allemaal op hetzelfde moment gemaakt worden. Het gevolg is dat de collectie van lokale toestanden die uiteindelijk wordt opgeleverd niet per se een globale toestand van het hele systeem is geweest, maar een samensmelting van losse delen van een reeks globale toestanden.

Andere fundamentele problemen waar we naar zullen kijken, zijn: het detecteren van een deadlock (alle componenten wachten op elkaar en maken daardoor geen van alle voortgang); het detecteren van terminatie (alle componenten zijn klaar met hun werk); het kiezen van een gemeenschappelijke leider (een unieke component in het systeem die ‘democratisch’ is gekozen door de andere componenten); en het kiezen van een gemeenschappelijke waarde (een uniek getal waarover de componenten in het systeem consensus hebben bereikt). We zullen bovendien aandacht besteden aan situaties waarin componenten plotseling uitvallen of zich oneigenlijk gedragen. Accepteren we in dergelijke gevallen dat het gedistribueerde systeem volledig faalt, of valt er iets te redden?

Leerdoelen
Na bestudering van deze cursus kun je:
- alle (cursieve) begrippen die worden geïntroduceerd in hoofdstuk 2 van het tekstboek uitleggen en toepassen op concrete situaties,
- de volgende gedistribueerde algoritmen handmatig toepassen op een klein netwerk: snapshots (Chandy-Lamport; Lai-Yang), waves (Tarry; Awerbuch; Cidon; Chang), deadlock detection (Bracha-Toueg), termination (Dijkstra-Scholten; Shavit-Francez; Rana; Safra), election (Chang-Roberts; Franklin; Dolev-Klawe-Rodeh; Itai-Rodeh), en enkele probabilistische gedistribueerde algoritmen,
- de gedistribueerde algoritmen genoemd in het vorige punt implementeren,
- redeneren over de (in)correctheid en complexiteit van gedistribueerde algoritmen.