null Gedistribueerde algoritmen

Gedistribueerde algoritmen

  • Informatica
  • IB2302
  • 5 EC
  • Vanaf € 324
  • Voor dit product gelden ingangseisen
Deze cursus heeft een vast startmoment. Kijk in het Jaarrooster wanneer de cursus van start gaat en wanneer de begeleiding is ingeroosterd.



Inhoud

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 degelijke gevallen dat het gedistribueerde systeem volledig faalt, of valt er iets te redden?

Leerdoelen
Bij succesvolle afronding van dit vak zal u:
- bekend zijn met alle (cursieve) begrippen die worden geïntroduceerd in hoofdstuk 2 van het tekstboek en deze kunnen toepassen op concrete situaties;
- de volgende gedistribueerde algoritmen handmatig kunnen toepassen op een klein netwerk: snapshots (Chandy-Lamport; Lai-Yang; Peterson-Kearns), waves (Tarry; Cheung; Awerbuch; Cidon; Chang), deadlock detection (Bracha-Toueg I), termination (Dijkstra-Scholten; Shavit-Francez; Rana; Safra; Mattern; Tseng), election (Chang-Roberts; Franklin; Dolev-Klawe-Rodeh; Gallager-Humblet-Spira; Itai-Rodeh; Tel), en consensus (Bracha-Toueg II; Chandra-Toueg; Bracha Toueg III);
- de gedistribueerde algoritmen genoemd in het vorige punt kunnen implementeren;
- kunnen redeneren over de (in)correctheid en complexiteit van gedistribueerde algoritmen.

Ingangseisen

Aanmelden voor deze cursus kan pas nadat u de cursussen Computernetwerken (IB0702), Logica, verzameling en relaties (IB0402), Formele talen en automaten (IB0802), Objectgeoriënteerd programmeren (IB1102), Geavanceerd objectgeoriënteerd programmeren (IB0902), Webapplicaties: de clientkant (IB1902) en Datastructuren en algoritmen (IB1502) conform uw online studiepad heeft afgerond, dan wel heeft vrijgesteld gekregen dan wel daarvoor bent ingeschreven (en u die cursussen grotendeels bestudeerd heeft).

Toelichting aanmelden

Deze cursus start 26 april 2021. We adviseren om uiterlijk zondag 11 april 2021 hiervoor aan te melden zodat u tijdig het eventuele cursusmateriaal ontvangt, toegang heeft tot de leeromgeving en (indien van toepassing) ingedeeld kunt worden in een studiegroep. Bij aanmelding na 11 april 2021 kunnen we dit niet garanderen. Aanmelden is mogelijk tot en met 25 april 2021.

De cursus wordt éénmaal per academisch jaar aangeboden.

Begeleidingsvorm

Deze cursus heeft een vast startmoment. Kijk in het Jaarrooster wanneer de cursus van start gaat en wanneer de begeleiding is ingeroosterd.

Begeleidingsbijeenkomsten via Collaborate, met Engelse slides en Nederlandse spraak (als er een Engelstalige student in de groep aanwezig is, kan worden overgeschakeld op het Engels).

Begeleidingsbijeenkomsten


Online bijeenkomsten
Kwartiel 4 - begeleider: dhr. dhr.ir. S. Jongmans
1. do 06-05-2021 / 19.00-21.00 uur
2. wo 19-05-2021 / 19.00-21.00 uur
3. wo 02-06-2021 / 19.00-21.00 uur
4. wo 16-06-2021 / 19.00-21.00 uur
5. wo 30-06-2021 / 19.00-21.00 uur

Tentamenvorm

Regulier schriftelijk tentamen bestaande uit open vragen (ov) en een practicum.

Tentamentoelichting

Afhankelijk van welke maatregelen noodzakelijk zijn om het coronavirus te bestrijden, is het mogelijk dat de Open Universiteit de tentaminering moet vervangen door een (online) alternatief. Meer informatie hierover vindt u op www.ou.nl/informatie-coronavirus. De actuele tentameninformatie met betrekking tot deze cursus vindt u na aanmelding in de online cursusomgeving.

U dient zelf tijdig aan te melden voor een tentamen.

De vragen zijn in het Engels, maar studenten mogen in het Nederlands antwoorden.

Tentamendata

Schriftelijk tentamen: 06-07-2021.
Practicum: volgens afspraak.

Tentamenhulpmiddelen

Een 'schoon' verklarend Nederlands woordenboek (op eigen risico)

Cursusmateriaal

Deze cursus bestaat uit:
- Tekstboek: ‘Distributed Algorithms: An Intuitive Approach (Second Edition)’ – Wan Fokkink;
- Aanvullende lecture notes (verspreid via de digitale leeromgeving).

Al het cursusmateriaal is in het Engels.

Digitale leeromgeving

Als student kunt u via de cursussite in de digitale leeromgeving naar de discussiegroepen. Hier kunt u met medestudenten en begeleider informatie uitwisselen en discussiëren over de leerstof.