; receive to q } // Verzamel n-t identiteiten S = {p} // Proces p kent zichzelf while ( |S| < n-t ) { receive to q do ; S = S+{q} } <= t+1 ) then { decide(leider) } else { decide(niet-leider) } if (q > p) { state = leider } else { state = niet-leider } Maar helaas, we moeten de aanname maken dat elke rangschikking van de namen mogelijk is, en dan kunnen er meerdere processen in de leider toestand terecht komen. De meeste algoritmen zijn wel gebaseerd op het onderling vergelijken van de namen, je kunt dit zien in sectie 5.3. De algoritmen hebben dan de eigenschap dat de executies hetzelfde blijven als je de identiteitsnummers wijzigt met behoud van onderlinge volgorde. Voor het geven van voorbeeld-executies of het analyseren van complexiteit kun je dan steeds uitgaan van de situatie dat de procesnummers de getallen 1 tot n zijn, maar nogmaals, de werking van het programma mag niet van dat uitgangspunt afhangen! 5.2.3
Circuleer een token
Je kunt het ongeveer zo proberen zoals je in een array van getallen het minimum bepaalt. Het eerste proces zendt zijn nummer naar de volgende, en elk proces zal, na ontvangst van een nummer, het minimum van het ontvangen nummer en zijn eigen nummer doorgeven. Na enige tijd (en uitwisseling van n berichten) ontvangt de beginner een bericht met het minimum erin. Een berichtje dat steeds wordt doorgegeven, eventueel met aanpassing aan de inhoud, tot het weer terugkomt waar het begon wordt vaak een token genoemd. Bedenk dat feitelijk steeds van een nieuw berichtje sprake is: en dat de ontvangst van ´e´en bericht alleen maar de aanleiding is om een nieuw bericht aan de volgende in de ring te sturen. Er is echter niet zoiets als “het eerste proces”, immers, alle processen zijn in dezelfde begintoestand! Als we reeds over een leider zouden beschikken, ja, dan konden we met n berichten het minimum achterhalen...
5.3
Enkele oplossingen
5.3.1
Het algoritme van LeLann
In 1977 publiceerde G´erard LeLann [LeL77] de volgende oplossing: 1. Elk proces stuurt een bericht rond met z’n eigen nummer. 2. Binnenkomende berichten met andere nummers worden doorgestuurd. 3. Een proces dat zijn eigen nummer ontvangt, beslist over leiderschap. Dit is nl. het teken dat het alle berichten heeft gezien. 4. Een proces dat het kleinste nummer heeft van alle die het gezien heeft, wordt leider. Het algoritme gebruikt dat kanalen de first-in, first-out (kortweg fifo) eigenschap hebben, dat wil zeggen dat berichten elkaar niet inhalen in de kanalen. Buffers zoals in hoofdstuk 3 hebben die eigenschap, maar die hoeft niet bij elk systeem te gelden.
5.3 Enkele oplossingen
67
Wat is de complexiteit? Het ziet ernaar uit dat elk proces ´e´en berichtje maakt, dat dan helemaal rondgaat: n berichten dus. Maar omdat elk bericht n keer wordt doorgestuurd is de complexiteit n2 . We tellen immers niet het aanmaken, maar het versturen van berichten. 5.3.2
Het algoritme van Chang en Roberts
Chang en Roberts bedachten in 1979 dat zo’n rondgaand berichtje best ge¨elimineerd mag worden door een proces met kleinere identiteit: dat constateert immers dat de afzender van het bericht niet zal winnen. 1. Elk proces stuurt een bericht rond met z’n nummer. 2. Elk proces stuurt berichten met kleinere namen dan zijn eigen door (en het wordt meteen niet-leider). Berichten met grotere nummers worden niet doorgestuurd. 3. Een proces dat zijn eigen nummer ontvangt wordt leider. Waarom werkt het? Zij MIN het kleinste proces. Omdat de ring rond is, komt het nummer van elk ander proces langs MIN (als het niet al eerder gestopt is), ergo, een proces anders dan MIN ziet z’n bericht niet terug. Niemand houdt MIN’s bericht tegen, en MIN ziet dus zijn bericht wel terug en wordt leider. Wat is de complexiteit? Het aantal berichten blijkt nu sterk af te hangen van de verdeling van stations over de ring! In het beste geval zijn de processen in dalende volgorde gerangschikt en er zijn dan 2n − 1 berichten. In het slechtste geval zijn de processen oplopend gerangschikt, elk bericht wordt pas afgestopt door MIN, en er zijn 21 n(n + 1) berichten. Het kunstige van Chang en Roberts’ werk [CR79] was dat zij inzagen dat het aantal berichten alleen afhangt van de rangschikking van processen op de ring, en niet van non-determinisme tijdens de executie. Zij slaagden er zelfs in, de gemiddelde complexiteit te berekenen. Propositie 5.1 Het gemiddelde aantal berichten (over de (n − 1)! verschillende rangschikkingen) is n.Hn . Hier is Hn het harmonisch getal 1 + 1/2 + 1/3... + 1/n, ongeveer ln n ofwel 0.693. lg n. De berekening is niet zo spannend, meer iets om thuis door te lezen. 5.3.3
Het algoritme van Peterson
Nu was de race goed geopend en men vroeg zich af of het ook met O(n lg n) berichten in worst case kon. Inderdaad lukte dit Hirschberg en Sinclair in 1980, maar zij namen wel aan dat er communicatie in beide richtingen over de ring mogelijk was (bidirectionele communicatie). We bekijken nu een variant van Peterson uit 1982 [Pet82] die hetzelfde voor elkaar krijgt maar iets simpeler is. De electie wordt gehouden in een aantal ronden, die tot doel hebben het aantal kandidaten te reduceren. 1. De eerste ronde begint met alle n processen als kandidaat voor het leiderschap. 2. In een ronde die met k > 1 kandidaten begint, worden ten minste k/2 kandidaten en ten hoogste k − 1 kandidaten ge¨elimineerd. 3. Als een ronde met 1 kandidaat begint, merkt deze dat hij de enige is en wordt leider. De kandidaten noemen we actief, degenen die al geelimineerd zijn passief; de eerste ronde begint dus met iedereen actief. Hier is de werking van een ronde.
68
5 Electie
1. Een actief station stuurt zijn nummer naar links en naar rechts. 2. Een passief station stuurt wat van rechts komt door naar links en wat van links komt naar rechts. 3. Een actief station ontvangt vervolgens een nummer van links en een van rechts. • Als deze gelijk zijn aan het eigen nummer, wordt het leider. • Als een van de nummers kleiner is dan het eigen nummer wordt het passief. • Als beide nummers groter zijn dan het eigen nummer gaat het actief naar de volgende ronde. Lemma 5.2 Er zijn ten hoogste lg n + 1 ronden. Bewijs. Een kandidaat kan de ronde alleen overleven als hij kleiner is dan zijn beide buurkandidaten. Hoogstens de helft van de kandidaten kan daarom overleven, en na ten hoogste lg n ronden is er slechts ´e´en kandidaat over. Dan is er nog 1 ronde waarin die kandidaat gekozen wordt. ¤ Lemma 5.3 In elke ronde worden precies 2n berichten verstuurd. Bewijs. Elk proces stuurt in een ronde precies ´e´en bericht naar links en ´e´en bericht naar rechts. ¤ De conclusie uit deze twee lemma’s is dat het algoritme electeert met circa 2n lg n berichten. Na publicatie van het artikel van Hirschberg en Sinclair werd nog enige tijd geloofd dat een O(n lg n) oplossing alleen mogelijk was met bidirectionele communicatie, maar dat er in geval van ´e´enrichtingsverkeer geen betere oplossing bestond dan Θ(n2 ) worst-case. Peterson liet echter ook zien dat je met een truukje zijn algoritme zo kon veranderen dat het in een unidirectionele ring werkt, zonder dat het meer berichten kost (zie kader 5.2). Zo bewees Peterson deze stelling: Stelling 5.4 Er bestaat een algoritme voor electie op een unidirectionele ring van n processen dat O(n lg n) berichten gebruikt in het slechtste geval. Peterson wist zijn idee nog zover te verbeteren dat het aantal berichten werd begrensd door 1.44n lg n worst-case, zowel bi- als unidirectioneel. De meeste berichten worden verstuurd door passieve stations, voor het doorsturen van de nummers van actieven, die immers steeds verder uit elkaar komen te liggen. Als het mogelijk is om directe kanalen te openen tussen actieve stations, kan de complexiteit tot lineair worden teruggebracht.
5.4
Een bewijs van ondergrens
Natuurlijk ging men zich na de uitvinding van Hirschberg en Sinclair afvragen of nog substanti¨ele verbeteringen mogelijk waren: bestaat er een algoritme met een asymptotisch lagere communicatiecomplexiteit, bijvoorbeeld O(n lg lg n) of O(n) berichten? Het antwoord is negatief, want Burns [Bur80] wist te bewijzen dat elk electie algoritme een executie heeft waarin tenminste 21 n lg n berichten worden ontvangen.
5.4 Een bewijs van ondergrens
69
Kader 5.2: Uitwisseling met eenrichtingsverkeer Een kaboutervolk leefde langs een lange oostwestweg, bij elke bushalte ´e´en kabouter. Er was bepaald dat op de jaarlijkse kabouterverkleeddag elke kabouter een sok moest ruilen met de twee kabouters die oostwaarts en westwaarts verderop aan de weg woonden. Geen probleem: elke kabouter trok zijn sokken uit, gaf er een mee met een bus die naar het oosten ging en een met een bus die naar het westen ging. Elke kabouter haalde een sok uit een bus die van het westen kwam en een uit een bus die van het oosten kwam, en klaar was de verkleedpartij. Maar er moest bezuinigd worden en voortaan reed de bus alleen nog maar oostwaarts; hoe moest de jaarlijkse sokkenruil nu uitgevoerd worden? Elke kabouter trok een sok uit en liet die bij de halte liggen, en nam de bus een halte naar het oosten. Bij de volgende halte trok de kabouter zijn andere sok uit en liet die in de bus, maar stapte zelf uit en vond de sok die door de vertrekkende kabouter was achtergelaten. Uit een bus vanuit het westen haalde de kabouter een sok om zijn kleding te completeren. Ga na dat de gewenste sokkenruil hiermee is uitgevoerd en bedenk een implementatie van Petersons algoritme op een unidirectionele ring.
Het bewijs (hier overgenomen uit [AW98]) is instructief vanwege de manier waarop wordt geredeneerd over gedistribueerde systemen. Steeds ziet men in bewijzen van ondergrenzen of onmogelijkheid het idee van replay terugkomen. Dit komt hieruit voort, dat een proces in een gedistribueerd systeem alleen kan handelen op basis van zijn programma en informatie die het eerder heeft ontvangen. Veronderstel, dat proces p een bericht X van q ontvangt en vervolgens een bericht Y verstuurt. Het versturen van Y is onafhankelijk van wat er verderop in het netwerk gebeurt; we kunnen zelfs naar een ander netwerk gaan kijken, waarin q een extra proces r als buur heeft. Tenzij er communicatie tussen r en q plaatsvindt voordat q bericht X stuurt, kan ook in de nieuwe situatie proces p het bericht Y sturen. Omdat het gespecificeerde antwoord van een proces doorgaans wel van de situatie afhangt, kan met replay worden beargumenteerd dat er communicatie moet plaatsvinden. Een replay-argument heeft dan ongeveer deze vorm. Eerst wordt gekeken naar een executie (of deel van een executie) van het algoritme, waarbij aangenomen wordt dat alles conform de specificatie verloopt en er een zeker antwoord wordt opgeleverd of een zeker gedrag wordt vertoond. Daarna wordt gekeken naar een netwerk met een andere structuur of een andere invoer, maar dat “lokaal” op het eerste netwerk lijkt. De stations in het nieuwe netwerk zullen in het begin van hun executie dezelfde stappen kunnen uitvoeren als in het eerste netwerk werd gedaan. Het feit dat niet de gehele executie kan worden geplayed (omdat het antwoord
70
5 Electie
in het eerste netwerk onacceptabel is in het tweede), volgt hieruit dat op bepaalde momenten communicatie nodig is. Een aantal aannamen over het systeem en het algoritme komen expliciet in de bewijsvoering terug: Minimum: Het algoritme maakt het proces met kleinste nummer leider. Uniform: De processen kennen de netwerkgrootte niet, dwz. de waarde van n is niet in het algoritme gecodeerd. Dat wil zeggen, dat het replay-argument ook kan worden gebruikt tussen netwerken van verschillende grootte. Willekeurige id’s: Elke deelverzameling van N kan de verzameling nummers op de ring zijn, en elke rangschikking is toegestaan. Asynchroon: Het algoritme is asynchroon, dwz. elke interleaving van instructies is mogelijk. Unidirectioneel: De ring kent communicatie in ´e´en richting. In het vervolg van deze sectie staat A voor enig electie-algoritme dat aan deze eigenschappen voldoet. Het redeneren over A is natuurlijk moeilijk omdat we niet weten hoe het werkt. Maar wel weten we inmiddels het ´e´en en ander over hoe gedistribueerde systemen in het algemeen werken, dus ook algoritme A. Het algoritme heeft voor elke invoer (elk netwerk) een executieboom, waarvan de knopen corresponderen met toestanden van het algoritme. De wortel van de boom is een systeemtoestand waarin alle processen in hun beginstand zijn en alle kanalen leeg. De kinderen van een knoop corresponderen met de mogelijke stappen in die toestand. Sommige processen kunnen geblokkeerd zijn (doordat ze wachten op een bericht dat nog niet ontvangen kan worden), andere kunnen een bericht verzenden en/of ontvangen. Een gedeeltelijke executie is een pad naar een punt in de boom, en een volledige executie gaat naar een punt waar alle processen geblokkeerd zijn. We gaan werken met het begrip mop, dit is een speciale klasse van gedeeltelijke executies van A waarin er nog maar ´e´en proces ongeblokkeerd is, en dit ene proces heeft nog niet ontvangen. Definitie 5.5 Een prefix van A is een beginreeks van stappen van de processen volgens A. Een prefix is open als er een kanaal is waarover nog geen ontvangst heeft plaatsgevonden. Een open prefix is maximaal (mop) als er, behalve de ontvangst van berichten over ´e´en kanaal, geen stappen mogelijk zijn. Bij het redeneren met en over mop’s gebruiken we de eigenschappen van gedistribueerde systemen; ten eerste dat het “bevriezen” en “ontdooien” van kanalen of processen in een asynchroon systeem helemaal niet tot verstoring van het algoritme leidt. Lemma 5.6 Elke mop is uitbreidbaar tot een complete executie van A. Bewijs. Omdat A een asynchroon algoritme is moet het correct werken in elke interleaving, dus ook als we voor ´e´en kanaal het ontvangen uitstellen tot er geen enkele andere stap meer mogelijk is. ¤ Het voltooien van de executie zal doorgaans wel vereisen dat het laatste kanaal ook wordt ontdooid, dus: berichten gaat afgeven. Dat is de strekking van het volgende lemma.
5.4 Een bewijs van ondergrens
71
Lemma 5.7 In een open prefix op een ring die geen proces met nummer 0 bevat heeft nog geen enkel proces de toestand leider aangenomen. Bewijs. We gaan gebruiken dat de processen niet weten hoe groot de ring is, en evenmin welke andere identiteiten aanwezig zijn, en deze informatie alleen kunnen krijgen door communicatie, het ontvangen van berichten. Zij P een open prefix op een ring met n processen, waarin proces p nog niet heeft ontvangen en stel (in tegenspraak met het lemma) dat er een proces r is dat zich leider heeft verklaard. Volgens de aanname in het lemma is het nummer van r positief. Maar omdat p nog nooit heeft ontvangen weet p, noch een van de andere processen, wat er direct v`o`or p in de ring zit! Bekijk een ring met n + 1 processen, die dezelfde nummers heeft als eerst, maar nu met proces 0 toegevoegd v`o` or p. Omdat A uniform is gedragen in die ring alle processen zich precies hetzelfde als eerst, en de prefix P is een mogelijke executie in de uitgebreide ring, inclusief de electie van r. Dit is strijdig met de eigenschap van A dat het kleinste proces wordt ge¨electeerd. ¤ Je ziet hier hoe we de aanname dat de ring-grootte onbekend is gebruiken: namelijk door een gegeven prefix af te spelen in een andere situatie die echter alleen in de ring-grootte verschilt en voor het overige gelijk is aan die waarin P ontstond. Dit is een zeer gebruikelijke methode in de gedistribueerde algoritmiek. De uitsluiting van een proces met nummer 0 is nodig in het bewijs: dat proces kan zich immers zonder ooit iets te ontvangen tot leider verklaren omdat er geen kleinere nummers bestaan. We bekijken daarom verder alleen executies op ringen waarin de 0 niet voorkomt, maar bedenk dat het algoritme correct moet werken op alle ringen, dus ook als 0 wel voorkomt. Daarom mag de veronderstelde afwezigheid van nummer 0 niet als gegeven in het algoritme ge¨exploiteerd worden! Corollarium 5.8 Het aantal receives in een open prefix is een ondergrens voor de worst case bericht-complexiteit van A. Bewijs. De prefix is onderdeel van een complete executie, en die executie heeft minstens zoveel ontvangsten als de prefix. ¤ Onze verdere redenering met mop’s zal een recurrente betrekking opleveren voor een ondergrens op het aantal berichten, en we zullen die eerst maar even oplossen met de substitutiemethode. Lemma 5.9 De oplossing van de recurrente betrekking M (2) = 1 M (2n) = 2.M (n) + n voldoet aan M (n) = 21 n lg n als n een tweemacht is. Bewijs. We bewijzen dit met inductie naar i voor n = 2i en nemen de inductiehypothese IH(i): 1 M (2i ) = 2i lg 2i . 2 i = 1: De linkerkant, M (21 ), is 1. De rechterkant is 12 21 lg 21 is ook 1.
72
5 Electie
1 6
R1
i
f1
?
)
1
6
f2
i
q
R2
?
)
1 e1q q1 p1 p2¾ q2 ? e2 i )
q
6 i
1
q
)
Figuur 5.3: Vorming van een Ring met Grootte 2n.
i + 1: Splits links een factor 2 af om de recurrentie en dan de inductiehypothese te gebruiken: M (2i+1 ) = M (2.2i ) = 2.M (2i ) + 2i = 2.( 21 2i lg 2i ) + 2i = 2i (lg 2i + 1) = 2i lg(2i+1 ) = 12 2i+1 . lg 2i+1
factor afsplitsen recurrente betrekking IH(i) termen harken rekenregel lg rekenregel macht ¤
Definieer nu M (n) als volgt: elke verzameling van n identiteiten kan zo gerangschikt worden, dat er op de ontstane ring een mop bestaat met tenminste M (n) receives. In de rest van deze sectie bewijzen we dat M voldoet aan de recurrente betrekking in lemma 5.9. Voor een ring met 2 processen hoef je alleen maar te bewijzen dat communicatie noodzakelijk is. Lemma 5.10 In elke ring met twee processen heeft A een mop waarin tenminste 1 bericht is ontvangen, ofwel M (2) ≥ 1. Bewijs. In een ring met twee processen kan geen proces zich leider maken voordat hij heeft gehoord dat de ander een groter nummer heeft; er is derhalve communicatie nodig. Je kunt een willekeurige executie nemen en die afkappen na de eerste ontvangst, dit geeft je een open prefix met 1 ontvangst. Vervolgens kun je alle stappen schedulen die gedaan kunnen worden zonder een ontvangst in het andere kanaal, je krijgt dan een mop met 1 of meer ontvangsten. ¤ In het vervolg van deze sectie gaan we bewijzen dat M (2n) ≥ 2 · M (n) + n. Laat een verzameling van 2n nummers gegeven zijn en splits deze in twee verzamelingen van n nummers elk. De inductiehypothese zegt dat we van die verzamelingen twee ringen kunnen maken, zeg R1 en R2 , die elk een mop hebben met tenminste M (n) ontvangsten erin; noem de betreffende prefixen P1 en P2 en de bevroren kanalen f1 , resp. f2 ; zie figuur 5.3. Nu vormen we ´e´en ring waar alle 2n namen op voorkomen en wel in de volgorde volgens R1 en R2 , waarbij de namen van ´e´en ring in de andere zijn tussengevoegd op het kanaal dat bevroren was in de prefixen P1 en P2 ; zie figuur 5.3. De nieuwe verbindende kanalen noemen
5.4 Een bewijs van ondergrens
73
we e1 en e2 met eindpunt p1 en p2 en beginpunt q1 en q2 . We gaan bewijzen dat de grote ring R een mop heeft met 2.M (n) + n ontvangsten. Lemma 5.11 De reeks stappen P1 · P2 is een open prefix van A op R. Bewijs. Door de uniformiteit van het algoritme kan het gedrag van de processen niet veranderen als we het netwerk ergens wijzigen waar ze geen bericht van hebben ontvangen. Door de asynchroniteit mag je de stappen in P2 vertragen. ¤ De open prefix P1 · P2 is geen mop omdat hij twee kanalen bevat waarover nog niet is ontvangen, en je kunt hem dus op twee manieren uitbreiden tot een mop, namelijk door ´e´en van de twee kanalen e1 of e2 te “ontdooien” en de andere dicht te houden. Om te bewijzen dat tenminste ´e´en van deze twee mogelijkheden tot n extra receives leidt gaan we kijken wat er gebeurt als het ontdooien van e1 tot minder dan n extra receives leidt. Lemma 5.12 Zij P1 · P2 · P3 een mop waarin geen ontvangst over e2 plaatsvindt en P3 bevat minder dan n receives. Dan bevat P3 geen stap van q2 (in het bijzonder worden geen berichten aan e2 toegevoegd) en geen overgangen naar de leider toestand. Bewijs. Alle processen in R2 zitten na de prefix P1 · P2 te wachten op berichten en kunnen pas iets doen na een ontvangst. Als P3 dus k receives bevat, kunnen dat alleen stappen van de eerste k processen van R2 zijn, en q2 doet derhalve niets. Dat niemand leider kan worden komt omdat de prefix nog steeds open is (lemma 5.7). ¤ Na afloop van de reeks stappen P3 staan alle processen in R2 dus weer te wachten; er moet door p1 weer iets worden ontvangen voordat er weer iets gebeurt in R2 . Het gevolg van ontdooiing van e2 is (inclusief bewijs) hetzelfde. Lemma 5.13 Zij P1 · P2 · P4 een mop waarin geen ontvangst over e1 plaatsvindt en P4 bevat minder dan n receives. Dan bevat P4 geen stap van q1 en geen overgangen naar de leider toestand. Voor de voortgang van het algoritme is het foute boel als van zowel lemma 5.12 als Lemma 5.13 de premisse waar is. Het is essenti¨eel dat het ontdooien van tenminste ´e´en kanaal leidt tot het sturen van een bericht over het andere kanaal. Lemma 5.14 Zij P1 · P2 · P3 een mop waarin geen ontvangst over e2 plaatsvindt, en P1 · P2 · P4 een mop waarin geen ontvangst over e1 plaatsvindt waarbij P3 en P4 elk minder dan n receives bevatten. Dan is P1 · P2 · P3 · P4 een prefix die alle processen in een wachttoestand ongelijk leider brengt. Bewijs. De reeks stappen P4 is toepasbaar na de reeks P1 · P2 , maar de reeks P3 verandert van geen enkel proces uit P4 de toestand. Omdat de acties van een proces alleen afhangen van de eigen toestand en niet van de toestand in een ander deel van de ring is reeks P4 na de reeks P1 ·P2 ·P3 nog steeds toepasbaar. In de betreffende reeksen is geen enkel proces leider geworden (lemmas 5.12 en 5.13) en aan het eind ervan staan alle processen in een wachttoestand. Met andere woorden, A is gedeadlocked zonder dat er een leider is gekozen. ¤ Als algoritme A niet deadlockt, zal derhalve het ontdooien van tenminste ´e´en van de twee kanalen e1 of e2 tot n of meer receives leiden. De prefix P1 · P2 is daarom tot een mop uit te breiden met tenminste 2.M (n) + n receives, hetgeen bewijst: Lemma 5.15 Elke verzameling van 2n identiteiten (waar de 0 niet in zit) kunnen we zo in een ring rangschikken dat die ring een mop heeft met tenminste 2.M (n) + n ontvangsten.
74
5 Electie
Stelling 5.16 Elk asynchroon uniform minimum-electie-algoritme heeft een worst-case berichtcomplexiteit van 12 n lg n of hoger. Bewijs. Voor het aantal berichten op een ring van n stations hebben we een ondergrens, M (n), bewezen, die voldoet aan de recursie van lemma 5.9. Lemma 5.10 geeft de inductiebasis en lemma’s 5.11 tot en met 5.15 geven de inductiestap. Lemma 5.9 lost de recurrentie voor M op, en lemma 5.8 tenslotte claimt dat M inderdaad een ondergrens is op de complexiteit van A. ¤ Tenslotte kijken we nog even naar de aannamen die we maakten voor het bewijs. • Minimum: De ondergrens geldt ook voor algoritmen die juist het grootste proces kiezen. Met een algoritmische reductie kan het resultaat ook gemakkelijk voor willekeurige electie-algoritmen worden bewezen (opgave 5.20). • Uniform: Er is geen betere complexiteit mogelijk als de processen de ring-grootte wel kennen. Het bewijs gebruikt dezelfde methoden (knippen en plakken van deel-executies) maar is een stuk lastiger omdat je alleen maar deelexecuties kunt “overzetten” naar ringen van gelijke grootte. • Willekeurige id’s: Als de verzameling namen erg klein is (bv.: de n processen hebben namen uit een verzameling van n + 10 getallen) is een effici¨entere oplossing mogelijk. Tenminste een van de elf kleinste getallen komt voor, en er kan een variant van het ChangRoberts algoritme worden gebruikt waarin een proces alleen een bericht rondstuurt als zijn nummer tot de elf kleinsten behoort. De complexiteit is dan ongeveer 11n berichten. In een realistische setting (“het netwerk heeft ongeveer een miljoen Pentium processoren elk met een 64-bits nummer”) heb je hier niets aan. • Asynchroon: In een synchroon systeem (waar alle processen en kanalen gegarandeerd ongeveer even snel gaan) is een algoritme met O(n) berichten mogelijk. • Unidirectioneel: De Ω(n lg n) ondergrens geldt ook voor bidirectionele ringen, maar weer is het bewijs wat lastiger.
Samenvatting en conclusies Wanneer er niet via gedeelde objecten, maar door het uitwisselen van berichten wordt gecommuniceerd, is alle communicatie expliciet. De hoeveelheid communicatie is dan exact meetbaar. Dit hoofdstuk behandelt een klassiek probleem op het gebied van procesco¨ ordinatie, namelijk het kiezen van een leider uit een collectie a priori gelijke processen. Het electieprobleem is bestudeerd in deze context: de stations hebben unieke identificatienummers, het systeem is asynchroon, de communicatie is beperkt tot een ringvormige communicatiestructuur. Voor het electieprobleem werden de algoritmen van LeLann, Chang-Roberts en Peterson bekeken. Het laatste heeft een lagere gegarandeerde complexiteit, maar in de praktijk is Chang-Roberts ook een goede keuze omdat de gemiddelde complexiteit erg laag is, namelijk O(n lg n) berichten op een ring met n stations. Er werd ook bewezen dat er geen oplossing bestaat die o(n lg n) berichten gebruikt. Hiervoor werd een belangrijke redeneermethode gebruikt, namelijk replay.
Opgaven bij hoofdstuk 5
75
Opgaven bij hoofdstuk 5 Opgave 5.1 Geef een voorbeeld waarbij het algoritme van sectie 5.2.2 eindigt met meerdere leiders. Wat is het maximale aantal (in een systeem met n processen)? Wat is het minimale aantal? Dezelfde vragen voor het algoritme in Sectie 5.2.1. Opgave 5.2 Schrijf een programma voor LeLann’s algoritme (sectie 5.3.1). Opgave 5.3 We schreven dat LeLann’s algoritme (sectie 5.3.1) essenti¨eel gebruikt dat kanalen de fifo-eigenschap hebben. Kijk wat er gebeurt als de eigenschap niet geldt, en geef een voorbeeld waar meerdere processen leider worden doordat berichten elkaar inhalen. Kan het algoritme ook zonder leider eindigen of blijven hangen? Opgave 5.4 In het algoritme van Chang en Roberts worden verslagen processen wel in de toestand niet-leider gebracht, maar kunnen het algoritme niet termineren omdat ze niet weten wanneer het laatste bericht langs is geweest. Breid het algoritme uit met een fase waarin de leider het wachten in de andere stations be¨eindigt door een communicatieronde (die n berichten kost). Opgave 5.5 Is de fifo-eigenschap van kanalen essentieel voor het algoritme van Chang en Roberts (sectie 5.3.2)? Opgave 5.6 Geef voorbeelden van het Chang-Roberts algoritme met 6 processen, waar het aantal berichten (i) 11, (ii) 21, (iii) 17 is. Is elk getal tussen 11 en 21 mogelijk? Opgave 5.7 Hoe weten de niet-leiders in Petersons algoritme (sectie 5.3.3) dat de electie is afgelopen? Opgave 5.8 Electie met Petersons algoritme. (Uit het tentamen van september 2004.) Bewijs, dat in het electie-algoritme van Peterson het aantal berichten dat verstuurd wordt door actieve processen, begrensd is door 4n. Opgave 5.9 Electie: Peterson. (Uit het tentamen van augustus 2000.) In het electie-algoritme van Peterson wordt in elke ronde minstens de helft van de kandidaten uitgeschakeld, tot er nog maar ´e´en over is. (a) Hoe wordt dit gedaan, en wat gebeurt er als er nog maar ´e´en kandidaat is? (b) Wat is het maximale aantal ronden bij een ring met 16 stations, en wat is het minimale aantal? Geef een beginsituatie waarvoor dit maximale cq. minimale aantal wordt gehaald. (c) Is elk aantal tussen het minimum en het maximum ook mogelijk? Opgave 5.10 Electie, Petersons algoritme. (Uit het tentamen van mei 2002.) Het electiealgoritme van Peterson begint met elk station als kandidaat, en reduceert in achtereenvolgende ronden het aantal kandidaten door elke kandidaat zijn identiteit te laten uitwisselen met de twee buurkandidaten. (a) Hoe komt het dat nooit alle kandidaten worden uitgeschakeld? (b) Hoe komt het dat (als een ronde met meer dan 1 kandidaat begint) tenminste de helft van de kandidaten wordt uitgeschakeld? (c) Hoeveel berichten worden hoogstens verstuurd? Motiveer het antwoord.
76
5 Electie
Opgave 5.11 Petersons electie. (Uit het tentamen van oktober 2006.) We kijken naar het electie-algoritme van Peterson op een ring met 16 stations, waarvan de identiteiten de getallen 10, 20, 30, ... 150, 160 zijn. (a) Geef een rangschikking van de identiteiten waarvoor het aantal ronden minimaal is. Hoeveel ronden neemt het algoritme, en hoeveel berichten worden uitgewisseld? (b) Geef een rangschikking van de identiteiten waarvoor het aantal ronden maximaal is. Hoeveel ronden neemt het algoritme, en hoeveel berichten worden uitgewisseld? (c) Bestaat er een rangschikking waarbij er precies 3 ronden nodig zijn? Motiveer! Opgave 5.12 Berekening op Ring. (Uit het tentamen van februari 2001.) In een ringvormig message-passing netwerk heeft elk station een uniek identificatienummer (id) en een integer invoer x. Geef een (zo effici¨ent mogelijk) algoritme dat bepaalt of de som van de invoeren even of oneven is. Beargumenteer waarom je oplossing correct is. Geef de berichtcomplexiteit. Opgave 5.13 Electie: Open Prefix. (Uit het tentamen van mei 2000.) Wat was, in het ondergrensbewijs voor electie algoritmen, (a) een prefix; (b) een open prefix; (c) een maximale open prefix? (d) Bestaan er maximale open prefixen waarin al een proces tot leider is gekozen? Leg uit. (e) Wat verstaan we onder het gebruik van replay in bewijzen over gedistribueerde algoritmen, en waarom is het hiervoor belangrijk dat een prefix open is? Opgave 5.14 Moet de lg n in lemma 5.2 naar boven of naar beneden worden afgerond? Opgave 5.15 Waarom worden in Petersons algoritme nooit alle kandidaten ge¨elimineerd in een ronde? Opgave 5.16 Schrijf een programma voor Petersons algoritme (Sectie 5.3.3). Opgave 5.17 Geef enkele voorbeelden van mop’s in de algoritmen van LeLann en Chang en Roberts. Opgave 5.18 Replay bij Electie. (Uit het tentamen van januari 2006.) Deze opgave bekijkt het probleem van electie onder n stations op een ring, met elk een unieke eigen identiteit. (a) Vertel hoe het electie-algoritme van Chang en Roberts werkt en waarom het correct is. (b) In het bewijs van de n log n ondergrens voor electie werd de techniek van replay gebruikt. Leg uit wat dit is. (c) Voor het bewijs werd de aanname gemaakt dat de stations de netwerkgrootte (het aantal stations) niet kennen. Waar loopt het bewijs spaak als deze grootte wel in het algoritme bekend is? Opgave 5.19 Bewijs dat de ondergrens op electie ook geldt voor electie-algoritmen die juist het grootste proces tot leider maken. Opgave 5.20 Bewijs dat een Ω(n lg n) ondergrens geldt voor elk electie-algoritme (zelfs waarbij geen restrictie geldt op het proces dat gekozen wordt).
Opgaven bij hoofdstuk 5
77
Opgave 5.21 Electie: Ondergrens. (Uit het tentamen van september 2003.) Wat is in het ondergrensbewijs voor electie algoritmen (a) een prefix, (b) een open prefix, (c) een maximale open prefix? (d) In het diktaat werd aangenomen dat A een electie-algoritme is dat het kleinste proces tot leider verkiest. Bewijs, dat de ondergrens van Ω(n log n) berichten ook geldt voor electiealgoritmen waarbij een willekeurig proces tot leider mag worden gekozen.
Hoofdstuk 6
Fouttolerantie en consensus
Het thema “complexiteit”, behandeld in hoofdstuk 5, is centraal in de studie van algoritmen: bij alle berekeningsmodellen is de vraag naar het beroep op resource van belang. Grotere problemen bij het ontwerp van gedistribueerde applicaties liggen echter niet bij de complexiteit van oplossingen, maar bij het fout-bestendig krijgen. Een realiteit in computersystemen is dat er componenten kunnen uitvallen en dat dit op de meest ongelukkige momenten kan gebeuren. Dat maakt van programmatuur een heel andere eigenschap van belang, namelijk de robuustheid of tolerantie tegen storingen in componenten. De uitgebreide algoritmische studies en onderzoeken naar robuustheid zijn vrijwel allemaal op gedistribueerde systemen gericht en vormen binnen het gedistribueerde onderzoek de belangrijkste lijn. In dit hoofdstuk kijken we naar het soort moeilijkheden dat robuustheid oplevert en we bewijzen de onmogelijkheid van het consensus probleem. Dit hoofdstuk en hoofdstuk 8 bekijken robuustheid in systemen waar met berichten wordt gecommuniceerd; ook in hoofdstuk 7 komt dit aan de orde. In de hoofdstukken over wachtvrij rekenen (9 tot 11) wordt robuustheid behandeld voor systemen die met gedeelde objecten communiceren.
6.1
Fouttolerant programmeren
Computers in een netwerk kunnen down gaan en threads van een multithreaded applicatie kunnen door het operating system worden gekilled. Zelfs als componenten op zich heel betrouwbaar zijn wordt de kans op zo’n storing groter naarmate het systeem meer componenten bevat. Wat we willen is dat in zo’n geval de overgebleven processen of threads kunnen overleven en de applicatie afmaken. Nu is het niet moeilijk om fouten af te vangen op zo’n manier dat het bijna altijd werkt. Als voorbeeld hiervan kijken we naar een constructie in de programmeertaal Modula-3. Het probleem is dat een thread bijvoorbeeld een semafoor kan pakken en crashen voor het vrijgeven ervan. Deze constructie is vrij gebruikelijk en een crash in de kritieke sectie kan de gehele applicatie blokkeren: s.P Kritieke Sectie s.V 78
6.1 Fouttolerant programmeren
79
Kader 6.1: Besturing van de Space Shuttle. Het primaire computersysteem van de Space Shuttle bestaat uit vier identieke computers, die allemaal exact dezelfde berekening uitvoeren. In geval van een storing in een van deze computers wordt de besturing automatisch overgenomen door de andere computers [SG84]. Automatische omschakeling is nodig omdat tijdens de start en landing het vliegtuig zal vergaan als er langer dan 400ms niet goed gestuurd wordt. Hoewel replicatie een voor de hand liggende oplossing lijkt om de betrouwbaarheid te vergroten, is het ontwerp van algoritmen om een cluster van (mogelijkerwijs gebrekige) computers te laten samenwerken verre van eenvoudig. Dit wordt ge¨ıllustreerd door het uitstel van de eerste lancering van de Shuttle (van 8 naar 10 april 1981), dat te wijten was aan een fout in de software die juist deze taak vervulde. De shuttle heeft een secundair systeem dat bestaat uit een vijfde computer als “hete reserve”; deze computer voert ook dezelfde berekeningen uit en door een handmatige druk op een rode knop wordt de besturing op deze computer overgeschakeld. Tenslotte is er een “koude reserve”, een computer die niet is ingeschakeld. Mochten alle werkende computers het begeven, dan kunnen de astronauten op een rustig moment de zesde computer uitpakken, opstarten en de besturing erop overschakelen.
(Hierin is s een semafoor en P en V zijn de pak- en vrijoperatie.) Daarom vond men voor de programmeertaal Modula-3 iets uit waarmee een thread aan het besturingssysteem een soort testament kon nalaten waarin stond wat er moest gebeuren als de thread in een bepaald fragment zou crashen. Omgezet naar de modernere syntax van Java zou de kritieke sectie er dan zo uit komen te zien: s.P try { Kritieke Sectie } exception { s.V } s.V Een heel aardig idee, want bij een crash in de kritieke sectie opent het besturingssysteem het testament en voert de vergeten s.V operatie uit. Maar waterdicht is het niet: een thread kan immers direct na de s.P operatie, dus voor de try sectie, crashen en dan val je naast het vangnet. Dan maar iets eerder je testament maken: try { s.P ; Kritieke Sectie } exception { s.V } s.V Het is nu onmogelijk dat een crashende thread de applicatie doet hangen. Maar nu is er een ander risiko: er kan een s.V gegeven worden zonder dat een s.P is voltooid (ga na!), waardoor de safety-eigenschappen van de applicatie gevaar lopen.
80
6 Fouttolerantie en consensus
Kader 6.2: Commit/abort voor transacties In een gedistribueerde database moet een transactie worden doorgevoerd in alle sites, of in geen. Nadat een transactie bij alle sites bekend is gemaakt, bepaalt elke site of die transactie in die site uitgevoerd kan en mag worden. Vervolgens moeten alle sites dezelfde beslissing nemen, of de transactie wordt uitgevoerd (commit) of niet (abort). De beslissing voor een commit mag alleen worden genomen als de transactie in alle sites doorgevoerd kan worden. Populaire protocollen zoals two-phase commit of three-phase commit (plaatje) gebruiken time-outs om te bepalen dat een site is gecrasht (zijn dus niet asynchroon) of kunnen blijven hangen als de co¨ ordinator crasht. Men zocht naar een asynchroon algoritme dat het crashen van een willekeurig proces kon overleven en dan in de andere processen een abort zou genereren en de data-locks vrijgeven. Maar vond het niet; de publicatie van Fischer, Lynch en Paterson maakte aan de zoektocht een eind.
6.1.1
Foutmodellen
Behalve dat threads kunnen crashen zijn andere soorten van storingen mogelijk. Bijvoorbeeld dat de thread ´e´en of meer instructies overslaat (omissie) en dan weer als normaal handelt. Of fouten waarbij een proces onjuiste waarden schrijft of berichten stuurt met foute inhoud; we spreken van Byzantijns falen. Dit soort storingen kunnen optreden bij ernstige hardwareof softwarefouten, maar ook wanneer in het systeem ´e´en of meerdere stations gehackt zijn en door aanvallers ongemerkt van andere software voorzien (attacks). In het laatste geval hebben we te maken met gehaaide tegenstanders met snode bedoelingen, en het behoud van integriteit van de applicatie is een zeer delicate kwestie. Bescherming tegen Byzantijns falen en aanvallen behoort tot het terrein van de gedistribueerde algoritmen [Tel00] en cryptografie [Tel02]. Hier beperken we ons tot crash fouten, die echter wel op elk willekeurig moment kunnen toeslaan. In dit hoofdstuk nemen we aan dat er geen gebruik wordt gemaakt van operating system primitieven die aan threads/processen informatie kunnen geven over gecrashte collega’s; dat komt in hoofdstuk 8. Er wordt dus ook geen gebruik gemaakt van time-outs; de processen moeten asynchroon zijn en dan is het onmogelijk om een gecrasht proces te onderscheiden van een dat “gewoon” erg traag is.
6.1.2
Beslisproblemen
Een vrij algemene benadering van de problematiek krijgen we met het model van beslisproblemen. In deze klasse van problemen moet elk correct (dwz., niet-crashend) proces een uitvoer genereren, en er gelden restricties op de waarden van die uitvoer. De eisen die aan de output worden gesteld zijn steeds een voortgangs-, en een consistentie-eis. Een voortgangs-eis vraagt dat alle correcte processen uiteindelijk iets berekenen; drie vormen worden onderscheiden:
6.1 Fouttolerant programmeren
81
• (Deterministische) Terminatie. In elke berekening van het algoritme neemt elk correct proces een beslissing. Deze beslissing moet onherroepbaar zijn, dwz., elk proces schrijft (slechts eenmaal) een waarde naar de speciale uitvoervariabele. • Probabilistische terminatie, of convergentie. De kans dat elk correct proces een beslissing neemt, dwz., een waarde naar de uitvoervariabele schrijft, is 1. Het verschil tussen deterministische en probabilistische terminatie is verduidelijkt aan de hand van programma 1.11. • Impliciete terminatie, of stabilisatie. Elke berekening van het algoritme is eindig en na afloop hebben alle processen een waarde in hun uitvoervariabele staan. Het verschil met terminatie is dat de processen niet weten of het huidige resultaat het uiteindelijke is, of in de toekomst nog veranderd gaat worden. Beslissingen van een proces zijn dus herroepbaar; dit wordt verder duidelijk in sectie 6.2.3. De consistentie-eis stelt vast welke waarden naar de uitvoer geschreven mogen worden. Bij commit/abort zal deze eis luiden: alle beslissingen zijn gelijk, en bij electie: ´e´en proces beslist op leider en de anderen op niet-leider. Je kunt vrij ingewikkelde probleemstellingen als kloksynchronisatie en renaming als beslisprobleem modelleren. Bij het synchroniseren van hardware-klokken van verschillende computers is de invoer de huidige klokwaarde, en de uitvoerwaarden van de diverse stations is een getal dat in de buurt van het gemiddelde over de invoeren moet liggen, en de uitvoerwaarden moeten dicht bij elkaar liggen. Bij renaming wil je de computers in je netwerk kleine identificatienummers toekennen. Naast de besproken eisen op het gedrag van een programma kunnen er eisen op de fouttolerantie (type en aantal fouten) worden gesteld. 6.1.3
Voorbeeld: flexibele electie
Een voorbeeld waarin een aantal typische, en fundamentele, aspecten van fouttolerante applicaties naar voren komen is programma 6.3. 1. Doorgaans is er een (kleine) verzameling van n processen die volledig verbonden zijn, dwz., elk proces kan aan elk van de andere berichten sturen. Het getal n staat voor het totale aantal opgestarte processen, en verandert dus bij een crash niet: correcte en gecrashte processen tellen beide mee. 2. De t in het programma is een veiligheidsparameter, de robuustheid, en geeft het maximale aantal crashes waartegen het programma gewapend is. 3. Het zogenaamde “shouten” (stuur een bericht aan alle stations) is acceptabel (qua kosten) omdat het aantal stations meestal niet groot is. 4. Na de shout wacht een proces op de berichten van de anderen, waarbij er echter op niet meer dan n − t processen gewacht wordt om blokkering te voorkomen. Tijdens het wachten weet een proces namelijk nooit of de zender van het bericht gecrasht of gewoon traag is. 5. En vervolgens hebben we een probleem met de interpretatie van de berichten, omdat (als er minder dan t processen gecrasht zijn) de diverse processen een verschillende deelverzameling van n − t berichten kunnen hebben gehoord!
82
6 Fouttolerantie en consensus
int n = ... t = ... set S
// Totaal aantal processen, constant // Robuustheid, constant // Processen die p kent
// Stuur identiteit aan alle processen forall proces q != p { send ; S = S + {q} } // Neem een beslissing if ( rang(p,S) <= t+1 ) { decide(leider) } else { decide(niet-leider) } Programma 6.3: Flexibele electie (voor proces p).
Programma 6.3 is een voorbeeld waarin ´e´en zo’n ronde wordt gebruikt. Het bekende electie-probleem (waar exact ´e´en proces in leider-toestand komt) is niet op te lossen als crashes mogelijk zijn; we formuleren de volgende zwakkere eisen: Terminatie: In elke executie waar hoogstens t processen crashen beslist elk correct proces op leider of op niet-leider. Flexibele Electie: Het aantal leider beslissingen is tenminste 1 en ten hoogste 1 + 2t. Stelling 6.1 Programma 6.3 is een asynchrone oplossing voor flexibele electie. Bewijs. Daar er hoogstens t processen crashen zijn er minstens n − t die niet crashen, en die maken hun zend-stappen af. Dit impliceert dat een correct proces tenminste n − t − 1 berichten kan ontvangen, en door de while-lus heen komt. Daarom voldoet programma 6.3 aan terminatie. De flexibele-electie-eis is probleemspecifiek en we laten het bewijs als opgave 6.2 omdat het hier de bedoeling was een algemeen mechanisme te behandelen. In het bewijs moet men er rekening mee houden, dat de diverse correcte processen hun beslissing op verschillende verzamelingen S kunnen baseren. ¤ In dit voorbeeld hebben we aan ´e´en ronde van communicatie genoeg, maar de wat ingewikkelder voorbeelden hebben er meerdere achtereen. Er blijven na afloop van het algoritme nog berichten over in de kanalen; dit is bij crash-robuuste algoritmen onvermijdelijk en wordt als zodanig geaccepteerd. Het betekent wel dat er “ontvang-deamons” actief moeten blijven die berichten van afgesloten programma’s in onvangst nemen en weggooien. Ook, dat als zo’n algoritme meerdere keren na elkaar wordt uitgevoerd, de berichten informatie moeten bevatten om ze van verschillende executies uit elkaar te houden. Let er op dat t niet staat voor het aantal fouten dat tijdens een executie optreedt, en zelfs niet voor het aantal fouten dat tijdens een executie kan optreden. Deze parameter is de
6.2 Consensus-algoritmen
83
robuustheid van het programma, en geeft aan hoeveel crashes het programma kan overleven. Het werkelijke aantal crashes kan hoger zijn, en dan blokkeert het programma misschien maar dit valt buiten de specificatie. Het werkelijke aantal crashes zal er in verreweg de meeste gevallen onder liggen. Bij het bewijzen van de correctheid van het programma mogen we altijd uitgaan van een aantal crashes begrensd door t.
6.2
Consensus-algoritmen
In het vervolg van dit hoofdstuk gaat het feitelijk niet om ´e´en probleem, maar we hebben het over een klasse van problemen die gemeenschappelijk hebben, dat alle stations hetzelfde antwoord moeten berekenen. Zulke problemen zijn er natuurlijk te over: commit/abort (kader 6.2), een chatbox, waar elke deelnemer dezelfde berichten moet zien, of een algoritme dat een conditie in het netwerk test en het resultaat in alle stations oplevert. Een algoritme waarin gelijkheid van beslissingen wordt ge¨eist noemen we een consensus-algoritme. De consistentie die ervoor geldt omvat deze eis: Overeenstemming: De genomen beslissingen zijn gelijk. Bij (flexibele) electie mogen leider en niet-leider beslissingen in ´e´en executie voorkomen; dit is daarom geen consensus-probleem. Bekijk nu het kloksynchronisatieprobleem. Synchronisatie wordt altijd uitgevoerd voordat de klokken elkaar te veel ontlopen, en laten we aannemen dat bij het begin van de synchronisatie het verschil tussen de snelste en de langzaamste klok ten hoogste een minuut bedraagt. Men kan eisen dat de stations beslissen op een gemeenschappelijke waarde, die tussen de hoogste en de laagste invoer in moet zitten. In dat geval is er sprake van een consensus-probleem en in sectie 6.3 wordt bewezen dat geen synchronisatieprogramma aan deze eis kan voldoen. Daarom wordt er een zwakkere eis gesteld, bijvoorbeeld dat de processen moeten beslissen op waarden die elkaar ten hoogste een seconde mogen ontlopen. Deze eis impliceert geen overeenstemming en is met een vrij eenvoudig programma te realiseren (kader 6.4). De volgende subsecties bespreken allemaal een eenvoudig programma dat aan overeenstemming voldoet. 6.2.1
Een triviale oplossing
Dit programma (uitgevoerd in elk proces) voldoet aan overeenstemming en terminatie: decide(0) Hier is decide de statement waarmee een proces een waarde naar zijn uitvoer schrijft; je mag die maar ´e´en keer uitvoeren. Alle beslissingen zijn gelijk (namelijk 0 in alle executies) en alle processen beslissen tenzij ze voor hun eerste instructie al crashen. Dit programma voldoet aan de tot nu toe geformuleerde eisen, maar erg nuttig is het waarschijnlijk niet (dit hangt natuurlijk van de verdere eisen op de uitvoer af). Een programma dat niet echt iets uitrekent maar altijd hetzelfde antwoord geeft noemen we triviaal. 6.2.2
De replicated server
Voor de volgende oplossing nemen we aan dat er twee servers zijn, p en q, die beschikken over dezelfde waarde, dwz., de invoerbits xp en xq zijn gelijk; programma 6.5 zorgt dat alle processen die waarde horen.
84
6 Fouttolerantie en consensus
Kader 6.4: Kloksynchronisatie door herhaalde convergentie // Er geldt |xp − xq | < D Stuur x aan alle stations Ontvang n − t klokwaarden in verzameling S x = gemiddelde(S) // Er geldt |xp − xq | < D.t/(n − t)
Als synchronisatie wordt gestart ontlopen de klokken elkaar maximaal δ: |xp − xq | < δ en het doel is een precisie van ² te bereiken. In een t ronde wordt de precisie met een factor n−t verbeterd. Elk station stuurt zijn klokwaarde aan alle anderen, wacht tot n−t waarden ontvangen zijn, en neemt van de n − t ontvangen waarden het gemiddelde.
Omdat de stations p en q Sp Sq elk ten hoogste t waarden niet ontvangen, hebben ze Waarden Waarden tenminste n − 2t waarden ¾ die alleen die alleen gemeenschappelijk. De t p heeft q heeft waarden die p alleen heeft verschillen elk minder dan 6 D van de t waarden die q n − 2t waarden gemeenschappelijk alleen heeft. Het gemiddelde over Sp en Sq verschilt daarom minder dan (D·t) n−t . Hoe kun je nu bij een gegeven begin- en eindprecisie het benodigde aantal ronden uitrekenen?
De servers beslissen elk op hun eigen bit, de aanname stelt dat die gelijk zijn. Elke client krijgt bits toegestuurd en de eerste die aankomt wordt genomen, maar voor de waarde maakt dat natuurlijk niet uit. Ook als een server crasht krijgt elke client tenminste ´e´en bit, en zelfs als de crashende server al bits had uitgestuurd, die bij sommige clients als eerste arriveren geldt overeenstemming. Aan terminatie is voldaan zolang er hoogstens ´e´en server crasht. Terminatie eist slechts dat elk proces beslist, over de berichten die na dit algoritme nog on-ontvangen in de kanalen rondzwerven wordt in de eis niets gezegd! Dit programma voldoet ook weer aan de geformuleerde eisen, maar voor de goede werking moet er wel voor gezorgd worden dat de servers a priori overeenstemmen. Niet alle mogelijke
Voor server p :
forall client c { send <xp> to c } decide (xp)
Voor server q :
forall client c { send <xq> to c } decide (xq)
Voor client i :
receive y decide (y)
// Mag van p of van q zijn
Programma 6.5: Broadcast door replica servers.
6.2 Consensus-algoritmen
Voor de server:
85
uitvoer = x if (x==1) { forall client c { send 1 to c }}
Voor elke client: uitvoer = 0 receive 1 // ’t doet er niet toe van wie uitvoer = 1 forall client c { send 1 to c } Programma 6.6: Een zwakke broadcast door een server.
combinaties van toegestane invoeren zijn als invoercombinatie toegestaan. 6.2.3
De zwakke broadcast
Met een broadcast bedoelen we een consensus-probleem waarbij het de bedoeling is dat elk proces de invoer van een bepaald proces (meestal de generaal maar hier de server genaamd) te weten komt. In aanvulling op overeenstemming eisen we namelijk: Broadcast: Als de server niet crasht, is elke uitvoer gelijk aan de invoer x van de server. Stelling 6.2 Programma 6.6 is een asynchroon stabiliserend broadcast algoritme. Bewijs. Merk als eerste op dat elke executie van het algoritme eindig veel stappen heeft: er zijn hoogstens n zendacties voor elk proces mogelijk. Als de server invoer 0 heeft heeft elk proces na afloop uitvoer gelijk 0; immers, de server zendt niets, en alle clients blijven na uitvoer = 0 wachten met uitvoer 0. Als de server invoer 1 heeft en correct is heeft elk correct proces na afloop uitvoer 1. Immers, de server zendt een 1 naar elke client dus elke client kan iets ontvangen, en zet de uitvoer op 1. Alleen door vroegtijdig te crashen kan een proces aan het eind nog 0 hebben. Het lastigste geval is wanneer de server 1 heeft en crasht. Misschien heeft hij al wat berichten verstuurd waardoor sommige clients hun uitvoer op 1 zetten, maar daarvan kunnen er natuurlijk ook weer crashen voordat ze aan iedereen berichten hebben gestuurd! Maar we kunnen inzien: als er een correct proces aan het eind uitvoer gelijk 1 heeft, dan hebben na afloop alle correcte processen uitvoer 1. Immers, zij p een correct proces met eindwaarde 1 en q ook een correct proces; na de uitvoer op 1 te zetten heeft p nog een bericht aan q gestuurd, en q moet dus een keer hebben ontvangen. We zien dat elk correct proces aan het eind dezelfde waarde heeft, en dat deze waarde gelijk is aan de invoer van de server mits deze niet crasht. ¤ Het programma illustreert het verschil tussen terminatie en stabilisatie (impliciete terminatie). We weten dat aan het eind alle uitvoeren gelijk zijn, maar een proces weet niet wanneer zijn uitvoer definitief is geworden! Immers, een proces met uitvoer 0 wacht op ontvangst van een bericht (dat hem naar 1 doet switchen) maar zolang het wacht weet het niet of zo’n bericht nog komt, dan wel 0 de eindwaarde is. Er is dus geen sprake van een beslissing die op een bepaald moment wordt genomen, dus aan terminatie is niet voldaan.
86
6 Fouttolerantie en consensus
Kader 6.7: Dijkstra- en Knuth-prijs voor Nancy Lynch. De Amerikaanse ACM (Association for Computing Machinery) heeft in april 2007 de Knuth-prijs toegekend aan Professor Nancy Lynch vanwege haar vele en belangrijke bijdragen aan de theorie van gedistribueerd rekenen. Het was de eerste keer dat deze prijs, die sinds 1996 bestaat, aan een vrouw werd toegekend. Haar werk (veel met co-auteurs uitgevoerd) omvat een precieze modellering van gedistribueerde systemen en het analyseren ervan, en deze inzichten hebben ook andere deelgebieden van de informatica be¨ınvloed, zoals database ontwerp en security. De inzichten die ze ontwikkelde over de mogelijkheden en onmogelijkheden van consensus zijn altijd haar bekendste wetenschappelijke bijdrage gebleven, en hiervoor werd ze in 2001 al onderscheiden met de Dijkstra-prijs. De prijzenkast in huize Lynch is inmiddels goed gevuld, want in 2006 mocht ze in het CWI in Amsterdam een gedeelde Van Wijngaarden-prijs in ontvangst nemen. In juli 2007 werd de Dijkstra-prijs toegekend aan het paper Consensus in the presence of partial synchrony van Cynthia Dwork, Nancy Lynch en Larry Stockmeyer [DLS88].
6.2.4
De sterke broadcast
Je zou dit algoritme natuurlijk expliciet kunnen laten termineren met timers: je moet dan eerst bepalen hoe lang het voor een client maximaal kan duren voor hij een bericht ontvangt. Als de client weet op welke tijd de broadcast in de server begint, kan met een time-out het wachten op een bericht in programma 6.6 be¨eindigd worden. Het resulterende programma is een sterke broadcast (voldoet aan terminatie ipv. stabilisatie), maar is niet langer asynchroon omdat je eisen nodig hebt op de tijdsduur van instructies in een machine. De berekening van de te gebruiken tijdconstanten is nog niet zo gemakkelijk (zie opgave 6.8).
6.3
Onmogelijkheid van consensus
Deze sectie bespreekt het baanbrekende werk van Michael Fischer, Nancy Lynch en Michael Paterson [FLP85], die in 1982 bewezen dat er geen asynchrone consensus-algoritmen bestaan. In de jaren daarna werd dit negatief geformuleerde resultaat op een constructieve manier gebruikt: de formulering van wat onmogelijk is, werd tegelijk een randvoorwaarde die systemen omschreef waarin consensus wel opgelost kon worden. We besteden in sectie 6.3.1 aandacht aan de formulering van het consensus-probleem, resulterend in vijf eigenschappen waaraan een gewenste oplossing voldoet. In sectie 6.3.2 worden deze eisen gebruikt om eigenschappen van de berekeningsboom van zo’n oplossing af te leiden, waaruit in sectie 6.3.3 een tegenspraak tussen de vijf eisen kan worden bewezen. Een discussie volgt in sectie 6.3.4.
6.3 Onmogelijkheid van consensus
6.3.1
87
Eisen op een consensus-oplossing
De verdere discussie veronderstelt een programma A, waarin processen eenmaal kunnen beslissen op waarden 0 en 1; we eisen overeenstemming. Overeenstemming: Binnen een executie zijn alle genomen beslissingen gelijk. Het programma van sectie 6.2.1 (en de variant die altijd 1 geeft) is waarschijnlijk nergens echt bruikbaar voor; een bruikbaar programma rekent “iets” uit, maar we willen ons niet vastleggen op wat dat kan zijn. De aanname dat een programma niet-triviaal is, sluit alle oplossingen uit die altijd op 0, of juist die altijd op 1 beslissen, maar doet dit niet op grond van de programmatekst maar op grond van het uitvoergedrag. Niet-trivialiteit: Er is een executie waarin op 0 wordt beslist en een executie waarin op 1 wordt beslist. Doorgaans wordt niet-trivialiteit ge¨ımpliceerd door de aanvullende eis op de genomen beslissingen. Let op, dat 0 en 1 voorkomen in verschillende executies, want binnen ´e´en executie zijn de genomen beslissingen steeds gelijk (wegens Overeenstemming). In programma 6.5 is er de noodzaak van a priori overeenstemming tussen de beide servers; hoewel invoer 0 op zich voor p toegestaan is, en invoer 1 voor q, is de combinatie van deze twee invoeren niet toegestaan. De volgende eis sluit zulke programma’s, waarin de overeenstemming als het ware al in de startconfiguratie vastligt, uit. Invoercombinaties: Elke combinatie van per proces toegestane initi¨ele toestanden, is een toegestane initi¨ele configuratie. De formulering van de terminatie concentreert zich op het nemen van beslissingen (in programma 6.6 gebeurt dat niet, al heeft elke executie een eindig aantal stappen) en niet op eindigheid van de executie. Om de formulering te vergemakkelijken nemen we juist aan, dat elk correct proces een oneindig aantal stappen kan doen; elk algoritme A is zo te beschrijven dat dit kan, bijvoorbeeld door te veronderstellen dat een proces na het beslissen altijd nog loze stappen kan doen. Definitie 6.3 Een run is een 1-crash run als tenminste n − 1 processen oneindig veel stappen doen in die run. Een run is fair als elk bericht dat aan een correct proces (dwz., een proces dat oneindig veel stappen doet) is verstuurd ook wordt ontvangen. Terminatie: In elke 1-crash fair run beslissen alle correcte processen. Merk op dat het de Terminatie-eis is die de robuustheid tegen crashes impliceert. Het programma uit sectie 6.2.4 tenslotte is niet asynchroon. Asynchroniteit: Het handelen van een proces is onafhankelijk van het tijdstip. Fischer, Lynch en Paterson [FLP85] hebben bewezen dat geen algoritme bestaat dat de vijf genoemde wenselijke eigenschappen combineert. Stelling 6.4 (Fischer, Lynch, Paterson, 1985.) Er bestaat geen gedistribueerd algoritme dat de vijf eigenschappen Overeenstemming, Niet-trivialiteit, Invoercombinaties, Terminatie en Asynchroniteit heeft. Voor elk van deze vijf eisen bestaat er een heel eenvoudig algoritme dat niet aan die eis, maar wel aan de andere vier voldoet. Dit impliceert, dat in het bewijs alle vijf de eigenschappen moeten worden gebruikt! In de onderstaande tekst wordt zoveel mogelijk aangegeven waar de getrokken conclusies van deze vijf eisen afhangen.
88
6 Fouttolerantie en consensus
6.3.2
Modelvorming
Deze sectie relateert de executieboom van A aan de bijbehorende configuraties, de toestanden die het algoritme bereikt na een reeks van stappen. Beschrijving van A. Algoritme A bestaat uit n (n ≥ 2) processen, waarbij proces p (o.a.) een input register xp en een output register yp heeft. De waarde van yp is 0, 1 of b (voor blanco) en dit register mag slechts ´e´enmaal geschreven worden (wanneer p beslist). Een configuratie van het protocol bestaat uit de lokale toestand van elk proces en de berichtverzameling van alle berichten die in die configuratie onderweg zijn. Voor elk bericht is er slechts ´e´en proces dat dit bericht kan ontvangen. In een initi¨ele configuratie zijn alle yp registers gelijk aan b, en er zijn geen berichten onderweg. We veronderstellen dat alle invoer voor p is gerepresenteerd door xp , dus de initi¨ele configuratie is volledig vastgelegd door de waarden van de xp registers (voor alle p). Als steeds redeneren we met de executieboom van een veronderstelde oplossing voor het probleem. De knopen van deze graaf zijn de configuraties van het algoritme en ze zijn gerangschikt aan de hand van de stappen die het algoritme kan doen. Enkele technische randopmerkingen zijn hier op z’n plaats. Ten eerste, omdat er verschillende beginconfiguraties kunnen zijn (afhankelijk van de invoer) is de graaf niet echt een boom maar een woud; toch blijven we de term executieboom voor deze graaf gebruiken. Ten tweede, omdat verschillende reeksen stappen tot dezelfde configuratie kunnen leiden kunnen twee knopen in de graaf dezelfde configuratie beschrijven. De Terminatie-eis op de oplossing dwingt een eigenschap van de executieboom af. Dat op een willekeurig moment (configuratie C) een willekeurig proces (p) kan crashen vertaalt zich in deze eigenschap: Propositie 6.5 Voor elke configuratie C in de executieboom en elk proces p, bestaat er een reeks stappen vanuit C waarin p geen stappen doet, en waarin elk proces behalve p dat in C nog niet beslist heeft, een beslissing neemt. Dit lijkt erg logisch tot men zich af begint te vragen: Hoe zit het met een configuratie C waarin al een proces, zeg q, gecrasht is? Omdat het protocol slechts ´e´en crash hoeft te overleven zou je nu voor de werking van het algoritme mogen aannemen dat andere stations niet meer crashen. Echter, in ons model is elke knoop in de executieboom te bereiken in een eindige reeks van stappen vanaf een wortel. Vanwege Asynchroniteit kun je niet spreken van een gecrasht proces binnen een eindige reeks! Proces q kan best een hele tijd niet aan de executiereeks hebben deelgenomen, maar de asynchroniteit staat toe dat tussen twee stappen van q een willekeurig groot aantal stappen van andere processen zit. Dus vanuit elk punt kan elk proces zijn executie hervatten en weer stappen gaan doen. Berichten, stappen, commuteren. Nu beschrijven we de stappen en configuraties in meer detail voor processen met communicatie door message passing. Een stap in de berekening wordt genomen door ´e´en proces en bestaat uit (1) het al dan niet ontvangen van ´e´en bericht (er wordt geen bericht ontvangen bij een interne stap); (2) een verandering van de toestand van het proces; (3) het verzenden van nul of meer berichten. De stap wordt genoteerd als e = (p, m), waar p het proces is dat de stap neemt, en m het bericht dat ontvangen wordt (m = ∅ als er geen bericht wordt ontvangen in de stap). De stap e = (p, m) is toepasbaar in configuratie C als m = ∅ of m is onderweg (naar p) in configuratie C. (Wanneer FIFO kanalen worden gemodelleerd, moet m ook nog voorin het kanaal staan;
6.3 Onmogelijkheid van consensus
89
dit heeft op het verdere betoog geen invloed.) De configuratie die ontstaat na de toepassing van e wordt genoteerd als e(C) en wordt als volgt uit C gevonden: 1. Als m 6= ∅ dan is m uit de berichtverzameling verdwenen. 2. De toestand van p is veranderd. 3. Er kunnen berichten toegevoegd zijn aan de berichtverzameling. De verandering in p’s toestand, en de verzonden berichten, zijn bepaald door het algoritme A. Ze hangen niet af van de tijd wegens Asynchroniteit en niet van de toestand van andere processen of de inhoud van de kanalen wegens de localiteit van p’s kennis. Uit de werking van een stap en de karakterisering van toepasbaarheid volgt, dat een nietgekozen stappen toepasbaar blijven. Propositie 6.6 Zij C een configuratie met daarin toepasbare stappen e en f . Dan is e toepasbaar in f (C). Het effect van stap e = (p, m) kan in f (C) anders zijn dan in C, maar alleen als stap f de toestand van p heeft gewijzigd. Uit de werking van de stap volgt dat toepasbare stappen in verschillende processen commuteren [Tel00, Thm. 2.19]. Lemma 6.7 Zij C een configuratie met daarin toepasbare stappen e en f voor verschillende processen p en q. Dan is f toepasbaar in e(C) en e toepasbaar in f (C), en e(f C)) = f (e(C)). Het bewijs is hoofdzakelijk een kwestie van alle toestandsovergangen heel precies uit te schrijven. Reeksen van stappen. Een reeks σ = (e1 , e2 , . . . , ek ) van stappen is toepasbaar in een configuratie C0 als e1 toepasbaar is in C0 , e2 is toepasbaar in C1 = e1 (C0 ), etc., en ek is toepasbaar in Ck−1 . Als σ toepasbaar is in C0 is σ(C0 ) = ek (ek−1 (..(e1 (C0 ))..)). Configuratie D is bereikbaar uit C als er een reeks σ is zodanig dat σ(C) = D. Herhaalde toepassing van Propositie 6.6 geeft: Propositie 6.8 Zij C een configuratie met een toepasbare stap e en een toepasbare reeks van stappen σ die e niet bevat. Dan is e toepasbaar in σ(C). Herhaalde toepassing van Lemma 6.7 geeft: Lemma 6.9 Laat de reeksen σ1 en σ2 van stappen toepasbaar zijn in configuratie C, waarbij er geen proces is dat zowel een stap doet in σ1 als in σ2 . Dan is σ2 toepasbaar in σ1 (C), en σ1 toepasbaar in σ2 (C), en σ2 (σ1 (C)) = σ1 (σ2 (C)). Klassificatie van configuraties: Valentie. In elke complete berekening komen beslissingen voor (Terminatie), en in de executieboom komen zowel 0- als 1-beslissingen voor (Niet-trivialiteit), maar in een berekening slechts ´e´en soort (Overeenstemming)! Door non-determinisme zijn vanuit een configuratie in het algemeen meerdere manieren om de executie voort te zetten. Op zijn minst door de mogelijkheid dat verschillende processen die een stap kunnen doen in verschillende volgorden aan de beurt kunnen komen, maar ook kunnen er voor ´e´en proces meerdere toepasbare stappen zijn. Vanuit een configuratie kunnen zo meerdere ontwikkelingen mogelijk zijn, en de verzameling mogelijkheden kan door het toepassen van
90
6 Fouttolerantie en consensus
D. 0 .. .. .. .. .. .. .. .. 0-bes
D. 1 .. .. .. .. .. .. .. .. 1-bes
Niettrivialiteit
C. ........ . . . . ... ..... . . ... ... ... .... . 0-bes 1-bes +
1-crash tolerantie
⇒
Initi¨ele conf.
Besliste conf.
Bivalente init. conf.
Figuur 6.8: De bivalente initi¨ ele configuratie.
een stap worden beperkt maar niet uitgebreid. Immers, de mogelijkheden in een punt zijn de vereniging van de mogelijkheden in de verschillende deelbomen. Voor het consensus-probleem is een belangrijk aspect van de mogelijke ontwikkelingen samen te vatten in: welke beslissingen zijn er vanuit deze configuratie nog mogelijk. Dit aspect van de configuratie wordt samengevat in de valentie. Een configuratie heet 0-beslist als er in deze configuratie een p is met yp = 0, en 1-beslist als er een p is met yp = 1. Wegens Overeenstemming zijn er geen configuraties die zowel 0als 1-beslist zijn. Uit Terminatie volgt, dat er vanuit elke bereikbare configuratie een (0- of 1-) besliste configuratie bereikbaar is. Een configuratie C heet 0-valent als alle besliste configuraties die uit C bereikbaar zijn, 0-beslist zijn, en 1-valent als alle besliste configuraties die uit C bereikbaar zijn 1-beslist zijn. Een configuratie C heet bivalent als zowel 0- als 1-besliste configuraties uit C bereikbaar zijn en univalent als hij 0- of 1-valent is. Opgave 6.11 werkt dit begrip verder uit. In een univalente configuratie hangt de beslissing zo te zeggen “in de lucht”: misschien heeft nog geen enkel proces de beslissing genomen (door het schrijven van de uitvoer) maar globaal is de keuze voor een bepaalde waarde al onontkoombaar. In een bivalente configuratie zijn beide mogelijkheden nog open. 6.3.3
Bivalentie in runs
Uit de eigenschappen van A zal nu worden afgeleid, dat A een oneindig lange fair run heeft waarin geen beslissing wordt genomen; hetgeen strijdig is met Terminatie. Hiertoe bewijzen we dat er een bivalente startconfiguratie is (Lemma 6.10) en daarna, dat bivalente configuraties willekeurig lang door bivalente kunnen worden gevolgd (Lemma 6.11). De bivalente startconfiguratie. De Niet-trivialiteit zegt dat de executiegraaf zowel 0als 1-besliste configuraties bevat, maar die zitten mogelijk in verschillende deelbomen, dwz., zijn mogelijk bij verschillende startconfiguraties. De fouttolerantie en Invoercombinaties worden gebruikt om te bewijzen dat deze twee soorten ook onder ´e´en startconfiguratie voorkomen; zie figuur 6.8. Lemma 6.10 Algoritme A heeft een bivalente initi¨ele configuratie. Bewijs. (1) Uit Niet-trivialiteit volgt dat er initi¨ele configuraties D0 en D1 zijn, zodanig dat vanuit D0 een 0-besliste configuratie, en vanuit D1 een 1-besliste configuratie bereikbaar
6.3 Onmogelijkheid van consensus
91
is. (2) Als D0 = D1 , dan is deze configuratie een bivalente initi¨ele configuratie. Laat verder D0 6= D1 . (3) Configuraties D0 en D1 verschillen mogelijk in meerdere processen, maar er zijn initi¨ele configuraties C0 en C1 , zodanig dat vanuit C0 een 0-besliste configuratie, en vanuit C1 een 1-besliste configuratie bereikbaar is, en C0 en C1 verschillen slechts in de input van ´e´en proces. (4) Om (3) te bewijzen, beschouw een serie initi¨ele configuraties, beginnend met D0 , en eindigend met D1 . Elke volgende configuratie wordt verkregen door van ´e´en proces, waarvan de input ongelijk is aan de input die dat proces in D1 heeft, de input te veranderen in de input van dat proces in D1 . Wegens Invoercombinaties is elke configuratie in deze reeks een toegestane startconfiguratie van A. Omdat er vanuit elke initi¨ele configuratie een besliste configuratie bereikbaar is, vanuit D0 een 0-besliste, en vanuit D1 een 1-besliste, kunnen C0 en C1 als in (3) gekozen worden als twee opeenvolgende configuraties in deze serie. (5) Noem het proces waarin C0 en C1 verschillen p, en zij r een 1-crash run vanuit configuratie C0 waarin p geen enkele stap neemt, en B de besliste configuratie die in die run wordt bereikt. (6) Als B 1-beslist is, is C0 bivalent omdat we al weten dat vanuit C0 een 0-besliste configuratie bereikbaar is. (7) Als B 0-beslist is, is C1 bivalent. Omdat C0 en C1 slechts in p verschillen en p geen stap doet in r, is r ook toepasbaar in C1 en leidt naar dezelfde 0-besliste configuratie B. We weten al dat vanuit C1 een 1-besliste configuratie bereikbaar is. ¤ Bivalente opvolgers. Vervolgens gaan we aantonen dat de overgang van een bivalente naar een univalente configuratie willekeurig lang kan worden uitgesteld. Het is hiervoor niet voldoende, te laten zien dat elke bivalente configuratie een bivalent kind heeft. Daaruit volgt wel, dat de berekeningsboom een oneindig lang pad bevat, maar net als in figuur 1.12 zou dit oneindige pad kunnen corresponderen met een unfair run. Wat we moeten aantonen is, dat er een oneindige niet-beslissende run is die ook nog fair is. Daarom nemen we in het volgende lemma niet alleen een bivalente configuratie C aan, maar ook een willekeurige in C toepasbare stap e. Er wordt bewezen dat C een bivalente afstammeling heeft, waarin e is toegepast. Achter het bewijs zit dit idee: stel dat de uitvoering van stap e in alle gevallen het systeem forceert univalent te worden, dan is er ergens ´e´en proces p dat de gehele uitkomst beslist, namelijk door e al dan niet voor een andere stap e0 uit te voeren. Als op dat punt echter p niets meer doet zit het systeem vast: Terminatie dwingt het systeem te beslissen, maar door Asynchroniteit is crashen in een eindige prefix niet te onderscheiden van een zeer traag proces. Ergo, als p lang genoeg stil houdt om het systeem tot een beslissing op i te forceren, kan p vervolgens inconsistentie afdwingen door de stap te doen die naar een ¯i beslissing leidt. Lemma 6.11 Zij C een bivalente configuratie en e = (p, m) toepasbaar in C. Zij C de verzameling configuraties die uit C bereikbaar zijn zonder e toe te passen, en D de verzameling configuraties die verkregen worden door e toe te passen op een configuratie in C: C = {σ(C)| e komt niet voor in σ}, D = {e(E)| E ∈ C en e is toepasbaar in E}. Dan is er een bivalente configuratie in D. Bewijs. (1) Stap e is toepasbaar in alle configuraties in C wegens propositie 6.8. (2) Er zijn configuraties G0 en G1 in C, zodanig dat vanuit e(G0 ) een 0-besliste, en vanuit
92
6 Fouttolerantie en consensus
e(G1 ) een 1-besliste configuratie bereikbaar is. (3) Om G0 en G1 te vinden, merk op dat C bivalent is, dus er zijn een 0-besliste configuratie B0 en een 1-besliste configuratie B1 bereikbaar uit C. Als Bi ∈ C, kies Gi = Bi (want e(Bi ) is nog steeds i-beslist). Als Bi 6∈ C, kies voor Gi de configuratie in de berekening die van C naar Bi leidt, van waaruit e is toegepast. (4) Als G0 = G1 , dan is e(G0 ) een bivalente configuratie in D en zijn we klaar. Veronderstel G0 6= G1 . Beschouw de opeenvolgende configuraties in berekeningen die van C naar G0 en G1 leiden, en noem twee van deze configuraties buren als de ene configuratie volgt op de andere. Omdat er vanuit e(G0 ) een 0-besliste configuratie bereikbaar is en vanuit e(G1 ) een 1-besliste, volgt dat er 1. onder de beschouwde configuraties een C 0 is waarvoor e(C 0 ) bivalent is; of 2. twee buren C0 en C1 zijn waarvoor e(C0 ) 0-valent en e(C1 ) 1-valent is. In het eerste geval is e(C 0 ) een bivalente configuratie in D. (5) Voor het tweede geval zullen we een tegenspraak afleiden. Er geldt C1 = e0 (C0 ) of C0 = e0 (C1 ), voor een stap e0 = (p0 , m0 ). Veronderstel C1 = e0 (C0 ) (het andere geval gaat analoog). Laat D0 = e(C0 ) en D1 = e(C1 ). Daar e(e0 (C0 )) = D1 een 1-valente configuratie is, en e0 (e(C0 )) = e0 (D0 ) een 0-valente configuratie, geldt e(e0 (C0 )) 6= e0 (e(C0 )). Met lemma 6.7 volgt nu dat p = p0 . (6) In configuratie C0 is de beslissing over de uiteindelijke output geheel in handen van proces p, immers p kan het systeem naar de 0-valente configuratie D0 of naar de 1-valente configuratie D1 voeren. (7) Hieruit volgt dat er niet beslist kan worden als p in deze configuratie stopt. Zij namelijk σ een reeks van stappen, die toepasbaar is in C0 , en waarin p geen stap doet, en laat A = σ(C0 ). Door toepassing van lemma 6.9 volgt dat e(A) = e(σ(C0 )) = σ(e(C0 )) = σ(D0 ) is 0-valent, en e(e0 (A)) = e(e0 (σ(C0 )) = σ(e(e0 (C0 ))) = σ(D1 ) is 1-valent, en dus is A bivalent. (8) Er is dus een 1-crash run (namelijk elke run die het systeem in configuratie C0 voert en daarna geen stap meer doet voor p) waarin niet wordt beslist. Dit is een tegenspraak met Terminatie. ¤ 6.3.4
Bewijs en discussie
Het bewijs van stelling 6.4 kan nu worden voltooid. Bewijs. Zij A een protocol; er kan een fair run r worden geconstrueerd waarin geen proces beslist. Zij A0 een bivalente initi¨ele configuratie van A (lemma 6.10). In Ai , kies voor ei de stap die het langst niet is toegepast in het pad dat naar Ai leidt. Laat Ai+1 een bivalente configuratie zijn waarin ei is toegepast (die bestaat volgens lemma 6.11). Verleng de run met de stappen die van Ai naar Ai+1 leiden. De geconstrueerde oneindige run blijft bivalent en er wordt dus geen beslissing in genomen. De run is tevens fair omdat geen enkele stap oneindig lang wordt uitgesteld. Bij elke stap zijn er namelijk maar eindig veel “oudere” stappen en dat impliceert dat elke stap die ooit toepasbaar wordt, een keer aan de beurt komt om als ei gekozen te worden (als hij niet al eerder wordt uitgevoerd in de constructie). De run is fair, maar geen proces beslist; dit is in tegenspraak met terminatie. ¤ Hoewel geformuleerd als een negatief resultaat, wordt de stelling van Fischer, Lynch en Paterson meestal ge¨ınterpreteerd als een overzicht van de manieren waarop consunsus-problemen juist wel kunnen worden aangepakt. Wil men het probleem kunnen oplossen, dan zal het
Samenvatting en conclusies
93
systeem aan een van de geformuleerde eisen niet voldoen en hier zijn enkele voorbeelden van succesvolle aanpakken. 1. Randomisering (hoofdstuk 7): De Terminatie-eis kan worden verzwakt door het bestaan van oneindige executies toe te staan. Populair gezegd worden deze oneindige executies “onschadelijk gemaakt” door aannamen over de waarschijnlijkheid van executies, en een bewijs dat de oneindige executies met kans 0 voorkomen. 2. Synchroniteit: Onder een aanname van synchroniteit verstaan we eigenlijk elke beperking van de mogelijke volgorde van stappen. Zo kan bijvoorbeeld de relatieve snelheid van processen als volgt begrensd zijn: tussen twee opeenvolgende stappen van proces p zitten ten hoogste 3 stappen van proces q. Deze aanname heeft invloed op de toepasbaarheid van stappen en maakt propositie 6.6 ongeldig. Kijk hiervoor naar een situatie waarin q net twee stappen heeft gedaan en kan kiezen tussen toepasbare stappen e en f . In f (C) is stap e niet toepasbaar omdat eerst p een stap moet doen voordat q weer in actie mag komen; ga na hoe het bewijs van lemma 6.11 als een kaartenhuis in elkaar stort. De FIFO-aanname voor kanalen is ook een vorm van synchroniteit, maar onvoldoende om consensus mogelijk te maken. 3. Fout-detectors (hoofdstuk 8): Ook het gebruik van fout-detectors maakt propositie 6.6 ongeldig. Veronderstel dat e een stap van p is en f een stap waarin q het crashen van p detecteert. In een configuratie C kunnen beide stappen toepasbaar zijn, maar het is een eigenschap van een accurate detector dat p geen stappen meer doet nadat q zijn falen geeft geconstateerd.
Samenvatting en conclusies Bij het ontwerp van gedistribueerde applicaties is robuustheid tegen het optreden van storingen in ´e´en of meerdere stations uiterst belangrijk. In een robuust algoritme mag een station nooit wachten op ontvangst van een bericht van een bepaald ander station; immers een crash van het tweede zou ook het eerste blokkeren. Daarom wordt informatie meestal uitgewisseld in ronden, waarin een station eerst informatie zendt aan alle stations, en vervolgens de informatie van n − t stations ontvangt. Men dient er nu rekening mee te houden dat de diverse stations verschillend verzamelingen berichten hebben ontvangen. Veel probleemstellingen zijn te modelleren als een beslisprobleem: de stations moeten aan het eind van het protocol een onherroepelijke beslissing nemen over hun uitkomst. Binnen de beslisproblemen onderscheiden we een belangrijke klasse, namelijk de problemen waarbij de beslissingen van de stations aan elkaar gelijk moeten zijn. Die klasse van problemen wordt consensus-problemen genoemd. Uit de literatuur is bekend dat, wanneer in een systeem een consensus-probleem kan worden opgelost, oplossingen voor veel andere problemen hieruit kunnen worden afgeleid. Fischer, Lynch en Paterson bewezen in 1985 dat er geen asynchroon en deterministisch consensusalgoritme bestaat dat bestand is tegen een enkele crash.
94
6 Fouttolerantie en consensus
Opgaven bij hoofdstuk 6 Opgave 6.1 Verzin voor programma 6.3 een executie (met n = 8 en t = 2) waarin slechts 1, en een andere waarin 5 processen leider worden. Opgave 6.2 Bewijs dat programma 6.3 aan Flexibele Electie voldoet. Bedenk dat de processen na afloop verschillende waarden van de verzameling S kunnen hebben! Opgave 6.3 Flexibele Electie. (Uit het tentamen van mei 2003.) Hier is Prog 6.3 voor flexibele electie in een systeem met n stations waarvan er hoogstens t kunnen crashen: forall proces q S = {p} while |S| < n-t { receive if ( rang (p,S)
!= p do send
(a) Waarom probeert een station slechts n − t, en niet alle identiteiten te ontvangen? (b) Laat een executie zien voor de waarden n = 5 en t = 2, waarin geen crashes voorkomen en er stations p1 en p2 zijn, die na afloop verschillende verzamelingen S hebben. (c) Wat is, voor n = 15 en t = 3, bij afwezigheid van crashes, het maximale en minimale aantal stations dat leider kan beslissen? Opgave 6.4 Consensus-eisen. (Uit het tentamen van februari 2001.) (a) Hoe luiden (bij consensus) de eisen Overeenstemming en Niet-trivialiteit? (b) De eigenschap van Geldigheid luidt: de uitvoer is gelijk aan de invoer van tenminste ´e´en proces. Bewijs dat Geldigheid impliceert Niet-trivialiteit. Opgave 6.5 Onmogelijkheid van Consensus. (Uit het tentamen van november 2003.) Fischer, Lynch, en Paterson bewezen in 1985 dat er geen asynchroon, deterministisch 1-crashrobuust consensusprotocol bestaat. (a) Welke specificaties van zo’n protocol zijn het uitgangspunt in het bewijs van FLP? Beschouw het volgende beslisprobleem, Ondergrens. Invoer van elk proces is een getal tussen 1 en 6. Uitvoer van proces i is een getal yi met de eigenschap dat • tenminste de helft van de invoeren grotergelijk yi is; • er is een proces j waarvan de invoerwaarde yi is. (b) Is Ondergrens een consensusprobleem en waarom (of waarom niet)? (c) Geef een algoritme voor Ondergrens. Bewijs dat het correct is. Waarom sluit de Stelling van FLP het bestaan van jouw algoritme niet uit? Opgave 6.6 Geen-extreem. (Uit het tentamen van november 2005.) In 1985 bewezen Fischer, Lynch, en Paterson (FLP85) de onmogelijkheid van algoritmen voor consensus. (a) Wat zijn de eigenschappen van zo’n algoritme die tezamen tot een tegenspraak leiden?
Opgaven bij hoofdstuk 6
95
(b) Geef van het volgende probleem aan, of er sprake is van een Consensus probleem (in de zin van FLP85); t is de robuustheid: Geen-extreem: Elk station p heeft een integer invoer xp en genereert (als het niet crasht) een integer uitvoer yp . Deze yp mag niet tot de t kleinste of de t grootste invoerwaarden behoren. Formeel: bij elke p zijn er tenminste t stations q waarvoor xq ≤ yp , en tenminste t stations r waarvoor geldt xr ≥ yp . (c) Als je antwoord op (b) JA luidt, bewijs dan dat de specificatie van Geen-extreem Niettrivialiteit en Overeenstemming impliceert. Als je antwoord op (b) NEE luidt, probeer dan een asynchroon t-robuust algoritme voor Geen-extreem te geven. Welke waarde kan t maximaal hebben? Opgave 6.7 Fouttolerante algoritmen. (Uit het tentamen van februari 2002.) We kijken naar een asynchroon consensus algoritme voor n processen, met fouttolerantie t. In elke ronde doet elk proces (1) een shout van zijn waarde (0 of 1); (2) wacht dan tot n − t stemmen zijn ontvangen; (3) neemt als nieuwe waarde de meerderheid van de ontvangen stemmen. (a) Waarom kunnen in het algoritme maar n − t stemmen in aanmerking worden genomen, ook als er geen processen zijn gecrasht? (b) Waarom kunnen de processen in stap 3 verschillende waarden als meerderheid vinden? (c) Hoeveel nullen of enen moeten er aan het begin van de ronde zijn opdat is gegarandeerd dat elk proces dezelfde waarde berekent in stap 3? Opgave 6.8 Na hoeveel tijd kan het wachten in programma 6.6 veilig be¨eindigd worden? Welke aannamen moet je allemaal maken? Opgave 6.9 Bewijs Lemma 6.7. Opgave 6.10 Consensusprobleem. (Uit het tentamen van mei 2002.) Hoe luiden de Terminatie, Overeenstemming, en Niet-Trivialiteit eisen waaraan een oplossing voor het Consensus probleem moet voldoen? Hoe luidt de stelling van Fischer, Lynch en Paterson? Opgave 6.11 Bewijs: als een bivalente configuratie alleen univalente kinderen heeft, zijn daar zowel 0-valente als 1-valente bij. Opgave 6.12 Zoek voor elk van de vier oplossingen uit sectie 6.2 uit, waarom het bewijs van Fischer, Lynch en Paterson niet van toepassing is. Opgave 6.13 Robuuste convergentie. (Uit het tentamen van november 2004.) Beschouw een systeem met n processen, waarin elk proces p een vijf-bits integer invoergetal xp ∈ [0 . . . 31] heeft. We willen dat elk proces zijn invoer vervangt door een getal dp , dat ligt binnen het bereik van de oorspronkelijke invoeren, maar zo dat de spreiding van de waarden kleiner is; hierbij verlangen we een robuustheid van t = n/4. In dit algoritme is floor de functie die een getal naar beneden afrondt op een integerwaarde. shout xp collect (n-t) waarden z = gemiddelde van de n-t ontvangen waarden decide floor(z)
96
6 Fouttolerantie en consensus
(a) Bewijs dat voor de besliswaarde dp van p geldt: er zijn q, r met xq ≤ dp ≤ xr . (b) Bewijs dat voor elke correcte p, q geldt: |dp − dq | ≤ 12. (c) Is het mogelijk de waarden dp weer als invoer van hetzelfde algoritme te gebruiken om zo de spreiding verder te verkleinen? Is een uiteindelijke spreiding van 0 (dus gelijkheid van de uitvoerwaarden) te garanderen? Opgave 6.14 Ongewenste kleine kleur. (Uit het tentamen van november 2006.) In deze opgave ontwerp je een algoritme voor een systeem van n processen, dat bestand is tegen het crashen van t ervan. De invoer xp van proces p is driewaardig: een kleur uit de verzameling {W, G, Z} (wit, grijs, zwart). Een kleur die t keer of minder voorkomt noemen we een kleine kleur. (Motivatie hiervoor, die verder niets met de opgave te maken heeft: zo’n kleur kan door crashes geheel uitgewist worden.) (a) Geef een algoritme dat voldoet aan Terminatie en voor elk correct proces p een niet-kleine kleur als uitvoer bepaalt: Niet-kleine kleur: De uitvoerwaarde dp van p komt voor als invoerwaarde xq van tenminste t + 1 processen q. (b) Hoe groot mag t zijn in je oplossing? Je collega poneert deze stelling: Onder de aanname dat er in de invoer geen kleine kleuren voorkomen (dwz., waarden die t keer of minder voorkomen) is het mogelijk, Consensus te bereiken met een deterministisch algoritme. (c) Bespreek de mogelijkheid om je algoritme uit (a) te gebruiken als een eerste fase in een deterministisch Consensus-algoritme. Opgave 6.15 Atomic Broadcast. (Uit het tentamen van november 2006.) Schiper [Sch06] zegt dat de moeilijkheid van het implementeren van actieve replicatie vrijwel geheel verborgen zit in de implementatie van de Atomic Broadcast. (a) Wat is het verschil tussen passieve en actieve replicatie? (b) Waar past Atomic Broadcast in een gelaagde netwerkarchitectuur? (c) Geef de specificatie van Atomic Broadcast. (d) Schets een algoritme dat Atomic Broadcast implementeert, gebruikmakend van Consensus. (Je mag dus veronderstellen dat een werkend Consensus primitief aanwezig is.)
Hoofdstuk 7
Randomisering
Dit hoofdstuk bekijkt het belang van gerandomiseerde algoritmen in gedistribueerde systemen. De eerste sectie (7.1) dient om het een en ander aan terminologie te introduceren, bijvoorbeeld de verschillende soorten gerandomiseerde algoritmen die we onderscheiden. We denken aan gerandomiseerde algoritmen als programma’s waar rand()-statements inzitten, maar de formele karakterisering is hier anders. Net zoals we in sectie 6.3 de triviale programma’s niet werden uitgesloten op grond van hun programmatekst maar op grond van hun uitvoergedrag, onderscheiden gerandomiseerde programma’s zich door hun specificaties. Verder laat sectie 7.1 een eerste voorbeeld zien dat aantoont dat randomisering ook daadwerkelijk de mogelijkheden van gedistribueerde systemen uitbreidt. Nog wel op een wat kunstmatig probleem misschien, maar juist door dit soort simpele voorbeelden kun je bij ingewikkelder problemen de werking van randomisering los gaan zien van de vele probleemdetails. In sectie 7.2 wordt aangetoond dat je met gerandomiseerde algoritmen een lagere complexiteit kunt halen. Dit wordt ook echt aangetoond, doordat een probleem wordt behandeld inclusief een ondergrens voor deterministische algoritmen. Deze werkwijze (ondergrens in ´e´en model plus een lagere bovengrens in een ander model) wordt vaak toegepast om de kracht van verschillende modellen met elkaar te vergelijken. Het behandelde probleem is een ge¨ıdealiseerde variant van de kanaaltoegang in netwerken als ethernet (waar ook randomisering in wordt gebruikt). Sectie 7.3 tenslotte zet randomisering vanuit de eerdere theoretische behandeling rechtstreeks op het menu van het gedistribueerde systeemontwerp. Met randomisering kun je namelijk oplossingen geven voor het consensus probleem, waarvan in sectie 6.3 werd bewezen dat een deterministische oplossing onmogelijk is.
7.1
Anonieme electie
Om een inzicht te krijgen in de diverse soorten gerandomiseerde algoritmen die er zijn (Las Vegas, Monte Carlo, Sherwood) beginnen we onze studie met een heel elementair probleem: electie in een ‘netwerk’ van 2 identieke stations. Een dergelijk netwerk, waar de stations noch door verschillende namen, noch door verschillende programma’s van elkaar worden onderscheiden noemen we anoniem. 97
98
7 Randomisering
7.1.1
Het probleem en deterministische onmogelijkheid
Twee stations p en q communiceren met elkaar door bericht-uitwisseling via kanalen Mpq en Mqp . We wensen beide stations met hetzelfde programma uit te rusten, dat toestanden leider en niet-leider kent, z`o dat aan de volgende twee eisen is voldaan: 1. Terminatie. Elke berekening van het gecombineerde systeem is eindig. 2. Verkiezing. In elke eindtoestand van het systeem is 1 station in toestand leider en 1 station in toestand niet-leider. De eis verkiezing is een voorbeeld van een parti¨ele correctheidseis: dit betekent dat er in een eindtoestand een bepaalde conditie moet gelden, maar de eis dwingt op zich niet af dat die ook wordt bereikt (dat staat in de andere eis, terminatie). Een algoritme dat aan terminatie (en ´e´en of andere eis van parti¨ele correctheid) voldoet noemen we deterministisch. De anonimiteit wordt impliciet vermeld, namelijk door het weglaten van een aanname die we in hoofdstuk 5 maakten: dat elk station een unieke naam heeft (die door het programma gelezen kan worden). We kunnen dus niet p en q met elkaar vergelijken en sinds een jaar of twintig bewijzen we de onoplosbaarheid van dit soort problemen met symmetrie-argumenten. Stelling 7.1 Er bestaat geen deterministisch electie-algoritme voor een anoniem netwerk van 2 processen. Bewijs. Een configuratie of globale toestand van het systeem is de combinatie van de toestanden van p en q en de kanalen: (sp , sq , Qpq , Qqp ). We noemen de configuratie symmetrisch als sp = sq en Qpq = Qqp ; het blijkt dat we een executie kunnen maken die telkens na 2 stappen weer in een symmetrische configuratie zit. Initieel zijn beide kanalen leeg en beide stations in de starttoestand dus de configuratie als geheel is symmetrisch. Zij nu (s, s, Q0 , Q0 ) een symmetrische configuratie en stel dat er voor station p een stap mogelijk is. De toestand van p verandert naar t, en eventueel wordt er een bericht gelezen uit Mqp en eventueel ´e´en toegevoegd aan Mpq ; noem de nieuwe configuratie (t, s, Q1 , Q2 ). Maar, omdat (s, s, Q0 , Q0 ) symmetrisch is, en p en q hetzelfde programma draaien, is dezelfde stap ook voor q mogelijk: ook q kan de toestand naar t veranderen. Als p iets ontving in de stap (Q2 = Q0 − m), dan zal q in deze stap ook bericht m uit Mpq verwijderen. Als p iets zond in de stap (Q1 = Q0 + n), dan zal q in deze stap ook bericht n aan Mqp toevoegen. Er ontstaat na de stap van q dus een symmetrische configuratie (t, t, Q3 , Q3 ). Deze constructie geeft ons een executie die na elk even aantal stappen een symmetrische configuratie heeft. Als de executie oneindig lang is, voldoet het algoritme niet aan terminatie. Als de executie eindig lang is voldoet het niet aan verkiezing: in een symmetrische eindconfiguratie zijn de stations in dezelfde toestand. ¤ Symmetrie-argumenten kun je ook op allerlei andere netwerken toepassen. Je kunt bijvoorbeeld gemakkelijk bewijzen dat je niet kunt verkiezen op een ringnetwerk met meer dan 2 stations, of op een ander netwerk waar ´e´en of andere vorm van symmetrie in zit. 7.1.2
Een terminerende oplossing: Monte Carlo
Programma 7.2 gebruikt het vijfmaal trekken van een random bit en voldoet aan de volgende, zwakkere eisen: 1. Terminatie. Elke berekening van het gecombineerde systeem is eindig.
7.1 Anonieme electie
99
Kader 7.1: Co¨ ordinatie van Lego-robots. Machines in netwerken en processen in een systeem hebben altijd een uniek identificatienummer, waardoor de interesse voor anonieme electie altijd theoretisch is gebleven. Echter, met het goedkoper worden van hardware is er ook een tendens om allerlei producten van processors te voorzien, die simpel moeten zijn maar wel met elkaar communiceren. Van Lego Mindstorm kun je allerlei programmeerbare robots bouwen. Meestal is na ´e´en robot (met controller) je zakgeld op, maar toch komen er soms meerdere robots bijeen, bijvoorbeeld om samen blikjes op te ruimen (foto). Dan moet er eentje tot co¨ ordinator van het karwei worden benoemd, en omdat de controllers geen serienummer hebben is er sprake van anonieme electie. Het programmeertutorial stelt de volgende oplossing voor. Elke robot begint een random tijd (gekozen uit 1 . . . 400) te wachten. Wordt binnen die tijd een bericht ontvangen, dan wordt de robot slaaf, anders zendt hij zelf een bericht en wordt master. De mogelijkheid dat meerdere robots tegelijk zenden wordt afgedaan als rather unlikely. Zie http://www.cs.uu.nl/~markov/lego/index.html.
2. Verkiezing met kans 0,96875. De kans dat in een bereikte eindtoestand van het systeem 1 station in toestand leider is en 1 station in toestand niet-leider, is tenminste 0,96875. Het algoritme gebruikt randomisering (het trekken van een getal uit het bereik 0 . . . 31) en we hebben de specificatie van parti¨ele correctheid verzwakt door toe te staan dat met een positieve kans (de faalkans, 1/32 in dit geval) een onbruikbare eindtoestand wordt bereikt. Je kunt de faalkans wel willekeurig klein maken door mijngetal uit een groter bereik te keizen, maar hoe groot het bereik ook is, de faalkans blijft altijd positief.
mijngetal = random(0..31) send mijngetal receive haargetal if (mijngetal < haargetal) { toestand = leider } else if (mijngetal > haargetal) { toestand = niet-leider } Programma 7.2: Monte-Carlo-electie.
100
7 Randomisering
toestand = onbeslist while (toestand == onbeslist) { mijngetal = random(0..31) send mijngetal receive haargetal if (mijngetal < haargetal) { toestand = leider } else if (mijngetal > haargetal) { toestand = niet-leider } } Programma 7.3: Las-Vegas-electie.
Definitie 7.2 Een Monte-Carlo-algoritme is een algoritme dat in elke executie termineert en met positieve kans een gewenste eindtoestand bereikt. 7.1.3
Een probabilistisch terminerende oplossing: Las Vegas
Programma 7.3 pakt de zaak anders aan: het trekken van getallen wordt net zo lang herhaald tot de stations een keer verschillende getallen hebben getrokken. Een station springt uit de lus omdat de getallen verschillend zijn, en als dat aan ´e´en kant gebeurt, gebeurt het aan de andere kant ook en er is dan precies 1 leider en 1 niet-leider. Programma 7.3 voldoet derhalve aan verkiezing. Maar hoe zit het met terminatie? Slecht, want men zal snel het bestaan van oneindige executies kunnen inzien: een oneindige reeks ronden, waarbij de twee stations telkens gelijke nummers trekken. Men zal denken dat dit “in de praktijk nooit voorkomt”, dit is misschien zo, maar bestaan doet zo’n executie toch wel. Wel kunnen we zeggen dat in de kansverdelingsruimte dit soort akelige verschijnselen een dichtheid van 0 hebben (al ga ik op de precieze wiskundige fundering van deze uitspraak liever niet in). Al met al voldoet programma 7.3 aan de volgende specificatie: 1. Terminatie met kans 1. De kans dat een berekening van het systeem eindigt is 1. 2. Verkiezing. In een eindtoestand van het systeem is 1 station in toestand leider en 1 station in toestand niet-leider. Mocht iemand nog denken dat terminatie met kans 1 hetzelfde is als terminatie: de combinatie van stelling 7.1 en programma 7.3 toont aan dat terminatie met kans 1 echt een zwakkere eigenschap is. Definitie 7.3 Een Las-Vegas-algoritme is een algoritme dat termineert met kans 1 en partieel correct is. In de praktijk heb je van oneindige executies van Las Vegas algoritmen nooit last. Oneindige executies zijn nog nooit voorgekomen! Al was het maar omdat er pas eindig lang computers bestaan. Omdat er op elk moment in de toekomst ook pas eindig lang computers bestaan zullen hebben, zullen oneindige executies in de toekomst ook nooit voorgekomen zijn. Oneindige executies bestaan dus nooit in het verleden, misschien in de toekomst, maar met kans 0 zit het er niet erg in.
7.1 Anonieme electie
101
Kader 7.4: Het orgel van de Notre Dame Las-Vegas-algoritmen voldoen in de praktijk meestal prima omdat de executies die voorkomen altijd eindig zijn. Er is echter een fundamenteel nadeel van al deze algoritmen: er is geen garantie op de tijd die het algoritme neemt. Immers, voor elk getal k is er een positieve kans dat het algoritme meer dan k stappen nodig heeft (ga na aan de hand van programma 7.3). In een groot kerkorgel is de verbinding tussen het klavier en de orgelpijpen meestal elektrisch en als het orgel erg groot en erg modern is kan dit een digitaal lokaal netwerk zijn. Een onzekere vertraging tussen het indrukken van een toets en het klinken van de toon is natuurlijk onacceptabel. Daarom kon bij de revisie van de tractie van het kerkorgel in de Notre Dame de Paris in 1992 niet gekozen worden voor ethernetverbindingen (sectie 7.2). Het orgel werd door Societ´e Synaptel voorzien van een IBM token ring. Links en rechts van de speeltafel werd een computermonitor ingebouwd. 7.1.4
Terminerend met faalkans 0
Het zal de lezer zijn opgevallen dat in ons voorbeeld het Monte-Carlo-algoritme een positieve faalkans had, terwijl bij het Les-Vegas-algoritme de kans op een oneindige executie slechts 0 was. Dingen die mogelijk zijn maar kans 0 hebben, komen alleen voor in de wereld van oneindige rijen; daarom is een Monte-Carlo-algoritme met faalkans 0 gewoon deterministisch correct. Stelling 7.4 Als A een Monte-Carlo-algoritme is dat met kans 1 een zekere postconditie bereikt, dan wordt die postconditie in elke executie bereikt. Bewijs. Alle executies van een Monte-Carlo-algoritme zijn eindig en in een eindige executie worden ook maar eindig veel random bits getrokken. Als er een executie is die in een nietgewenste toestand eindigt, dan is er dus een eindige reeks random keuzes die tot deze toestand leidt, en de kans dat deze keuzes worden gemaakt is positief, zodat A een positieve faalkans heeft. Faalkans 0 sluit dus het bestaan van (eindige) incorrecte executies uit. ¤ We zien nu ook in hoe programma 7.3 een kans 0 op een oneindige executie kan hebben: het is dan nodig dat er oneindig vaak gelijke getallen worden getrokken. Definitie 7.5 Een Sherwood-algoritme is een algoritme dat randomisering gebruikt, maar aan terminatie en parti¨ele correctheid voldoet. Waar kun je deze algoritmen voor gebruiken? Stelling 7.4 laat zien dat Sherwood-algoritmen niet, zoals Monte-Carlo- of Las-Vegas-algoritmen, gebruikt kunnen worden om problemen
102
7 Randomisering
op te lossen die geen deterministische oplossing hebben. Je kunt een Sherwood-algoritme ook altijd “de-randomiseren”: Stelling 7.6 Zij A een Sherwood algoritme voor een zeker probleem; dan bestaat er ook een niet-randomiserend algoritme B voor hetzelfde probleem. Bewijs. Beschouw de executie van A waarin alle getrokken random bits 0 zijn. Omdat A aan terminatie voldoet is deze executie eindig (en heeft daardoor zelfs positieve kans van voorkomen). Omdat A partieel correct is voldoet de eindtoestand aan de gestelde eis. Het algoritme B is bijna gelijk aan A, maar alle random trekkingen zijn vervangen door een deterministische procedure die altijd 0 oplevert. De executies van B zijn eindig en de eindtoestand is correct, waarmee B een niet-randomiserend, terminerend en partieel correct algoritme is. ¤ Als voorbeeld van een Sherwood-algoritme kun je denken aan quicksort: de gerandomiseerde versie kiest een random pivot, maar je kunt ook een gederandomiseerde versie nemen die bv. altijd het eerste element van een segment als pivot neemt. Dit voorbeeld maakt ook duidelijk waarom je een Sherwood algoritme zou willen gebruiken: de verwachte complexiteit is vaak lager dan die van een niet-randomiserend algoritme.
7.2
Coordinatie over een broadcast-kanaal
De Medium Access Control protocollen van Ethernet zijn randomiserend. In een Ethernetsysteem zitten meerdere computers op ´e´en kabel aangesloten. Een station dat een bericht wil versturen plaatst het, zonder overleg of zonder met een schema rekening te houden, op de kabel. Hierbij bestaat het risico dat verschillende uitzendingen overlappen en beide boodschappen gaan dan verloren. De stations merken dit (nog tijdens de uitzending!), breken de uitzending af en proberen het na een random gekozen tijdsinterval opnieuw. Vanwege de mogelijkheid dat er heel vaak achter elkaar botsingen plaatsvinden lijkt dit idee niet zo goed, toch is het de meest effici¨ente manier om van zo’n kanaal gebruik te maken. In deze sectie leer je waarom: met randomiserende protocollen kunnen we een complexiteit bereiken die niet-randomiserend onmogelijk is. Om deze claim hard te maken moet er een ondergrens zijn voor deterministische oplossingen en een bovengrens die lager is voor een randomiserende oplossing. Nu is rekenen aan Ethernet nogal lastig en daarom vertalen we de onderliggende conflictsituatie naar een model met discrete tijd, dwz. de tijd is niet als R maar als N gemodelleerd. Net als bij Ethernet zoeken we naar het eerste moment waarop een station alleen zendt. 7.2.1
Probleemstelling
Een satelliet (figuur 7.5) kan vanuit verschillende grondstations worden bestuurd. Deze stations berekenen, wanneer zij actief zijn, allemaal hetzelfde stuurcommando op tijdstip 0 en kunnen dit radiografisch overbrengen. Radiocommunicatie is georganiseerd in zg. slots, dwz., de tijd is in kleine stukjes verdeeld die elk net lang genoeg zijn om de stuurcommando’s over te zenden. De satelliet kan de commando’s ontvangen als in een bepaald slot exact ´e´en grondstation zendt; als meerdere stations tegelijk zenden worden de uitzendingen verstoord. De grondstations weten niet, welke andere stations actief zijn of de satelliet in zicht hebben en kunnen hierover ook niet communiceren (anders hadden ze die prachtige satelliet natuurlijk
7.2 Coordinatie over een broadcast-kanaal
103
..... .... ....
..... ..... ...
..... ..... ...
1
2
..... ..... ...
.. ........ ..
..... ..... ...
..... ..... ...
n
Figuur 7.5: Een satelliet met grondstations.
helemaal niet nodig). Het zendgedrag van een station kan daarom niet afhangen van welke stations er actief zijn, of van welke stations zenden in eerdere ronden. We zoeken een strategie die voor elk station bepaalt wanneer (in welke slots) er gezonden wordt, en wel zo, dat als er tenminste ´e´en grondstation actief is, de satelliet het commando krijgt. De communicatie moet zo snel mogelijk afgerond zijn: we kijken naar het aantal slots dat het algoritme nodig heeft. 7.2.2
Niet-randomiserende oplossingen
Omdat de stations geen informatie van elkaar ontvangen kunnen we ons een deterministische strategie voor K ronden voorstellen als de toekenning van een verzameling Si ⊆ {1, . . . , K} aan station i. Deze verzameling Si is het zendschema voor station i, dwz. station i zendt precies in de slots in Si . Let op dat i in het geheel niet zendt als hij inactief is, en dat Si niet van het al dan niet actief zijn van de anderen mag afhangen. Een andere representatie van de strategie is, per tijdstip te vermelden welke stations willen zenden: Rt is de verzameling stations die kunnen zenden in slot t, dus: Rt = {i : t ∈ Si }. Als A de deelverzameling van de actieve stations is, zijn de daadwerkelijk zendende stations in slot t gegeven door Rt ∩ A. De werking van het schema vereist dat er voor elke niet-lege verzameling A tenminste ´e´en slot is waarin precies ´e´en actief station zendt: ∀A ⊆ {1, ..., n}, A 6= ∅ : (∃t : |Rt ∩ A| = 1) Een voor de hand liggende oplossing is de volgende: grondstation i zendt (indien actief) in slot i. Er vinden nimmer overlappende uitzendingen plaats, en als er tenminste ´e´en station operationeel is zendt dat station de boodschap op. In het bovenstaande model uitgedrukt: Si = {i}, en Rt = {t}. Als nu u ∈ A, dan is Ru ∩ A = {u}, dus deze oplossing voldoet aan de eis. Het aantal gebruikte ronden (het aantal verzamelingen R dat je nodig hebt) is hier n, het aantal stations. Zie opgaven 7.7 en 7.8. De geschetste oplossing (en die in de opgaven) is meteen de best mogelijke, met andere woorden: er bestaat geen deterministische strategie die minder dan n slots gebruikt. Het bewijs is voor de lijn van ons betoog van ondergeschikt belang, maar wordt volledigheidshalve hier gegeven.
104
7 Randomisering
m = "station heeft boodschap" for (i=1 ; i <= 2*lg(n) ; i++) if (m) { send message in slot i m = random(0,1) } Programma 7.6: De vervalprocedure.
Stelling 7.7 Elke deterministische strategie gebruikt tenminste n ronden. Bewijs. We gaan het bewijs doen met inductie naar n, maar merk eerst op dat een oplossing correct blijft onder het permuteren van stations, en onder het permuteren van slots. De inductiehypothese is (voor n): Een rij R1 , . . . , RK ⊆ {1, ..., n} die voldoet aan ∀A ⊆ {1, ..., n}, A 6= ∅ : ∃t : |Rt ∩ A| = 1 bevat tenminste n verzamelingen (ie. K ≥ n). n = 1: Het element 1 zal tenminste eenmaal moeten voorkomen in een Rt , er is dus tenminste 1 verzameling. n + 1: Zij nu R1 , ..., RK een oplossing voor n + 1. Vul nu A = {1, .., n + 1} in in de eis, dan is steeds Rt ∩ A = Rt en hieruit volgt: ∃t : |Rt | = 1. Omdat we de slots mogen permuteren kunnen we stellen dat |RK | = 1, en omdat we de stations mogen permuteren kunnen we stellen dat RK = {n + 1}. Nu voldoet t = K aan de correctheids-eis voor alle verzamelingen A die n + 1 bevatten, maar voor geen enkele A die n + 1 niet bevat; voor die verzamelingen A moet er dus een andere t zijn: ∀A ⊆ {1, ..., n}, A 6= ∅ : ∃t < K : |Rt ∩ A| = 1. De Rt zijn deelverzamelingen van {1, ..., n + 1}, maar omdat de bekeken A’s niet n + 1 0 bevatten, kunnen we die uit de verzamelingen verwijderen. Definieer R10 tm RK−1 door 0 Rt = Rt − {n + 1} en nu voldoen deze K − 1 deelverzamelingen van {1, ..., n} aan ∀A ⊆ {1, ..., n}, A 6= ∅ : ∃t : |Rt0 ∩ A| = 1. De inductiehypothese zegt nu dat K − 1 ≥ n, waarmee K ≥ n + 1 is bewezen. ¤ 7.2.3
Een randomiserende oplossing: de vervalprocedure
Programma 7.6 toont een randomiserende procedure: elk station dat de boodschap heeft begint te zenden en gaat hiermee net zolang door tot een random-bittrekking voor de eerste keer 0 oplevert of slot 2 lg(n) is afgelopen. Stelling 7.8 Programma 7.6 is een Monte-Carlo-algoritme met faalkans hoogstens 1/2.
7.2 Coordinatie over een broadcast-kanaal
105
Bewijs. Omdat het zenden na 2 lg(n) slots wordt afgebroken is elke executie eindig. Het aantal zendende stations wordt van slot tot slot uitgedund, en we hebben succes als er in het laatste slot waarin gezonden werd precies ´e´en zendend station was. De kans dat het zenden van een station wordt afgebroken doordat de grens op het aantal ronden werd bereikt is zo klein (hoe klein precies?), dat we dit in de berekening gaan verwaarlozen. Zij S(n) de kans op succes ingeval er n stations aan het zenden beginnen. Er geldt S(0) = 0 omdat zonder zenders geen bericht wordt overgebracht en S(1) = 1 omdat een enkele zender meteen in de eerste ronde succes heeft. De precieze berekening van de slaagkansen is voor de lijn van ons betoog weer van ondergeschikt belang maar volledigheidshalve geven we hier de hoofdlijn. Voor het berekenen van S(2) bedenken we, dat in het eerste slot de zenders tegelijk zenden en er geen boodschap wordt overgebracht: het zal er dus van afhangen hoeveel stations er in het volgende slot doorgaan. Met kans 14 trekken beide stations 0 en stoppen ze allebei, en met kans 12 trekt er ´e´en een 0 en heeft de volgende ronde succes, Met kans 14 trekken ze allebei een 1 en in dit geval gaan beide stations door en is het in de volgende ronde net zo alsof ze dan beginnen1 . We vinden S(2) = 41 S(0) + 21 S(1) + 14 S(2), met oplossing S(2) = 32 . Bij drie stations hebben we kans 18 dat geen station een 1 trekt, kans 83 dat 1 station een 1 trekt, kans 38 dat 2 stations een 1 trekken, en kans 18 dat 3 stations een 1 trekken. Daarom is S(3) = 18 S(0) + 38 S(1) + 38 S(2) + 18 S(3), met oplossing S(3) = 75 . µ ¶ P n 1 Voor n stations vinden we S(n) = nk=0 2n S(k) en de oplossing hiervan is S(n) = k µ ¶ n 1 Pn−1 S(k). We zien dat S(n) een gewogen gemiddelde van de slaagkansen voor k=0 2n −1 k kleinere waarden is. Met inductie kun je nu bewijzen dat S(n) > 12 voor alle n. ¤ Met een module als programma 7.6 kun je verschillende dingen doen. Bedenk zelf of/hoe je programma 7.2 op dezelfde manieren kunt gebruiken. 1. E´enmalig toepassen als snel maar onzeker algoritme. Zoals we zagen, kost dit slechts 2 lg(n) ronden en de faalkans van dit Monte-Carlo-algoritme is beter dan 1/2. 2. Meervoudig toepassen voor kleinere faalkans. Net als bij programma 7.2 kunnen we met een kleine ingreep de faalkans willekeurig klein (maar positief!) maken. Als we de vervalprocedure r maal herhalen hebben we nog steeds een Monte-Carlo-algoritme, dat 2r lg(n) slots gebruikt, maar de faalkans wordt 21r . 3. Met een test combineren tot een Las-Vegas-algoritme. Als de satelliet na afloop van slot 2 lg(n) kan terugzenden of de boodschap is overgekomen, kunnen we de vervalprocedure simpelweg herhalen tot het optreden van succes. Dan is het resultaat partieel correct, maar terminatie geldt niet meer, alleen terminatie met kans 1: we hebben dan een Las-Vegas-algoritme. Dit is ruwweg wat er in ethernet gebeurt, en daarmee is het bij ethernet wel zeker dat elk aangeboden bericht ook wordt verzonden, maar er is geen harde limiet op de tijd waarbinnen dit gebeurt; zie kader 7.4. 4. Met een deterministisch algoritme combineren tot een Sherwood-algoritme. Verdeel de slots, draai in de even slots het Las-Vegas-algoritme en in de oneven slots de nietrandomiserende oplossing uit sectie 7.2.2, met dien verstande dat het wordt afgebroken als er in de even slots succes wordt gerapporteerd. Dit algoritme voldoet aan terminatie 1
Feitelijk is de slaagkans iets kleiner geworden, doordat de twee stations een ronde dichter bij een mogelijke geforceerde terminatie zijn gekomen. Maar het afbreken zouden we in de berekening verwaarlozen.
106
7 Randomisering
(op zijn laatst in de ne oneven slot slaagt het niet-randomiserende algoritme) en is partieel correct (we stoppen pas als de satelliet het bericht heeft). De verwachte complexiteit is slechts 8 lg(n) ronden, hetgeen behoorlijk beter is dan het beste niet-randomiserende algoritme. De uitbreiding tot een Las-Vegas-algoritme is mogelijk met elk Monte-Carlo-algoritme waarvan het succes achteraf te testen is.
7.3
Ben-Ors consensus-algoritme
Als klap op de gerandomiseerde vuurpijl gaan we laten zien hoe je randomisering (het verzwakken van terminatie tot terminatie met kans 1) kunt toepassen om een oplossing te vinden voor een consensus-probleem. In sectie 6.3 was meer sprake van een klasse van problemen, want we bewezen de onmogelijkheid van elk probleem waarbij overeenstemming van uitvoeren gevraagd is. Wat men doorgaans verstaat onder “het consensus-probleem” is een soort stemming over de invoer, waarbij elke uitslag acceptabel is mits deze door minstens ´e´en kiezer wordt ondersteund (geldigheid). Het algoritme dat we gaan zien heeft in elk proces een invoer (0 of 1) en processen kunnen beslissen op 0 of 1, waarbij aan deze eisen wordt voldaan: Terminatie met kans 1: De kans dat elk correct proces beslist is 1. Overeenstemming: Alle genomen beslissingen zijn gelijk. Geldigheid: De genomen beslissing komt voor als invoerwaarde. Geldigheid stelt in feite dat als alle processen dezelfde waarde v als invoer hebben, deze v ook de uitvoer is. Als zowel 0 als 1 als invoer vookomen dan zijn beide uitvoerwaarden toegestaan. 7.3.1
Uitleg van het algoritme
Het algoritme werd bedacht door Ben-Or [BO83], we volgen de presentatie uit Aguilera en Toueg [AT98]. Het algoritme van Ben-Or verloopt in een aantal ronden, die elk uit drie fasen bestaan: een rapportagefase, een voorstellenfase (proposal-fase) en een verwerkingsfase. Een parameter t is de tolerantie: er mogen maximaal t processen crashen voor de goede werking (maar in de meeste executies crashen natuurlijk veel minder processen). We nemen voor het algoritme aan dat t < n2 ; je kunt trouwens ook bewijzen dat als t groter is, randomisering niet voldoende is om een oplossing te kunnen vinden. Een proces begint elke ronde met een waarde x die 0 of 1 kan zijn, en voor de eerste ronde is dit de invoer van het proces. In de eerste fase worden de waarden uitgewisseld: een proces zendt zijn waarde aan alle processen en wacht de ontvangst van n − t berichten af. Zou er op meer berichten worden gewacht, dan wordt het crashen van t stations door de overgeblevenen niet overleefd. We moeten er nu wel op bedacht zijn dat de verzameling van ontvangen rapporten daardoor, juist bij afwezigheid van crashes van proces tot proces kan verschillen! In de tweede fase kan een voorstel (proposal) tot beslissen worden ingediend. Een proces dient een voorstel voor v in als er in de eerste fase meer dan n/2 rapporten met die waarde werden ontvangen. Merk op dat, omdat er slechts n − t rapporten werden ontvangen, het mogelijk is dat dit aantal voor geen van de twee mogelijke waarden wordt gehaald; in dat geval
7.3 Ben-Ors consensus-algoritme
107
uitvoer = @ x = invoer k = 0 klaar = False while (not Klaar) { k++ ; if (uitvoer != @) { Klaar = True } // Fase 1: Rapporteer forall j { send
stelt het proces de waarde @ voor. De proposals worden weer aan alle processen verstuurd, en er wordt gewacht tot er n − t zijn ontvangen. In de derde fase worden de ontvangen proposals geanalyseerd. De waarde voor de volgende ronde is bij voorkeur een waarde waarvoor proposals werden ontvangen, maar als geen proposals (anders dan voor @) werden ontvangen gaat het proces de volgende ronde in met een random bit. Er wordt beslist op een waarde waarvoor meer dan t proposals zijn ontvangen. Als er een beslissing is genomen doet het proces nog ´e´en ronde mee en daarna loopt het programma af. 7.3.2
Bewijs van overeenstemming en geldigheid
In deze sectie bewijzen we dat beslissingen van verschillende processen gelijk zijn, hoogstens ´e´en ronde na elkaar komen, en aan geldigheid voldoen. Lemma 7.9 Als elk proces dezelfde invoer v (in {0, 1}) heeft, neemt elk correct proces (in de eerste ronde) een beslissing voor v.
108
7 Randomisering
Bewijs. Elk rapport in fase 1 is in dit geval voor v, zodat de drempel voor het voorstellen van v in fase 2 door alle processen wordt gehaald (immers, n − t > n/2). Elk voorstel is dus voor v, waarmee de drempel voor beslissen wordt gehaald (immers, n − t > t). ¤ 1 2n
Een beslissing voor v is zelfs al gegarandeerd als er een voldoende grote meerderheid (van + t processen) voor v is; zie opgave 7.16.
Lemma 7.10 Voor elke k geldt: als er niet v` o` or ronde k − 1 een beslissing is genomen, maakt elk correct proces ronde k af. Bewijs. Er wordt in de ronde gewacht op rapporten en proposals, maar er zijn genoeg correcte processen om het benodigde aantal toe te sturen. Pas als er in ronde k − 1 is beslist gooien correcte processen na ronde k de handdoek in de ring waardoor andere correcte processen niet aan het vereiste aantal komen. ¤ Lemma 7.11 In elke ronde wordt voor hoogstens ´e´en waarde (ongelijk @) een proposal gestuurd. Bewijs. Stel proces i doet een proposal voor v en proces j ´e´en voor w, in dezelfde ronde. Dan ontving i meer dan n/2 rapporten voor v, en w ontving meer dan n/2 rapporten voor w. Er is nu tenminste ´e´en proces dat zowel een v-rapport aan i als een w-rapport aan j zond; en omdat een proces voor hoogstens ´e´en waarde rapporten zendt in een ronde, impliceert dit v = w. ¤ Lemma 7.12 Als proces i in ronde k voor v beslist, dan beslissen alle correcte processen voor v, en wel in dezelfde ronde of ten hoogste ´e´en ronde later. Bewijs. Neem aan dat k de eerste ronde is waarin een beslissing wordt genomen. Proces i ontving meer dan t proposals voor v, en nu sluit lemma 7.11 meteen uit dat er proposals voor de andere waarde zijn: er wordt dus in ronde k geen tegenstrijdige beslissing genomen. Je weet niet, hoeveel proposals voor v door de andere processen ontvangen werden: sommige ontvingen er misschien ook meer dan t en beslisten ook in ronde k, anderen ontvingen er misschien minder. Maar omdat er minstens t + 1 processen een v-proposal stuurden, ontving elk correct proces tenminste ´e´en v-proposal! Dus gaan alle correcte processen ronde k + 1 in met waarde v, waarmee (net zoals in lemma 7.9 werd beredeneerd) alle processen in die ronde voor v gaan beslissen. ¤ Je ziet nu waarom een proces kan stoppen na de ronde volgend op de eigen beslissing: alle processen hebben dan gegarandeerd ook beslist. De processen die pas in ronde k + 1 beslisten willen ronde k + 2 ook nog uitvoeren, en in die ronde blijven ze misschien hangen omdat er niet genoeg berichten worden verstuurd. Dit hangen is niet in strijd met de gewenste voortgang, omdat terminatie met kans 1 alleen over het nemen van beslissingen (extern gedrag) gaat en niet over het hangen van programma’s (interne toestand). 7.3.3
Bewijs van convergentie
In het voorgaande is al gebleken dat het algoritme snel klaar is zodra alle (levende) processen een ronde ingaan met dezelfde waarde van x. Het aardige van het algoritme is, dat dit door de random keuzes die worden gemaakt, in elke ronde met positieve kans gaat gebeuren.
Samenvatting en conclusies
109
Lemma 7.13 Elke ronde heeft een kans van tenminste proces dezelfde waarde heeft.
1 2n−1
om te bereiken dat na afloop elk
Bewijs. We onderscheiden twee gevallen. Stel dat er voor een v ∈ {0, 1} een proposal wordt ontvangen door tenminste ´e´en proces. We weten uit lemma 7.11 dat er geen proposals voor de andere waarde worden verstuurd. Minstens ´e´en proces ontvangt een proposal voor v, er zijn dus hoogstens n − 1 processen die 1 trekken zij alle hun nieuwe waarde door een random-keuze bepalen; met kans tenminste 2n−1 de waarde v. Stel nu dat er in de ronde geen proposals (anders dan @) worden ontvangen. De n processen nemen allemaal een random waarde: met kans 21n nemen ze allemaal 0, met kans 21n nemen ze 1 allemaal 1, dus met kans 2n−1 zijn de getrokken waarden gelijk. (Een technische opmerking: we nemen aan dat de volgorde van ontvangst van berichten niet kan afhangen van de uitkomst van de random trekkingen die het algoritme doet.) ¤ Stelling 7.14 Ben-Ors algoritme (programma 7.7) is een asynchroon gerandomiseerd consensus algoritme. Bewijs. We hebben overeenstemming bewezen in lemma 7.12, en geldigheid in lemma 7.9. Voor een oneindige executie is nodig dat de processen oneindig vaak met verschillende waarden een nieuwe ronde ingaan, en wegens lemma 7.13 is de kans hierop 0. Dit bewijst terminatie met kans 1. ¤
Samenvatting en conclusies In dit hoofdstuk hebben we gezien dat randomisering, nog in meerdere mate dan in het geval van sequenti¨ele programmering, een belangrijk hulpmiddel is bij het ontwerpen van gedistribueerde applicaties. Net als bij sequenti¨ele berekeningen is het mogelijk randomiserende algoritmen te ontwerpen met een lagere (verwachte) complexiteit. De algoritmen kunnen dan zo gemaakt worden, dat elke berekening eindig is en bovendien de uitkomst gegarandeerd juist is; we spreken dan van een Sherwood-algoritme. In het geval van gedistribueerd rekenen kennen we ook problemen, waarvoor geen oplossing bestaat wanneer er terminatie `en parti¨ele correctheid worden verlangd. Zulke problemen zijn soms wel oplosbaar met randomiserende algoritmen, waarbij een kleine kans op een onjuist antwoord, of het bestaan van oneindige berekeningen moet worden geaccepteerd. Zo zijn er Monte-Carlo-algoritmen, waarvan elke berekening eindig is, maar een onjuist eindantwoord mogelijk is. Aan de andere kant kennen we Las-Vegas-algoritmen, waarbij het eindantwoord gegarandeerd juist is maar er geen harde grens is op de lengte van een berekening. Van de diverse soorten algoritmen hebben we in dit hoofdstuk voorbeelden gezien, en ook, dat hiermee problemen oplosbaar zijn die dat met deterministische algoritmen niet zijn: • Sectie 7.1 gaf een Monte-Carlo- en een Les-Vegas-oplossing voor electie zonder identiteiten. Deze electie is deterministisch onmogelijk. • Sectie 7.2 gaf diverse algoritmen voor het versturen van een bericht over een gedeeld kanaal. Het basisprincipe (de vervalprocedure) kan op een Sherwood-, Monte-Carlo- of Las-Vegas-manier worden gebruikt. De complexiteit ervan is lager dan met een deterministische oplossing kan worden gehaald.
110
7 Randomisering
• Sectie 7.3 behandelde een randomiserend consensus-algoritme van het Las-Vegas-type. In hoofdstuk 6 werd bewezen dat hiervoor geen deterministisch alternatief bestaat.
Opgaven bij hoofdstuk 7 Opgave 7.1 In computersystemen worden random bits helemaal niet met ´e´en of ander fysisch randomiserend mechanisme bepaald, maar deterministisch bepaald door een pseudo-random number generator. Onderzoek wat dat precies is. Wat is het effect van het gebruik van pseudo-randomisering op de werking van programmas 7.2 en 7.3? Wat is het effect op de werking van programma 7.7? Opgave 7.2 Is het electie-algoritme uit de Lego-tutorial (kader 7.1) van het Monte-Carlo- of van het Las-Vegas-type? Wat is de faalkans, resp., de verwachte complexiteit? Kun je het algoritme verbeteren? Opgave 7.3 Randomisering. (Uit het tentamen van mei 2000.) Hier zie je een Monte Carlo algoritme voor electie tussen twee processen: mijngetal = random(0..31) send mijngetal ; receive haargetal if (mijngetal < haargetal) then { toestand = leider } else if (mijngetal > haargetal) then { toestand = niet-leider } (a) (b) (c) (d)
Wat is het verschil tussen terminatie en terminatie met kans 1? Aan welke van deze voldoet dit algoritme? Wat is een Las Vegas algoritme? Verander het algoritme zo dat het een Las Vegas algoritme wordt.
Opgave 7.4 Laat zien dat je, gegeven een Las-Vegas-algoritme voor een zeker probleem, altijd een Monte-Carlo-algoritme (met elke gewenste faalkans) kunt maken. Opgave 7.5 Gerandomiseerde electie. (Uit het tentamen van november 2005.) Itai en Rodeh bedachten in 1981 een originele oplossing voor het probleem van electie op ringen. Stations kiezen een random getal (uit het bereik 1 . . . n2 , waar n het aantal stations is) als identiteit, en gebruiken die identiteit vervolgens om het (deterministische) algoritme van Chang en Roberts uit te voeren. (a) Bespreek wat er kan gebeuren in het (onwaarschijnlijke) geval dat enkele stations gelijke getallen als identiteit kiezen. (b) Wat kun je zeggen over de bericht-complexiteit van deze aanpak? (c) Is er sprake van een Monte Carlo, Las Vegas, of Sherwood algoritme? Opgave 7.6 Randomiserende algoritmen. (Uit het tentamen van mei 2001.) Piet heeft een nieuw randomiserend algoritme uitgevonden. (Het berekent een Rangordening van Invoer, dwz. elk station heeft een invoergetal waarvan de rang in de verzameling invoeren wordt bepaald, maar dat is voor deze opgave eigenlijk niet van belang.) Helaas is het aantal ronden dat het algoritme gebruikt niet begrensd, maar bij terminatie geeft het wel altijd een correct resultaat. (a) Wat is het verschil tussen een Las Vegas en een Monte Carlo algoritme? Van welk type is
Opgaven bij hoofdstuk 7
111
Piet’s algoritme? (b) Piet’s algoritme heeft een verwacht aantal ronden van R. Bewijs dat voor elke s geldt: de kans dat het algoritme s of meer ronden nodig heeft is begrensd door Rs . (c) Piet wil voor ongeduldige gebruikers een variant maken die wel een begrensd aantal ronden gebruikt, maar dan kan het resultaat incorrect zijn. De faalkans en/of aantal ronden moet instelbaar zijn en wel zo dat de faalkans zo klein kan worden als de gebruiker wil. Leg uit hoe dat kan en hoe verhouden zich dan de tijdgrens en de faalkans? Opgave 7.7 Dit is een alternatieve deterministische strategie voor het broadcast probleem: Station i zendt in alle ronden tot en met i. Geef de S- en R-verzamelingen van deze strategie, analyseer de tijd, en bewijs de correctheid. Dezelfde vragen voor deze strategie: Station i zendt in ronde i en, als i > 1, ook in i − 1. Opgave 7.8 Een strategie voor het satellietprobleem heeft deze eigenschap: elk station i zendt voor het eerst in slot i (en wat hij daarna nog doet interesseert ons niet). Druk deze eigenschap uit als eisen op de R- en S-verzamelingen en bewijs dat elke strategie met deze eigenschap correct is. Hoeveel slots zijn nodig? Opgave 7.9 Bereken S(n) (zie stelling 7.8) voor alle n ≤ 10. Wat is de limiet? Opgave 7.10 Zij T (z) de exponentieel voortbrengende functie van S(n): T (z) =
P
zn n≥0 S(n) n! .
(a) Bewijs dat T (z) = z/2 + ez/2 · T (z/2). (b) Kun je een uitdrukking opstellen voor de k-de afgeleide T (k) (z)? (c) Kun je S(n) vinden als T (n) (0)? Opgave 7.11 In een variant op programma 7.6 zendt een station niet elke ronde tot de eerste 0, maar juist alleen in de eerste ronde met een 0. Bewijs dat de slaagkans hierdoor stijgt. Bereken de slaagkans. Opgave 7.12 Vervalprocedure. (Uit het tentamen van november 2003.) In de vervalprocedure (Prog. 7.6) zendt een station in elk slot, totdat een keer de waarde 0 de uitkomst van een random-instructie µ is. ¶ Voor S(n), de slaagkans wanneer er n stations P n n−1 S(k). (We negeren in de berekening een eventuele deelnemen, geldt S(n) = 2n1−1 k=0 k ingebouwde limiet op het aantal ronden.) In de Verbeterde Vervalprocedure zendt elk station precies ´e´en keer, namelijk in die ronde waarin hij voor ’t eerst een 0 trekt. (a) Geef hiervoor een programma (pseudocode). (b) Zij T (n) de kans dat de verbeterde procedure slaagt als er n stations aan beginnen; geef een recurrente betrekking voor T (n). (Kun je bewijzen dat T (n) ≥ S(n)?) Opgave 7.13 Je kunt in programma 7.6 ook een “valse munt” gebruiken; zij p de kans op een 1 en q (= 1 − p) de kans op een 0. Als we p wat groter maken duurt het langer voor alle stations gestopt zijn met zenden, maar de kans op succes wordt groter. Welke p minimaliseert de verwachte tijd van het afgeleide Las Vegas algoritme? Opgave 7.14 Laat zien dat geldigheid in sectie 7.3 niet-trivialiteit impliceert. Waarom sluit stelling 6.4 het algoritme van Ben-Or niet uit?
112
7 Randomisering
Opgave 7.15 Consensus. (Uit het tentamen van augustus 2000.) Voor het consensus-probleem bewezen Fischer, Lynch en Paterson een onmogelijkheidsresultaat, toch bestaat hiervoor het algoritme van Ben-Or. (a) Hoe luidt de stelling van Fischer, Lynch en Paterson? (b) Leg uit waarom deze stelling het algoritme van Ben-Or niet uitsluit. (c) Is Ben-Or’s algoritme van het Las Vegas, Monte Carlo of Sherwood type? Leg uit waarom. Opgave 7.16 Bewijs de volgende versterking van lemma 7.9: Als aan het begin van een ronde meer dan 12 n + t processen dezelfde waarde v (in {0, 1}) hebben, beslist elk correct proces in die ronde v.
Hoofdstuk 8
Foutdetectie Het is lastig dat het consensus-probleem niet oplosbaar is in asynchrone systemen (stelling 6.4) omdat het werken aan asynchrone programmatuur erg prettig is. Het belang van het consensusprobleem zal in de latere hoofdstukken verder duidelijk worden. Nu zijn er in hoofdlijnen drie manieren om het resultaat van Fischer, Lynch en Paterson te omzeilen, namelijk door versterking van het reken-model of door verzwakking van de eisen aan de oplossing: 1. Maak het model synchroon. In de praktijk zijn computersystemen niet helemaal asynchroon, het is bijvoorbeeld redelijk aan te nemen dat een eenvoudige optelling korter duurt dan een ingewikkelde berekening, of dat “de meeste berichten binnen een jaar ontvangen worden”. Je mag als programmeur echter nooit uitgaan van wat redelijk is of vaak gebeurt, maar uitsluitend gebruik maken van gespecificeerde (en gegarandeerde) eigenschappen van het onderliggende systeem. Je kunt een zekere mate van synchroniteit modelleren in je rekenmodel en er dan in je algoritme gebruik van maken. Dolev, Dwork en Stockmeyer [DDS87, DLS88] maakten een uitgebreide studie over hoeveel synchroniteit noodzakelijk is. We zien een voorbeeld van een synchroon algoritme in sectie 8.1. 2. Randomisering. Er zijn diverse voorbeelden die aantonen dat randomisering het gedistribueerde rekenmodel sterker maakt, zowel in complexiteit (met randomisering kun je “door een deterministische ondergrens heen”) als in berekenbaarheid; zie hoofdstuk 7. Consensus is een voorbeeld van het laatste, en Ben-Or [BO83] gaf een gerandomiseerd algoritme voor consensus (sectie 7.3). 3. Foutdetectie. We nemen aan dat de processen enig inzicht hebben in welke processen zijn gecrasht. Dit inzicht berust vaak op gebruik van timers en dus impliciete aannamen over synchroniciteit van het systeem. De programmeur heeft echter met tijd-constanten en timers niets te maken omdat hij de detector als abstracte module aanspreekt, en bovendien zijn andere implementaties (dan met tijd) van detectors mogelijk.
8.1
Motivatie: synchrone consensus
Neem aan dat er een maximum µ geldt op de looptijd van een bericht: op tijdstip t verzonden betekent v`o`or t + µ ontvangen. Neem aan dat ρ de maximale tijd is voor het uitvoeren van de forall in de body van het hoofdprogramma van programma 8.1. 113
114
8 Foutdetectie
V[1..n]
// accumuleer invoer van alle processen
telkens wanneer een vector W wordt ontvangen: { forall j in 1..n if ( V[j] == @ and W[j] != @ ) { V[j] = W[j] } } Hoofdprogramma voor i (start op tijd t0): V = ( @, @, ..., x, .. @ ) // x staat op positie i for (r = 1 ; r < n ; r++) { forall j in 1..n { send V to j } sleep until (t0 + r*(mu+rho)) } decide( MAJ(V) ) Programma 8.1: Synchrone stemming (consensus).
Preconditie voor het programma is dat elk station op tijd t0 over een invoerbit beschikt; het programma voert een “stemming” uit en kiest de vaakst voorkomende bit. In de stemming tellen de invoeren van alle correcte, en een deelverzameling van de crashende processen mee. Proces i spaart invoeren in een vector V, initi¨eel wordt daarvan de waarde V[i] ingevuld. In programma 8.1 zie je dat ontvangen waarden in de vector worden verwerkt, en dat het proces periodiek alle bekende waarden rondzendt (dit flood set principe wordt in veel algoritmen toegepast). Merk op dat een bericht dat in ronde r wordt verstuurd, nog in diezelfde ronde wordt ontvangen (waarom)? Na n − 1 van deze ronden wordt op de meerderheid uit V beslist. Stelling 8.1 Programma 8.1 is een synchroon niet-triviaal consensus algoritme. Bewijs. Omdat het zenden en beslissen door de klok worden gestuurd zal een proces nooit wachten, er treedt geen deadlock op en elk correct proces zal op tijd t0 + (n − 1)(µ + ρ) een beslissing nemen. Dat deze beslissing in elk proces gelijk is volgt uit de gelijkheid van de V-vectoren van verschillende processen. Merk eerst op dat als proces j ooit iets invult in V[i], dit de juiste waarde van xi is. We gaan bewijzen dat correcte processen dezelfde waarden hebben ingevuld: Stel i en j zijn correct en na afloop heeft i V[k] ingevuld; dan heeft ook j V[k] ingevuld. Bewijs: Zij r de ronde waarin i de waarde van xk voor ’t eerst vernam; als r < n − 1, dan zendt i de waarde in de volgende ronde, o.a. naar j, waarmee het zeker is dat ook j de waarde een keer gezien heeft. Maar wat als i de waarde xk in ronde n − 1 voor het eerst zag? In elk van de ronden 1 tot n − 1 is er een proces geweest dat deze waarde voor het eerst heeft verzonden; in het bijzonder heeft j die al een keer gezien. Uit het voorgaande blijkt dat processen dezelfde beslissing nemen (MAJ is een deterministische functie die de meest voorkomende waarde ongelijk @ selecteert). In ieder geval tellen de invoeren van niet-crashende processen mee, waarmee ook niet-trivialiteit wordt bewezen. ¤ Het algoritme is niet vreselijk ingewikkeld, maar er zijn wel verschillende aannamen op het gebied van timing nodig en de diverse tijdconstanten vinden we allemaal terug in het
8.2 Definities
115
programma. Het programma moet dus worden aangepast om het op een snel of een langzaam systeem te draaien; aanpassingen kunnen ingewikkeld zijn omdat er per systeem verschillende dingen kunnen zijn waar precies tijdgrenzen op bestaan. Een ander probleem met synchrone systemen is dat ze vaak onnodig veel tijd gebruiken omdat de bovengrenzen op de looptijd als worst case tijd zijn gespecificeerd. Een typische situatie is dat het systeem een bovengrens van 100ms op de looptijd garandeert, maar in het meeste gebruik komt het zelden voor dat een bericht langer dan 3ms onderweg is. Bij het bepalen van de timerwaarden moet je dan in programma 8.1 van 100ms per ronde uitgaan, terwijl een asynchroon programma (zoals programma 6.3) een ronde per 3ms afwerkt. Bij compatibele computersystemen zijn doorgaans wel de functionele, maar niet de temporele eigenschappen van de componenten gelijk. IBM heeft een kwart eeuw computers gebouwd met dezelfde architectuur (System/360, zie Kader 1.6), maar model 3090-400 was 2000 maal zo snel als model 30. Hier zou compatibiliteit afdwingen dat de 3090-400 wordt afgeremd tot het tempo van de 30. Wat is nu het geheim achter programma 8.1? Het programma kan werken omdat synchrone systemen een perfecte foutdetectie bieden: als aan het eind van een ronde niets van proces j is ontvangen, dan is j gecrasht. We willen graag de zegeningen van deze mogelijkheid gebruiken, zonder de programmeur op te zadelen met stapels timing-aannamen en constanten. Bovendien willen we weten hoe goed je fouten moet kunnen detecteren om consensus te kunnen bereiken. Voor beide doelen is de foutdetector een ideale abstractie.
8.2
Definities
Een foutdetector is een module die aan ieder proces een verzameling verdachte processen levert; in de programma’s schrijven we dit als de test j in D en die vertelt of proces j op dat moment al dan niet verdacht is. Om over foutdetectors te kunnen redeneren moeten we deze uitvoer kunnen relateren aan de daadwerkelijke crashes, zoals uitgedrukt in het foutpatroon. In het vervolg is Π een (eindige) verzameling processen. Om uitdrukkingen in modale (temporele) logica te omzeilen voeren we een expliciete tijdsvariabele t in (met range T , bv. de natuurlijke getallen). De daadwerkelijk in een executie optredende fouten worden gemodelleerd als een wiskundige constructie, het foutpatroon, en de uitvoer van de detector als een foutdetectorhistory. De bruikbaarheid van de detector wordt natuurlijk uitgedrukt in termen van relaties die tussen deze twee begrippen gelden. Het foutpatroon F , de tijd t, de afgeleide verzamelingen Crash(F ) en Corr (F ), alsmede de foutdetector history zijn voor de processen niet observeerbaar! Het enige dat proces q “ziet” is de waarde van H(q, t), wanneer het op tijd t zijn foutdetector D aanspreekt. Foutpatroon en foutdetector-history. We beschrijven eerst de input van de detector, te weten het patroon van optredende fouten tijdens een executie. De crashes die tijdens een berekening optreden worden gemodelleerd met een foutpatroon F : T → P(Π). Hier stelt Π de verzameling processen voor en P de powerset. Dan is F (t) de verzameling processen die op tijd t gecrasht zijn. Omdat we geen herstarts modelleren is F altijd monotoon: t1 ≤ t2 ⇒ F (t1 ) ⊆ F (t2 ), dus een proces dat ´e´enmaal gecrast is blijft daarna altijd gecrasht. De verzamelingen van defecte en correcte processen zijn door F gedefini¨eerd; processen gelden als defect als ze ooit tijdens de executie crashen, dus Crash(F ) = ∪t∈T F (t). Ze zijn correct als ze dat niet doen, dus Corr (F ) = Π \ Crash(F ).
116
8 Foutdetectie
Kader 8.2: Kritiek op het gebruik van foutdetectors Foutdetectie werd rond 1991 als abstract mechanisme geformuleerd door de onderzoeksgroep van Sam Toueg uit Cornell, en na 5 jaar verscheen een lijvig artikel [CT96] met veel fundamentele resultaten, waaraan onze definities zijn ontleend. Van verschillende kanten stond de aanpak onder kritiek, met name dat het mechanisme van foutdetectors “niets oplost”. Immers, voor de implementatie van detectors zijn weer onderliggende mechanismen nodig (zoals tijd, zie sectie 8.3), en zonder deze mechanismen blijven detectors onimplementeerbaar en dus consensus onoplosbaar. Nu is hetzelfde argument toepasbaar op vrijwel alles wat er in de informatica is uitgevonden, van programmeertalen tot devicedrivers. Ook de laatsten doen immers alleen maar dingen die je “net zo goed” (hm!) rechtstreeks vanuit de applicatie zou kunnen doen? Het invoeren van abstracties is echter een essentieel hulpmiddel in de gestructureerde bestudering van een onderwerp, en het onderbrengen van functionaliteit in een module maakt het gebruik ervan gemakkelijker en toegankelijker.
De output van de detector bestaat uit de (mogelijk steeds wisselende) verzamelingen verdenkingen. Verdenkingen kunnen in de tijd en per proces verschillen, daarom modelleren we een foutdetector history als functie H : Π × T → P(Π). Hier is H(q, t) natuurlijk de verzameling processen die op tijd t door q worden verdacht. Een foutdetector is non-deterministisch: gegeven een foutpatroon zijn er altijd meerdere foutdetector histories mogelijk. Eisen op de histories. Tot nu toe hebben we geen verband gelegd tussen de fouten die in een executie optreden en de foutdetector history, maar om iets aan de foutdetector te hebben moeten we dat natuurlijk wel doen. De eisen zijn steeds van twee typen, namelijk Compleetheid (gecrashte processen worden verdacht) en Accuratesse (correcte processen worden niet verdacht). In de formules komen een foutpatroon F en een foutdetector history H vrij voor; de formule moet natuurlijk gelden voor alle combinaties van F en H die onder de foutdetector D mogelijk zijn. We bekijken compleetheid slechts in ´e´en verschijningsvorm: Definitie 8.2 Foutdetector D is compleet als geldt dat elk gecrasht proces uiteindelijk door elk correct proces wordt verdacht: ∃t : ∀t0 ≥ t : ∀p ∈ Crash(F ) : ∀q ∈ Corr (F ) : p ∈ H(q, t0 ). Accuratesse wordt in vier vormen onderscheiden. Naast een sterke (geen correct proces wordt verdacht) is er een zwakke variant waarin slechts wordt ge¨eist dat er tenminste ´e´en correct proces is dat niet wordt verdacht. Van beide onderscheiden we bovendien een “uiteindelijke” versie, waarbij de detector zich in het begin willekeurig mag vergissen, maar na een eindige periode de gewenste accuratesse gaat vertonen.
8.2 Definities
117
Kader 8.3: Sterke en zwakke compleetheid, reducties Soms wordt een onderscheid gemaakt tussen sterke en zwakke compleetheid. Bij sterke compleetheid wordt (definitie 8.2) ge¨eist dat een gecrasht proces door elk correct proces zal worden verdacht. Bij zwakke compleetheid wordt alleen ge¨eist dat een gecrasht proces door tenminste een correct proces zal worden verdacht. D0
D ?
TD→D0 ?
Algoritme A gebruikt D0
Chandra en Toueg [CT96] defini¨eren reducties, dit zijn nog abstractere mechanismen die werken op foutdetectors. Veronderstel dat de processen beschikken over een foutdetector D die zwak compleet is; we willen echter een algoritme A gebruiken dat een sterk complete detector veronderstelt. De beoogde reductie TD→D0 laat elk proces q regelmatig de verdenkingen (van D) rondsturen. Elk proces p houdt een verzameling H 0 (p) bij; deze is initi¨eel leeg. Op ontvangst van een verzameling H van q wordt deze aangepast als H 0 (p) = H 0 (p) ∪ H \ {q}.
De foutdetector D0 toont A de verzamelingen H 0 . Wanneer een gecrasht proces door een correct proces wordt verdacht, zal de verdenking door de andere correcte processen worden overgenomen. Een proces wordt pas verdacht door D0 als het eerder door D verdacht was, en tijdelijke onterechte verdenkingen worden opgeheven. Het gevolg is dat D0 sterk compleet is, en aan dezelfde eigenschappen van accuratesse voldoet als D. Definitie 8.3 Foutdetector D is sterk accuraat als geen enkel ongecrasht proces ooit wordt verdacht: ∀t : ∀p, q 6∈ F (t) : p 6∈ H(q, t). Foutdetector D is zwak accuraat als er een correct proces is dat nooit wordt verdacht: ∃p ∈ Corr (F ) : ∀t : ∀q 6∈ F (t) : p 6∈ H(q, t). Foutdetector D is uiteindelijk sterk accuraat als er een tijdstip bestaat waarna geen enkel correct proces meer wordt verdacht: ∃t : ∀t0 ≥ t : ∀p, q ∈ Corr (F ) : p 6∈ H(q, t0 ). Foutdetector D is uiteindelijk zwak accuraat als er een tijdstip bestaat en een correct proces dat na dat tijdstip niet meer wordt verdacht: ∃t : ∃p ∈ Corr (F ) : ∀t0 ≥ t : ∀q ∈ Corr (F ) : p 6∈ H(q, t0 ). Hoewel de abstractie van de foutdetector beoogt een scheiding aan te brengen tussen de implementatie en het gebruik van de foutdetectie, worden de onderscheiden vormen van accuratesse toch gemotiveerd door zowel de implementatie als het gebruik. Bij de implementatie (sectie 8.3) zien we dat een gebruikt mechanisme onterechte verdenkingen niet helemaal kan uitsluiten, maar wel in uiteindelijke zin. Bij de implementatie van consensus (programma 8.6 en 8.7) zien
118
8 Foutdetectie
set D // verdachte processen, initieel leeg timer rec[PI] // ontvang-timer voor elk proces // het zenden: op elk veelvoud van sigma: forall j { send IkLeef to j } // het ontvangen: telkens als IkLeef binnenkomt van j: rec[j] = sigma+mu // de time-out als de timer rec[j] afloopt: D = D + {j} Programma 8.4: Perfecte detectie in synchroon systeem.
we dat onterechte verdenkingen te tolereren zijn, mits tenminste ´e´en proces buiten verdenking is. Het is erg gemakkelijk een foutdetector te maken die compleet is (namelijk ´e´en die altijd iedereen verdenkt: H(q, t) = Π) en even gemakkelijk een die accuraat is (verdenk nooit iets: H(q, t) = ∅). Interessante en nuttige detectors hebben daarom een combinatie van compleetheid en accuratesse. Definitie 8.4 Een foutdetector is perfect als hij compleet en sterk accuraat is; de klasse van deze detectors heet P. Een foutdetector is sterk als hij compleet en zwak accuraat is; de klasse van deze detectors heet S. Een foutdetector is uiteindelijk perfect als hij compleet en uiteindelijk sterk accuraat is; de klasse van deze detectors heet 3P. Een foutdetector is uiteindelijk sterk als hij compleet en uiteindelijk zwak accuraat is; de klasse van deze detectors heet 3S.
8.3
Implementaties van foutdetectors
Een voordeel van de foutdetector als abstractie is dat we alleen met de eigenschappen en niet met de implementatie rekening hebben te houden. Toch gaan we kort op mogelijke implementaties in, o.a. als motivatie voor de misschien wat vreemd aandoende definities. 8.3.1
Synchrone systemen: perfecte detectie
Neem weer aan dat er een bovengrens µ op de berichtenlooptijd is. Elk proces zendt periodiek (telkens na σ tijdseenheden) een IkLeef bericht aan alle anderen, en een proces waarvan zo’n bericht gedurende µ + σ niet is ontvangen wordt verdacht; zie programma 8.4.
8.3 Implementaties van foutdetectors
set D timer rec[PI] int muSch
119
// verdachte processen, initieel leeg // ontvang-timer voor elk proces // schatting voor mu, initieel 1
// het zenden: op elk veelvoud van sigma: forall j { send IkLeef to j } // het ontvangen: telkens als IkLeef binnenkomt van j: if (j in D) { D = D - {j} muSch += 1 } rec[j] = sigma + muSch // de time-out als de timer rec[j] afloopt: D = D + {j} Programma 8.5: Uiteindelijk perfecte detectie.
8.3.2
Parti¨ eel synchrone systemen: uiteindelijk perfecte detectie
Als het systeem wel een bovengrens op de looptijd heeft maar deze is onbekend, of je wilt hem niet in je programmatuur verwerken terwille van portability, is toch nog uiteindelijk perfecte detectie mogelijk (programma 8.5). Het programma begint met een kleine schatting van µ (bv. 1), waardoor het mogelijk is dat er te snelle time-outs plaatsvinden en correcte processen worden verdacht. Wordt alsnog een bericht van zo’n proces ontvangen, dan wordt het direct uit D verwijderd en de schatting voor µ wordt verhoogd. Je kunt nu bewijzen dat in elke executie eindig vaak een correct proces wordt verdacht, met andere woorden, de detectie is uiteindelijk perfect. 8.3.3
Ondersteuning door het besturingssysteem: incompleet
In het besturingssysteem wordt een tabel bijgehouden van alle threads/processen. Een poging te communiceren met een zekere thread kan dan worden beantwoord met een melding dat de thread niet (langer) bestaat. Dergelijke meldingen zijn doorgaans accuraat: een proces verdwijnt uit de tabel als het crasht door het uitvoeren van een illegale actie, bv. delen door nul of stack overflow, en levende processen staan er nog in. Een proces kan echter ook crashen door in een oneindige lus terecht te komen, het blijft dan in de procestabel, het blijft ook actief rekenen maar geeft nooit meer respons. Bij dergelijke crashes kan de respons van het operating system incompleet zijn. Het is voor het operating system niet mogelijk uit te maken of een proces dat geen respons geeft, dat ooit nog weer gaat doen of dat het gecrasht is (dit heeft met het Halting Problem te maken). Een niet erg subtiele oplossing is de volgende: een proces dat gedurende een bepaalde tijd
120
8 Foutdetectie
x = invoer for (r = 1 ; r <= n ; r++) { if ( i == r ) { forall j do send (x,r) to j } wait until ( received (x’,r) from r OR r in D ) if received (x’,r) { x = x’ } } decide (x) Programma 8.6: Een rotating-coordinator-algoritme met S.
geen respons heeft gegeven wordt door het operating system afgebroken en uit de tabellen verwijderd. Nu is de respons compleet en accuraat, maar een dergelijke “euthanasie” door het o.s. kan de correcte werking van correct geprogrammeerde systemen behoorlijk verstoren.
8.4
Consensus met zwakke accuratesse
In deze en de volgende sectie bekijken we twee consensus-algoritmen; ze voldoen aan terminatie en de consistentie wordt uitgedrukt als overeenstemming en geldigheid: Terminatie: Elk correct proces neemt eenmaal een beslissing. Overeenstemming: Alle genomen beslissingen zijn gelijk. Geldigheid: Een beslissing is gelijk aan de invoer van tenminste ´e´en proces. Geldigheid impliceert niet-trivialiteit. Hoe kun je foutdetectors in een programma gebruiken? Een complete detector kan gebruikt worden om blokkering in ontvangopdrachten te voorkomen. Een manier hiervoor die we al hebben gezien, bijvoorbeeld in programma 6.3, is om nooit meer dan n − t berichten te ontvangen (t is de robuustheid). Deze methode is niet erg verfijnd omdat berichten van correcte processen buiten beschouwing blijven als er minder dan t crashes zijn. Het gebruik van time-outs zoals in programma 8.1 is natuurlijk alleen in synchrone systemen mogelijk. Foutdetectors werken preciezer omdat je kunt programmeren dat er een bericht van een met name genoemd proces q moet worden ontvangen, waarbij het wachten wordt afgebroken als q wordt verdacht. Een proces kan dan uit de wachttoestand komen door de ontvangst van een bericht, of door het verdenken van q, en in een programma geven we dit zo aan: wait until ( received msg from q
OR
q in D )
Als de detector compleet is, leidt dit nimmer tot blokkering van een correct proces. Steeds moeten we rekening houden met de mogelijkheid dat correcte processen verschillende (verzamelingen) berichten accepteren. Denk bijvoorbeeld aan opgaven 6.1 en 6.2. Bij het gebruik van foutdetectors kan een bericht gemist worden door onterechte verdenkingen en worden de verschillen in ontvangen berichten beperkt door de accuratesse van de detector. Programma 8.6 bereikt consensus met een zwak accurate foutdetector. Dit betekent dat er ´e´en proces is dat nooit verdacht wordt, maar uiteraard weten de processen niet welk proces
8.5 Uiteindelijke zwakke accuratesse
121
dat is! Daarom gebruiken we een rotating coordinator: elke ronde kent een andere coordinator, zodat het onverdachte proces een keer aan de beurt komt (al weten we niet wanneer). De coordinator stuurt zijn waarde aan iedereen, en deze waarde wordt, indien ontvangen, overgenomen; als iedereen coordinator is geweest wordt beslist. Lemma 8.5 Elk correct process maakt alle ronden af en beslist. Bewijs. Terminatie van dit soort algoritmen wordt meestal met inductie naar het rondenummer bewezen. V`o`or ronde 1 wordt niet gewacht, dus elk correct proces bereikt ronde 1. Stel nu dat elk correct proces ronde r bereikt. Als de coordinator (proces r) correct is voltooit hij het zenden aan alle processen en de wachtende processen zullen uitendelijk ontvangen (als ze niet daarvoor r verdenken). Als de coordinator crasht zullen alle wachtende processen r uiteindelijk verdenken wegens compleetheid van de detector (als ze niet daarvoor het bericht hebben ontvangen). In beide gevallen maken alle correcte processen ronde r af en gaan door naar ronde r + 1 (of de beslissing, als r = n). ¤ Lemma 8.6 Als aan het begin van ronde r alle processen dezelfde waarde van x hebben, geldt dat aan het eind van de ronde ook. Bewijs. Een proces kan zijn waarde houden of de waarde van de coordinator overnemen, maar in het laatste geval neemt hij (volgens de premisse) dezelfde waarde over als die hij had. ¤ Stelling 8.7 Programma 8.6 is een correct consensus-algoritme. Bewijs. De terminatie is in lemma 8.5 bewezen. Wegens zwakke accuratesse is er een proces dat nooit wordt verdacht. In de ronde waarin dit proces coordinator is, breekt geen proces het wachten op een bericht af wegens verdenking van de coordinator. Dus hebben na afloop van die ronde alle processen dezelfde waarde van x, namelijk de waarde die werd verstuurd door de coordinator. Lemma 8.6 zegt dat de processen dan ook tot aan het eind gelijke waarden houden, dus alle beslissingen zijn gelijk (overeenstemming). Voor geldigheid moet je bewijzen (weer met inductie over de ronden) dat de waarde van x steeds een invoerwaarde is. ¤
8.5
Uiteindelijke zwakke accuratesse
In programma 8.6 wordt zwakke accuratesse gebruikt, waarmee het na een volledige cyclus van n ronden zeker is dat er een ronde is geweest met een onverdachte coordinator. Is de detector echter slechts uiteindelijk zwak accuraat, dan kunnen er in het begin (willekeurig lang) verdenkingen bestaan tegen alle processen, en pas na verloop van tijd stoppen de verdenkingen tegen tenminste ´e´en proces. Het kan dan willekeurig veel ronden duren voordat alle (of bijna alle) processen dezelfde waarde hebben, daarom herhaalt programma 8.7 de ronden, net zolang tot de coordinator overeenstemming constateert. Het programma gebruikt een parameter t die het maximale aantal crashes geeft waartegen het beschermd is, en de werking vereist dat t < n/3. Programma 8.6 gebruikt zo’n parameter niet, en is bestand tegen n − 1 crashes. Je kunt bewijzen dat,
122
8 Foutdetectie
x = invoer ; r = 0 while (true) { r++ cr = (r-1)%n + 1
// nieuwe ronde // bepaal coordinator
// Fase 1: alle processen send (x,r) to cr // Fase 2: alleen coordinator if ( i == cr ) { wait until received n-t maal (vq,r) v = (meerderheid uit ontvangen vq) d = (forall q: vq == v) forall j { send (d,v,r) to j } } // Fase 3: alle processen wait until ( received (d,v,r) from cr OR cr in D ) if ( received (d,v,r) ) { x = v if ( d AND (ouput==@) ) decide(v) // beslis alleen eerste keer } } Programma 8.7: Een rotating-coordinator-algoritme met 3S.
omdat de detectie niet accuraat is maar slechts uiteindelijk accuraat, er altijd zo’n grens moet zijn, en dat t < n/2 voor alle mogelijke programmas moet gelden. De coordinator cr van ronde r is het (unieke) proces waarvan het nummer modulo n gelijk is aan r. Elk (levend) proces stuurt zijn waarde aan de coordinator; deze gebruikt nog niet zijn detector, maar wacht tot n − t waarden zijn ontvangen. Hij bepaalt de meerderheid (v) en zendt die rond, daarbij aangevend (met bit d) of de ontvangen waarden hieraan unaniem gelijk waren. (Let op: dit impliceert niet dat alle correcte processen die waarde hadden aan het begin van de ronde!) De processen die de meerderheidswaarde van de coordinator ontvangen (de enige ontsnapping uit deze ontvangactie is de coordinator te verdenken) nemen die over. Er mag beslist worden als de waarde unaniem was. Merk op dat het programma wel aan terminatie voldoet, maar dat de executies niet eindig zijn: de processen gaan na een beslissing gewoon door om de processen die nog niet beslist hebben ook over de streep te trekken. Het correctheidsbewijs lijkt op dat van programma 8.6 maar de diverse resultaten zijn iets anders geformuleerd. Lemma 8.8 Voor elke r maakt elk correct proces ronde r af. Bewijs. Als lemma 8.5.
¤
Samenvatting en conclusies
123
Lemma 8.9 Als aan het begin van een ronde tenminste n − t processen dezelfde waarde v hebben, geldt dat aan het eind van de ronde ook. Bewijs. Een proces kan in de ronde de coordinator verdenken en dan blijft zijn waarde gelijk; deze verandert alleen als hij een bericht met waarde v 0 van de coordinator ontvangt. De coordinator heeft dan n − t berichten ontvangen en daar de meerderheid van bepaald. Maar er zijn hoogstens t procesen die iets anders hebben dan v, dus onder de n − t berichten die de coordinator ontving zijn er minstens n − 2t met waarde v. En omdat t < n/3 is n − 2t > t, dus de berichten met v zijn bij de coordinator in de meerderheid. De door de coordinator verspreide waarde v 0 is dus gelijk aan v, waarmee bewezen is dat elk proces dat z’n waarde verandert, ook v kiest. ¤ Lemma 8.10 Er zijn geen tegenstrijdige beslissingen: als p voor v beslist en q voor v 0 , dan v = v0. Bewijs. Een beslissing voor v impliceert dat er aan het begin van de ronde tenminste n − t processen met waarde v waren; volgens lemma 8.9 blijft dat voor alle latere ronden zo. Een beslissing in dezelfde of een latere ronde is dus altijd ook een beslissing voor v. ¤ Lemma 8.11 Elk correct proces beslist. Bewijs. Wegens uiteindelijke zwakke accuratesse komt er een ronde r waarvan de coordinator c nooit meer wordt verdacht. Op zijn laatst in die ronde krijgen alle correcte processen dezelfde waarde; immers, ze ontvangen allemaal het bericht van c. Vanaf die ronde hebben alle correcte processen dezelfde waarde (bewijs conform lemma 8.9). Alle coordinators zullen daarna een uniforme waarde (met d = true) verspreiden. Op zijn laatst in de ronde waarin c weer coordinator is (r + n) wordt dit bericht door elk correct proces ontvangen, en na die ronde hebben alle correcte processen dus beslist. ¤ Stelling 8.12 Programma 8.7 is een correct consensus-algoritme met foutdetectie in 3S. Bewijs. We bewezen overeenstemming in lemma 8.10 en terminatie in lemma 8.11. Met inductie over de ronden bewijs je dat alle waarden van x ooit een invoer zijn geweest, waarmee geldigheid ook is bewezen. ¤ Het resultaat is bevredigend omdat 3S de zwakste eigenschap van foutdetectors is die werd gedefinieerd (definitie 8.4). Een detector die aan deze zwakste eigenschap voldoet is dus al voldoende om het consensus-probleem op te lossen. Chandra, Hadzilacos en Toueg bewezen in een opmerkelijk artikel [CHT96] dat een nog zwakkere detector niet voldoet, oftewel, dat 3S de minimale eigenschap is van een detector waarmee consensus kan worden opgelost. In hun constructie gebruiken zij een willekeurige detector die consensus kan bereiken, om consensus te bereiken over tenminste een proces dat niet gecrasht is. Op deze manier blijft uiteindelijk een proces onverdacht, wat een van de eisen is voor een detector in 3S.
Samenvatting en conclusies In gedistribueerde systemen wordt meestal een of ander mechanisme gebruikt waarmee processen informatie verkrijgen over het al dan niet correct functioneren van andere processen. Hiervoor kunnen bijvoorbeeld time-outs worden gebruikt.
124
8 Foutdetectie
Om een helder ontwerp te kunnen maken, verdient het aanbeveling om deze functionaliteit niet te verweven met de rest van de applicatie, maar in afzonderlijke modules onder te brengen, de foutdetectors. Foutdetectie kan dan in afzondering worden bestudeerd, waarbij met name de vraag voorop staat, hoe goed een foutdetector moet zijn om het consensus-probleem op te kunnen lossen. In dit hoofdstuk worden compleetheid en accuratesse van foutdetectors gedefinieerd, en enkele eenvoudige implementaties met timers worden getoond. Ook werden enkele consensusalgoritmen besproken die met foutdetectors werken.
Opgaven bij hoofdstuk 8 Opgave 8.1 In programma 8.1 is (impliciet) aangenomen dat de klokken van de diverse processen exact gelijklopen. Hoe moet het programma worden aangepast aan de meer realistische aanname dat er een verschil van hoogstens ² tussen de uitlezingen van verschillende klokken bestaat? Als je dat te makkelijk vindt: de aanname dat de klokken niet even snel lopen maar begrensde drift hebben: in een tijdseenheid neemt de klokwaarde tussen 1 − φ en 1 + φ toe. Opgave 8.2 In het bewijs van stelling 8.1 wordt gebruikt dat als i een waarde voor het eerst zag in ronde n − 1, dan was er in elke ronde een proces dat het voor het eerst zag. Waarom is dat zo? Opgave 8.3 Bewijs dat als er hoogstens t processen kunnen crashen, een beslissing in programma 8.1 al genomen kan worden na t + 1 ronden (in plaats van n − 1) van communicatie. Opgave 8.4 Zij F een fout-patroon; bewijs dat er een t is waarvoor geldt F (t) = Crash(F ). Waar gebruikt je bewijs dat Π eindig is? Opgave 8.5 Fout-detectie: eisen. (Uit het tentamen van augustus 2000.) Een fout-detector moet over het algemeen voldoen aan eisen van twee typen: compleetheid en accuraatheid. (a) Wat is compleetheid en wat is accuraatheid? (b) Waarom is het erg gemakkelijk een detector te implementeren die aan slechts ´e´en van deze twee eisen voldoet? (c) Geef een implementatie van een fout-detector met behulp van timers in een gedistribueerd systeem waar een maximale transmissietijd µ van berichten gegarandeerd is. Opgave 8.6 Sterke accuratesse is sterker dan de eis dat geen enkel correct proces ooit wordt verdacht: ∀F : ∀H ∈ D(F ) : ∀t : ∀p ∈ Corr (F ), q 6∈ F (t) : p 6∈ H(q, t). Geef een voorbeeld van een foutdetector history die hieraan voldoet, maar voor een sterk accurate detector niet is toegestaan. Opgave 8.7 Hoeveel tijd kan er in programma 8.4 verstrijken tussen een crash en de detectie daarvan? Opgave 8.8 Bewijs de uiteindelijke perfectie van programma 8.5. Geldt in elke executie uiteindelijk muSch ≥ µ?
Opgaven bij hoofdstuk 8
125
Opgave 8.9 Proces p stuurt een bericht aan q en daarna aan r; dezen wachten op ontvangst van p of verdenking van p. Laat met een voorbeeld zien dat het zelfs ingeval van perfecte detectie mogelijk is dat q het bericht niet, en r het wel ontvangt. Opgave 8.10 Perfecte Fout-detectie. (Uit het tentamen van februari 2003.) (a) Hoe luiden de eisen waaraan een perfecte fout-detector moet voldoen? (b) Proces p stuurt een bericht aan q en daarna aan r; dezen wachten op ontvangst van het bericht of het verdenken van p. Laat met een voorbeeld zien dat het, zelfs bij perfecte foutdetectie, mogelijk is dat q het bericht niet, en r het bericht wel ontvangt. Opgave 8.11 Consensus. (Uit het tentamen van februari 2003.) Voor het consensus-probleem bewezen Fischer, Lynch en Paterson een onmogelijkheidsresultaat, toch bestaan hiervoor (1) het algoritme van Ben-Or en (2) enkele rotating-coordinatoralgoritmen. (a) Hoe luidt de stelling van Fischer, Lynch en Paterson? (b) Leg uit waarom deze stelling het algoritme van Ben-Or niet uitsluit. (c) Is Ben-Or’s algoritme van het Las Vegas, Monte Carlo of Sherwood type? Leg uit waarom. (d) Waarom sluit de stelling van Fischer, Lynch en Paterson de rotating-coordinatoralgoritmen niet uit? Opgave 8.12 Het bewijs van lemma 8.5 is nogal slordig. Formuleer een nette inductiehypothese en bewijs hem. Opgave 8.13 Bewijs geldigheid van programma 8.6. Opgave 8.14 Rotating Coordinators. (Uit het tentamen van februari 2001.) Het Rotating Coordinator Algoritme (met S) werkt zo: (1) In elke ronde shout de coordinator zijn waarde x; (2) Alle stations wachten tot ze ofwel die waarde ontvangen, danwel de coordinator verdenken, en in het eerste geval nemen ze de waarde van de coordinator over. (a) Wat houden de eigenschappen Accuraat en Compleet voor een fout-detector in? (b) Leg uit waarom correcte processen nooit geblokkeerd raken (wachtend op een bericht) in het Rotating Coordinator Algoritme. (c) Hoeveel ronden zijn nodig en waarom is aan Overeenstemming voldaan? Opgave 8.15 Formuleer programma 8.7 als een eindig algoritme. Opgave 8.16 Verzin een executie van programma 8.7 waarin processen in verschillende ronden beslissen.
Hoofdstuk 9
Wachtvrije implementaties met registers
Atomiciteit van operaties vereist dat het resultaat van operaties altijd is alsof de operaties na elkaar zijn uitgevoerd; de operaties gelden dan als ondeelbaar. Vanaf de jaren vijftig heeft dit begrip ondeelbaar niet alleen een belangrijke rol gespeeld in de betekenis van atomiciteit, maar ook bij de implementatie ervan. Steeds moest een thread voor het uitvoeren van een operatie op data een exclusieve toegang tot de data of code verkrijgen, met als resultaat dat de toegang voor andere threads geblokkeerd was. De steeds “modernere” ontwikkelingen betroffen alleen de manier waarop dit wachten was geregeld: eerst via mutual exclusion code, later via semaforen en monitors of database locks. Halverwege de jaren tachtig ontstond belangstelling voor de vraag, in hoeverre atomaire operaties ge¨ımplementeerd kunnen worden zonder dat onderling wachten noodzakelijk is. Dit betekent dat alle instructies van de operaties zelf, dus niet alleen van de speciaal ontworpen of beschermde synchronisatiecode, willekeurig kunnen worden afgewisseld. Het blijkt wel degelijk mogelijk om programma’s te ontwerpen die aan deze zware eis kunnen voldoen. Wel bleek al snel dat uitgaande van atomaire registers de mogelijkheden beperkt waren, maar gebruikmakend van speciale parallellisme-ondersteunende instructies zoals de test-and-set kon er al meer worden ge¨ımplementeerd. De komende drie hoofdstukken bestuderen enkele belangrijke concepten uit deze theorie van wachtvrije implementaties. Dit hoofdstuk definieert wat een wachtvrije implementatie is en er wordt ook gekeken naar enkele voorbeelden die met registers mogelijk zijn. In hoofdstuk 10 worden de grenzen van wat met registers mogelijk is overschreden: we zien dat het consensusprobleem niet met registers kan worden opgelost, maar wel met een test-and-set of ander primitief. In hoofdstuk 11 zullen we zien wat de krachtigste primitiva zijn die er voor wachtvrij rekenen bestaan, en dat de compare-and-swap tot deze categorie van krachtigste objecten behoort. De resultaten zijn op een objectgeori¨enteerde manier geformuleerd. De wachtvrije synchronisatie heeft, ondanks de duidelijke voordelen, nog nauwelijks zijn weg gevonden naar operationele producten.
126
9.1 Voordelen van wachtvrije synchronisatie
9.1
127
Voordelen van wachtvrije synchronisatie
Zowel bij het “klassiek” programmeren met gedeelde variabelen (hoofdstukken 1 tot 4) als bij programmeren met berichtuitwisseling (hoofdstukken 5 tot 8) hebben we te maken gehad met processen die op de een of ander manier op elkaar moeten wachten. We hebben daarvan diverse nadelen gezien, waaronder de mogelijkheid tot deadlock en starvation (hoofdstuk 4). Als de berekening “snelle” en “langzame” processen bevat (bijvoorbeeld doordat het netwerk naast supercomputers ook nog wat oude trage stations bevat), is er de mogelijkheid dat de snelle processen voor hun voortgang afhankelijk zijn van de trage, zodat er van snel werken weinig komt. Tenslotte zijn wachtende processen extreem kwetsbaar voor het crashen van het proces waarop gewacht wordt; daarom moest in hoofdstuk 4 altijd de aanname worden gemaakt dat een filosoof eindig lang eet. In een wachtvrij programma komen, zoals de naam al zegt, geen wacht-opdrachten voor; om ook een impliciete busy-wait uit te sluiten wordt bovendien ge¨eist dat elke operatie wordt afgerond binnen een begrensd aantal instucties van het proces. De eisen worden straks preciezer geformuleerd in een objectgeori¨enteerde context. Onderling wachten wordt hiermee inderdaad uitgesloten, en de volgende voordelen van programmeren met wachtvrije objecten zijn natuurlijk de negaties van de nadelen van wachten: 1. Geen deadlocks: Omdat er bij wachtvrije oplossingen niet wordt gewacht, is ook een circulaire wacht onmogelijk, en er treden dus geen deadlocks op. 2. Begrensde responstijd: Omdat er niet wordt gewacht en een operatie binnen een begrensd aantal instructies wordt afgerond, is een proces voor zijn voortgang niet afhankelijk van de snelheid van andere componenten. Anders gezegd, een proces heeft zijn responstijd helemaal “in eigen hand”. 3. Fouttolerant: Als processen halverwege operaties afbreken heeft dit op de voortgang van andere processen geen invloed, want die hoeven niet te wachten. Bovendien is de werking van de (asynchrone) operaties zo, dat als de processen de operaties zouden afmaken, de integriteit van de objecten blijft gelden.
9.2
Probleemstellingen modelleren als objecten
We zullen zowel de systeemprimitieven als de op te lossen problemen formuleren als objecten, met een toestand en toepasbare methoden. De methoden zijn altijd atomair! Het resultaat van (deels) overlappende methode-aanroepen is dus hetzelfde als wanneer de methoden in ´e´en of andere volgorde na elkaar waren aangeroepen. Het wekt weinig verwondering dat eenvoudige (of complexe) datastructuren, zoals registers of queues, als objecten gemodelleerd kunnen worden. Voor co¨ ordinatieproblemen, zoals we die in gedistribueerde programma’s tegenkomen (electie, consensus), ligt dit minder voor de hand. Immers, we denken hierbij altijd aan programma’s waaraan de processen tegelijk bezig zijn en met elkaar interacteren, terwijl we bij (atomaire) objecten juist denken aan processen die na elkaar methoden uitvoeren. Toch is het heel goed mogelijk om electie of consensus als een object met atomair gedrag te modelleren; het electie-object kan zelfs op twee manieren (zie verderop).
128
9 Wachtvrije implementaties met registers
9.2.1
Definities van gebruikte objecten
We behandelen nu de diverse classes (objecttypen) die we bij de bestudering van dit onderwerp tegen zullen komen. De inpassing van willekeurige types zoals die in een programma voor zullen komen vindt in hoofdstuk 11 plaats. Register. Een register (soms ook read-write register genaamd) is een object met als toestandsruimte een willekeurige verzameling V en twee methoden, namelijk read en write(x). De eerste levert de toestand van het object op, de tweede verandert de toestand in x en levert niets op. Over het type van het register (integer, boolean, char, etc., m.a.w. wat de verzameling V is) zullen we ons niet druk maken. Een binair register, waarbij V = {0, 1}, wordt ook wel een bit genoemd. Als V meer dan twee elementen bevat spreken we van een multivalued of meerwaardig register. Bij registers maken we ook een onderscheid naar het aantal processen dat er toegang toe heeft. Heeft slechts ´e´en proces de mogelijkheid de methode write aan te roepen en ´e´en proces de mogelijkheid om de read methode aan te roepen, dan spreken we van een single writer, single reader register. Bij een single writer, multiple reader register is er eveneens ´e´en proces dat kan schrijven, maar alle processen kunnen het register lezen. En wat zou een multiple writer, multiple reader register zijn? Test-and-set. Een test-and-set is een object met twee toestanden, 0 en 1, en eveneens twee methoden, TaS en reset. De kracht van dit type zit erin, dat het in ´e´en methode mogelijk is zowel de toestand te veranderen als de (oude) toestand te lezen. De TaS levert de toestand van het object op en zet de toestand op 1. De reset zet de toestand op 0. In sectie 3.3 bleek het test-and-set object al een handig hulpmiddel omdat je er heel gemakkelijk iets mee kunt doen waar je met registers ingewikkelde programma’s voor nodig hebt. We zullen in hoofdstuk 10 zien, dat er op het gebied van wachtvrij rekenen iets mee kan worden gedaan wat met registers onmogelijk is. Queue. Een queue heeft als toestandruimte de verzameling V ∗ , de rijtjes over een verzameling V , en methoden enq(x) en deq. De methode enq(x) voegt x aan de queue toe, dwz verandert toestand σ ∈ V ∗ in σ · x, en levert niets op. De deq levert het eerste element op en verwijdert dit: dwz. als de toestand y · σ is, levert de methode y op en verandert de toestand naar σ. Als de queue leeg is blijft de toestand onveranderd en de returnwaarde is een speciaal symbool @ (niet in V ). Bij een queue veronderstellen we geen methode front, die het eerste element oplevert maar niet verwijdert. Als die methode beschikbaar is spreken we van een front-queue. De queue is de objectge¨orienteerde formulering van het producer-consumer probleem dat we in sectie 3.4 hebben besproken. Daar werd echter bij een lege buffer gewacht tot de producer weer een element had toegevoegd, maar het woord “wachten” is vanaf dit hoofdstuk uit ons woordenboek geschrapt. Compare-and-swap. Een compare-and-swap is een wat uitgebreidere variant op het thema test-and-set; ook hier vinden we een methode die tegelijk de toestand leest en be¨ınvloedt. Toestandsruimte is weer een verzameling V en er zijn methoden read en CaS(x, y). De methode read levert de toestand op net als bij een register. De methode CaS(x,y) levert ook
9.2 Probleemstellingen modelleren als objecten
129
Kader 9.1: Compare-and-Swap in IBM System/370. Een Compare-and-Swap instructie werd aan de IBM/370 architectuur (zie ook Kader 1.6) toegevoegd in 1973 om multiprocessing te ondersteunen. Weliswaar bestond er al een Testand-Set instructie, maar de ervaring had geleerd dat hiermee minder krachtige operaties konden worden ondersteund. Met de Test-and-Set kun je semaforen verkrijgen, maar alle ingewikkelder operaties vereisen dan alsnog het uitsluiten van andere threads door zo’n semafoor. In 1973 was al bekend dat Compareand-Swap meer kan doen in een enkele instructie, wat locking overbodig maakt. De studie van wacht-vrij rekenen vanaf 1990 formaliseerde dat dit niet slechts een ervaringsfeit, gebaseerd op huidige kennis is. Compare-and-Swap is bewijsbaar in staat problemen op te lossen die met Test-and-Set niet oplosbaar zijn.
de toestand op maar verandert deze in y als hij gelijk aan x was; je kunt je zijn werking dus zo voorstellen: CaS(x,y):
tmp = state if (tmp == x) then { state = y } return tmp
De test-and-set is eigenlijk een speciaal geval van de compare-and-swap; wel is het zo dat de compare-and-swap op het gebied van wachtvrij rekenen bewijsbaar meer mogelijkheden biedt. Snapshot. Een snapshotobject is een array waarvan elk proces een locatie kan schrijven, en die als geheel gelezen kan worden. De toestandsruimte is dan V n en er zijn methoden update(x) en scan. De methode update(x), aangeroepen door proces i, verandert component i van de toestand in x en de methode scan levert de toestand op. Electie. In het electieprobleem hebben stations geen invoer (behalve eventueel het identificatienummer), en daarom heeft de enige methode, elect, geen parameter. De zwakke electie vertelt elk station of het leider is of niet, en de sterke electie vertelt, wie er leider is geworden. Formeel gezegd, de elect-methode van het zwakke electie-object levert een waarde uit {leider, nonleider} op. De enige correctheidseis waar het object verder aan moet voldoen is, dat ongeacht hoeveel aanroepen er plaatsvinden (mits meer dan 0), er exact eenmaal het antwoord leider wordt gegeven. De elect-methode van het sterke electie-object levert een een getal op, namelijk de identiteit van de leider. De correctheidseis is dan dat alle antwoorden gelijk zijn, en wel aan de identiteit van een van de aanroepende stations. In een klassieke gedistribueerde omgeving is het verschil tussen deze twee vormen nauwelijks relevent; de leider (bij het zwakke object) kan de anderen laten weten wie leider is, zodat het
130
9 Wachtvrije implementaties met registers
zwakke object in feite het sterke implementeert. In het volgende hoofdstuk zullen we zien, dat in een wacht-vrije context het verschil wel degelijk relevant is. Consensus. Een consensusobject is een objectformulering van het consensus probleem. Het kan door elk proces hoogstens ´e´enmaal worden aangeroepen, met als argument een element van V ; de aanroep levert weer een element van V op, maar natuurlijk voor alle aanroepen hetzelfde element. Omdat we bovendien eisen dat de gemeenschappelijke returnwaarde voorkomt onder de invoeren, volgt hieruit dat elke aanroep van het object de eerste invoer oplevert: het object kan immers niet “in de toekomst kijken” om bij de eerste aanroep alvast een latere invoer op te leveren. We kunnen daarom het consensusobject defini¨eren met toestandsruimte V ∪ {@} en ´e´en methode submit(x) met deze werking: Als de toestand @ is, levert submit(x) de waarde x op en verandert de toestand in x, als de toestand y != @ is wordt y opgeleverd. Het zal blijken dat een consensusobject krachtiger is naarmate er meer processen gebruik van kunnen maken; een n-consensusobject kan door precies n processen worden aangeroepen. 9.2.2
Implementaties
Van sommige classes mag de programmeur de beschikbaarheid veronderstellen, bijvoorbeeld van registers en, in modernere computersystemen, soms de test-and-set of compare-and-swap. Doel van het programmeren is dan, classes met algemenere eigenschappen te implementeren met behulp van de gegeven classes. Definitie 9.1 Een wachtvrije implementatie van class B bestaat uit 1. een specificatie van objecten A1 t/m Ak waaruit een B-object wordt ge¨ımplementeerd, met hun initi¨ele toestanden; 2. voor elk proces i ∈ 1...n, en elke methode meth van B, een toegangsprocedure Pi,meth die beschrijft hoe proces i meth kan aanroepen, in termen van de onderliggende objecten A1 t/m Ak . Elke toegangsprocedure is wachtvrij, dwz., bevat geen wait instructies en termineert na een begrensd aantal instructies. De toegangsprocedures gebruiken, behalve de gedeelde objecten A1 tot Ak alleen locale variabelen van de processen. Bedenk dat de eis van een begrensd aantal instructies per toegangsprocedure sterker is dan te eisen dat er een eindig aantal operaties wordt gedaan. Begrensd betekent hier, dat er een a priori bovengrens is op het aantal instructies, en dat aantal geldt voor elke aanroep van de betreffende procedure. Het aantal stappen dat een correct proces doet voor een decide in programma 8.7 bijvoorbeeld, is wel eindig maar niet begrensd. Merk ook op dat de toegansprocedure voor elk proces anders mag zijn, ook al is de semantiek van een bepaalde methode van B voor elk proces gelijk. Nu nemen registers in onze beschouwing een bijzondere plaats in omdat we altijd aannemen dat ze in het systeem aanwezig zijn. In de definitie van A implementeert B mag je daarom altijd extra registers gebruiken. Definition 9.2 Class A implementeert class B, notatie A |= B, als er een wachtvrije implementatie van B-objecten is, waarin de gedeelde objecten A1 tot Ak elk van class A of Register zijn.
9.3 Registers: van single naar multiple reader
131
Zoals te verwachten was, is implementatie transistief: Lemma 9.3 Als A |= B en B |= C, dan A |= C. Bewijs. De gegeven implementatie van een C-object bestaat uit een aantal B-objecten en registers. Vervang elk B-object door de A-objecten en registers die het implementeren, en vervang in de toegangsprocedures voor C alle aanroepen van een B-methode door de toegangsprocedure die deze methode implementeert uit de A-objecten. De nieuwe toegangsprocedures implementeren C-objecten vanuit A-objecten en registers. De toegangsprocedures in de gegeven implementaties gebruiken alle een begrensd aantal stappen, en de procedures voor de methoden van C gebruiken daarom maar een begrensd aantal aanroepen van methoden van B. Omdat elk van die aanroepen op zijn beurt weer een begrensd aantal stappen kost, is het totale aantal stappen in de nieuwe toegangsprocedures begrensd. ¤ Omdat implementatie ook reflexief is, kun je nu bewijzen dat wederzijdse implementatie een equivalentierelatie is. Definition 9.4 Classes A en B zijn equivalent, notatie A ≡ B, als A |= B en B |= A.
9.3
Registers: van single naar multiple reader
In dit hoofdstuk beperken we ons tot objecten die vanuit registers implementeerbaar zijn. Bij registers is de scheiding tussen het weggeven van informatie en het verkrijgen van informatie heel strikt. De write verandert de toestand van het object, maar verkrijgt volstrekt geen informatie over die toestand: een thread die de write uitvoert wordt op geen enkele manier en in geen enkele situatie be¨ınvloed door de (oude) toestand van het object. De read verkrijgt wel informatie uit het object, zelfs alle informatie want de hele toestand wordt opgeleverd, maar verandert de toestand volstrekt niet: op geen enkele manier en in geen enkele situatie is aan het object zichtbaar dat er een read is uitgevoerd. De objecten die met registers te implementeren zijn hebben deze scheiding ook. Van objecten die gecombineerde operaties hebben (bv. een queue waarvan de deq operatie een waarde uit het object oplevert en meteen verwijdert) zullen we in hoofdstuk 10 zien dat ze met registers niet te implementeren zijn. De implementaties die we gaan zien zijn (1) een multiple-reader register uit single-reader registers; (2) een snapshotobject (sectie 9.4). Bij het gebruik van registers gaat men er doorgaans vanuit dat ze door alle processen te lezen en te schrijven zijn, hoewel een dergelijke flexibiliteit vanuit hardware-oogpunt verre van vanzelfsprekend is. Met name overlappende schrijfacties door verschillende processen geven soms onverwachte effecten. Registers met sterke concurrency-eigenschappen zijn echter softwarematig uit registers met zwakke eigenschappen samen te stellen, waarvan we in deze sectie een voorbeeld zien. De behandeling is overgenomen uit [AW98, Sec. 10.2.2]. We laten zien dat multiple-reader registers vanuit single-reader registers te implementeren zijn; dit blijkt lastiger dan het lijkt en geeft een aardige indruk hoe gecompliceerd wachtvrij rekenen kan zijn. Er komen ook een paar voor dit gebied typische redeneerwijzen en technieken aan de orde. We beschouwen ´e´en writer, proces w, en n readers, 1 tm n. Om de methoden van de Single-Reader registers en van het Multiple-Reader register te onderscheiden zullen we ze SRread, etc., noemen.
132
9 Wachtvrije implementaties met registers
var
Val[1..n] : SRregister
method MRwrite(x): { for ( i=1 ; i <= n ; i++ ) { Val[i].SRwrite(x) } } method MRread voor proces i: { v = Val[i].SRread return v } Programma 9.2: Incorrecte implementatie van MR-register.
9.3.1
Hoe het niet moet
Omdat elk door w beschreven register door maar ´e´en proces gelezen kan worden, is het nodig dat de writer zijn waarde in meerdere registers schrijft, voor elke lezer apart. Een voor de hand liggende, maar incorrecte, uitwerking (programma 9.2) is het gebruik van ´e´en SR-register Val[i] voor elke reader i. In een MRwrite(x) zal de writer achtereenvolgens alle SR-registers met x beschrijven, en een reader leest gewoon het voor hem bestemde register. Figuur 9.3 laat zien wat hier mis aan is (bij 2 readers): de writer overschrijft de waarde 0 met 1, maar tussen het beschrijven van Val[1] en Val[2] kan er een leesactie van 1 worden gevolgd door ´e´en van 2. De eerste leesactie krijgt dan de nieuwe waarde van het register al te zien terwijl de latere leesactie de oude waarde krijgt. Er is sprake van schending van de atomiciteit omdat het niet mogelijk is elke operatie een contractiepunt binnen het tijdsinterval van die operatie te geven. Een “klassieke” oplossing zou zijn, de registers te gebruiken om exclusieve toegang tot het object te garanderen, zodat het onmogelijk is dat er iemand leest tussen de twee schrijfacties van de writer. Het zal duidelijk zijn dat dit niet strookt met de eis van wachtvrijheid die we ons hebben opgelegd. De writer kan immers tussen twee SR-writes willekeurig lang wachten, en in de tussentijd moet het object voor de readers beschikbaar zijn zonder dat zij moeten wachten. Ook is in te zien dat een busy wait een onbegrensd aantal malen de test kan uitvoeren en dus niet aan de formele eis van een begrensd aantal operaties voldoet. Je kunt het programma ingewikkelder gaan maken door meerdere keren te gaan lezen of
w 1 2
Val[1].SRwrite(1) ? ?
Val[2].SRwrite(1) ? MRwrite(1)
Val[1].SRread Val[2].SRread
?
MRread MRread
Figuur 9.3: Tegenvoorbeeld voor programma 9.2.
9.3 Registers: van single naar multiple reader
133
schrijven, of zelfs te eisen dat de writer behalve x nog aanvullende informatie wegschrijft. Alles is tevergeefs, want tegenvoorbeelden blijven mogelijk, en de uiteindelijke oplossing gebruikt ook SR-registers die door de readers worden beschreven! Een leesactie van een reader zal dus de interne toestand van het MR-register wijzigen; in feite op een manier die ervoor zorgt dat een deels afgewikkelde MR-write van de writer wordt voltooid en in de objecttoestand definitief wordt. Het is in de informatica gebruikelijk om altijd te blijven zoeken naar betere oplossingen. In dit geval echter is bewezen, dat de genoemde concessie noodzakelijk is; er hoeft dus niet te worden gezocht naar een oplossing waarin de readers niet schrijven. Over het algemeen kan een bewijs van onmogelijkheid of ondergrens knap lastig zijn zoals we eerder hebben gezien. Echter de strenge eisen die op wachtvrije implementaties gelden werken nu in ons voordeel: een veronderstelde implementatie moet heel veel interleavings van instructies toestaan. Van die interleavings kunnen we vaak gemakkelijk wat eigenschappen combineren om te bewijzen dat geen enkel programma ooit aan de eisen kan voldoen. Stelling 9.5 Er bestaat geen wachtvrije implementatie van MR-register uit SR-registers waarin niet tenminste ´e´en van de readers een SR-register beschrijft. Bewijs. Veronderstel dat er een implementatie bestaat waarin geen van de readers schrijft in een gedeeld object. Neem nu aan dat het MR-register waarde 0 heeft; we bekijken een MRwrite(1) door de writer w. Omdat de enige gedeelde objecten SR-registers zijn met writer w, bestaat een MRwrite(1) uit een reeks SRwrites, zeg W1 tot en met Wm . Uit de aanname dat de readers niet schrijven volgt dat deze reeks, dus de activiteit van de writer, niet door overlappende MRreads worden be¨ınvloed. Omdat elk SR-register slechts door ´e´en proces gelezen kan worden, kunnen we de SR-registers verdelen in S1 , S2 , . . ., waar de SR-registers in Si slechts door proces i worden gelezen. We gaan nu even kijken welke waarden worden opgeleverd als er een complete MRread door een van de readers wordt uitgevoerd tussen twee SRwrites van de writer. Op grond van de wachtvrijheid van de implementatie is dit altijd mogelijk. Zo’n MRread kan uit een aantal SRreads zijn opgebouwd, maar de eisen van wachtvrijheid dwingen af dat de gehele transactie hoe dan ook kan aflopen voordat de writer zijn volgende SRwrite doet. Zij xi,j de waarde die wordt opgeleverd in een MRread door proces i vlak na Wj (en xi,0 de waarde die wordt opgeleverd door een MRread v`o` or W1 ). De eis van atomiciteit van het te implementeren register impliceert dat elke reader eerst steeds 0 leest, en vanaf een zeker moment steeds 1, dus: 0 = x1,0 = . . . = x1,k−1 ,
x1,k = . . . = x1,m = 1,
0 = x2,0 = . . . = x2,l−1 ,
x2,l = . . . = x2,m = 1,
De waarde die reader i leest kan namelijk alleen veranderen als er een register in Si wordt geschreven, en dit impliceert dat l 6= k. Stel k < l. Bekijk een executie die tussen Wk en Wk+1 een complete MR-read van reader 1, en daarna een van reader 2 heeft. Omdat (volgens de aanname) reader 1 niet schrijft tijdens zijn MR-read, verloopt de MR-read van reader 2 precies hetzelfde als wanneer de MR-read van reader 1 niet had plaatsgevonden. Hoewel dan de read van reader 1 is afgelopen voordat die van reader 2 begint, ziet reader 1 al de nieuwe waarde (1) en reader 2 nog de oude. Het register is dus niet atomair. Het geval l < k wordt analoog behandeld. ¤ Je kunt met dit bewijs nog iets verder gaan en, voor het geval er meer dan twee readers zijn, iets bewijzen over het aantal SR-registers dat nodig is.
134
9 Wachtvrije implementaties met registers
SR-register SR-register integer
Val[n] Report[n,n] seqNr
: : :
initieel (v0, 0) initieel (v0, 0) initieel 0
MRwrite(x): { seqNr ++ for (i=1 ; i <= n ; i++) { Val[i].SRwrite((x,seqNr)) } } MRread voor proces i: { (v,s) = Val[i].SRread for (j=1 ; j <= n ; j++) { (w,t) = Report[j,i].SRread if (t>s) then v,s = w,t } for (j=1 ; j <= n ; j++) { Report[i,j].SRwrite((v,s)) } return v } Programma 9.4: MR-register uit SR-registers.
9.3.2
Oplossing: readers helpen elkaar
In onze oplossing laten de readers aan elkaar weten welke waarde ze het laatst hebben gezien. De gedachte hierachter is het onderling helpen van threads, in dit geval is het de writer die geholpen wordt door snelle readers. In de situatie die in het bewijs werd uitgebuit, was de writer zo ver gevorderd dat zijn operatie zichtbaar was geworden voor ´e´en van de readers, maar nog niet voor een andere. Het help-mechanisme zorgt ervoor dat een reader die een nieuwe waarde heeft gezien, helpt deze voor de andere readers zichtbaar te maken voor het geval de writer zelf traag is in het afmaken van zijn MR-write. Een reader kan nu verschillende waarden te zien krijgen, namelijk rechtstreeks van de writer of van zijn collega’s en daarom is het belangrijk dat een reader oude en nieuwe waarden kan onderscheiden. De ordening van waarden wordt bijgehouden met een serienummer. Daarom gebruiken we, voor de implementatie van een MR-register van type V , een aantal SR-registers van type V × N. De writer schrijft zijn waarde, samen met het serienummer, in een SR-register voor elke reader, vergelijkbaar met programma 9.2. Een reader begint met het lezen van het voor hem bedoelde register, maar leest ook een waarde van elke andere reader; voor elk paar readers (i, j) is er een SR-register Report[i,j]. De meest recente waarde wordt weggeschreven voor de andere readers, en opgeleverd; zie programma 9.4. Hierin is v0 de initi¨ele waarde van het MR-register. Let op hoe mooi wachtvrij het programma is: een MRwrite(x) gebruikt n, en een MRread gebruikt 2n + 1 operaties op gesharede objecten, zonder tussendoor op bepaalde condities te wachten. Let ook op het gebruik van de SR-registers in de implementatie: elk register heeft
9.3 Registers: van single naar multiple reader
135
´e´en writer en ´e´en reader. Het register Var[i] heeft w als writer en reader i als reader, en Report[i,j] heeft reader i als writer en reader j als reader. De variabele seqNr wordt door de writer gelezen en geschreven, en wordt eigenlijk niet als een gedeeld object meegeteld. Om te bewijzen dat het programma inderdaad een atomair MR-register implementeert construeren we vanuit een executie van SR-operaties een volgorde van MR-operaties. Zij dus α een executie: dit is een reeks van stappen (SR-operaties en locale instructies) van de diverse processen genomen volgens het programma. Dat betekent dat als je uit α de stappen van ´e´en proces isoleert, dan zie je een aantal achtereenvolgende executies van de methode van dat proces, waarbij de laatste eventueel incompleet is. Nu vormen we een reeks π van MR-operaties. Neem eerst de rij van alle MRwrite(x) operaties, in hun volgorde in α: deze volgorde is gedefini¨eerd omdat er maar 1 writer is. Vervolgens gaan we de voltooide MRreads ertussen vlechten. De MRreads die de waarde opleveren die werden weggeschreven met serienummer t zetten we tussen de te en (t + 1)ste MRwrite, in de volgorde van hun be¨eindiging. Door deze keuze levert elke MRread precies de waarde op die is geschreven in de laatst voorafgaande MRwrite. Wat we nog moeten aantonen is dat deze volgorde niet strijdig is met de werkelijke timing van de operaties. Lemma 9.6 Als Op1 en Op2 MR-operaties zijn, zodanig dat Op1 afliep voordat Op2 begon (in α) dan komt Op1 voor Op2 in π. Bewijs. We onderscheiden vier gevallen: 1. Op1 en Op2 zijn MRwrites. Verschillende MRwrites overlappen niet en de constructie behoudt hun volgorde. 2. Op1 is een MRwrite en Op2 een MRread door proces i. Het schrijven van Val[i] in de MRwrite is al voltooid voordat proces i in de MRread Val[i] leest: proces i ziet dus meteen een serienummer dat tenminste dat van Op1 is. De uiteindelijk opgeleverde waarde kan alleen maar een hoger, geen lager serienummer hebben. 3. Op1 is een MRread door proces i en Op2 een MRwrite. Voordat een MRwrite met serienummer t begint, zijn er alleen maar kleinere serienummers te zien. Op1 levert dus een waarde op die met een kleiner serienummer is geassocieerd, en wordt dus v`o`or Op2 in de reeks π geplaatst. 4. Op1 is een MRread door proces i en Op2 een MRread door proces j. Voor deze situatie hebben we het onderling rapporteren van readers: zij t het serienummer van de waarde die door Op1 is opgeleverd. Omdat Op1 is afgelopen voordat Op2 begint, leest proces j uit Report[i,j] een serienummer van tenminste t, en het serienummer t0 van de opgeleverde waarde is dus tenminste t. Als t0 gelijk is aan t, zit Op2 toch achter Op1 in π omdat MRreads met dezelfde waarde in volgorde van be¨eindiging zijn opgenomen. Als t0 > t zit Op2 na de t0e MRwrite, dus achter Op1. ¤ Deze eigenschap van π impliceert dat we elke MR-operatie kunnen samentrekken in een punt dat binnen het interval ligt dat de operatie heeft geduurd. Het lijkt erop dat we ten opzichte van stelling 9.5 nogal wat hebben ingeleverd: we bewezen dat het schrijven door tenminste ´e´en reader noodzakelijk is, maar onze uiteindelijke oplossing
136
9 Wachtvrije implementaties met registers
Kader 9.5: Multiple-Writer snapshot objecten In sectie 9.4 nemen we steeds aan dat elk proces alleen schrijft in de eraan toegewezen geheugenlokatie (Fragment[i] voor proces i). Faith Fich vertelt op de Sofsem conferentie van 2005 in Liptovsk´ y J´an over een algemenere variant, waarbij een proces in elk van de locaties van het object mag schrijven. De hier beschreven beperktere versie noemt Fich de single-writer variant. Het algoritme voor de multiplewriter variant is vrijwel gelijk aan dat voor de single-writer versie, maar er is een uitbreiding van de serienummers nodig. Probeer zelf te bedenken waarom dat zo is (inclusief een concreet tegenvoorbeeld van hoe het anders mis kan gaan!) en probeer zo’n uitbreiding te bedenken.
laat alle readers schrijven voor alle readers. In totaal wordt de waarde van het register n(n+1) maal gedupliceerd opgeslagen! Door het bewijs van de genoemde stelling kritisch te bezien en verder uit te breiden kan men echter bewijzen dat een Ω(n2 )-voudige duplicatie noodzakelijk is in elke oplossing; zie Opgaven 9.3 en 9.5.
9.4
Het snapshotobject
Een belangrijk probleem in gedistribueerde berekeningen is het vastleggen van een consistente globale toestand [Fic05]. Het achtereenvolgens vastleggen van toestanden van alle componenten is niet correct, omdat de verkregen combinatie van deeltoestanden misschien nooit als globale toestand is voorgekomen. Denk bijvoorbeeld aan een systeem met meerdere sensoren of meters, waarvan waarden op willekeurige momenten kunnen veranderen, en waarvan we een totaaloverzicht van ´e´en moment willen bepalen. Een globaal consistente toestand is ook nuttig indien een berekening na een opgetreden fout herstart moet worden. Het snapshotobject heeft als toestand een vector van n waarden, en een proces kan middels een update(x) zijn eigen component in x veranderen en middels een scan de hele vector lezen. Dit wordt gebruikt in situaties waar je op ´e´en plaats informatie over de hele verzameling processen wilt bijhouden. Met een update kan een thread zijn eigen informatie wijzigen, en de scan moet dan een combinatie van waarden geven die op een bepaald moment tegelijk zijn voorgekomen. Het snapshotobject verschilt van een register in deze zin, dat de eenheid van schrijven kleiner is dan de eenheid van lezen. Bij een register wordt immers de gehele inhoud van het object in ´e´en keer gelezen, maar ook de gehele inhoud in ´e´en keer geschreven. Als elementaire oplossing kan men denken aan een rij van registers die samen de toestand implementeren: een update is dan een simpele write, en voor een scan worden de waarden achter elkaar gelezen. Maar net als programma 9.2 lijdt zo’n oplossing aan het probleem van
9.4 Het snapshotobject
Fragment[1]
137
Fragment[1].read
?
modificatie van Fragment[i]
Fragment[n] ?Scan
Figuur 9.6: Contractiepunt van een directe scan.
nieuw/oud inversie. Bovendien kan het achtereenvolgens lezen van de waarden worden onderbroken door updates, waardoor niet eens is gegarandeerd dat de opgeleverde combinatie ook ooit tegelijkertijd is voorgekomen. Het blokkeren van het object tijdens uitlezen is natuurlijk weer uit den boze. Kan dan de hele vector als een enkel register (van type V n ) worden ge¨ımplementeerd? Bij een update van proces i moeten de waarden van andere processen ongewijzigd blijven, maar het schrijven in een register overschrijft de gehele toestand. Dus moet proces i eerst de hele vector lezen, dan zijn eigen component wijzigen en de hele vector weer wegschrijven. Uiteraard geeft dit problemen met de consistentie wanneer tussen het lezen en terugschrijven van de vector een andere thread de vector leest of schrijft. De oplossing van Afek et al. [AAD+ 93] maakt uitsluitend gebruik van registers, en we hebben aan single writer registers genoeg. Net als in het vorige algoritme wordt elke waarde x (in de methode update(x)) opgeslagen samen met een serienummer, zodat een proces die deze waarde leest, kan vergelijken en zien of er sinds het vorige lezen van dit register iets veranderd is. De vector van n waarden wordt in n registers Fragment[i] opgeslagen, waarbij Fragment[i] wordt geschreven door proces i en door allen wordt gelezen. In de methode update(x) wordt ´e´enmaal de waarde x naar Fragment[i] geschreven: het moment waarop dit gebeurt is het contractiepunt van de update operatie. Op dit moment wordt de toestand van het ge¨ımplementeerde snapshot object veranderd. Het doel van de scan is nu om binnen een begrensd aantal operaties een rij waarden te vinden die tegelijk zijn voorgekomen binnen het tijdsinterval van de scan. Het tijdstip waarop die waarden tegelijk voorkwamen is dan het contractiepunt van de scan. Anders dan in het vorige programma zien we dat de control flow bij het scannen sterk wordt be¨ınvloed door de waarden die worden gelezen; het aantal instructies is echter begrensd zodat het programma toch wachtvrij is. Het idee achter een scan (uitgevoerd in de locale procedure makescan) is dat een proces de hele vector, component voor component, leest, en dan nog een keer leest: dit principe heet double collect. Als de tweede verkregen vector gelijk is (inclusief de serienummers!) aan de eerste, lag voor geen enkele i het contractiepunt van een update(x) tussen de twee inspecties van Fragment[i]; zie figuur 9.6. Dit impliceert dat de verkregen vector gelijk is aan de toestand van het object op het tijdstip tussen de twee lees-ronden, en dit moment wordt gekozen als het contractiepunt van een dergelijke scan. Als er wel tussentijds is geschreven moet een nieuwe scan-poging worden gewaagd, daarom bevat programma 9.8 een lus in de makescan procedure, waarin de double collect wordt herhaald. (De nieuwe collect in array b wordt dan vergeleken met de tweede collect van de ronde ervoor.) Nu zou het te simpel zijn om het double collecten net zo lang te herhalen totdat er
138
9 Wachtvrije implementaties met registers
........ ... ..
6
update(x)
6
Fragment[j] was onveranderd
... .. ........
update(x)
....... .. ...
Fragment[j] was veranderd
Figuur 9.7: Begin van update ligt binnen scan.
een keer geen tussentijdse update heeft plaatsgevonden; immers we moeten garanderen dat dit slechts begrensd vaak gebeurt! Hiertoe wordt een helpmechanisme ingebouwd ten behoeve van scannende threads die te vaak opnieuw moeten collecten wegens tussentijdse wijzigingen. Als een scanner voor de tweede maal constateert dat eenzelfde proces j tussentijds heeft geschreven (zie figuur 9.7), ligt het beginstuk van de tweede interfererende update binnen het interval van de scan. We laten nu elke update beginnen met het maken van een scan (ook weer via procedure makescan), die samen met de nieuwe waarde wordt opgeslagen. Een scan die voor de tweede maal een verandering in Fragment[j] constateert, levert de vector op die met Fragment[j] is opgeslagen. Het type van Fragment[j] is dan ook V × N × V n , en Fragment[j] heeft drie componenten: Fragment[j].v is de geschreven waarde, Fragment[j].sn is het serienummer en Fragment[j].s is de bijbehorende scan. De makescan procedure is door toevoeging van het helpmechanisme wachtvrij omdat hij termineert zodra wordt geconstateerd dat zeker proces tweemaal zijn Fragment heeft veranderd. Het maximale aantal slagen van de hoofdlus is dan n + 1 (na zoveel slagen moet een thread herhaald als geupdate j voorkomen) en hieruit volgt een bovengrens op het aantal instructies in de makescan. Beschouw nu een executie van het programma; we gaan elke scan en update een contractiepunt binnen zijn tijdsinterval geven en aantonen dat de semantiek van het object klopt. Zoals gezegd, het contractiepunt van een update(x) is het moment waarop x (samen met een serienummer en een scan) naar Fragment[j] wordt geschreven. Een uitvoering van makescan noemen we direct als de opgeleverde scan wordt verkregen doordat tweemaal dezelfde vector werd gelezen, en indirect als de scan uit een Fragment[j].s werd overgenomen. Lemma 9.7 Een directe makescan levert de toestand van het object op een tijdstip binnen de uitvoering van de makescan. Bewijs. Het betreffende tijdstip is een moment dat tussen de twee lees-ronden ligt, cf. figuur 9.6. Omdat Fragment[j] niet geschreven werd tussen de eerste en tweede lezing, is de waarde op het moment van die tweede lezing gelijk aan de waarde op het contractiepunt. ¤ Lemma 9.8 Een indirecte makescan levert de toestand van het object op zoals die is berekend in een andere makescan, die geheel binnen de eerste makescan ligt. Bewijs. De opgeleverde vector, zeg door i, is geconstrueerd met makescan door j en weggeschreven in een update. Dit wegschrijven gebeurde tussen twee achtereenvolgende inspecties van Fragment[j] door i, en de makescan van j vond dus voor de laatste inspectie plaats; zie figuur 9.7. Er was echter al eerder een verandering van Fragment[j] geconstateerd, en deze
9.4 Het snapshotobject
V,integer,V[n] integer
139
Fragment[n] seqNr[n]
// Gedeeld // seqNr[i] alleen
procedure makescan { boolean change[n] = (F,F,F, ...,F) boolean succeed = F for (j=1 ; j<=n ; j++) { a[j] = Fragment[j].read } while not succeed do { for (j=1 ; j<=n ; j++) { b[j] = Fragment[j].read }
voor i
// first collect
// second collect
if (exists j: a[j].sn < b[j].sn) // { if change[j] // { sc = b[j].s ; succeed = T } // else { change[j] = T a = b } } else { for (j=1 ; j<=n ; j++) { sc[j] = b[j].v } // succeed = T }
update door j tweede update indirecte scan
directe scan
} return sc } scan door proces i: { return makescan } update(x) door proces i: { sc = makescan seqNr[i] ++ Fragment[i].write((x,seqNr[i],sc)) } Programma 9.8: Implementatie van snapshotobject
eerdere update van j overlapte ook al met de makescan van i. De makescan waarvan uiteindelijk het resultaat is overgenomen is daarna begonnen, en ligt dus geheel binnen de makescan van i. ¤ Aannemende dat de makescan van j de toestand oplevert op een tijdstip binnen zijn uitvoering, volgt hetzelfde voor i, immers de makescan van j ligt geheel binnen die van i. Het bewijs
140
9 Wachtvrije implementaties met registers
is nu formeel af te maken met een inductie over de nesting-structuur van makescan aanroepen: die nesting is eindig diep omdat er maar n processen tegelijk bezig kunnen zijn. De basisstap (een directe makescan) is bewezen in lemma 9.7, en de inductie-stap in lemma 9.8.
Samenvatting en conclusies In dit hoofdstuk is een begin gemaakt met de behandeling van wachtvrije synchronisatie. Doel hierbij is het implementeren van objecten, waarbij een thread nooit hoeft te wachten in een methode. De instructies van verschillende threads worden dan willekeurig ge¨ınterleaved. Bij wachtvrije implementaties is vaak sprake van onderling helpen door threads. Als een thread signaleert dat een andere thread aan een operatie is begonnen, maakt hij hem af zodat de andere threads het resultaat ervan ook kunnen zien. Bij het bewijzen van de correctheid van de implementaties wordt vaak geredeneerd over het overlappen of juist voorafgaan van operaties. Er is speciale aandacht nodig voor het bewijzen van een bovengrens op het aantal stappen dat in een methode wordt gedaan. Registers hebben per methode slechts een richting van informatieuitwisseling. In een read verkrijgt een proces toestandsinformatie, maar de toestand wijzigt niet. In een write wijzigt de objecttoestand, maar het proces verkrijgt geen informatie over de toestand zoals die was. Het snapshotobject dat in dit hoofdstuk met registers werd ge¨ımplementeerd vertoont een ingewikkelder gedrag, maar behoudt wel deze registerachtige scheiding tussen lezen en schrijven.
Opgaven bij hoofdstuk 9 Opgave 9.1 Wacht-vrije implementatie. (Uit het tentamen van mei 2002.) Waaruit bestaat een wacht-vrije implementatie van class B en hoe komt hierin de eis van wacht-vrijheid tot uiting? Laat zien dat de relatie |= tussen classes transitief is. Opgave 9.2 Implementeer een 2-consensusobject met een test-and-set object. Opgave 9.3 Breid het bewijs van stelling 9.5 uit om te laten zien dat het aantal SR-registers in gebruik voor communicatie tussen readers onderling, tenminste 12 n(n − 1) bedraagt. Opgave 9.4 Het is niet zo gemakkelijk om voor programma 9.4 een contractiepunt van de MRwrite aan te geven. Construeer een executie waarin de writer een 1 schrijft, die door reader 1 wordt gezien, waarna er een volledige read door reader 2 plaatsvindt die nog de oude waarde 0 oplevert. Laat door keuze van contractiepunten zien dat deze executie aan atomiciteit voldoet. Laat ook zien dat het contractiepunt van de MRwrite wordt vervroegd als reader 1 zijn operatie sneller afwikkelt. Opgave 9.5 Verander programma 9.4 zo dat minder SR-registers worden gebruikt. Kun je het aantal uit opgave 9.3 halen?
Opgaven bij hoofdstuk 9
Opgave 9.6 Multiple-read registers. (Uit het tentamen van januari 2006.) In de implementatie van een Multiple-Reader register uit Single-Reader registers, werden n2 Report registers gebruikt waarin readers elkaar informeren over de waarde die ze opgeleverd hebben. In de oplossing hiernaast wordt het aantal registers ongeveer gehalveerd: een reader schrijft alleen voor hoger genummerde readers, en een reader leest alleen van lager genummerde readers. Beargumenteer dat inversies zijn uitgesloten: als een read-operatie r1 is afgelopen voordat read-operatie r2 begint, dan is de waarde die r2 oplevert, ten minste zo recent als die welke r1 oplevert.
141
MRwrite(x): { seqNr ++ for (i=1 ; i <= n ; i++) { Val[i].SRwrite((x,seqNr)) } } MRread voor proces i: { (v,s) = Val[i].SRread for (j=1 ; j < i ; j++) { (w,t) = Report[j,i].SRread if (t>s) then v,s = w,t } for (j=i+1 ; j <= n ; j++) { Report[i,j].SRwrite((v,s)) } return v }
Opgave 9.7 Wacht-vrij Snapshot Object. (Uit het tentamen van mei 2000.) (a) Beschrijf de toestandsruimte en de methoden van een Snapshot object. In de implementatie gebruikten we een procedure makescan die onderscheid maakte tussen een directe en een indirecte scan. (b) Wanneer leidt een double collect tot een directe scan en waarom is de opgeleverde waarde dan correct? Opgave 9.8 Snapshot object. (Uit het tentamen van mei 2001.) (a) Wat zijn de methoden van een snapshot object (namen en semantiek). (b) Leg uit hoe (in de behandelde implementatie) een double collect kan leiden tot een directe scan en waarom het opgeleverde resultaat correct is. (c) Leg ook uit hoe threads elkaar helpen om te komen tot een indirecte scan. Opgave 9.9 Stel dat we programma 9.8 vereenvoudigen door de serienummers weg te laten, en de vergelijking tussen de first en second collect te doen met de test: if (exists j: a[j].v != b[j].v) Laat ten eerste zien dat het mogelijk is dat er tussen de twee collects iets is veranderd aan het object maar dat dit niet wordt gemerkt. Probeer dan dit verschijnsel zo in een executie in te bedden dat er een incorrecte uitkomst ontstaat (er wordt een vector opgeleverd die nooit de toestand is geweest). Opgave 9.10 Wat is het maximale aantal register-operaties (reads) in een makescan in programma 9.8? Opgave 9.11 Wachtvrije counter. Het counter object heeft een integer toestand, initieel 0, en een methode inc die de waarde met 1 verhoogt en een show die de waarde oplevert. Dit is een wachtvrije implementatie van een counter voor 2 processen:
142
9 Wachtvrije implementaties met registers
object counter var s[2] : register type integer, initieel 0 inc voor thread i: t = s[i].read t = t+1 s[i].write(t)
show voor thread i: t1 = s[1].read t2 = s[2].read return t1+t2
(a) Waarom is dit een wachtvrije implementatie met registers? (b) Bewijs dat de methodes atomair zijn. (Hint: (1) definieer de toestand van de counter in termen van s[1] en s[2] en (2) kies als contractiepunt voor de inc het moment van schrijven in s[i].) (c) Bewijs (na lezing van hoofdstuk 10), dat het niet mogelijk is om met een counter 2Consensus te implementeren.
Hoofdstuk 10
Wachtvrije consensus
Met de definite van diverse objecttypen komt als vraagstelling naar voren: gegeven objecten van type A, is het mogelijk hiermee objecten van type B te implementeren. (Onder implementatie verstaan we in dit hoofdstuk altijd een wachtvrije implementatie.) Het zal blijken dat consensusobjecten een zeer centrale rol spelen bij het beantwoorden van deze vragen. In dit hoofdstuk zullen we enkele voorbeelden zien, waarin consensus wordt gebruikt om de onmogelijkheid van een implementatie aan te tonen. Er wordt bijvoorbeeld aangetoond dat een object B wel, en een object A niet in staat is om consensus te implementeren, waaruit volgt dat , B niet implementeert. Deze redenering is alleen bruikbaar voor deterministische algoritmen, want, zoals we zullen zien in sectie 10.4, kan consensus gerandomiseerd met alleen registers worden ge¨ımplementeerd.
10.1
Consensusobject met registers
We herinneren ons dat een consensusobject slechts ´e´en methode, submit(x) heeft, en elke submit levert de invoer van de eerste submit op. De werking van een consensusobject is weergegeven als programma 10.1. Uiteraard is dit programma niet bruikbaar als implementatie omdat bij meerdere processen de werking door interleaving van statements wordt verstoord. Een consensusobject dat door n processen kan worden aangesproken noemen we een n-consensus object.
register toestand
V + {@}
init @
submit(x): { if (toestand == @) {toestand = x} return toestand } Programma 10.1: Werking van een consensusobject. 143
144
10 Wachtvrije consensus
Natuurlijk kun je met registers een consensusobject maken dat werkt voor ´e´en enkel proces: je hebt dan van concurrency geen last en programma 10.1 kan als implementatie worden gebruikt. We tonen nu aan, dat een consensus object voor meer dan ´e´en proces niet met registers kan worden ge¨ımplementeerd. Stelling 10.1 Er bestaat geen implementatie van 2-consensus met registers. Bewijs. Het bewijs is in zekere zin een verkorte en uitgeklede versie van het bewijs van Fischer, Lynch en Paterson; voor een uitleg van het zeer centrale begrip valentie verwijzen we naar sectie 6.3.2. Stel dat er een wacht-vrije implementatie van 2-consensus bestaat. Een configuratie is in deze context: de toestanden van de gedeelde objecten en de processen (inclusief program counters). In een configuratie C zijn diverse stappen mogelijk doordat de volgende instructie van verschillende processen afkomstig kan zijn; met pi (C) bedoelen we de configuratie die verkregen wordt als vanuit C proces pi ´e´en stap doet. De eigenschappen van het wachtvrije rekenmodel kunnen nu worden vertaald naar eigenschappen van de executieboom van de veronderstelde oplossing. Propositie 10.2 Vanuit elke configuratie C bestaat er voor elk proces pi een reeks van stappen van uitsluitend pi , waarbij pi zijn submit operatie afmaakt. Bewijs. Het kan gebeuren dat het systeem in configuratie C is en dan alle processen behalve pi traag gaan werken. Er worden dan een tijdje lang alleen maar stappen van pi gedaan, en de wacht-vrijheid van de oplossing dwingt af dat pi zijn submit voltooit. ¤ De ge¨eiste wachtvrijheid van de oplossing staat ons toe, conclusies te trekken als twee configuraties er, vanuit het “oogpunt” van een enkel proces, hetzelfde uitzien: Definitie 10.3 Configuraties C1 en C2 zijn i-gelijk, notatie C1 ≈i C2 , als de toestand van de gedeelde objecten en van pi in C1 en C2 overeen komen. Configuraties C1 en C2 verschillen slechts in de toestand van processen pj anders dan pi , en de wachtvrijheid verbiedt pi afhankelijk te zijn van het verkrijgen van informatie uit proces pj . Daarom mag met propositie 10.2 een conclusie getrokken worden over de valentie van i-gelijke configuraties. (Het lemma gaat over univalente configuraties; het is wel mogelijk dat van i-gelijke configuraties de ene univalent is en de andere bivalent. Dit maakt het mogelijk randomiserende oplossingen voor consensus te maken, maar hierop gaan we niet in.) Lemma 10.4 Zij C1 en C2 univalente configuraties en er is een i zdd. C1 ≈i C2 ; dan is de valentie van C1 en C2 gelijk, dwz C1 is v-valent dan en slechts dan als C2 v-valent is. Bewijs. Stel het systeem zit in configuratie C1 ; de wacht-vrijheid dwingt af dat er een reeks van stappen, slechts van pi , is waarmee pi zijn operatie afmaakt en een resultaat krijgt (propositie 10.2). Omdat C1 v-valent is, is dit resultaat v. Maar dezelfde reeks van stappen van pi is geheel toepasbaar in C2 , immers, in C2 zit pi in dezelfde toestand, en pi “ziet” dezelfde waarde van alle gedeelde objecten. ¤ Net als in sectie 6.3 construeren we vanuit een bivalente configuratie een oneindige run van bivalente configuraties, maar omdat de eisen op de oplossing hier wat sterker zijn, hebben we het bij de bewijsvoering gemakkelijker. Een bivalente initi¨ele configuratie is bijvoorbeeld gemakkelijk gevonden. Zij C0 de configuratie die ontstaat als p1 een submit(0) start en p2 een
10.2 Consensus met test-and-set, queue en compare-and-swap
145
submit(1), maar er is nog geen stap gezet. Bewering: C0 is bivalent. Omdat de return-waarde van elke submit de invoer van de eerste submit is, zal, als p1 vanuit C0 voldoende stappen doet de waarde 0 afgedwongen worden en als p2 voldoende stappen doet de waarde 1. Als C een bivalente configuratie is en pi (C) is univalent noemen we pi kritiek in C; dit zegt feitelijk dat pi de mogelijkheid heeft een beslissing af te dwingen in de (vooralsnog onbepaalde) configuratie C. Een cruciaal punt in het verhaal is dat de processen niet alle kritiek zijn: Lemma 10.5 Als C bivalent is, is tenminste ´e´en proces niet kritiek. Bewijs. Als alle processen kritiek zijn is pi (C) voor elke i univalent, maar omdat C zelf bivalent is moeten zich onder deze configuraties zowel 0- als 1-valente configuraties bevinden (opgave 6.11). Zij pi (C) 0-valent, en pj (C) 1-valent. Wat voor stappen kunnen er vanuit C door processen pi en pj gezet worden? • Als ´e´en ervan geen register gebruikt of ze gebruiken verschillende registers, dan geldt pi (pj (C)) = pj (pi (C)), en dit is strijdig met de verschillende valentie van pi (C) en pj (C). • Hetzelfde geldt als beide processen lezen uit hetzelfde register. • Het overblijvend geval is waar ´e´en proces (zeg pi ) schrijft in een register dat door pj wordt gebruikt (voor lezen of schrijven). Echter, wie schrijft in een register maakt de voorafgaande actie op dat register onzichtbaar: de toestand van het register is in pi (pj (C)) gelijk aan die in pi (C). Omdat ook de interne toestand van pi gelijk is en de overige gedeelde objecten u ¨berhaupt niet veranderd zijn in deze stappen, geldt pi (pj (C)) ≈i pi (C), hetgeen met lemma 10.4 tegenspreekt dat pj (C) 1-valent is. ¤ Vanuit configuratie C0 kan het systeem willekeurig lang bivalent blijven, namelijk als steeds een stap van een niet-kritiek proces wordt uitgevoerd. Dit is een tegenspraak met de wacht-vrijheid en bewijst stelling 10.1. ¤
10.2
Consensus met test-and-set, queue en compare-and-swap
Als we de mogelijkheid onderzoeken om consensus te implementeren met andere objecten uit hoofdstuk 9, blijkt al snel dat sommige tot meer in staat zijn dan registers. In sectie 10.2.1 zien we dat test-and-set wel 2-consensus, maar geen 3-consensus kan implementeren. Daarna nemen we aan dat objecten van type queue aanwezig zijn en onderzoeken de mogelijkheden om daarmee consensusobjecten te maken. In sectie 10.2.4 zullen we zien dat er conclusies te trekken zijn die verder gaan dan die over consensusobjecten. 10.2.1
Consensus met test-and-set
Programma 10.2 implementeert 2-consensus met een test-and-set. Initi¨eel bevat de test-andset arbiter een 0, en in een submit(v) schrijft een proces eerst zijn waarde op (in register proposal[i]) en doet een TaS. Komt daar 0 uit, dan was het proces de eerste die een TaS deed en daarmee “wint” zijn invoer de strijd om de opgeleverde waarde te worden. Leverde de TaS 1 op, dan was het andere proces eerder en wordt diens invoer overgenomen (als er twee processen, 1 en 2 zijn, is 3 − i het nummer van het andere proces).
146
10 Wachtvrije consensus
register proposal[2] : testandset arbiter :
init 0
// schrijf invoer weg // wie was eerst?
submit(v) voor proces i: { proposal[i] = v test = arbiter.TaS if (test == 1) { return proposal[3-i] } else { return proposal[i] } } Programma 10.2: Implementatie van 2-consensus met test-and-set
Belangrijk in de werking is de eigenschap van de TaS methode die atomair informatie over de toestand geeft en die wijzigt. Hierdoor kan een thread zien of hij de eerste was die een operatie uitvoerde, of niet, en dit blijkt voldoende voor 2-consensus. Je kunt een soortgelijke truuk uithalen met een queue (sectie 10.2.2) of een stack object. Willen we programma 10.2 uitbreiden naar 3 processen, en dat willen we, dan stuiten we op een probleem. Een proces dat 1 uit de arbiter krijgt weet, dat het niet als eerste was, maar weet vervolgens niet welk van de andere twee processen wel als eerste was. Dit is niet op te lossen door een proces, na de TaS, naar een shared object te laten schrijven of het al dan niet de consensus “gewonnen” heeft. Tussen de TaS en die schrijfactie kan willekeurig lang verlopen waardoor de andere processen niet wachtvrij verder kunnen. Je denkt misschien dat het nu tijd is om een list te verzinnen, maar geen list is slim genoeg: de test-and-set is onvoldoende krachtig om 3-consensus te implementeren, wat we gaan bewijzen met een uitbreiding van stelling 10.1. Hoewel de constructie in programma 10.2 alleen de TaS methode van test-and-set gebruikt, moeten we in het bewijs natuurlijk over alle mogelijkheden van het object redeneren, en ook de reset bekijken. Stelling 10.6 Er bestaat geen imlementatie van 3-consensus met test-and-set. Bewijs. Definitie 10.3 en lemma 10.4 zijn ook in een systeem met drie processen van toepassing, en op dezelfde manier als in het bewijs van stelling 10.1 vinden we een bivalente beginconfiguratie. Slechts lemma 10.5 moet voor het mogelijk gebruik van test-and-set worden uitgebreid. Lemma 10.7 Als C bivalent is, is tenminste ´e´en proces niet kritiek. Bewijs. Als alle processen kritiek zijn is pi (C) voor elke i univalent, maar omdat C zelf bivalent is moeten zich onder deze configuraties zowel 0- als 1-valente configuraties bevinden. Zij pi (C) 0-valent, pj (C) 1-valent, en pk het derde proces (ongelijk pi en pj ). Wat voor stappen kunnen er vanuit C door processen pi en pj gezet worden? • Als ze verschillende objecten gebruiken of hetzelfde register volgt een tegenspraak als in het bewijs van lemma 10.5; in de andere gevallen gebruiken pi en pj dezelfde test-and-set T.
10.2 Consensus met test-and-set, queue en compare-and-swap
147
• Als pi en pj beide een T.TaS doen: De TaS methode heeft geen argumenten, en het effect van een TaS operatie door pi is voor pk niet te onderscheiden van een operatie door pj . Er geldt pi (C) ≈k pj (C) (“pk kan niet zien wie er geTaSt heeft”) en een tegenspraak volgt met lemma 10.4. (Merk op dat niet geldt pi (C) ≈i pj (C) en ook niet pi (C) ≈j pj (C), want pi en pj zien zelf wel verschil tussen een configuratie waarin ze al wel, of nog niet de TaS hebben gedaan.) • Als pi en pj beide een T.reset doen: De reset methode heeft geen argumenten, en het effect van een reset operatie door pi is voor pk niet te onderscheiden van een operatie door pj . Er geldt pi (C) ≈k pj (C) (“pk kan niet zien wie er gereset heeft”) en een tegenspraak volgt met lemma 10.4. • Als pi een T.TaS doet en pj een T.reset: In configuratie pi (C) kan pj nog altijd de reset doen, wat leidt tot een configuratie pj (pi (C)), die volgens de aanname (dat pi (C) 0-valent is), 0-valent is. De reset methode resulteert altijd in waarde 0 van het object, ongeacht de waarde die het daarvoor had, met andere woorden, de reset door pj , in configuratie C of pi (C), verbergt voor pk of de TaS door pi heeft plaatsgevonden. Er geldt pj (pi (C)) ≈k pj (C) (“pk kan niet zien of pj geTaSt heeft”) en een tegenspraak volgt met lemma 10.4. (Het geval dat pi een T.reset doet en pj een T.TaS verloopt analoog.) ¤ Net als in het bewijs van stelling 10.1 is hiermee bewezen dat het systeem willekeurig lang bivalent kan blijven, hetgeen het bewijs van stelling 10.8 voltooit. ¤ 10.2.2
Queue implementeert 2-consensus
Programma 10.3 implementeert 2-consensus met een queue, op een manier vergelijkbaar met programma 10.2. Initi¨eel bevat de queue ´e´en getal (1), en in een submit(v) schrijft een proces eerst zijn waarde op en probeert dan uit de queue te lezen. Komt er iets uit, dan was het proces de eerste die uit de queue las en daarmee “wint” zijn invoer de strijd om de opgeleverde waarde te worden. Leverde de queue @ op, dan was het andere proces eerder en wordt diens invoer overgenomen. Net als de TaS methode van test-and-set, kan de deq methode atomair informatie over de toestand geven en die wijzigen. Hierdoor gebruik je alleen maar van de queue dat een thread kan zien of hij de eerste was die er een operatie op uitvoerde of niet. Je kunt een soortgelijke truuk uithalen met een zwakke electie of een stack object. 10.2.3
Queue implementeert geen 3-consensus
Willen we programma 10.3 uitbreiden naar 3 processen, en dat willen we, dan stuiten we op een probleem. Net als de test-and-set, kan de queue een proces wel laten weten of hij de eerste was met een bepaalde operatie of niet, maar niet welk proces dan eventueel wel eerst was. Ook van de queue gaan we bewijzen dat hij onvoldoende krachtig is om 3-consensus te implementeren, weer met een uitbreiding van stelling 10.1. Het basisidee van het bewijs is hetzelfde, alleen er moet natuurlijk met de specifieke eigenschappen van de queue worden geredeneerd en daardoor pakt ´e´en van de te behandelen gevallen veel ingewikkelder uit. Herinner, dat er bij een queue geen front methode wordt verondersteld.
148
10 Wachtvrije consensus
register proposal[2] : queue arbiter :
init <1>
// schrijf invoer weg // wie was eerst?
submit(v) voor proces i: { proposal[i] = v test = arbiter.deq if (test == @) { return proposal[3-i] } else { return proposal[i] } } Programma 10.3: Implementatie van 2-consensus met queue
Stelling 10.8 Er bestaat geen imlementatie van 3-consensus met queues. Bewijs. Definitie 10.3 en lemma 10.4 zijn ook in een systeem met drie processen van toepassing, en op dezelfde manier als in het bewijs van stelling 10.1 vinden we een bivalente beginconfiguratie. Slechts lemma 10.5 moet voor het mogelijk gebruik van queues worden opgerekt. Lemma 10.9 Als C bivalent is, is tenminste ´e´en proces niet kritiek. Bewijs. Als alle processen kritiek zijn is pi (C) voor elke i univalent, maar omdat C zelf bivalent is moeten zich onder deze configuraties zowel 0- als 1-valente configuraties bevinden. Zij pi (C) 0-valent, pj (C) 1-valent, en pk het derde proces (ongelijk pi en pj ). Wat voor stappen kunnen er vanuit C door processen pi en pj gezet worden? • Als ze verschillende objecten gebruiken of hetzelfde register volgt een tegenspraak als in het bewijs van lemma 10.5; in de andere gevallen gebruiken pi en pj dezelfde queue Q. • Als pi en pj beide een Q.deq doen geldt pi (C) ≈k pj (C) (“pk kan niet zien wie er eerst gedequeued heeft”) en een tegenspraak volgt met lemma 10.4. • Als pi een Q.enq(x) doet en pj een Q.deq en Q is niet leeg in C, dan is pj (pi (C)) = pi (pj (C)) en dit is in tegenspraak met de verschillende validiteit van pi (C) en pj (C). • Als pi een Q.enq(x) doet en pj een Q.deq en Q is leeg in C, zal pj het wel merken of pi eerst een Q.enq(x) uitvoert, maw. in pj (pi (C)) heeft pj een andere toestand dan in pj (C); pj kreeg in het eerste geval @ retour. Echter, voor pk is niet te zien of pj al dan niet gelezen heeft voor het enqueuen door pi omdat een Q.deq die @ oplevert de toestand van Q niet verandert. Er geldt in dit geval pi (C) ≈k pi (pj (C)) en dit is wegens lemma 10.4 weer in tegenspraak met de verschillende valenties van pi (C) en pj (C). • Het geval dat pi een Q.deq doet en pj een Q.enq(x) is analoog aan de vorige twee gevallen. • Het laatste geval is waar pi een Q.enq(a) doet en pj een Q.enq(b); zie figuur 10.4. In configuratie C staat dus zowel pi als pj op het punt om een Q.enq te doen (van waarde a, respectievelijk b). Merk op dat het voor de locale toestand van pi en pj niet uitmaakt
10.2 Consensus met test-and-set, queue en compare-and-swap
149
C:b pi (C) : 0
ª
R
pj (C) : 1
R C1 : 1 C0 : 0 . ª .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . C10 = σ 0 (C1 ) : 1 C00 = σ 0 (C0 ) : 0 .... . . . . ... ... Q.deq . . . . ... ... .? ... ... . . . . . . . .. ... ... .. ... D1 = τ 0 (C10 ) : 1 D0 = τ 0 (C00 ) : 0 .. .. .. .. Q.deq ª ? .. ? .. . . .. . . . . ... ? σ(C0 ) : 0 ? ... . . .. p (p (D )) : 0 p1 (p2 (D1 )) : 1 τ (C00 ) 1 2 0
Figuur 10.4: Processen pi en pj doen een Q.enq().
welk van de twee processen het eerst een stap doet, want bij een Q.enq verkrijgt een proces geen informatie uit de queue. Toch hangt de valentie volgens de aanname af van de volgorde waarin de processen hun Q.enq uitvoeren: C0 = pj (pi (C)) is 0-valent en C1 = pi (pj (C)) is 1-valent, en deze twee configuraties verschillen slechts in de volgorde waarin a en b in de queue staan. De rest van het bewijst preciseert de volgende intu¨ıtie. Het verschil tussen de twee configuraties zit alleen in de volgorde van slechts twee elementen in de queue. Het uitlezen van informatie uit een queue is “destructief”, dwz. dat een proces alleen iets aan de queue kan zien door het eruit te halen (maar vergelijk opgave 10.6!). Daarom kunnen slechts twee threads het verschil tussen de twee configuraties “direct” waarnemen. En ze zijn met z’n drie¨en, maar het derde proces mag er niet van afhankelijk zijn dat ´e´en van de andere twee hem vertelt wat hij uit de queue heeft gelezen, dit is nl. strijdig met de wachtvrijheid. Daarom construeren we een executie waarin twee processen de queue uitlezen; deze reeks is toepasbaar in C0 en C1 , en levert twee configuraties die voor het derde proces gelijk zijn. Zij ρ de inhoud van Q in configuratie C. Omdat het systeem wachtvrij is, is er (volgens propositie 10.2) vanuit C0 een reeks σ van stappen van alleen p1 waarin p1 iets retourneert; omdat C0 0-valent is, is dit de waarde 0. Omdat dezelfde reeks van stappen niet toepasbaar is vanuit C1 (die is immers 1-valent en van daaruit is geen 0-beslissing mogelijk) wordt in σ op z’n minst de waarde a door p0 gelezen. Nu houden we p1 even tegen op het moment dat hij die Q.deq wil doen: σ 0 is de prefix van σ tot aan die stap en C00 = σ 0 (C0 ). Merk op dat de reeks σ 0 ook in C1 toepasbaar is (het verschil in queue-toestand wordt pas geobserveerd als a of b uit de queue gelezen wordt), en zij
150
10 Wachtvrije consensus
C10 = σ 0 (C1 ). Omdat het systeem wacht-vrij is, is er vanuit C00 een reeks τ van stappen van alleen p2 waarin p2 iets retourneert; omdat C00 0-valent is, is dit de waarde 0. Omdat dezelfde reeks van stappen niet toepasbaar is vanuit C10 (die is immers 1-valent en van daaruit is geen 0-beslissing mogelijk) wordt in τ op z’n minst ´e´enmaal uit de queue gelezen. Nu houden we p2 even tegen op het moment dat hij dat wil doen: τ 0 is de langste prefix van τ waarin p2 geen Q.deq uitvoert. Merk op dat de reeks τ 0 ook in C10 toepasbaar is. Zij nu D0 = τ 0 (C00 ) en D1 = τ 0 (C10 ). Zowel in D0 als in D1 staan zowel p1 als p2 op het punt een Q.deq uit te voeren, het enige verschil tussen D0 en D1 is dat in de ene Q begint met ab en in de andere met ba, en de valentie verschilt. Als nu beide processen hun Q.deq uitvoeren, is er voor p3 geen verschil meer te observeren: p1 (p2 (D0 )) ≈3 p1 (p2 (D1 )), hetgeen met lemma 10.4 een tegenspraak is met de verschillende valentie van D0 en D1 . ¤ Net als in het bewijs van stelling 10.1 is hiermee bewezen dat het systeem willekeurig lang bivalent kan blijven, hetgeen het bewijs van stelling 10.8 voltooit. ¤ 10.2.4
Het consensusgetal
De resultaten tot nu toe hadden allemaal betrekking op consensus, maar we kunnen nu concluderen dat registers onvoldoende sterk zijn om een queue te implementeren. Corollarium 10.10 Er bestaat geen implementatie van een queue met registers. Bewijs. Omdat de queue 2-consensus implementeert (sectie 10.2.2) en implementatie transitief is (lemma 9.3) zou een dergelijke implementatie bewijzen dat registers 2-consensus implementeren, wat in tegenpraak is met stelling 10.1. ¤ We herinneren ons dat type queue het klassieke producer-consumer probleem beschrijft; we hebben net bewezen dat in een systeem dat alleen registers biedt, dit probleem niet wachtvrij op te lossen is. Het wordt duidelijk dat we een gereedschap in handen hebben om het niet bestaan van een implementatie te bewijzen: als object A voor meer processen consensus kan implementeren dan object B, dan bestaat er geen implementatie van A met B. Definitie 10.11 Het consensusgetal van class A, notatie CN (A), is het hoogste aantal n waarvoor er een implementatie van n-consensus met A bestaat (∞ als zo’n implementatie voor alle n bestaat). Stelling 10.12 Als CN (A) > CN (B) dan B 6|= A in een systeem met meer dan CN (B) processen. Het bewijs (met transitiviteit van |=) laten we graag aan de lezer over; we vatten de reeds bekende consensusgetallen samen in de volgende stelling. Stelling 10.13 Registers hebben consensusgetal 1, Queues hebben consensusgetal 2. Het is een erg populaire sport om van allerlei obscure typen het consensusgetal te achterhalen. Men kan zich na het bestuderen van deze sectie wel voorstellen dat een implementatie van n-consensus met zeker object nog redelijk overzichtelijk is. Het bewijs dat (n + 1)-consensus onmogelijk is, is daarentegen vaak behoorlijk gecompliceerd; stelling 10.8 is hier nog maar een simpel voorbeeld van! Een kleine greep uit wat er bekend is:
10.3 Wachtvrije hi¨erarchie¨en
151
compare-and-swap toestand:
init @
submit(v): { w = toestand.CaS(@,v) if (w == @) { return v } else { return w } } Programma 10.5: Consensus met compare-and-swap.
• Het consensusgetal van test-and-set en stack is 2. • Voor elk natuurlijk getal n bestaat er een object met consensusgetal n. 10.2.5
Consensusobject met compare-and-swap
De compare-and-swap blijkt bijzonder krachtig: hij heeft consensusgetal oneindig, omdat hij voor elke n, n-Consensus implementeert en wel volgens programma 10.5. Voor het implementeren van een consensusobject dat waarden uit verzameling V kan verwerken, gebruiken we een compare-and-swap object met toestandsruimte V ∪ {@}, waarbij @ betekent dat er nog geen waarde is beslist. De CaS-methode van compare-and-swap staat toe dat een proces atomair bekijkt of de toestand nog @ is, en in dat geval de waarde vervangt door zijn invoer.
10.3
Wachtvrije hi¨ erarchie¨ en
Een klassificatie van wachtvrije objecten in sterke en minder sterke objecten volgens een scherp gedefini¨eerd criterium noemen we een wachtvrije hi¨erarchie. In dit hoofdstuk baseerden we de indeling op de mogelijkheid, met het object deterministisch het consensus probleem op te lossen; daarom heet deze indeling de consensushi¨erarchie. Hij werd voorgesteld door Herlihy in 1991 [Her91], maar er zijn ook andere mogelijk. De consensushi¨erarchie is heel geschikt om individuele classes te vergelijken; er geldt namelijk: • Als CN (A) < CN (B), dan A 6|= B. Dit is stelling 10.12; de conclusie refereert natuurlijk aan deterministische implementaties. • Object A implementeert (deterministisch) alle classes, dus ook consensus, in elk systeem met hoogstens CN (A) processen. Dit wordt bewezen in hoofdstuk 11. Voor het vergelijken van combinaties van classen is de consensushi¨erarchie niet geschikt. Er zijn diverse voorbeelden bekend van typen A1 en A2 , beide met consensusgetal k, die in combinatie met elkaar een class met consensusgetal > k implementeren. Ook wanneer naar randomiserende algoritmen wordt gekeken, is de hi¨erarchie niet geschikt, omdat er dan geen verschil meer is tussen de consensus-klassen. In sectie 10.4 laten we zien
152
10 Wachtvrije consensus
dat met randomisering, registers in staat zijn consensus te implementeren voor willekeurig veel processen. En mocht je denken dat met twee trema’s in ´e´en woord het maximum van de Nederlandse taal wel bereikt is: het is mogelijk op een abstracter niveau de verschillende hi¨erarchie¨en te vergelijken en te klassificeren in een hi¨erarchie¨enhi¨erarchie (waarvan er weer meerdere zijn trouwens).
10.4
Consensus met randomisering
Net als in het berichten-model is randomisering voldoende om het onmogelijkheidsresultaat voor Consensus te doorbreken. Programma 10.6 toont een algoritme van Buhrman et al. [BPSV06], dat Consensus bereikt voor een willekeurig aantal processen; het gebruikt randomisering en geen andere gedeelde objecten dan (multiple-reader, multiple writer) registers. Een proces dat v submit, begint aan ronde 1 met waarde v. We zeggen dat waarde v ronde p heeft bereikt, als een proces het register bereik[v, p] op True heeft gezet. Een proces dat (met v) ronde p bereikt zet dit register, en kijkt dan, welke ronde al is bereikt door de andere waarde (1 − v). Als de andere waarde de volgende ronde (p + 1) al heeft bereikt, wordt een overstap overwogen; als de andere waarde ook ronde p heeft bereikt wordt een random keuze gedaan; als de andere waarde pas in ronde p − 1 is zal het proces waarde v houden, als zelfs ronde p − 1 nog niet is gehaald, wordt op v beslist. Een overwogen overstap wordt geannuleerd als de eigen waarde inmiddels ronde p + 1 heeft bereikt. Merk allereerst op, dat er geen “gaten” in de bereikte waarden van v vallen: bereik[v,p] kan alleen True worden als bereik[v,p-1] dat al is. Noemen we het front voor v de hoogste p waarvoor bereik[v,p] True is, dan kunnen de fronten dus steeds met ´e´en positie tegelijk opschuiven, waarbij ze elkaar willekeurig vaak in kunnen halen. Een belangrijke observatie voor de geldigheid is dat het front voor v alleen positief wordt als minstens een proces v submit. Belangrijk voor de overeenstemming is dat als het front voor v ooit twee posities voorkomt op dat van 1 − v, het front van 1 − v nog hoogstens 1 positie wint. Lemma 10.14 Als op tijdstip t, bereik[v,p+1] True is en bereik[1-v,p] False, dan blijft bereik[1-v,p+1] daarna altijd False. Bewijs. Een proces dat na t met waarde 1 − v aan ronde p begint, kan bereik[1-v,p] nog op True zetten, maar de constatering dat op dat moment bereik[v,p+1] al True is zal dit proces doen overwegen, over te stappen naar v. Die overstap wordt inderdaad gemaakt omdat bij de laatste test, bereik[1-v,p+1] nog steeds op False staat. ¤ Uit lemma 10.14 volgt dat als het front voor v twee plaatsen voorligt, alle processen daarna met die waarde verder gaan en, op z’n laatst in ronde p+2, op v beslissen. De fronten schuiven atomair op, maar niet tegelijk en daarom ligt er telkens een van de waarden ´e´en positie voor. Het voorliggende front kan zijn voorsprong vergroten tot twee met een probabilistisch “duwtje in de rug”, dat bestaat uit een uniforme random keuze in ´e´en ronde. Terminatie volgt uit lemma 10.15, dat impliceert dat elke ronde een kans van minstens 1/2n heeft om de situatie uit het vorige lemma te realiseren. Voor willekeurige ronde p is hierin v de waarde die het eerst ronde p bereikt. Lemma 10.15 Als (1) op tijdstip t, bereik[v,p] True is en bereik[1-v,p] False, en (2) alle random keuzes in ronde p zijn voor v, dan blijft bereik[1-v,p+1] altijd False.
10.4 Consensus met randomisering
153
register bereik[2, int] initieel bereik[0, 0] = bereik[1, 0] = True submit(v) voor proces i: p = 1 while (dec == @) { bereik[v, p] = True if (bereik[ 1-v, p+1]) { overweeg = 1-v } else if (bereik[ 1-v, p]) { overweeg = random(0,1) } else if (bereik[ 1-v, p-1 ]) { overweeg = v } else { dec = v } if (not bereik[v, p+1]) { v = overweeg } p = p+1 } return dec Programma 10.6: Gerandomiseerde n-proces consensus.
Bewijs. Zolang bereik[1-v,p+1] inderdaad nog op False staat, is het gedrag van processen na t als volgt. Een proces dat met v ronde p inkomt (of daar al is op t), constateert niet dat de andere waarde de volgende ronde al heeft bereikt, en overweegt dus een random keuze of v te houden. De tweede premisse impliceert dat dit proces in ieder geval met v naar de volgende ronde gaat. Een proces dat met v − 1 ronde p ingaat, doet dat na t. Het ziet misschien dat v al ronde p + 1 heeft bereikt, het overweegt dan v, maar anders ziet het zeker dat v ronde p heeft bereikt en overweegt een random keuze, die conform de tweede premisse voor v uitvalt. Daar bereik[1-v,p+1] nog False is, kiest het proces die waarde inderdaad. We zien hieruit dat elk proces dat door ronde p komt, met v naar ronde p+1 gaat, waardoor bereik[1-v,p+1] inderdaad False blijft. ¤ Uit de twee lemma’s is de correctheid van het algoritme gemakkelijk af te leiden. Net als Ben-Or’s algoritme (sectie 7.3) is de complexiteit erg hoog; de kans op succes in een ronde is namelijk exponentieel klein. Hiervoor is een oplossing bedacht, namelijk de shared coin; dit is een gedistribueerd protocol waarin stations op fout-tolerante manier een random trekking doen, maar op zo’n manier dat gelijkheid met significante kans geldt. De complxiteit van Ben-Or’s algoritme en van programma 10.6 wordt hiermee polynomiaal, maar we gaan hierop verder niet in (zie [BPSV06]). Een interessante eigenschap van programma 10.6 is, dat er geen registers worden gebruikt waarvan de betekenis in relatie staat tot een bepaald proces. Ook wordt in het programma de index i van een proces helemaal niet gebruikt. Het kan daarom worden gebruikt in situaties waar de processen niet door unieke namen of nummers worden onderscheiden, en Buhrman et al. [BPSV06] noemen een dergelijk algoritme anoniem.
154
10 Wachtvrije consensus
Samenvatting en conclusies In dit hoofdstuk werd gereedschap ontwikkeld om diverse wachtvrije objecten onderling in sterkte te kunnen vergelijken. Er wordt, voor een object A, gekeken naar het hoogste aantal processen waarvoor een of meerdere A-objecten een consensusobject kunnen implementeren. Dit aantal heet het consensusgetal, CN (A), van A. We hebben gezien dat registers geen consensus kunnen implementeren voor twee processen, en dus consensusgetal 1 hebben. Een queue kan wel consensus implementeren voor twee processen, maar niet voor drie, en heeft dus consensusgetal 2. Een compare-and-swap implementeert consensus voor willekeurig veel processen en heeft consensusgetal ∞. Hoe sterk is een object met een hoog consensusgetal? In dit hoofdstuk werden consensusgetallen gebruikt (zie stelling 10.12) om het niet bestaan van een implementatie aan te tonen. De stelling beantwoordt niet de vraag of er een implementatie van queue vanuit compare-andswap is. De premisse van de stelling is hier niet van toepassing omdat het consensusgetal van compare-and-swap hoger is dan van queue. Maar dat we de stelling niet kunnen toepassen impliceert nog niet dat de conclusie onwaar is. Met andere woorden, om ook het bestaan van implementaties te kunnen concluderen uit consensusgetallen moeten we nog meer dingen bewijzen; dit is het onderwerp van hoofdstuk 11. De consensus-hi¨erarchie is alleen een zinvol instrument voor het bekijken van deterministische implementaties. Met randomisering kan consensus met registers worden ge¨ımplementeerd, waardoor er een ineenstorting van de hi¨erarchie plaatsvindt.
Opgaven bij hoofdstuk 10 Opgave 10.1 Laat zien dat test-and-set consensusgetal 2 heeft. Opgave 10.2 Laat zien hoe 2-consensus kan worden ge¨ımplementeerd met een stack. (Hint: ga uit van programma 10.3.) Opgave 10.3 Laat zien dat de stack geen 3-consensus implementeert. (Hint: ga uit van stelling 10.8.) Opgave 10.4 Een fetch-and-increment object heeft toestandsruimte N (initi¨ele toestand 0) en een methode FaI die de toestand oplevert en met 1 verhoogt. Wat is het consensusgetal van dit type? Opgave 10.5 Consensus met Fetch-and-Increment. (Uit het tentamen van mei 2000.) Een fetch-and-increment object heeft als toestand een integer (initi¨eel 0), en als enige methode FaI, die de waarde van het object verhoogt en de nieuwe waarde oplevert. (a) Geef een implementatie van Consensus voor 2 processen met een fetch-and-increment object. (b) Bewijs dat er geen implementatie van 3-Consensus met dit object bestaat. (Je mag de begrippen en lemma’s uit het dictaat gebruiken.) (c) Wat is het consensus getal van fetch-and-increment? Opgave 10.6 Het bewijs van stelling 10.8 gebruikte essenti¨eel dat je uit een queue niet kunt lezen zonder de toestand te veranderen. Een front queue heeft behalve de methoden enq(v) en
Opgaven bij hoofdstuk 10
155
deq een methode front die de eerste waarde uit de queue oplevert (@ bij lege queue) maar niet verwijdert. Bewijs dat deze front queue consensusgetal ∞ heeft. Opgave 10.7 Consensus met Front-Queue. (Uit het tentamen van februari 2003.) Een Front-Queue object heeft een rijtje als toestand en methoden: enq(x) die x achteraan toevoegt, deq die het voorste element verwijdert en oplevert (@ als het rijtje leeg is), en front die het voorste element oplevert (@ als het rijtje leeg is) maar niet verwijdert. (a) Beargumenteer of de Front-Queue krachtig genoeg is om Consensus te implementeren voor 1 thread en voor 2 threads. (b) Kun je met een Front-Queue consensus implementeren voor 3 threads? (c) Wat is het Consensus-getal van de Front-Queue? Opgave 10.8 Consensus met Ticket Dispenser. (Uit het tentamen van februari 2001.) Een Ticket Dispenser object heeft een integer toestand (initi¨eel 1) en ´e´en methode: ticket, die de waarde oplevert `en verhoogt. Beargumenteer, of de Ticket Dispenser krachtig genoeg is om Consensus te implementeren voor 1, 2, of 3 threads. Wat is het Consensus-getal van de Ticket Dispenser? Opgave 10.9 Geef een implementatie van 2-consensus met type queue (waarbij je er wel twee mag gebruiken) waarbij de gebruikte queues initi¨eel leeg zijn. Opgave 10.10 Wat is het consensusgetal van een snapshotobject? Opgave 10.11 In hoofdstuk 9 was sprake van twee soorten electie-object. Het zwakke type retourneert op een elect-methode aan exact ´e´en thread leider en aan de anderen nonleider. Het sterke type retourneert aan elk proces de identiteit van een van de aanroepende processen. (a) Bewijs dat het eerste type consensusgetal 2 heeft. (b) Bewijs dat het tweede type consensusgetal ∞ heeft. Opgave 10.12 Universaliteit van Memory-Swap. (Uit het tentamen van mei 2001.) De memory-swap klasse bestaat uit een array van registers. Elk register kan individueel gelezen (met read(i)) en geschreven (met write(i,x)) worden. Daarnaast is er een swap(i,j) methode die de waarden op locaties i en j verwisselt. (a) Wanneer is een klasse universeel (voor een systeem)? (b) Bewijs dat een memory-swap object met k registers universeel is in een systeem met k − 1 threads. Opgave 10.13 Consensus met Swap-register. (Uit het tentamen van januari 2006.) Een swap-register is een object dat als toestandsruimte een vector van waarden heeft. Er zijn operaties write(i,x) die de waarde x in locatie i schrijft, en read(i) die de waarde van locatie i oplevert. Daarnaast is er een operatie swap(i,j) die de waarden van locaties i en j verwisselt. We gaan laten zien dat een swap-register Arb met n + 1 locaties (genummerd 0 t/m n), n-Consensus kan implementeren. (a) In de submit(x) operatie zal thread i precies eenmaal een instructie Arb.swap(0,i) uitvoeren. Hoe kun je de initi¨ele waarde van Arb kiezen om ervoor te zorgen dat de eerste swap-operatie iets aan de inhoud verandert, maar de latere swaps niet meer? (b) Kan een thread na het uitvoeren van zijn swap zien, als hoeveelste hij de swap deed? (c) Kan een thread na het uitvoeren van zijn swap zien, welke thread als eerste de swap deed? (d) Kan een thread na het uitvoeren van zijn swap zien, welke thread als tweede de swap deed? (e) Geef een wachtvrij algoritme dat een swap-register gebruikt en n-Consensus implementeert.
156
10 Wachtvrije consensus
Opgave 10.14 Consensusgetal van Swapper. (Uit het tentamen van februari 2002.) Een Swapper-object heeft een waarde als interne toestand, en een methode swap(x) die deze toestand oplevert en vervangt door x. Wat is het consensusgetal van de Swapper?
Hoofdstuk 11
Universaliteit van consensus In hoofdstuk 10 zagen we enkele voorbeelden van implementaties die (deterministisch) niet mogelijk zijn, en hoe dit bewezen kan worden met consensusgetallen. In dit hoofdstuk (sectie 11.1) zien we enkele implementaties die wel mogelijk zijn. Ook hier spelen consensusgetallen een belangrijke rol, maar de werkelijkheid is iets gecompliceerder dan dat een class zondermeer alle classes met kleiner consensusgetal zou kunnen implementeren. Belangrijkste resultaat is, dat een n-consensus object universeel is in een systeem met n processen: het kan daar elk object implementeren, en dit zullen we zien in sectie 11.3. Een consequentie is dat van de operaties die men tegenwoordig in hardware aangeboden ziet, de compare-and-swap de krachtigste is wanneer het op de ondersteuning van (deterministisch) wachtvrij rekenen aankomt. In gerandomiseerd rekenen is niet consensus, maar het uitdelen van unieke namen het meest crusiale primitieve object (sectie 11.4).
11.1
Compare-and-swap implementeert test-and-set
De test-and-set heeft consensusgetal 2, en compare-and-swap heeft consensusgetal ∞. Het laatste type is dus sterker dan het eerste als het er op aan komt, consensus te implementeren. Maar het is ook in andere zin sterker; compare-and-swap implementeert test-and-set; zie programma 11.1. Het test-and-set object kent, zoals vermeld in sectie 9.2.1, toestanden 0 en 1. De reset methode zet de toestand op 0 en hoeft dus alleen iets te veranderen als de toestand 1 is: de CaS(1,0) methode op de toestand is precies wat we nodig hebben. De TaS methode zet de toestand op 1, en verandert dus alleen iets als de toestand 0 is: de CaS(0,1) doet dit en levert de oude toestand op zoals ook voor de TaS methode nodig is. In programma 11.1 zijn de toegangsprocedures onafhankelijk van het proces dat ze uitvoert, en er zijn geen objecten die per proces informatie bijhouden. De implementatie werkt voor een willekeurig groot aantal processen.
11.2
Fetch-and-increment
We gaan nu enkele voorbeelden bekijken met een nieuwe class, de (finite) fetch-and-increment, waarvan we het consensusgetal kunnen vaststellen zonder onmogelijkheidsbewijzen te hoeven 157
158
11 Universaliteit van consensus
CompareAndSwap toestand set: { toestand.Cas(0,1) } reset: { toestand.CaS(1,0) } TaS: { return toestand.CaS(0,1) } Programma 11.1: Test-and-set met compare-and-swap.
geven. Een fetch-and-increment is een object dat een methode FaI heeft, die de waarde van het object oplevert en verhoogt. Het object geeft in volgorde de natuurlijke getallen uit: de ie aanroep geeft dus i. Het is daardoor te gebruiken als een “ticket dispenser” want het werkt precies als de nummertjesautomaat bij de bakker of in het postkantoor. Een finite fetch-and-increment geeft na een aantal aanroepen steeds hetzelfde getal. Preciezer gezegd, een k-fetch-and-increment object heeft toestandsruimte {1, . . . , k} en methode FaI die de waarde oplevert en, indien < k, met 1 ophoogt. De class k-fetch-and-increment heeft consensusgetal minstens 2, want je kunt er voor twee processen consensus mee implementeren op dezelfde manier als dat met de queue kan (programma 10.3). De fetch-and-increment is dus met registers niet te implementeren. (Opmerking: dit laatste geldt alleen voor k > 1!) 11.2.1
Compare-and-swap implementeert fetch-and-increment
Vaak is een implementatie wel wat gecompliceerder dan die in programma 11.1, waar elke methode van het ge¨ımplementeerde object precies ´e´en aanroep op een onderliggend object vereiste. Met een compare-and-swap kan het wel (zie programma 11.2), maar de FaI methode
CompareAndSwap next:
init 1
FaI: { t = 1 ; s = False while ( t
11.2 Fetch-and-increment
159
TestAndSet weg[k-1]
init
FaI: { t = 1 ; s = 1 while ( t <= k-1 and { s = weg[t].TaS if (s==1) { t++ } } return t }
0
s==1 ) // Probeer nummer t te pakken
Programma 11.3: Finite fetch-and-increment met test-and-set.
gebruikt een aantal achtereenvolgende aanroepen van compare-and-swap. Het compare-and-swap object next geeft de waarde van het volgende getal dat moet worden uitgedeeld, en het proces dat erin slaagt next te verhogen van t naar t+1 krijgt nummer t. Een proces begint pas aan next.CaS(t,t+1) wanneer zeker is dat de waarde van next tenminste t is. 11.2.2
Test-and-set implementeert fetch-and-increment
Niet alleen zijn soms meerdere operaties op een gebruikt object nodig, maar ook moet je soms van meerdere instanties van een class gebruik maken; hiervan volgt nu een voorbeeld. De kfetch-and-increment is ook te bouwen uit een reeks van k−1 test-and-set objecten: test-and-set weg[i] geeft dan aan dat getal i al is uitgedeeld. Een proces gaat proberen nummer i te pakken als het heeft geconstateerd dat alle kleinere nummers al vergeven zijn; zie programma 11.3. Het bestaan van een implementatie van fetch-and-increment uit test-and-set laat een conclusie toe over het consensusgetal van fetch-and-increment. Omdat fetch-and-increment consensus implementeert voor twee processen en zelf uit test-and-set (met consensusgetal 2) is te implementeren, heeft hij consensusgetal 2. De implementaties die we gezien hebben zijn gemakkelijk aan te passen om gebruik te maken van andere objecten, bv. de queue, van consensusgetal 2 of hoger. 11.2.3
Universaliteit
Nu zijn er zeer veel klassen, en het zou ondoenlijk zijn voor elke klasse die een andere implementeert een implementatie expliciet te geven. En telkens als je een nieuwe klasse wilt implementeren moet je weer gaan onderzoeken of de beschikbare klassen deze kunnen implementeren. Gelukkig is het soms mogelijk van een bepaalde klasse te bewijzen dat je er in jouw systeem alles mee kunt implementeren wat je maar wilt. Definitie 11.1 Een klasse A is universeel (voor een zeker systeem) als er voor elke klasse B een implementatie van B uit A bestaat. Heb je bewezen dat een klasse universeel is, dan weet je meteen dat een implementatie van elk denkbaar object in je systeem bestaat. Het bewijs van universaliteit (zie sectie 11.3) is
160
11 Universaliteit van consensus
constructief, dwz., geeft een implementatie. Die implementatie is echter meestal niet de best denkbare. We zullen bewijzen dat n-consensus universeel is in een systeem met n (of minder) processen. Daaruit volgt dat een class met consensusgetal n in die systemen alle objecten kan implementeren.
11.3
Consensus is universeel
De centrale rol die consensus speelt in alle beschouwingen over gedistribueerde systemen, wordt gemotiveerd door de volgende stelling; het doel van deze sectie is, die stelling te bewijzen. Theorem 11.2 (Herlihy [Her91]) Veronderstel dat n asynchrone processen 1, . . . , n communiceren via gedeelde objecten, waarbij objecten van type Consensus aanwezig zijn. Dan kan elk type object deterministisch worden ge¨ımplementeerd. Om te bewijzen dat consensus elke class kan implementeren zullen we eerst een model voor willekeurige classes moeten opstellen. In ons model is S de verzameling toestanden van een object (en in ∈ S de initi¨ele toestand), M de verzameling methoden (inclusief parameters) die kan worden aangeroepen, en R de verzameling return-waarden. Het gedrag van het object wordt beschreven door twee functies (new state) ns : S × M → S en (return waarde) rw : S × M → R. Wanneer op het object in toestand s een methode m wordt toegepast, levert de methode rw(s, m) op en de toestand van het object verandert in ns(s, m). (Dit model is van toepassing op deterministische classes, waarbij een methode-aanroep altijd maar ´e´en mogelijke uitkomst heeft en ´e´en mogelijke toestandsovergang. Voor non-deterministische classes moet het gedrag met relaties worden gemodelleerd; het algoritme blijft ongeveer gelijk.) 11.3.1
Werking van de universele implementatie
De universele constructie in deze sectie zorgt ervoor dat het feitelijke evalueren van de objectfuncties vrij van interleaving is. Er wordt namelijk een wachtvrije synchronisatie verzorgd, en het is daarmee een beetje te vergelijken met de mutual exclusion uit hoofdstuk 2. Wel is extra werk nodig om de wachtvrijheid te garanderen: een thread wordt nooit uitgesloten van het object, maar kan zijn eigen werk uitvoeren en eventueel eerst het werk van een andere thread afmaken. De constructie gebruikt consensusobjecten als een soort write-once register waarbij verschillende processen kunnen proberen dit object te “pakken” en hun waarde te schrijven, maar slechts het eerste proces slaagt hierin. Naast consensus objecten worden allerlei registers gebruikt (aanroep, gezien, etc.). Het object wordt gerepresenteerd als een gelinkte lijst, waarin elke uitgevoerde methode wordt opgenomen, uiteraard in volgorde van toepassing. Een proces dat een methode wil uitvoeren maakt een cel aan waarin de methode wordt beschreven, en probeert die in de gelinkte lijst op te nemen. Op twee manieren wordt de techniek van “onderling helpen” toegepast. (1) Als een cel van pi in de lijst is opgenomen, mogen andere processen de waarde van ns en rw invullen; dit voorkomt dat de andere processen op pi moeten wachten met volgende operaties. (2) Als pi een cel heeft aangemaakt, kunnen andere processen pi helpen de cel in de lijst te krijgen; dit voorkomt livelock van het soort waar pi willekeurig vaak moet proberen zijn cel in de lijst te krijgen. Elke cel bevat de volgende informatie (zie programma 11.4):
11.3 Consensus is universeel
class cel { integer M S R Consensus
161
seqnr meth st ret next
cel(m:M) // Constructor krijgt een methode mee { seqnr = 0 ; meth = m ; next = new Consensus } max(a,b: *cel) { if (a.seqnr > b.seqnr) { return a } else { return b } } } Programma 11.4: De class cel voor de universele constructie.
• Integer seqnr: rangnummer in de lijst. Cellen die aangemaakt zijn maar nog niet in de lijst opgenomen hebben serienummer 0. Het serienummer wordt gebruikt om van twee objecten te bepalen welke het meest recent aan de lijst is toegevoegd (functie max in
Kader 11.5: Structuur van cel en implementatie Elke cel (rechts) bevat een serienummer, een methode met returnwaarde en de nieuwe objecttoestand, en een verwijzing naar de volgende cel. Het onderstaande voorbeeld toont een queue (van integers) waarop achtereenvolgens de methoden enq(3), dec en dec zijn uitgevoerd. Proces 1 is bezig met een dec en proces 2 met een enq(5) operatie. anker
- 1
< > -
gezien aanroep
- 2
enq(3) <3> -
- 3
deq < > 3
1 2
0 deq
sn next meth st ret
- 4
deq < > @
0 enq(5)
µ
-
162
11 Universaliteit van consensus
cel anker : init [1, -, in, -, new Consensus] cel gezien[n] : init anker // hoogste cel die pi gezien heeft cel aanroep[n]: // methode waar pi mee bezig is methode voor proces i: { mijn = new cel( methode ) aanroep[i] = mijn for (j=1 ; j <= n ; j++) { gezien[i] = max(gezien[i], gezien[j]) } while (aanroep[i].seqnr == 0) { // Bepaal welke cel geprobeerd wordt c = gezien[i] help = aanroep[ (c.seqnr mod n) + 1] if (help.seqnr == 0) { poging = help } else { poging = aanroep[i] } // Probeer invoegen en toepassen d = (c.next).submit(poging) d.st = ns(c.st, d.meth) d.ret = rw(c.st, d.meth) d.seqnr = c.seqnr + 1 gezien[i] = d } return aanroep[i].ret } Programma 11.6: De universele methode.
programma 11.4). • De aangeroepen methode meth ∈ M . • De toestand st ∈ S ontstaan na toepassen van meth. • De waarde ret ∈ R die is opgeleverd door meth. • Een consensus object next dat naar de volgende cel wijst. Initi¨eel wordt het object gerepresenteerd door ´e´en cel, het anker, waarin de initi¨ele toestand van het object is opgeslagen. Elk proces houdt bij (in gezien[i]) wat de hoogstgenummerde cel is die het gezien heeft, en (in aanroep[i]) met welke methode het eventueel bezig is. Het uitvoeren van methode door pi wordt beschreven in programma 11.6. Terwille van de leesbaarheid worden gedeelde registers als gewone variabelen aangesproken en niet met hun read en write() methoden. Allereerst maakt pi een nieuwe cel mijn en zet daarin de aan te roepen methode (inclusief argumenten) en de pointer aanroep[i] gaat naar deze cel wijzen. Het plaatsen van deze pointer in aanroep[i] noemen we het aankondigen van de operatie door pi ; we zullen zien dat vanaf deze aankondiging ook de uitvoering van de operatie gegarandeerd is, zelfs als pi er
11.3 Consensus is universeel
163
niets meer aan doet. Na de aankondiging gaat pi proberen deze cel aan de gelinkte lijst toe te voegen en dan de nieuwe toestand en returnwaarde te berekenen. Om te voorkomen dat pi de hele lijst moet aflopen (wat willekeurig lang kan duren) bekijkt hij de array gezien en schat zo wat de laatste cel ongeveer is. Bedenk wel, dat wanneer pi bij de hoofdlus aankomt, al weer enige cellen kunnen zijn toegevoegd. In de hoofdlus onderneemt pi herhaald pogingen een cel aan de lijst toe te voegen en de betreffende methode uit te voeren. We zien de vormen van onderling helpen hier verschijnen. Ten eerste is pi niet zo ego¨ıstisch om dit onvoorwaardelijk met zijn eigen cel te gaan proberen. Behalve de cel aanroep[i] komt ook de cel van collega (gezien[i].seqnr mod n) + 1 in aanmerking. Als die een onbehandelde cel (seqnr == 0) heeft, krijgt poging de waarde van die cel. Vervolgens probeert pi de cel poging aan de ketting te rijgen, en wel volgend op de cel die pi het laatst gezien heeft. Natuurlijk is het mogelijk, dat er al een cel is die daarna is gelinkt, en een assignatie c.next = poging zou de juiste werking grondig kunnen verstoren. Daarom is de next pointer een consensusobject: mocht c.next al een waarde hebben, dan wordt hij niet veranderd! Als resultaat van de submit(poging) wordt de pointer d opgeleverd, naar de cel die volgt op cel c. Dit kan hetzij poging zijn, danwel een andere cel die eerder door een ander proces was gesubmit als opvolger van c. Dan zien we de tweede vorm van helpen in actie. Zelfs als een ander proces eerder een cel na c heeft toegevoegd dan pi wil dit nog niet zeggen dat de uitkomst van de operaties is ingevuld. Daarom gaat pi die operatie afmaken door d.seqnr, d.st en d.ret in te vullen. Tenslotte wordt gezien[i] aangepast, immers, d heeft een hoger nummer dan c. Het algoritme eindigt wanneer pi ziet dat zijn eigen operatie is uitgevoerd (seqnr != 0). 11.3.2
Bewijs van de universele implementatie
De datastructuur die wordt opgebouwd is een gelinkte lijst van genummerde cellen, elk bevatten ze een methode en de resulterende toestand van het object. Telkens wanneer een cel is toegevoegd, wordt (door minstens ´e´en, maar misschien door meerdere processen) de objecttoestand en returnwaarde ingevuld. We moeten bewijzen dat een proces hoogstens een begrensd aantal stappen doet in de universele methode. Eerst laten we zien dat een operatie niet willekeurig lang kan worden uitgesteld na aankondiging ervan. Lemma 11.3 Vanaf het moment dat pi zijn cel aangekondigd heeft kunnen hoogstens n + 1 cellen worden toegevoegd voordat pi ’s cel erbij zit. Bewijs. Door het toegepaste helpmechanisme heeft pi ’s operatie “voorrang” bij het toevoegen van elke k e cel waar k ≡n i. Onder de volgende n + 1 toe te voegen cellen zitten opeenvolgende nummers k − 1 en k waarvoor dit geldt. Het proces (zeg pj ) dat de k e cel toevoegt bekijkt aanroep[i] nadat de (k − 1)e cel is toegevoegd, en kan dus om deze cel niet heen als het sequencenummer nog steeds 0 is. Dit betekent dat pi ’s cel al is opgenomen voordat pj gaat linken, of pj helpt pi . ¤ Komt pi door het lezen van de gezien pointers inderdaad bij het eind van de lijst uit? Zij x het nummer van de laatst gethreade cel op het moment van pi ’s aankondiging. Omdat pi de pointers leest na de aankondiging, ziet pi minstens nummer x. Nu kan er echter tijdens het bekijken van die pointers een willekeurig hoog aantal cellen toegevoegd zijn: maar als het er meer dan n zijn is pi ’s operatie al gethread! In dat geval doorloopt pi hoogstens ´e´enmaal de hoofdlus (om de waarden en het sequencenummer in te vullen). Op het moment dat pi aan de
164
11 Universaliteit van consensus
hoofdlus begint geldt dus: gezien[i] zit hoogstens n + 1 plaatsen van het eind van de lijst, of pi ’s operatie is al toegevoegd. In elke slag van de hoofdlus van pi neemt gezien[i] toe: zo is er een garantie dat de lijst telkens langer wordt, al dan niet door het toedoen van pi zelf! Na ten hoogste n + 1 slagen zijn gegarandeerd n + 1 cellen toegevoegd sinds de aankondiging, hetgeen met lemma 11.3 impliceert dat de operatie van pi is toegevoegd, waarna pi de hoofdlus verlaat en aanroep[i].ret oplevert. 11.3.3
Reflectie
De universele implementatie is behoorlijk ineffici¨ent: zo wordt voor elke operatie bijvoorbeeld een nieuwe kopie van de objecttoestand aangemaakt. De nieuwe toestand wordt door meerdere processen berekend en ingevuld. Daarnaast is er de overhead van lijst bijhouden en sequencenummers. (Op de grootste zorg, het onbegrensd groeiende geheugengebruik, komen we straks terug.) Deze ineffici¨entie is een gevolg van de universaliteit van de constructie: de implementatie moet voor alle doelclasses werken en daardoor is het onmogelijk, specifieke overeenkomsten tussen gegeven class en doel class te benutten zoals dat in programma’s 11.2 en 11.3 gebeurde. Een universele constructie kan ook geen gebruik maken van eigenschappen van de ge¨ımplementeerde methoden, maar moet ze als een “black box” zien, zoals gemodelleerd in de functies ns en rw. De constructie gebruikt een nieuwe cel voor elke aanroep op het ge¨ımplementeerde object. Afgezien van de omvang van de cellen (elk bevat een kopie van de objecttoestand) doet dit het geheugengebruik onbegrensd groeien. Dit probleem is op te lossen door de lijst van het beginstuk af weer af te breken en de cellen te recyclen. Er moet dan wel vastgesteld kunnen worden, dat een bepaald beginstuk door geen proces meer gelezen hoeft te worden, en die vaststelling kan behoorlijk achterlopen. Herlihy [Her91] heeft laten zien, dat het voldoende is elk proces een pool van n2 cellen te geven: dan is het mogelijk een cel te vinden waarvan de recyclebaarheid kan worden aangetoond. Het totale geheugengebruik is dan O(n3 ) cellen. Voor een non-deterministische class kan de implementatie worden aangepast. Probleem is dat verschillende processen die de waarde d.st (en d.ret) willen invullen, verschillende uitkomsten kunnen krijgen ook al roepen ze de functie ns (en rw) aan met dezelfde parameters. Dit wordt opgelost door ook deze component van een cel als een consensusobject uit te voeren, zodat de waarde wordt vastgelegd door het eerste proces dat de toestandsberekening voltooit en de waarde naar het object stuurt (submit). Omdat de implementatie zo ineffici¨ent is zul je hem meestal niet gebruiken om grote objecten mee te implementeren, zoals grafen of andere ingewikkelde datastructuren. Voor compacte objecten die cruciale rol in procesco¨ordinatie spelen, zoals fetch-and-increment of semaforen kan de aanpak geschikt zijn. Er zijn diverse andere universele implementaties bedacht om de nadelen van de behandelde op te vangen, maar een behandeling ervan valt niet binnen het doel van dit boek.
11.4
Universaliteit van naamgeving
In sectie 11.3 is aangetoond (stelling 11.2), dat consensus voldoende is om elk object te implementeren, en in sectie 10.4, dat randomisering voldoende is om consensus (met geen andere objecten dan registers) te implementeren. De conclusie is, dat wanneer randomisering wordt toegevoegd aan Herlihy’s model, implementatie van alle objecttypen mogelijk is.
11.4 Universaliteit van naamgeving
165
ZwElect Identity[..] name: { id = 0 while ( id==0 ) { i++ ; if Identity[i] { id = i } } return id } Programma 11.7: Naming object met Zwakke Electie.
Buhrman et al. [BPSV06] wezen op het belang van een aanname van Herlihy’s model, namelijk de beschikbaarheid van unieke identificatienummers voor de processen. (Omdat deze aanname doorgaans gerechtvaardigd is, en dan ook zeer algemeen wordt gemaakt, is het werk van Buhrman meer van theoretisch dan van praktisch belang.) Volgens de gebruikelijke definitie van implementaties (definitie 9.1) zijn processen genummerd, en mag het procesnummer ook in de code voor het proces worden gebruikt. In de universele implementatie van Herlihy (programma 11.6) gebeurt dit ook, doordat er voor elk proces een eigen entry in de arrays aanroep en gezien is. Dat niet alle implementaties het procesnummer essentieel gebruiken is te zien aan het gerandomiseerde consensus-object (programma 10.6). Die implementatie is anoniem in de zin dat processen hun nummer niet nodig hebben, en er geen variabelen zijn die aan bepaalde processen gekoppeld zijn. Om de vraag te beantwoorden, welke anonieme implementaties mogelijk zijn, speelt het naming (naamgeving) object een cruciale rol. Een naming object voor n processen biedt een methode name, die door elk proces eenmaal mag worden aangeroepen, en geeft elk proces een verschillend getal (bv. uit het bereik 1 . . . n). In feite is een finite-fetch-and-increment of counter als naming object te gebruiken, maar in principe hoeft een naming object de getallen niet eens aansluitend en op volgorde uit te delen. Een object A dat universeel is in anonieme systemen, implementeert daar alle objecten, dus ook het naming object. Omgekeerd, als een object A naming implementeert, maakt het daarmee de toepassing van Herlihy’s universele implementatie mogelijk en daarmee implementeert het, in combinatie met consensus of randomisering, elk mogelijk object. Het is daarom gerechtvaardigd om naming zelf als universeel object te beschouwen in anonieme systemen met randomisering. Buhrman et al. bewezen, dat naming niet, zoals consensus, kan worden ge¨ımplementeerd met alleen multiple-reader, multiple-writer registers, zelfs niet als Las Vegas algoritme met randomisering. (Wel is er een Monte Carlo oplossing: laat elk proces een random getal kiezen in een voldoende groot bereik, dan is met bepaalde kans elk getal uniek.) Las Vegas naming kan wel worden ge¨ımplementeerd met single-writer registers. Met registers en randomisering is de zwakke electie te implementeren, en daarmee naming (volgens programma 11.7, zie [BPSV06]). Dat de tweede implementatie deterministisch is, toont aan dat zwakke electie niet zonder randomisering te realiseren is in een anoniem systeem, zelfs niet met behulp van consensus objecten. Daarmee is zwakke electie een object dat in een ge¨ıdentificeerde, deterministische setting, zwakker is dan consensus (consensus-getal 2), maar in een randomiserende, anonieme setting sterker is dan consensus (implementeert naming).
166
11 Universaliteit van consensus
Samenvatting en conclusies In dit hoofdstuk werd bekeken in hoeverre een hoog consensusgetal een garantie biedt voor het bestaan van implementaties. De centrale stelling van dit hoofdstuk is dat als een object consensus kan implementeren, dan kan het alle objecten implementeren. Hiertoe werd bewezen dat consensus zelf universeel is, dat wil zeggen, elk object kan implementeren. Het materiaal in dit hoofdstuk illustreert het belang van het consensusprobleem. Ook in systemen met berichtuitwisseling gelden soortgelijke resultaten: zodra consensus kan worden opgelost, liggen andere co¨ordinatieproblemen doorgaans binnen bereik. Tenslotte moeten we in het oog houden wat precies bewezen is: een class met consensusgetal n is universeel, dwz., kan elke class implementeren, in een systeem met n processen. Dit betekent niet, dat dezelfde class ook voor een systeem met meer processen kan worden ge¨ımplementeerd. De compare-and-swap class, met zijn consensusgetal oneindig, heeft hiervan natuurlijk geen last: in elk systeem kan het elke class implementeren, en het is hiermee het krachtigste object dat we hebben gezien. Andere voorbeelden van classes en operaties die consensusgetal ∞ hebben zijn: memory-to-memory move of swap (zie opgave 11.8), en de front-queue, maar de laatste zal als hardware primitief niet aangetroffen worden. De consensus-hi¨erarchie is zinvol voor deterministische implementaties; met randomisering is consensus uit registers te implementeren.
Opgaven bij hoofdstuk 11 Opgave 11.1 Waarom kun je met een compare-and-swap geen oneindige fetch-and-increment implementeren op de manier van programma 11.2? Opgave 11.2 Geef een implementatie van k-fetch-and-increment vanuit queue, die slechts ´e´en queue gebruikt. Opgave 11.3 Bewijs dat compare-and-swap de oneindige fetch-and-increment kan implementeren. Opgave 11.4 Sterke Electie. Gegeven is een Sterk Electie-object, dat bij elke aanroep de identiteit van de leider retourneert. Dat wil zeggen, het resultaat van elect is een threadnummer, dit nummer is bij alle aanroepen (van alle threads) gelijk, en het is het nummer van een thread die een aanroep heeft gedaan. (a) Is de Sterke Electie te implementeren met de zwakke vorm (die alleen leider of nonleider retourneert? (Motiveer!) (b) Wat is het consensus-getal van het Sterke Electie-object? Opgave 11.5 Maak de verzamelingen S, M en R en de functies ns en rw, zoals gedefini¨eerd in sectie 11.3, expliciet voor de test-and-set class. Opgave 11.6 Maak de verzamelingen S, M en R en de functies ns en rw, zoals gedefini¨eerd in sectie 11.3, expliciet voor de consensus class. Dezelfde vraag voor de electie class. Opgave 11.7 Geef voorbeelden van deterministische en non-deterministische classes.
Opgaven bij hoofdstuk 11
167
Opgave 11.8 De memory-swap class bestaat uit een array van registers, die individueel atomair gelezen en geschreven kunnen worden. Daarnaast is er een swap methode, die twee indices meekrijgt en de twee betreffende array-waarden (atomair) verwisselt. Bewijs dat memory-swap consensusgetal oneindig heeft.
Bibliografie [AAD+ 93] Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., and Shavit, N. Atomic snapshots of shared memory. J. ACM 40, 4 (1993), 873–890. [AT98]
Aguilera, M. K. and Toueg, S. A proof of Ben-Or’s randomized consensus algorithm. Manuscript, 1998.
[AW98]
Attiya, H. and Welch, J. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. McGraw-Hill, 1998.
[BD93]
Burns, A. and Davies, G. Concurrent Programming. Addison-Wesley, 1993.
[BO83]
Ben-Or, M. Another advantage of free choice: Completely asynchronous agreement protocols. In proc. 2nd Symp. on Principles of Distributed Computing (Montreal, 1983), pp. 27–30.
´ i, P. On the impor[BPSV06] Buhrman, H., Panconesi, A., Silvestri, R., and Vitany tance of having an identity or, is consensus really universal? Distributed Computing 18 (2006), 167–176. [Bur80]
Burns, J. E. A formal model for message passing systems. Tech. rep. TR–91, Indiana University, 1980.
[CHT96]
Chandra, T. D., Hadzilacos, V., and Toueg, S. The weakest failure detector for solving consensus. J. ACM 43, 4 (1996), 685–722.
[CR79]
Chang, E. J.-H. and Roberts, R. An improved algorithm for decentralized extrema finding in circular arrangements of processes. Commun. ACM 22 (1979), 281–283.
[CT96]
Chandra, T. D. and Toueg, S. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2 (1996), 225–267.
[DD98]
Deitel, H. M. and Deitel, P. J. Java: How to Program. Prentice Hall, 1998.
[DDS87]
Dolev, D., Dwork, C., and Stockmeyer, L. On the minimal synchronism needed for distributed consensus. J. ACM 34 (1987), 77–97.
[Dij68]
Dijkstra, E. W. Co-operating sequential processes. In Programming Languages, F. Genuys (ed.), Academic Press, 1968, pp. 43–112.
[DLS88]
Dwork, C., Lynch, N. A., and Stockmeyer, L. Consensus in the presence of partial synchrony. J. ACM 35, 2 (1988), 288–323. 168
Gedistribueerd programmeren
169
[Fic05]
Fich, F. E. How hard is it to take a snapshot? In proc. SOFSEM 2005: Theory and Practice of Informatics (Berlin, 2005), P. Vojt´aˇs, M. Bielikov´ a, B. CharronBost, and O. S´ ykora (eds.), vol. 3381 of Lecture Notes in Computer Science, Springer-Verlag, pp. 28–37.
[FLP85]
Fischer, M. J., Lynch, N. A., and Paterson, M. S. Impossibility of distributed consensus with one faulty process. J. ACM 32 (1985), 374–382.
[Fra86]
Francez, N. Fairness. Springer-Verlag, 1986 (295 pp.).
[GS87]
Gifford, D. and Spector, A. Case study: IBM’s system/360-370 architecture. Commun. ACM 30, 4 (1987), 291–307.
[Her91]
Herlihy, M. P. Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13, 1 (1991), 124–149.
[Hoa74]
Hoare, C. A. R. Monitors: An operating system structuring concept. Commun. ACM 17 (1974), 549–557.
[JTFK01] Jayanti, P., Tan, K., Friedland, G., and Katz, A. Bounding Lamport’s bakery algorithm. In proc. SOFSEM 2001: Theory and Practice of Informatics (Berlin, 2001), L. Pacholski and P. Ruˇziˇcka (eds.), vol. 2234 of Lecture Notes in Computer Science, Springer-Verlag, pp. 261–270. [Lam74]
Lamport, L. A new solution of Dijkstra’s concurrent programming problem. Commun. ACM 18, 8 (1974), 453–455.
[LeL77]
LeLann, G. Distributed systems: Towards a formal approach. In proc. Information Processing ’77 (1977), B. Gilchrist (ed.), North-Holland, pp. 155–160.
[Pet82]
Peterson, G. L. An O(n log n) unidirectional algorithm for the circular extrema problem. ACM Trans. Program. Lang. Syst. 4 (1982), 758–762.
[Sch06]
Schiper, A. Group communication: From theory to practice. In proc. SOFSEM2006: Theory and Practice of Computer Science (Berlin, 2006), J. Wiederˇ mann, G. Tel, J. Pokorn´ y, M. Bielikov´ a, and J. Stuller (eds.), vol. 3831 of Lecture Notes in Computer Science, Springer-Verlag, pp. 117–136.
[SG84]
Spector, A. and Gifford, D. The Space Shuttle computer system. Commun. ACM 27 (1984), 874–900.
[Tan96]
Tanenbaum, A. S. Computer Networks, 3rd edition. Prentice Hall, 1996.
[Tel00]
Tel, G. Introduction to Distributed Algorithms, 2nd edition. Cambridge University Press, 2000 (596 pp.).
[Tel02]
Tel, G. Cryptografie: Bescherming van de Digitale Maatschappij. AddisonWesley, 2002 (363 pp.).
Index Hn , 67 802.5, 65
consensusobject, 130 continue (notify and), 44 contractiepunt, 137 convergentie, 11, 81 crash, 80 critical section, 18
accuraat (foutdetector), 116 anoniem (algoritme), 153 anoniem netwerk, 97 atomair, 7, 17 attack, 80
database (deadlock), 57 deadlock, 21, 54 and-requests, 55 or-request, 55 deadlock avoidance, 57 deadlock detection/recovery, 56 deadlock prevention, 58 Dekkers algoritme, 24 deterministisch, 98 deterministische terminatie, 81 Dijkstra, 25, 49 dining philosophers, 49 direct (makescan), 138 double collect, 137
bakery-algoritme, 26 begrensde buffer, 39 Ben-Or, consensus, 106 bereikbaar (configuratie), 89 bericht, 64 bericht-complexiteit, 64 beslisprobleem, 80 bidirectionele ring, 67 binair register, 128 binaire semafoor, 35 binomiaalco¨effici¨ent, 1 bit, 128 bit-complexiteit, 64 bivalent, 90 blocked wait, 36 bovengrens, 63 broadcast, 85 busy wait, 19 Byzantijns falen, 80
Edsger W. Dijkstra, 25 electie, 63, 129 sterk, 129 zwak, 129 electie probleem, 65 entry protocol, 18 Ethernet, 102 executieboom, 9, 70, 88, 144 exit (notify and), 44 exit protocol, 18
Chang en Roberts algoritme, 67 commit/abort, 80 communicatie-complexiteit, 64 compare-and-swap, 128, 151 compleet, 116 compleet (foutdetector), 116 concurrency, 1 voordelen, 4 concurrent programma, 3 conditie (monitor), 42 configuratie, 88, 98 consensus, 78, 83, 97 consensusgetal, 150 consensushi¨erarchie, 151
faalkans, 99 fetch-and-increment, 154, 157 Fiber Distributed Data Interface, 65 fifo (kanalen), 66 Fischer, Lynch, Paterson (St.), 87 flexibele electie, 81 flood set, 114 foutdetectie, 113 foutdetector history, 116 foutmodel, 80
170
Gedistribueerd programmeren
foutpatroon, 115 fouttolerantie, 78 front queue, 154 front-queue, 128 gaat-vooraf-aan, 39 geldigheid (consensus), 120 granularity, 11 harmonisch getal, 67 Herlihy, stelling, 160 IBM System/360, 7 implementatie (wachtvrij), 130 impliciete terminatie, 85 indirect (makescan), 138 Java, 11, 45 kanaal, 64 kloksynchronisatie, 81 Knuth-prijs, 86 kritiek, 145 kritieke sectie, 18 Lamport, bakery-algoritme, 26 Las-Vegas-algoritme, 100 Lego-robot, 99 leider (electie), 65 LeLann algoritme, 66 liveness, 21 Lynch, Nancy, 86 makescan (snapshot), 137 maximale open prefix, 70 medium access control, 102 message passing, 64 Mindstorm (Lego), 99 Modula-3, 78 monitor, 40 Monte-Carlo-algoritme, 100 mutual exclusion, 19, 29 na-u gedrag, 22 naamgeving, 165 naming, 165 Netscape, 4 non-determinisme, 3, 89 notify, 36, 43 Notre Dame, orgel, 101 omissie, 80 onafhankelijkheidsaxioma, 6 ondergrens, 63 ontvangen, 64 open prefix, 70
171
orgel (Notre Dame), 101 overeenstemming, 83, 120 pak, P, 33 parti¨ele correctheid, 98 parti¨ele synchronisatie, 13 perfecte foutdetector, 118 Peterson algoritme, 67 poor man’s supercomputer, 12 pre-emption, 56 prefix, 70 priority scheduling, 56 probabilistische terminatie, 11, 81 producer-consumerprobleem, 39, 128 progress, 21, 29 queue, 128, 145 quicksort, 102 randomisering, 113 read-write atomicity, 11 read-write register, 128 receive, 64 register, 128 renaming, 81 replay, 69 ring (netwerk), 65 robuustheid, 83 rotating coordinator, 121 safe sluice, 21 safety, 21 semafoor, 33 binair, 35 send, 64 sequenti¨ele specificatie, 6 sequentialiseren, 17 servet, 57 shared coin, 153 Sherwood algoritme, 101 shout, 81 signal (semafoor), 33 single writer, multiple reader, 128 single writer, single reader, 128 skip (instructie), 19 snapshotobject, 129 socket, 5, 64 Space Shuttle, 79 spaghetti, 49 stabilisatie, 81, 85 starvation, 22, 23, 29, 54 sterk accuraat, 117 sterke broadcast, 86 sterke foutdetector, 118 supercomputer, 12
172
symmetrie-argument, 98 synchronisatie, 17 synchronized (Java), 45 synchroon model, 113 synchroon parallellisme, 13 System/360 (IBM), 7 terminatie, 81, 120 test-and-set, 7, 37, 128, 157 thread, 5 three-phase commit, 80 token, 66 token ring, 65 Toueg, Sam, 116 two-phase commit, 80 uiteindelijk perfecte foutdetector, 118, 119 uiteindelijk sterk accuraat, 117 uiteindelijk sterke foutdetector, 118 uiteindelijk zwak accuraat, 117 uniform, 70 univalent, 90 universeel, 159 update (snapshot), 137 valent (configuratie), 90 valentie, 144 veiligheid, 21 vervalprocedure, 104 vrij, V, 33 wachtvrij, 127 wachtvrije hi¨erarchie, 151 wachtvrije implementatie, 130 wait, 36 wait (monitor), 42 wait (notify and), 44 wait (semafoor), 33 wait-for-graph, 54 zenden, 64 zwak accuraat, 117 zwakke broadcast, 85
Index