VERKIEZING 1 Probleemstelling 2 Algoritmen 2.1 LeLann, 1977 2.2 Chang & Roberts, 1979 2.3 Peterson, 1982 3 Ondergrens. 1 Probleemstelling. ------------------------ Stel een zekere berekening moet door precies 1 proces gestart worden. Uitgaande van een netwerk met alle stations in dezelfde toestand willen we bereiken dat een proces als LEIDER bekend staat en de anderen als NIET-LEIDER. We beginnen met de context waarin het probleem als eerste opdook, namelijk een ring-vormige configuratie met verkeer in een richting. We nemen aan dat elk proces een unieke naam of nummer kent en die naam gaan we gebruiken. In 1980 werd bewezen dat dit noodzakelijk is. Idee: we gaan het proces met kleinste nummer leider maken. Hoe pakken we dit aan? Eerste oplossing. "Die nummers, dat is vast: 0 .. n-1." IF p=0 THEN leider ELSE non-leider AANNAME: De namen komen uit een groot domein. Het is dus niet van 0 noch van enig ander getal zeker dat het voorkomt. Tweede oplossing. "Als die nummers opklimmend gerangschikt zijn is er precies een proces dat een GROTERE voorganger heeft." send

; receive ; if q > p then leader else non-leader AANNAME: Elke rangschikking van de namen is mogelijk. De meeste algoritmen zijn wel gebaseerd op het onderling vergelijken van de namen. Derde oplossing: "Ik stuur een token rond dat alle processen bekijkt en de kleinste naam onthoudt" Eh.... Waar moet dit token beginnen? We zullen een leider moeten kiezen voor we met de verkiezing kunnen beginnen. 2 Algoritmen ------------------ 2.1 LeLann, 1977 -------------------- Neem aan dat berichten elkaar niet kunnen inhalen op de links. 1. Elk proces stuurt een bericht rond met z'n eigen naam. 2. Berichten met andere namen stuur je door. 3. Als je eigen bericht weer terugkomt, heb je alle berichten gezien. 4. Als je de kleinste bent win je. Iedereen van de correctheid overtuigd? Wat is de complexiteit? 2.2 Chang & Roberts, 1979 ----------------------------- 1. Elk proces stuurt een bericht rond met z'n naam. 2. Berichten met KLEINERE namen stuur je door (en je wordt non-leader), met GROTERE namen gooi je weg. 3. Als je eigen bericht weer terugkomt, win je. Iedereen van de correctheid overtuigd? Zij MIN het kleinste proces. Omdat de ring rond is, komt elk bericht langs MIN als het niet eerder weggeknikkerd is, ergo, een proces anders dan MIN ziet z'n bericht niet terug. Niemand, maar dan ook niemand, houdt MIN's bericht tegen. Wat is de complexiteit? Het aantal berichten blijkt af te hangen van de verdeling van stations over de ring! Geluk-geval: processen zijn in dalende volgorde gerangschikt, geeft 2n-1 berichten. Pech-geval: processen zijn oplopend gerangschikt, elk bericht wordt pas afgestopt door MIN, geeft 1/2 n (n-1) berichten. Het knappe van C&R was berekening van het gemiddelde aantal. Propositie: 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). 2.3 Peterson, 1982 ---------------------- Nu was de race goed geopend en men vroeg zich af of het ook met O(n.lg(n)) WC kon en dit lukte Hirschberg en Sinclair in 1980, zij het met de aanname dat je in TWEE richtingen over de ring kunt zenden. We bekijken nu een variant van Peterson uit 1982 die hetzelfde voor elkaar krijgt maar iets simpeler is en waarbij berichten slechts in een richting verzonden worden. De verkiezing 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. 2. In een ronde die met k>1 kandidaten begint, worden TENMINSTE k/2 kandidaten en TEN HOOGSTE k-1 kandidaten geelimineerd. 3. Als een ronde met 1 kandidaat begint, merkt hij 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. 1. Als je ACTIEF bent, stuur je je naam twee stappen naar rechts: send

; receive ; send ; receive 2. Als je PASSIEF bent, stuur je wat je van rechts of links ontvangt gewoon door. 3. Als je ACTIEF bent, vergelijk je je naam p met die van je twee voorgangers q en r. 3a. Als de eerst ontvangen naam je eigen naam is, word je leider. 3c. Als q groter is dan p en r ga je ACTIEF naar de volgende ronde met q als nieuwe naam. 3b. Anders word je PASSIEF. Het is niet zo moeilijk om in te zien dat als er minimaal twee actieve nodes zijn en een van de nodes actief blijft aan het einde van een ronde, de eerste actieve voorganger passief wordt. Hieruit volgt: Stelling 1. Er zijn hoogstens lg(n) + 1 ronden. (Hierbij is lg(n) de logaritme voor het grondtal 2 van n: de macht waartoe je 2 moet verheffen om n als uitkomst te krijgen, dus q = lg(n) <=> 2^q = n ) Stelling 2. Er worden precies 2n berichten per ronde uitgewisseld, behalve in de laatste ronde waarin n berichten worden uitgewisseld. Conclusie: Het algoritme kiest een leider met circa 2nlg(n) + n berichten. Peterson heeft ook nog een variant bedacht die in 1.44nlgn werkt, zowel bi- als unidirectioneel. 3 Ondergrens ------------------ In 1984 hebben Pachl, Korach en Rotem bewezen dat geen algoritme een verkiezing kan doen met minder dan nlgn berichten in het slechtste geval.