Gedistribueerde Algoritmen

Inleiding

In de cursus Algoritmen en Programma's heb je kennis gemaakt met het begrip algoritme. Algoritmen zijn voor een computer wat recepten zijn voor een kok: een reeks instructies die in een eindig aantal stappen van een begintoestand naar een beoogd doel leidt. Daar waar een recept helpt om iets lekkers te maken, zoals een appeltaart of een aardappelsalade, is het doel van een algoritme om iets uit te rekenen: de kortste route tussen twee steden, een plaatje van een fractal, enzovoorts.

De algoritmen in de cursus Algoritmen en Programma's worden uitgevoerd door één enkele computer.  Maar in computernetwerken zijn ook algoritmen nodig waarbij een aantal computers samen een probleem oplossen. We noemen dit gedistribueerde algoritmen.  Voorbeelden van problemen waarbij gedistribueerde algoritmen een rol spelen zijn:

• De computers binnen het internet zijn er gezamenlijk voor verantwoordelijk dat berichten aankomen, ook al vallen er soms verbindingen en computers uit, en zijn er hackers die de boel in het honderd willen laten lopen.
• In vliegtuigen zijn alle belangrijke systemen uitgevoerd in twee- of drievoud, zodat een vliegtuig bestuurbaar ook al gaat er iets kapot. Zo zijn er vaak drie computers met elk een eigen hoogtemeter. Deze computers moeten het eens kunnen worden over de juiste hoogte van het vliegtuig, ook in situaties waarin een van de computers of een van de hoogtemeters stuk is en verkeerde waarden doorgeeft.
• Wanneer een aantal CPUs gebruik maken van een gedeeld geheugen, zoals in een multi-core computer, wil je voorkomen dat meerdere CPUs tegelijk op dezelfde plek in het geheugen lezen of schrijven.