Gedistribueerd Programmeren Samenvatting Geertjan van Vliet
Disclaimer: Aan deze teksten kunnen geen rechten ontleend worden. Bepaalde passages zijn de visie van de auteur en niet die van de docent. Copyright: Een groot gedeelte van de tekst is min of meer letterlijk overgenomen uit het dictaat Gedistribueerd Programmeren van Gerard Tel. Alle rechten tot vermenigvuldiging liggen bij hem.
1
Hoofdstuk 7
Computerprogramma’s moeten robuust worden uitgevoerd, zodat uitval van componenten niet leidt tot dramatische gevolgen. Als threads worden getermineerd door het operating system, dan moeten de overige threads dit goed kunnen opvangen. (bijvoorbeeld goed afsluiten, of de fout detecteren) Een thread die net een semafoor heeft en vervolgens crasht in de kritieke sectie kan de andere threads blokkeren. Een oplossing hiervoor die bijna werkte was een soort van try-catch blok. Als een thread dan crasht dan zal het catch(exception) gedeelte de semafoor weer vrijgeven. Dit werkte echter niet omdat het ook mis kan gaan vlak voor het try-statement. Een try rond het pakken (s.P) zetten werkt ook niet, omdat het kan zijn dat s.P crasht zonder de semafoor te pakken, en dan laat het catch blok wel een s.V gaan. Er zijn diverse soorten storingen mogelijk: 1. crashen 2. omissie : overslaan van instructies 3. onjuiste waarde in geheugen of berichten: Byzantijns falen GDP richt zich op crashes die zich elk moment kunnen voordoen. Voorlopig gaan we ervan uit dat het OS geen mededelingen kan doen over gecrashte threads aan hun collega’s.
1
1.1
Beslisproblemen
Een correct proces crash niet. Bij beslisproblemen moet elk correct proces (dat niet crasht) een uitvoer genereren en voldoen aan voorgangs-, consistentie- en niet-trivialiteitseisen De voortgangs-eis vraagt dat alle correcte processen uiteindelijk iets berekenen. Er zijn drie vormen 1. Deterministische terminatie 2. Probabilistische terminatie (convergentie) 3. Impliciete terminatie (stabilisatie) Deterministische terminatie Er wordt door ieder correct proces een beslissing en schrijft deze beslissing exact ´e´enmaal naar de uitvoervariabele. Probabilistische terminatie De kans dat elk correct proces een beslissing neemt (en dus ´e´enmaal naar de uitvoervariabele schrijf) is 1. Impliciete terminatie Beslissing zijn herroepbaar en de uitvoervariabele wordt telkens verandert. De berekening van elk algoritme is echter eindig en uiteindelijk stabiliseert de beslissing dus. Voorbeelden van beslisproblemen zijn: commit/abort of consensus - alle beslissingen zijn gelijk en electie - een proces beslist op leider en de rest op niet-leider. Niet-trivialiteit : Aan een programma dat altijd dezelfde waarde teruggeeft, onafhankelijk van de invoer is triviaal en niet nuttig te gebruiken. Formeel: Niet-trivialiteit Er is een executie waarin op 0 wordt beslist en een executie waarin op 1 wordt beslist
1.2
Voorbeeld: flexibele electie
Er is een situatie waarin een set processen in staat zijn een beslisprobleem robuust uit te voeren. 1. De n gestarte processen zijn volledig verbonden en kunnen dus naar iedereen berichten sturen. 2. Er crashen maximaal t processen. De variabele t is de veiligheidsparameter, die aangeeft hoeveel crashes het programma aankan. 3. Als n klein is dan roept iedereen naar iedereen. 4. Na het roepen (“shouten”) wacht het proces op shouts van n−t processen, voor tolerantie van t crashes. 5. Omdat processen mogelijk berichten hebben gehoord van gecrashte processen en andere processen niet, hebben de processen niet allemaal dezelfde informatie. Dit kan leiden tot interpretatieproblemen.
2
Vanwege puntje 5 hierboven is zijn de eisen voor electie verzwakt tot flexibele electie: Het aantal leider beslissingen is tenminste 1 en ten hoogste 1 + 2t. Daarnaast is er nog terminatie : In elke executie waar hoogstens t processen crashen beslist elk correct proces op leider of niet-leider. Worden er meerdere ronden uitgevoerd, dan moeten de berichten onderscheidbaar zijn per ronde, omdat er altijd berichten van een vorige ronde kunnen achterblijven in de INBOX, als gevolg van de robuustheid. Een ontvanger deamon moet actief blijven en alle messages die nog bij een vorige ronde horen weggooien. 1.3
Consensus-algoritmen (7.2)
Bij een consensus probleem geldt de volgende eis: Overeenstemming: Alle genomen beslissingen zijn gelijk. Voor ieder probleem wordt een terminatie-eis gespecificeerd en wat dan die gemeenschappelijke beslissing kan of moet zijn. Electie is geen consensus-probleem omdat er juist maar ´e´en proces leider mag worden en de rest niet-leider. Is een kloksynchronisatie nu wel of geen consensus-probleem? Dat hangt ervan af of er sprake is van exacte synchronisatie. In dat geval is het wel en consensus-probleem , maar dit probleem blijkt onoplosbaar (?)
Een (triviaal) programma dat voldoet aan overeenstemming en terminatie is decide(0) De volgende oplossing maakt gebruik van twee servers die hun waarden geven aan al de clients. De clients wachtn op een bericht. Als een van de servers crasht dan komt een waarde toch nog aan en beslissen alle clienten hetzelfde als de server. De twee servers moeten wel a priori overeenstemming hebben, dus niet alle invoercombinaties zijn toegestaan. Er wordt dan dus aan overeenstemming voldaan. Een client termineert als hij een bericht heeft gekregen. Er is dus ook sprake van terminatie zolang niet beide servers crashen. Nu kunnen we ook een zwakke broadcast proberen. Hierbij komt ieder proces de invoer van hetzelfde serverproces te weten. Er wordt een eis toegevoegd: Broadcast: Als de server niet crasht, is elke uitvoer gelijk aan de invoer x van de server. In het broadcast algoritme zal iedere client de waarde doorsturen naar iedere andere client. Zolang een client niks ontvangt blijft de uitvoer hangen op nul en als dus de invoer van de server nul is, zal de server de uitvoer op nul zetten en niets sturen. Als een correct proces (niet-crashend) aan het eind een 1 geeft, dan hebben gegarandeerd alle andere correcte processen ook een 1 als 3
uitvoer. Er is dus overeenstemming. Er is sprake van implicitie terminatie, dwz stabilisatie. Maar in het geval dat de invoer van het algoritme nul is (via de server) dan wordt er geen beslissing genomen door de processen, want ze blijven hangen op nul en wachten om op 1 te gaan. Er is dus geen terminatie. Een oplossing hiervoor is de sterke broadcast. Hierbij wordt met timeouts gewerkt. Daarvoor moet eerst berekend worden hoelang het maximaal kan duren voordat een bericht met een 1 door iedere client ontvangen is. Deze berekening is niet eenvoudig. 1.4
Stelling van Fischer, Lynch en Paterson - 7.3
Even ter herhaling: Niet-trivialiteit Er is een executie waarin op 0 wordt beslist en een executie waarin op 1 wordt beslist Het gaat hier om verschillende executies, want binnen een executie zijn de uitvoeren allemaal gelijk wegens overeenstemming. Hoe maken we een programma dat asynchroon, terminerend en niet-triviaal is en dat alle invoercombinaties (zie replicate servers) aankan. Fischer, Lynch en Paterson hebben aangetoond dat dit niet kan. Hun stelling is Stelling 7.7 - FLP,1985 Er bestaat geen asynchroon, deterministisch 1-crash robuust consensus protocol Hun bewijs bevat de redenering dat mocht er zo’n programma bestaan, noem deze P , dat er een oneindig aantal stappen te verzinnen is binnen zo’n programma waarbij er bij elke stap van P nog een proces is dat kan besluiten tot 1 en nog een proces dat kan besluiten tot 0. Er wordt dus niet besloten en dat is in strijd met terminatie. 1.4.1 Het maken van een model voor een bewijs Een model moet precies en kort de relevante eigenschappen van een klasse van computersystemen beschrijven. Het model wat voor het bewijs van FLP gebruikt wordt is het volgende [letterlijk uit dictaat, newlines toegevoegd] : “Een protocol bestaat uit n ≤ 2 processen , die elk (o.a.) een input register xp en een output register yp hebben. De waarde van yp is 0, 1 of b en dit register mag slechts ´e´enmaal geschreven worden (wanneer proces p beslist). Een configuratie van het protocol bestaat uit de locale toestand van elk proces en de berichtenverzameling van alle berichten, die in de configuratie onderweg zijn. Voor elk bericht is er slechts ´e´en proces, dat dit bericht kan ontvangen. In een 4
initi¨ele configuratie zijn alle yp gelijk aan b, en er zijn geen berichten onderweg. Een initi¨ele configuratie is volledig vastegelegd door de waarden van de xp registers. ”
5
