null Gedistribueerde algoritmen

Gedistribueerde algoritmen

  • Informatica
  • IB2302
  • 5 EC
  • Vanaf € 352
  • 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 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.

Ingangseisen

Aanmelden voor deze cursus kan pas nadat je de cursussen Computernetwerken (IB0702), Datastructuren en algoritmen (IB1502), (danwel aantoonbare kennis elders), Formele talen en automaten (IB0802), Geavanceerd objectgeoriënteerd programmeren (IB0902), Logica, verzameling en relaties (IB0402) en Objectgeoriënteerd programmeren (IB1102) conform je online studiepad hebt afgerond, dan wel hebt vrijgesteld gekregen dan wel daarvoor bent ingeschreven (en je die cursussen grotendeels bestudeerd hebt).

Toelichting aanmelden

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

De cursus wordt eenmaal 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 vinden plaats 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


Studiedag Informatica en Informatiekunde Den Bosch, onder voorbehoud
Kwartiel 4 - begeleider: dhr. dr. G. Mailette de Buy Wenniger
1. za 04-05-2024 / startbijeenkomst / tijd ntb
Tijdig aanmelden via http://www.ou.nl/studiedag-inf-ink

Online-bijeenkomsten
Kwartiel 4 - begeleider: dhr. dr. G. Mailette de Buy Wenniger
1. wo 08-05-2024 / 19.00-21.00 uur
2. wo 22-05-2024 / 19.00-21.00 uur
3. wo 05-06-2024 / 19.00-21.00 uur
4. wo 19-06-2024 / 19.00-21.00 uur
5. wo 03-07-2024 / 19.00-21.00 uur

Tentamenvorm

Digitaal groepstentamen met open vragen en een practicum.

Tentamentoelichting

U dient zelf tijdig aan te melden voor een tentamen.

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

Tentamendata

Digitaal groepstentamen: 09-07-2024 19:00.
Practicum: volgens afspraak.

Tentamenhulpmiddelen

Het online woordenboek
Het online woordenboek t.b.v. ANS

Cursusmateriaal

Deze cursus bestaat uit:
- tekstboek: ‘Distributed Algorithms: An Intuitive Approach (Second Edition)’ – Wan Fokkink,
- aanvullende lecture notes (verspreid via de online leeromgeving).

Al het cursusmateriaal is in het Engels.

Digitale leeromgeving

Als student kun je, na inschrijving, via de cursussite in de online leeromgeving naar de discussiegroepen. Hier kun je met medestudenten en begeleiders informatie uitwisselen en discussiëren over de leerstof.