keskiviikko 3. helmikuuta 2010

Itsepäinen joukko.


Rinnakkaisissa järjestelmissä on sellainen hauska piirre, että kun niiden käyttäytymistä mallinnetaan esim. tilakoneina, joilla on ns. lomitetun ajan semantiikka (interleaving semantics), periaatteessa toisistaan täysin riippumattomat tapahtumat tuottavat "eri" tulevaisuuden.

Esimerkikki: järjestelmä, jossa kaksi komponenttia, A ja B toimivat toisistaan riippumatta; A vilkuttaa punaista valoa ja B vihreää (tämä on vain esimerkki, ei mikään mielekäs järjestelmä) ja kolmas komponetti odottaa, että kumpikin valo on vilkkunut viisi kertaa ja sitten se piippaa. Olemme kiinnostuneita tulevaisuudesta, jossa tapahtuu "piippaus". A ja B vilkkuvat miten sattuu; niillä on viidenteen valon syttymiseen asti yhteensä 36 eri tilayhdistelmää (6*6). Tämä on vähän hölmöä, koska oikeasti olemme kiinnostuneita kummankin kuudesta tilasta, eikä näiden muilla yhdistelmillä ole merkitystä kuin sillä, jossa molemmat ovat vilkkuneet jo viisi kertaa.

Jokaisessa tilassa ennen kuin jompi kumpi lamppu vilkkunnut viisi kertaa, järjestelmä voi toimia kahdella eri tavalla: joko A vilkkuu tai B vilkuu. A:n vilkkuminen ei estä B:tä vilkkumasta ja toisaalta B:n vilkkuminen ei estä A:ta vilkkumasta. Lisäksi, tulevaisuus, jossa sekä A että B ovat vilkkuneet kerran, on identtinen, riippumatta siitä, kumpi tapahtuu ensin. Tulevaisuus, jossa "piippaus" tapahtuu, ei jää tutkimatta, vaikka tutkittaisiin vain toinen näistä järjestyksistä. Sanomme, että A ja B ovat riippumattomat mainitussa tilassa.

Riippumattomuuden käsite yleistyy laajemminkin. Oletetaan, että olemme kiinnostuneita tulevaisuuksista, joissa "kaikki" on jo tapahtunut, so. järjestelmä on lopettanut toimintansa. Haluamme säilyttää nämä tulevaisuudet, mutta tutkia mahdollisimman vähän tilasiirtymiä kustakin tilasta. Oletamme, että järjestelmässä on "tapahtumia" ja "tiloja" - en erittele tätä sen tarkemmin.

Sanomme, että joukko T tapahtumia on itsepäinen annetussa tilassa (stubborn, ks esim A stubborn attack on state explosion) jos sillä on seuraavat ominaisuudet:
A1: Jos tapahtuma t kuuluu joukkoon T ja se voidaan suorittaa tulevaisuudessa s', joka saavutetaan suorittamalla tietty sekvenssi joukon ulkopuolisia tapahtumia, se voidaan suorittaa heti. Tällöin lopputulos on riippumaton siitä, suoritetaanko t mainitun sekvenssin jälkeen vai sitä ennen.
A2: Joukosta löytyy yksi tapahtuma, joka voidaan suorittaa heti, ja jonka suorittamista ei voi estää suorittamalla joukon ulkopuolisia tapahtumia. Tätä nimitetään avaintapahtumaksi.

Jos jokaisessa tilassa tutkitaan vain ne tulevaisuudet, jotka saavutetaan tutkimalla itsepäinen joukko tapahtumia, ei hukata ainuttakaan sellaista tulevaisuutta, jossa järjestelmä on pysähtynyt. Tämän todistaminen ei ole vaikeaa: Jos järjestelmä on pysähtynyt, avaintapahtuman on joko täytynyt tapahtua tai sitten se on täytynyt estää. Koska joukon ulkopuoliset tapahtumat eivät voi sitä estää, ja sisäpuolisten tapahtumien tuottamat tulevaisuudet tutkitaan, niin todistus on valmis.

Syystä, joka ei ole minulle täysin ilmeinen, esimerkiksi Wikipedia tuntee ainoastaan itsepäistä joukkoa aidosti heikomman menetelmän, ns. "ample set"-karakterisoinnin riippumattomuutta hyödyntävälle reduktiolle. Karakterisointi on vaikeampi, todistus oikeellisuudesta on vaikeampi ja tiedetään, että reduktio on aidosti huonompi.

4 kommenttia:

Otso kirjoitti...

Syystä, joka ei ole minulle täysin ilmeinen, esimerkiksi Wikipedia tuntee ainoastaan itsepäistä joukkoa aidosti heikomman menetelmän, ns. "ample set"-karakterisoinnin riippumattomuutta hyödyntävälle reduktiolle.

Syy on triviaali: et ole lisännyt stubborn set reduktiota sinne vielä.

Tiedemies kirjoitti...

Triviaali syy on tietenkin tuo. Ihmettelen asiaa siksi, että stubborn set reduktio on vanhempi ja parempi. Kun aloin viime vuonna tutkia osittaisjärjestysreduktiota, törmäsin samaan ilmiöön.

Otso kirjoitti...

Luulisin, että tässä ollaan jo sen verran spesifien kiinnostuksen kohteiden äärellä, että silkka satunnaisvaihtelu riittää selittämään jonkin yksittäisen sivun löytymisen tai löytymättömyyden wikipediasta.

Ihmisiä, joilla on:
i) ymmärrys stubborn set reduktiosta riittävällä tasolla,
ii) riittävä usko ymmärryksensä riittävyyteen,
iii) sellainen suhde wikipediaan, että saattaisi lisätä sinne sivun, ja
iv) riittävä kiinnostus aiheeseen,

ei yksinkertaisesti ole kuin kymmeniä, ehkä satoja.

Oiekastaan sanoin jo kaiken tämän ensimmäisessä kommentissa, mutta sorruin selittelemään tässä töitä vältellessäni. Pahoitteluni.

Tiedemies kirjoitti...

Luulen, että olet oikeassa.

Tiedän lisäksi, että stubborn set-reduktio on paljon harvinaisemmin käytetty. Syyt ovat sosiaaliset. Tämä harmittaa minua, sillä Ample-set karakterisoinnin abstraktiot ovat epätarkoituksenmukaiset, sen määritelmä haiskahtaa ad hoc-kehitetyltä ja sen todistaminen oikeaksi on hankalampaa.