Vísindin um dreifða vinnslu

Við notum sífellt fleiri tæki sem vinna saman: snjallsímar, netþjónar, bílar, mælar og jafnvel efni með innbyggðri skynjun. Á bak við þessa samvinnu býr mikilvæg og vaxandi grein tölvunarfræðinnar - dreifð vinnsla (e. distributed computing). Hún snýst um hvernig margir hlutar kerfis geta unnið saman að sameiginlegu markmiði, þótt þeir búi aðeins yfir takmörkuðum upplýsingum og samskiptum.

Í þessari grein verður stiklað á stóru um fræðin sem liggja að baki: Hvað er hægt að reikna í dreifðum kerfum? Hversu hratt? Og hvernig geta þau tekist á við truflanir, takmarkanir og ósamræmi?

Hvað er dreifð vinnsla?
Dreifð vinnsla á sér stað þegar margir aðilar - tölvur, ferlar eða jafnvel líkamlegir hlutir - taka þátt í að leysa verkefni, þar sem enginn einn aðili hefur yfirsýn yfir alla myndina. Þeir þurfa að treysta á samskipti sín á milli til að ná sameiginlegum árangri.

Eins og Nancy Lynch skilgreindi árið 1996, samanstanda dreifð kerfi af mörgum tölvueiningum sem hvorki deila sameiginlegu minni né hafa samhæfðar klukkur - en verða engu að síður að vinna eins og eitt heildarkerfi.

Við rekumst á slík kerfi allt í kringum okkur: fjölkjarna örgjörva, netþjóna tengda með Ethernet, jafningjakerfi (P2P), bálkakeðjur (e. blockchains) og netskynjara í Internet of Things (IoT).

Líffræðin býður einnig upp á sambærileg dæmi - svo sem mauraþúfur þar sem einstaklingar vinna saman með einfaldar reglur, og í efnafræði, þar sem dreifð viðbrögð stjórna hegðun snjall efna.

Þetta undirstrikar hversu víðtæk og í grundvallaratriði dreifð vinnsla er í tæknilegum og náttúrulegum kerfum dagsins í dag.

Fræðilegi grunnurinn - af hverju vísindi?
Hvað aðgreinir vísindi dreifðrar vinnslu frá hagnýtri verkfræði? Það er einbeitingin á frumreglur og möguleika. Á borð við eðlisfræðina sem afmarkar hvað er framkvæmanlegt í verkfræði, þá spyr fræðin um dreifð kerfi:

• Hvað er yfirhöfuð reiknanlegt í slíku kerfi?
• Hver eru hraðatakmörk?
• Hvernig hafa samskiptatakmarkanir, tímasetningar eða gallar áhrif á möguleikana?

Þessi frumspekilegu viðfangsefni eru ekki aðeins huglæg - þau hafa bein áhrif á hvernig við hönnum öruggar, sveigjanlegar og skilvirkar lausnir.

Dæmigerðar rannsóknarspurningar
Helstu spurningar í fræðum dreifðrar vinnslu snúa meðal annars að:

• Staðbundinni vitneskju (e. locality): Hversu mörg samskiptaskref þarf til að leysa verkefni þegar hver þátttakandi hefur aðeins nálæga innsýn?
• Bilanaþoli (fault tolerance): Hvernig heldur kerfið áfram að starfa þótt hlutar þess bili eða detti út?
• Reiknanleika (computability): Hvernig hafa takmörk á minni, tíma eða bandbreidd áhrif á það sem hægt er að reikna?
• Samskeiðun (concurrency control): Hvernig tryggjum við öruggan aðgang að sameiginlegum auðlindum án gagnaóreiðu eða ósamræmis?

Rannsóknir á Íslandi
Við Háskólann í Reykjavík er öflug rannsóknastarfsemi á þessu sviði. Þar rannsakar Dr. Marcel Kyas hvernig samnýting og dreifð úrvinnsla virkar í Internet of Things. Dr. Hans P. Reiser sérhæfir sig í kerfum sem þurfa að halda réttri virkni þrátt fyrir truflanir og bilanir - afar mikilvægt í öryggiskerfum og gagnastýringu. Dr. Gísli Hjálmtýsson vinnur að notkun blokkakeðjutækni til að byggja upp örugg, rekjanleg og dreifð kerfi, sér í lagi í stafrænum prófskírteinum og rekjanleika í aðfangakeðjum með notkun kerfa eins og Hyperledger. Einnig er unnið að grunnrannsóknum á reiknifræði og reiknanleika dreifðra kerfa. Þar er meðal annars rannsakað hvernig módel með mismunandi forsendum um samskipti, vitneskju eða tímaskipan breyta möguleikum kerfanna.

Litun neta — dæmigert vandamál
Eitt dæmigert vandamál í dreifðri vinnslu er svokölluð litun neta (e. graph coloring). Hver hnútur í neti þarf að fá lit, þannig að engir tveir tengdir hnútar fái sama lit. Þetta hefur hagnýta þýðingu: Ef aðeins einn „litahópur“ framkvæmir aðgerð í einu, forðumst við árekstra og truflanir.

En verkefnið er flókið þegar það þarf að fara fram dreift og hratt, með sem fæstum litum. Í klassískri niðurstöðu frá Nati Linial (1992) kemur fram að ómögulegt er að finna góða litun með föstum fjölda samskiptaskrefa, óháð stærð netsins. Þetta leiðir til djúpra fræðilegra spurninga:

Hversu mörg samskiptaskref eru nauðsynleg?
Hversu mikilli upplýsingamiðlun þarf að koma við?
Hvernig hefur fjöldi lita áhrif á reiknigetu?
Við í HR höfum lagt okkar af mörkum til að svara slíkum spurningum, meðal annars með rannsóknum á litun neta undir ólíkum forsendum um bandbreidd, vitneskju og tímasetningar.

Að lokum
Vísindin um dreifða vinnslu snúast í grunninn um samvinnu undir takmörkunum - hvernig ófullkomnir aðilar ná samanlagt að framkvæma stórvirk verkefni. Þetta á ekki aðeins við í tækni - heldur einnig í náttúru, samfélögum og jafnvel framtíð mannkynsins. Í heimi þar sem stærstu áskoranir okkar - frá loftslagsbreytingum til stafrænna innviða - kalla á skalanlegar og sveigjanlegar lausnir, eru dreifð kerfi hluti af lykillausninni.

Þessi fræði eru í mótun hér á Íslandi. Smáríki með öfluga þekkingu getur átt þátt í að móta framtíð þar sem samvinna og gagnvirkni verða meginreglur. Og kannski er það einmitt það sem gerir þetta svið svo spennandi - að það snýst ekki bara um tölvur, heldur um það hvernig heimurinn vinnur saman.

Höfundur: Magnús M. Halldórsson, prófessor við tölvunarfræðideild Háskólans í Reykjavík. Greinin birtist upphaflega í Tölvumálum.