Samenvatting proefschrift

Communicatie netwerken als het Internet verbinden computers onderling. Dit maakt het mogelijk om met meerdere computers tegelijk een taak te verrichten. Daarbij vormen de computers en het netwerk een zogenaamd gedistribueerd systeem. Communicatie, synchronizatie en fout-tolerantie vormen een belangrijk bestanddeel van zo'n systeem. Ze worden echter zelden volledig door de hardware ondersteund, en zeker niet tot op het noodzakelijke nivo.

Onderzoek naar gedistribueerde algoritmen heeft tot doel efficiente algoritmen voor allerlei nivo's van communicatie, synchronizatie en fout-tolerantie te ontwikkelen en te analyseren. Dit proefschrift analyseert een zevental problemen op dit gebied, en bevat verschillende algoritmen als oplossing daarvan.

Routering is een bekend communicatie probleem. Voor het effectief versturen van boodschappen over wereldwijde netwerken als het Internet moet de bestemming binnen afzienbare tijd bereikt worden. Dit proefschrift bewijst dat dit mogelijk is mits men bereid is om op elk van de computers op de route gemiddeld veel geheugen te spenderen aan de routerings-tabellen.

Computer fouten komen veelvuldig voor. Computers kunnen vastlopen; kortstondige storingen kunnen waarden opgeslagen in het geheugen veranderen. Fout-tolerante algoritmen verbergen of verhelpen de effecten van dergelijke fouten.

Zelf-stabiliserende algoritmen herstellen automatisch van geheugenfouten. In dit proefschrift worden twee van zulke algoritmen beschreven: voor wederzijdse uitsluiting en voor ring-orientatie.

Zogenaamde wait-free algoritmen laten een computer zinvol voortgang maken zelfs als alle andere computers zijn vastgelopen. In dit proefschrift wordt een wait-free implementatie van snapshot objecten uit binaire snapshot objecten beschreven, en wordt het eerste snelle algoritme voor long-lived renaming afgeleid.

Een belangrijk probleem is het bereiken van overeenstemming tussen computers over, bijvoorbeeld, een gemeten waarde, terwijl een fractie van de computers (eventueel willens en wetens) foutief functioneerd. Alle correcte computers moeten eenmalig allemaal dezelfde meetwaarde kiezen. De gekozen meetwaarde moet ook echt door één van de computers gemeten zijn. Dit probleem is oplosbaar als ten alle tijde slechts 1/3-de van de computers geïnfecteerd is. Zelfs als de computer fouten zich, als virussen, over het netwerk verspreiden, tenminste als ook nog één van de computers altijd gezond is.

Tenslotte wordt in dit proefschrift een aanzet gegeven voor onderzoek naar extreem fout-tolerante algoritmen die zowel geheugen-fouten als computer crashes kunnen overleven. Eerst wordt een algemene definitie van wait-free zelf-stabilizerende geheugen objecten gegeven; daarna komen enkele implementaties aan bod.

Thesis summary

(TBD)