hyväky
iäiväavaaave

arvostelija

Itsevakautuva järjestäytyminen ja päivittäminen

EsaElovaara

Helsinki29.10.2007

HELSINGIN YLIOPISTO

EsaElovaara

Itsevakautuva järjestäytyminen ja päivittäminen

29.10.2007

12 sivua+ 0liitesivua TekijäFörfattareAuthor

TyönnimiArbetetstitelTitle

OppiaineLäroämneSubjet

TyönlajiArbetetsartLevel AikaDatumMonthandyear SivumääräSidoantalNumberofpages

TiivistelmäReferatAbstrat

AvainsanatNykelordKeywords

SäilytyspaikkaFörvaringsställeWheredeposited

Sisältö

1 Johdanto 1

2 Itsevakautuvuus 2

3 Algoritmien vaativuusanalyysi 2

4 Verkon virittävän puun rakentaminen 3

5 Verkon solmujen määrän laskeminen 5

6 Verkon solmujen nimeäminen 7

7 Järjestäytyminen 8

8 Päivittäminen 9

Lähteet 12

1 Johdanto

Itsevakautuvatalgoritmitovattärkeitävikasietoistenhajautettujenjärjestelmienra-

kentamisessa. Itsevakautuvan algoritmin suorittaminen voidaan aloittaa mistä ta-

hansa mahdollisesta tilasta ja silti voidaan taata, että algoritmi päätyy lailliseen

tilaan rajoitetun ajan kuluttua. Itsevakautuva algoritmi pystyy siis palautumaan

mistä tahansaväliaikaisesta tietoliikenneviasta taimuistivirheestä.

Tässä paperissa esiteltävät algoritmit liittyvät kahteen hajautettujen järjestelmien

tyyppiin. Itsevakautuva järjestäytyminen muuntaa erikoisprosessorijärjestelmää si-

ten, että järjestelmässä voidaan käyttäätunnuksellisellejärjestelmälle suunniteltua

algoritmia.Itsevakautuva päivittäminen muuntaa tunnuksellista järjestelmää siten,

että järjestelmässä voidaan käyttää erikoisprosessorijärjestelmälle suunniteltua al-

goritmia.

Erikoisprosessorijärjestelmässäyksiprosessori onmuistapoikkeavaerikoisprosessori

ja muut järjestelmän prosessorit ovat keskenään täysin identtisiä. Tunnuksellisessa

järjestelmässäjokaisellaprosessorilla on ainutlaatuinentunnus.

Hajautettujen järjestelmien rakenteiden määrittelyyn käytetään verkkoja. Verkon

solmut vastaavat järjestelmän prosessoreita ja solmuja yhdistävät kaaret kuvaavat

prosessoreiden välisiäsuoriaviestintäyhteyksiä.

Järjestäytyminen koostuu useammasta osa-algoritmista, jotka yhteistyössä toimi-

malla saavuttavat halutun päämäärän. Algoritmit toimivat toistensa kanssa limit-

täinsiten,ettäalgoritmi

A i−1

^tuojärjestelmänalgoritmin

A i

^olettamaanlähtötilaan.

Dolev [Dol00℄ todistaa kirjansivulla 23,että kahden itsevakautuvanalgoritminrei-

lu kooste on myös itsevakautuva algoritmi. Reilukoostaminen tarkoittaa sitä, että

algoritmeja ajetaan rinnakkain ja jokainen algoritmi pääsee suorittamaan käskyjä

odotettuaan vuoroaanäärellisen ajan.

Selvyyden vuoksi osa-algoritmitesitelläänensin yksitellen, jonkajälkeen näytetään

kuinkaniitä koostamallasaadaan aikaan algoritmijärjestäytymiselle.

Esiteltävät algoritmit toimivat asynkronisissa järjestelmissä ja käyttävät prosesso-

2 Itsevakautuvuus

Itsevakautuva järjestelmävoidaankäynnistäämielivaltaisessatilassaja sen voidaan

siltitaata ennen pitkää käyttäytyvän tehtävänsä mukaan.

Tehtävän mukainen käytös määritellään joukolla hyväksyttyjä käskyjä

LE

^{. Itseva-}

kautuvanjärjestelmän tulee ennenpitkää päätyä suorittamaanjoukon

LE

^käskyjä.

LE

^riippujärjestelmän tehtävästä.

Järjestelmänkonguraatio koostuu prosessoreiden tiloistaja jaetussa muistissaole-

vienrekistereiden sisällöstä.

Järjestelmänkonguraatioonturvallinen,josjokainenkonguraatiostaalkanutreilu

suorituskuuluu joukkoon

LE

^.

Algoritmionitsevakautuva,josmielivaltaisestatilastaalkanutreilu suorituspäätyy

turvalliseentilaan.

Reilussasuorituksessajokaisellejärjestelmänprosessorilletaataantilaisuussuorittaa

käskyjä äärellisen odotusajanjälkeen.

3 Algoritmien vaativuusanalyysi

Itsevakautuvien algoritmien aikavaativuuden mittana käytetään mielivaltaisestati-

lasta turvalliseen tilaan siirtymiseen tarvittavien kierrosten määrää.Kierroksen ai-

kana jokainen järjestelmänprosessori pääseesuorittamaanohjelmaansaainakin yh-

den käskyn verran. Käsky koostuu yhdestä viestintä-askeleesta ja sitä edeltäväs-

tä prosessorin sisäisestä laskennasta. Yksi viestintä-askel on rekisteriin kirjoittami-

nen/rekisteristälukeminen.

Aikavaativuuttavoidaan mitata myös sykleissä. Yhden syklin aikana jokainen pro-

sessori ehtii suorittaa vähintään yhden kokonaisen iteraation ikuisen silmukkansa

koodia.

Tilavaativuuden mittana käytetään järjestelmän tarvitseman muistin määrän suh-

4 Verkon virittävän puun rakentaminen

Algoritmirakentaaerikoisprosessorijärjestelmäntiedonvälitysverkonvirittävänpuun

leveyssuuntaista hakua käyttäen. Prosessori

P i

^{kommunikoi naapurinsa}

P j

^kanssa

kirjoittamallarekisteriin

r ij

^{ja lukemalla} rekisteristä

r ji

^.

Systeemissä, jossa on

n

prosessoria, prosessorit

P 2 . . . P n

suorittavat samanlaista ohjelmaa. Erikoisprosessori

P ₁

^{tulee olemaan virittävän puun juuri ja se suorittaa}

muista prosessoreista poikkeavaaohjelmaa.

Jokainenrekisteri

r ij

^{koostuukahdestakenttästä:}

r ij .dis

^ja

r ij .parent

^.

r ij .dis

^sisältää

prosessorin

P i

^{etäisyydenpuunjuuresta.Prosessori}

P i

^{siisilmoittaakaikillenaapuri-}

prosessoreilleen (oletetun) etäisyytensäpuun juuresta.Etäisyyden suurinmahdolli-

nenarvoon

N

^{,jokaonsysteemin}prosessoreiden enimmäismäärä.Tätä suuremman arvon asettaminen rekisteriinei onnistu, vaan rekisterin arvoksi tulee tällöin

N

^.

P i

asettaa

r ij .parent

^{kentän arvoksi}

1

^{, jos}

P i

^valitsee prosessorin

P j

vanhemmakseen virittävässä puussa. Muussa tapauksessa

P i

^{asettaa kentän arvoksi}

0

^.

Jokainen systeemin prosessori yrittää selvittää etäisyytensä prosessorista

P 1

^{ja il-}

moittaa etäisyytensä naapureilleen.

P 1

luonnollisesti tietää etäisyyden itsestään ja

sen suorittama ohjelma kirjoittaa rekistereihin loputtomasti paria

h0, 0i

^{, eikä kos-}

kaan lue naapureiltatulleita viestejä.

Erikoisprosessori suorittaaalgoritmia1.

δ

^onprosessorin naapureiden lukumäärä.

Algorithm 1 Virittäväpuu: erikoisprosessori [Dol00℄

1: while true do

2: for

m := 1

^to

δ

^do

3: write

r im := h0, 0i

4: end for

5: endwhile

Tavallinenprosessori

P j

⁽

2 ≤ j ≤ n

^)lukeenaapureidensa lähettämätviestitjavalit- seeniidenperusteellavanhemmakseenprosessorin,jokailmoittaaolevansalähimpä-

näprosessoria

P 1

^.Etäisyydekseen

P j

^ilmoittaavanhempansaetäisyydenkasvatettu- nayhdellä. Tämän jälkeen prosessori kirjoittaatiedotnaapureidensa rekistereihin.

Perusprosessorit suorittavat algoritmia2.

δ

^on prosessorin naapureidenlukumäärä.

Virittävä puu voidaan päätellä systeemin rekistereiden sisällöstä, kun algoritmi on

vakautunut. Jos

r ij .parent

^{arvo on}

1

^, prosessoreiden

P i

^ja

P j

^{välinenlinkki kuuluu}

Algorithm 2 Virittäväpuu: perusprosessori [Dol00℄

1: while true do

2: for

m := 1

^to

δ

^do

3:

lr mi :=

^read

(r mi )

4: end for

5:

F irstF ound := f alse

6:

dist := 1 + min{lr mi .dis|1 ≤ m ≤ δ}

7: for

m := 1

^to

δ

^do

8: if not

F irstF ound

^and

lr mi .dis = dist − 1

^then

9: write

r im := h1, disti

10:

F irstF ound := true

11: else

12: write

r im := h0, disti

13: endif

14: end for

15: endwhile

Järjestelmäonturvallisessatilassa,kunjokaisenprosessorin

P i dist

^{muuttujanarvo}

on prosessorin etäisyys erikoisprosessorista ja perusprosessorit ovat valinneet van-

hemmakseen erikoisprosessoria lähimpänä olevistanaapureistaan ensimmäisen.

Kelluva etäisyys on prosessorin

P i

^{todellista etäisyyttä pienempi arvo} rekisterissä

r ij .dis

^.

∆

^{oneniten yhteyksiäomaavan}prosessorin yhteyksien määrä.

Teoreema 1. Järjestelmän suoritettua

∆ + 4k∆

^{kierrosta (}

k > 0

^{), seuraavat väit-}

tämät ovat tosia järjestelmän konguraatiolle: (1) Jos konguraatiossa on kelluva

etäisyys, pienimmän kelluvan etäisyyden arvo on vähintään

k

^{. (2) Jos virittävän}

puun juuren

P i

^ja prosessorin

P j

^etäisyys

d

^{on enintään}

k

^, prosessorin

P j

^jokaisen

rekisterin arvo on

h1, di

^tai

h0, di

^.

Todistus. Induktiolla syklien määrän

k

^suhteen.

Suoritettuaan

2∆

^{kierrosta,prosessori onlukenut}naapureidensarekisteritjakirjoit- tanutomiin rekistereihinsä.

Perusaskel:(

k = 1

⁾Rekistereihinjasisäisiinmuuttujiintalletetutetäisyydetovatei- negatiivisia,jotenensimmäisenkonguraationpienimmänkelluvanetäisyydenarvo

on vähintään 0. Ensimmäisen

2∆

^{kierroksen aikana,} prosessorit

P i

⁽

i 6= 1

^{) laskevat}

muuttujan

dist

^arvon. Muuttujalle laskettu arvo on aina suurempi kuin 0. Olkoon

c 2

järjestelmän konguraatio, kun prosessorit ovat laskeneet muuttujan

dist

^arvon

ensimmäistäkertaa.Jokainenprosessori

P i

⁽

i 6= 1

^)kirjoittaakonguraatiota

c 2

^seu-

raavien

2∆

^{kierroksen aikana}

dist

muuttujansa arvon rekistereihinsä. Näin ollen,

4∆

^kierrosta seuraavassa konguraatiossa vainjuurisolmun prosessorinrekistereissä on etäisyyden arvona 0. Juurisolmun etäisyys itsestään on 0, joten kyseessä ei ole

kelluvaetäisyys. Tämätodistaaväittämän(1).Juurisolmunprosessori kirjoittaare-

kistereihinsä arvonnolla ensimmäisten

∆

^{kierrostenaikana. Olkoon}

c 1

järjestelmän konguraatio

∆

^{kierroksenjälkeen. Juurennaapuritlukevatjuuren rekisteritja kir-}

joittavat omiin rekistereihinsä arvon 1 konguraatiota

c 1

^seuraavien

4∆

^kierroksen

aikana. Tämä todistaaväittämän(2).

Induktioaskel: (oletetaan väittämät tosiksi arvoilla

k ≥ 0

^ja todistetaan ne tosik- si arvolla

k + 1

^{) Olkoon}

m ≥ k

^{pienin kelluva etäisyys} konguraatiossa

c _4k

^{, johon}

järjestelmä siirtyy suoritettuaan ensimmäiset

∆ + 4k∆

^{kierrosta. Seuraavien}

4k∆

kierroksen aikana jokainen prosessori, jonka lukemista etäisyyksistä

m

^{on pienin,}

kirjoittaa rekistereihinsä arvon

m + 1

^{. Näin ollen,}

m + 1

^{on pienin kelluva etäi-}

syys konguraatiossa

c 4(k+1)

^{. Tämä todistaa väittämän (1). Olkoon} prosessorin

P j

etäisyysjuuresta

k + 1

^ja

P i

prosessorin

P j

^{naapuri,jonkaetäisyys juurestaon}

k

^.In-

duktio-oletuksen mukaan prosessorin

P i

rekistereihin onkirjoitettu arvo

k

^{. Kohdan}

(1) mukaan pienin kelluva etäisyys on

m ≥ k

^{, joten pienin} prosessorin

P j

^lukema

etäisyys on

k

^ja

P j

^kirjoittaa rekistereihinsä arvon

k + 1

^{. Tämä todistaa väitteen}

(2).

Kun prosessorit ilmoittavatetäisyytensätodenmukaisesti, jokainen prosessori valit-

see vanhemmakseen ensimmäisen erikoisprosessoria lähimpänä olevan naapurinsa.

Näin ollen, järjestelmä pystyy siirtymään mielivaltaisestatilasta turvalliseen tilaan

ja algoritmionitsevakautuva.

5 Verkon solmujen määrän laskeminen

Algoritmiolettaa verkonvirittävänpuun olevantiedossa.

Algoritmi etenee laskemalla virittävän puun alipuidenprosessoreiden määriä puun

lehdistäalkaen. Jokainen Prosessori

P i

^{on virittävänpuun alipuunjuuri ja}

P i

^pitää

alipuun prosessoreiden määrää muuttujassa

count i

^{. Jokainen prosessori lukee lap-}

siensa ilmoittamanprosessoreiden määrän ja ilmoittaa omalle vanhemmalleen lue-

määränoikeinjokatilanteessa.Koskalehdilläeimääritelmällisestiolelapsia,

count i

muuttujan summaksitulee aina

1

^.

Erikoisprosessorin suorittama ohjelma poikkeaa perusprosessoreiden suorittamista

ohjelmistavainyhden piirteenkohdalla:erikoisprosessorinei tarvitse lähettäävies-

tejä,koska silläeiole vanhempaa.

Järjestelmä on turvallisessa tilassa, kun jokaisen prosessorin

P i count i

^muuttujan

arvoonprosessorista

P i

^{alkavanvirittävänpuunalipuun}prosessoreiden lukumäärä.

Teoreema 2. Järjestelmän suoritettua

k

^{sykliä, jokaiselle} prosessorille

P i

^korkeu-

della

0 ≤ h < k

^{pätee seuraava väittämä:muuttujan}

count i

^{arvo on} prosessorista

P i

alkavanvirittävän puun alipuun prosessoreiden lukumäärä.

Todistus. Induktiolla syklien määrän

k

^suhteen.

Perusaskel (

k = 1

⁾

k = 1 ⇒ h = 0

^{. Jokainen prosessori asettaa iteraation aluksi}

muuttujan

sum

^{arvoksi 0.} Korkeudella 0 olevilla prosessoreilla ei ole lapsia, joten rivejä 4 ja 5 ei suoriteta. Rivillä 7 muuttujan

count i

^{arvoksi asetetaan}

sum + 1 = 0 + 1 = 1

^.

Induktioaskel: (oletetaan väittämä todeksi arvoilla

k ≥ 0

^ja todistetaan se todeksi arvolla

k + 1

⁾Korkeudella

k

^olevanprosessorin lapsienkorkeus onpienempi kuin

k

^,

joteninduktio-oletuksen mukaan lapsien

count

^{muuttujien arvot ovat} totuudenmu- kaisia. Rivit 4 ja 5 laskevat lapsien (alipuiden)

count

^{muuttujien summanja rivi 7}

kasvattaasummaayhdellä,jotenmuuttujan

count i

^arvoonprosessorista

P i

^alkavan

virittävänpuun alipuunprosessoreiden lukumäärä.

Erikoisprosessori suorittaaalgoritmia3.

Algorithm 3 Solmujenlaskeminen:erikoisprosessori [Dol00℄

1: while true do

2:

sum := 0

3: for all

P j ∈ children(i)

^do

4:

lr ji :=

^read

(r ji )

5:

sum := sum + lr ji .count

6: end for

7:

count i := sum + 1

8: endwhile

Algorithm 4 Solmujenlaskeminen:perusprosessori [Dol00℄

1: while true do

2:

sum := 0

3: for all

P j ∈ children(i)

^do

4:

lr ji :=

^read

(r ji )

5:

sum := sum + lr ji .count

6: end for

7:

count i := sum + 1

8: write

r i,parent .count := count i

9: endwhile

6 Verkon solmujen nimeäminen

Algoritmiolettaa verkonvirittävänpuun rakenteen ja virittävän puun kaikkienali-

puidensolmujen määränolevantiedossa.

Algoritmimäärääjokaisellesolmulleainutkertaisentunnusnumeron, jokakuuluuvä-

liin

[1 . . . n]

^{, missä}

n

^{on verkon solmujen määrä. Tunnusten} määräytyminen tapah- tuurekursiivisesti:solmusaavanhemmaltaanvapaantunnusnumeron

id

^{. Vanhempi}

pitää huolen siitä, että numerot

[id . . . (id + count i )]

^{ovat vapaana, eikä niitä ole}

annettu muille solmuille. Solmu asettaa

id

^{:n omaksi} tunnuksekseen ja jakaa välin

[id + 1 . . . (id + count i )]

^{tunnukset omille}lapsilleen.Virittävänpuun juurena toimi-

va erikoisprosessori

P 1

^onainoa prosessori, joka tietää aina lopullisentunnuksensa.

Erikoisprosessori eisaa tunnustaanmuilta prosessoreilta,vaan sen tunnukseksiase-

tetaanaina

1

^.

Järjestelmä on turvallisessa tilassa, kun erikoisprosessorin tunnus

ID ₁

^{on 1 ja jo-}

kaisen perusprosessorin vanhempionkirjoittanutlapsensarekisteriinainutkertaisen

tunnuksen väliltä

[2 . . . n]

^.

Teoreema 3. Järjestelmän suoritettua

k

^{sykliä, seuraavat väitteet ovat tosia: (1)}

Prosessorille

P i

^{on asetettu tunnus}

ID i ∈ {1 . . . n} ∧ d(P i , P 2 ) < k ∧ ID i 6= ID j

^,

kun

d(P j , P 1 ) < k

^{. (2)} Prosessorille

P i

^{on varattu yhtenäinen joukko tunnuksia}

ids i ⊂ {1 . . . n}∧d(P i , P 1 ) = k∧ID j ∈ / ids i

^,kun

d(P j , P 1 ) < k ∧ T

d(P j ,P ₁ )=k ids j = ∅∧

joukon

ids i

^{koko on} prosessorin

P i

^alipuun prosessoreiden lukumäärä.

Todistus. Induktiolla syklien määrän

k

^suhteen.

Perusaskel (

k = 1

⁾ Erikoisprosessori

P 1

^{suorittaa rivin 2 ja}

ID 1 = 1

^. Etäisyydel- lä

k − 1

^{ei ole muita} prosessoreita, joten

ID 1

^on ainutkertainen. Tämä todistaa

väitteen (1). Kun

ID i

^on kiinnitetty, vapaiden tunnusten joukko on

{2 . . . n}

^{. Eri-}

koisprosessorin

P 1

^alipuissaon

n − 1

prosessoria, jotentunnuksiaonjäljelläriittävä määrä.Rivit 4,6ja 7pilkkovatjoukon alipuidenprosessoreiden määräävastaaviin,

toisiaanleikkaamattomiinyhtenäisiinalijoukkoihin, ja lähettävätalijoukojentiedot

erikoisprosessorin lapsille.Tämä todistaa väitteen (2).

Induktioaskel: (oletetaan väittämä todeksi arvoilla

k ≥ 0

^ja todistetaan se todeksi arvolla

k + 1

⁾ Indiktio-oletuksen mukaan jokaisella prosessorilla

P i

^{, jonka etäisyys}

juuresta on

k

^{, on joukko vapaita tunnuksia}

ids i

^{ja näiden joukkojen leikkaus on}

tyhjä joukko. Etäisyydellä

k

^olevatprosessorit voivat siisvalitatunnuksekseen

ID i

minkätahansa oman joukkonsa alkion, tunnuksien yhteentörmäyksiä pelkäämättä.

Prosessori valitsee tunnuksekseen joukon pienimmän tunnuksen rivillä4. Tämä to-

distaaväitteen(1). Indiktio-oletuksenmukaanjoukon

ids i

^{kokoonalipuun}

P i

^koko,

joten tunnuksen

ID i

kiinnittämisen jälkeen vapaita tunnuksia on riittävästä pro- sessorin

P i

^alipuille. Perusprosessoreiden algoritmin rivit 6, 7, ja 8 jakavat vapaat tunnukset prosessorin

P i

^{alipuille.Tämä todistaa väitteen (2).}

Erikoisprosessori suorittaaalgoritmia5.

Algorithm 5 Solmujennimeäminen: erikoisprosessori [Dol00℄

1: while true do

2:

ID i := 1

3:

sum := 0

4: for all

P j ∈ children(i)

^do

5:

lr ji :=

^read

(r ji )

6: write

r ij .identif ier := ID i + 1 + sum

7:

sum := sum + lr ji .count

8: end for

9: endwhile

Perusprosessorit suorittavat algoritmia6.

7 Järjestäytyminen

Virittävänpuunrakennus,puunsolmujenlaskujapuunsolmujennimeämis-algorit-

mit muuntavat yhdessä erikoisprosessorisysteemin tunnukselliseksi systeemiksi. Ne

Algorithm 6 Solmujennimeäminen: perusprosessori [Dol00℄

1: while true do

2:

sum := 0

3:

lr parent,i .identif ier :=

^read

(r parent,i )

4:

ID i := lr parent,i .identif ier

5: for all

P j ∈ children(i)

^do

6:

lr ji :=

^read

(r ji )

7: write

r ij .identif ier := ID i + 1 + sum

8:

sum := sum + lr ji .count

9: end for

10: endwhile

päällä voidaan ajaa mitä tahansa tunnukselliselle systeemille suunniteltua algorit-

mia.

8 Päivittäminen

Päivitysalgoritmientehtävä on pitää järjestelmän prosessorit ajan tasalla järjestel-

mäntopologiasta.Tässä esitettyalgoritmiselvittää jokaisen prosessorinkytkettyyn

komponettiin kuuluvat prosessorit. Tämä tieto riittää johtajan valintaan järjestel-

mässä, joka koostuu ainutkertaisilla tunnuksilla varustetuista prosessoreista. Algo-

ritmivakautuu

O(d)

^{ajassa, missä}

d

^{on verkon}halkaisija.

On olemassamyös ajassa

O(d)

^vakautuva,anonyymeissä järjestelmissä toimivasa- tunnaistettujohtajanvalinta-algoritmi[Dol94℄.

Jokainen prosessori

P i

^{pitää yllä pareista}

hid, disi

^{koostuvaa joukkoa}

P rocessors i

jaetussa muistissa. Parivastaa järjestelmänprosessoria, jonka tunnus on

id

^{ja etäi-}

syys prosessorista

P i

^on

dis

^. Prosessorin

P i

^{naapurit pystyvät lukemaan joukon}

P rocessors i

^alkiot.

Järjestelmänturvallisessakonguraatiossajokaiselleprosessorille

P i

^{pätevätseuraa-}

vat väittämät:

• P rocessors i

^{sisältää parin}

hj, yi

^jokaista järjestelmän prosessoria

P j

^kohden

siten, että

y

^onprosessoreiden

P i

^ja

P j

^etäisyys toisistaan,

•

prosessorinnaapureiden

P j ∈ N (P i ) P rocessors j

^{joukkojenparitovatsellaisia,}

että joukon

P rocessors i

^{sisältöei muutu algoritmin}seuraavalla iteraatiolla.

Yhdessäalgoritminiteraatiossaprosessori

P i

^lukeenaapureidensa

P j ∈ N (P i ) P rocessors j

joukkojen alkiot yhdistejoukkoon

ReadSet i

^{, muokkaa joukkoa}

ReadSet i

^{ja asettaa}

uudeksi

P rocessors i

^{joukoksi muokatun}

ReadSet i

^joukon.

Joukkoa

ReadSet i

^muokataanseuraavasti(suluissaviittauksetvastaaviinoperaatioi- hin algoritmissa7):

1. kaikki parit joiden tunnisteena onprosessorin

P i

^{tunniste poistetaan (rivi 6),}

2. jäljelläolevien parien etäisyyksiäkasvatetaanyhdellä(rivi 7),

3. joukkoonlisätään pari

hi, 0i

^(rivi8),

4. jos prosessorin

P j

^{tunnus esiintyy useammassa joukon parissa, pareista pois-}

tetaankaikki paitsietäisyydeltään pieninpari(rivi 10),

5. jos

dis max

^{on suurin joukosta löytyvä etäisyys ja joukossa ei ole yhtään paria}

etäisyydellä

dis v < dis max

^{, kaikki parit joiden etäisyys onsuurempi kuin}

dis v

poistetaan joukosta(rivi 12),

6. jos joukossa on enemmän pareja kuin systeemissä on prosessoreita,

|G|

^etäi-

syydeltään pienintäparia säilytetään ja loputpoistetaan joukosta(rivi 12).

Prosessorit suorittavatalgoritmia7.

Algorithm 7 Päivittäminen[Dol00℄

1: while true do

2:

ReadSet i := ∅

3: for all

P j ∈ N (i)

^do

4:

ReadSet i := ReadSet i ∪

^read

(P rocessors i )

5: end for

6:

ReadSet i := ReadSet i \ \hi, ∗i

7:

ReadSet i := ReadSet i + +h∗, 1i

8:

ReadSet i := ReadSet i ∪ {hi, 0i}

9: for all

P j ∈ processors(ReadSet i )

^do

10:

ReadSet i := ReadSet i \ \NotMinDist(P j , ReadSet i )

11: end for

12: write

P rocessors i := ConP ref ix(ReadSet i )

Lemma 4. Järjestelmän suoritettua

k

^{sykliä, jokaiselle} prosessorille

P i

^ja

P j

^etäi-

syydellä

l < min(k, d+1)

^{pätevätseuraavatväittämät:}

(1) processors i

^{sisältääparin}

hj, li

^ja

(2)

^{jos pari}

hx, yi

^{kuuluu joukkoon}

processors i

^ja

y ≤ l

^{, niin on olemassa}

prosessori

P x

etäisyydellä

y

prosessorista

P i

^.

Todistus. Induktiolla syklien määrän

k

^suhteen.

Perusaskel:(k=1)Ensimmäisensyklinaikanajokainenprosessorilisäärivillä8parin

hi, 0i

^joukkoon

ReadSet i

^{. Rivin 7} suorittaminen takaa, että jokaisen parista

hi, 0i

poikkeavan poikkeavan parin etäisyys on suurempi kuin 0. Näin ollen, rivien 9,10

ja 12 suorittaminen ei poista paria

hi, 0i

^{ja pari päätyy}

processors i

^{joukkoon. Tä-}

mätodistaa väittämän(1). Koskaetäisyydet ovatpositiivisia, yhdenkään

ReadSet i

joukon parin etäisyydeksi eiolevoinutrivin 7suorituksen takiatulla 0.Näin ollen,

joukossa eivoiolla muita (virheellisiä)pareja etäisyydellä 0.

Induktioskel: Oletetaan, että väittämät (1) ja (2) pätevät järjestelmän suoritettua

k

^{sykliä, kun}

l < min(k, d + 1)

^{. T}odistetaan, että väittämät (1) ja (2) pätevät

yhden lisäsyklin jälkeen, kun

l < min(k + 1, d + 1)

^{. Syklin}

k + 1

^{aikana jokainen}

prosessori

P i

^lukee naapureidensa

P j ∈ N (i) processors j

^joukot.Induktio-oletuksen mukaan kaikkiparit, joidenetäisyys onpienempi taiyhtäsuuri kuin

l − 1

^{sisältävät}

virheetöntätietoajärjestelmästä.Induktio-oletustakaamyössen,ettäluetutjoukot

sisältävät kaikki mahdolliset virheettömät parit. Näin ollen, jokainen iteraatiossa

k + 1

^{laskettu pari}

hid, li

⁽

∀P id

^{) on} oikeellinen ja tuloksena saatavat

processors i

joukot ovat maksimaalisia.

Lemma 5. Järjestelmänsuoritettua

d + 2

^{sykliä, jokaiselle parille}

hx, y i

^{pätee väit-}

tämä: järjestelmässäon prosessori, jonka tunnus on

x

^.

Todistus. Lemman 4 mukaan

d + 1

^{syklin jälkeen jokainen pari, jonka etäisyys on}

pienempi tai yhtä suuri kuin

d

^{ei ole kelluva pari. Jos jokin}

P rocessors

^joukko

sisältää kelluvan parin

hx, yi

^{, täytyy päteä}

y > d

^{. Sykli}

d + 2

^{kasvattaa kelluvan}

parin etäisyyden suuremmaksi kuin

d + 1

^{ja rivin 12suoritus poistaa parin.}

Teoreema 6. Järjestelmän suoritettua

d + 3

^sykliä, järjestelmä on turvallisessa konguraatiossa.

Todistus. Lemman 4 mukaan

d + 1

^{syklin jälkeen jokainen pari, jonka etäisyys on}

pienempi tai yhtä suuri kuin

d

^{ei ole kelluva pari ja kaikki}

P rocessors

^{joukot ovat}

maksimaalisia. Lemman 5 mukaan

d + 2

^{syklin jälkeen} järjestelmässä ei ole kel- luvia pareja. Näin ollen, järjestelmä siirtyy turvalliseen tilaan syklin

d + 3

^aikana

prosessoreiden luettua naapureidensa

P rocessors

^{joukkot sisäiseen} muistiinsa.

Turvallisessa konguraatiossa

P rocessors i

^{sisältää kaikkien} prosessoriin

P i

^suoras-

sa tai epäsuorassa yhteydeydessä olevien prosessoreiden tunnukset. Toisin sanoen,

jokainen kytketyt komponentin prosessori tietää muiden komponentin prosessorei-

den tunnukset. Kytketyn komponentin prosessorit voivat siisvalitajohtajan yksin-

kertaistakriteeriäkäyttämällä(esim.johtajaksivalitaanprosessori, jonkatunnuson

pienin).

Lähteet

Dol94 Dolev, S., Optimal time self-stabilization in uniform dynami sys-

tems. 6th IASTED International Conferene on Parallel and

Distributed Computing and Systems, 1994, sivut 2528, URL

iteseer.ist.psu.edu/dole v94o ptim al.h tml.

Dol00 Dolev, S., Self-Stabilization. MIT Press, Marh 2000.