Seminaari: Hajautetut algoritmit

Aikataulu · Yleistä · Aihepiiri · Työmuodot · Aiheluettelo · Lähteet · Sanastoa

Ajankohtaista

Seminaari on päättynyt, kiitos kaikille osallistujille! Muistattehan antaa kurssipalautetta seminaarista.

Seminaarin aihepiiriin liittyviä graduaiheita voi tiedustella seminaarin vastuuhenkilöltä.

Aikataulu

Seminaaritapaamiset, seminaaritöiden aiheet ja esiintyjät:

Muita tärkeitä päivämääriä:

• ma 5.10.2009 kello 12.00: kirjoitelman ensimmäisen version palautus (Joel R., Jan)
• ma 12.10.2009 kello 12.00: kirjoitelman ensimmäisen version palautus (Janne K., Jara)
• pe 16.10.2009 kello 12.00: kirjoitelman ensimmäisen version palautus (muut)
• pe 27.11.2009 kello 12.00: vertaispalaute
• pe 11.12.2009 kello 12.00: kirjoitelman viimeistelty versio

Yleistä

• Seminaari kokoontuu syksyllä 2009, periodeissa I ja II.
• Kokoontumiset torstaisin klo 12–14 salissa C220.
• Laajuus 3 op.
• Vastuuhenkilö Jukka Suomela.
• Seminaari pidetään suomeksi.
• Esitietovaatimukset: tieteellisen kirjoittamisen kurssi tulee olla suoritettuna.

Osallistujilta edellytetään jonkin verran algoritmisen ajattelun hallintaa ja riittävät matemaattiset perusvalmiudet – esimerkiksi verkkoihin liittyvät peruskäsitteet on hyvä tuntea. Hajautettuihin järjestelmiin liittyviä esitietoja ei vaadita.

Seminaarin aihepiiri osuu laitoksemme opetuksessa algoritmien ja koneoppimisen erikoistumislinjan ja hajautettujen järjestelmien ja tietoliikenteen erikoistumislinjan välimaastoon. Seminaari soveltuu hyvin molempien linjojen opiskelijoille.

Aihepiiri

Seminaarissa tarkastellaan laskennallisten ongelmien ratkaisemista hajautetuissa järjestelmissä. Lähestymistapa on samantapainen kuin algoritmien ja laskennan teorian tutkimuksessa yleensäkin. Tutkittava ongelma formalisoidaan ja ongelman laskennallisesta vaativuudesta yritetään tämän jälkeen saada mahdollisimman kattava kuva. Pääpaino on todistuksilla, ei niinkään esim. kokeellisella työllä.

Seminaarin aihevalinnat eroavat huomattavasti tyypillisestä hajautettua laskentaa tai rinnakkaislaskentaa käsittelevästä kurssista tai oppikirjasta. Emme käsittele esimerkiksi vikasietoisuutta, keskinäistä poissulkemista ja konsensusongelmia.

Johdantoa. Hajautettu järjestelmä kuvataan yleensä verkkona G = (V, E): verkon solmut v ∈ V suorittavat laskentaa ja verkon kaaret e ∈ E kuvaavat solmujen välisiä tiedonsiirtoyhteyksiä. Alkutilanteessa kukin solmu tietää vain osan syötteestä, ja lopuksi kukin solmu tarvitsee osan tuloksesta.

Tarkastellaan esimerkkinä erästä klassista laskennallista ongelmaa, verkon värittämistä. Perinteisten algoritmien näkökulmasta yleensä ajatellaan, että alkutilanteessa väritettävä verkko on tallennettuna tietokoneen keskusmuistissa (tai vaikkapa Turingin koneen nauhalla), ja algoritmin suorittamisen jälkeen myös lopputulos on tallennettuna tietokoneen keskusmuistissa.

Hajautettujen algoritmien näkökulmasta tyypillinen tilanne puolestaan on se, että väritettävä verkko on nimenomaan verkko G, joka kuvaa hajautetun järjestelmän rakennetta. Alussa verkon solmu v ∈ V tietää esim. vain oman yksilöllisen tunnisteensa, ja lopputilanteessa solmun v tulee tietää oma värinsä.

Hajautetussa laskennassa kiintoisaa on yleensä tapaus, jossa laskennallisen järjestelmän rakenne – siis verkko G – on tuntematon. Hajautettu algoritmi joudutaan laatimaan ennen kuin tiedämme, millaisessa järjestelmässä sitä tullaan suorittamaan. Hajautetun algoritmin on itse tarkasteltava järjestelmän rakennetta ja pystyttävä löytämään kelvollinen ratkaisu kaikissa mahdollisissa verkoissa.

Laskennan mallit. Hajautettujen algoritmien tarkastelussa on tärkeää määritellä huolella, mitä laskennan mallia tarkastellaan; vaihtoehtoja on useita.

Eräs yksinkertainen esimerkki hajautetun laskennan mallista on synkroninen hajautettu järjestelmä (ks. esim. Lynch 1996, luku 2). Tällöin kunkin kommunikointikierroksen aikana suoritetaan seuraavat vaiheet:

1. Kukin solmu suorittaa paikallista laskentaa.
2. Kukin solmu lähettää viestin kullekin naapurisolmulleen verkossa G.
3. Viestit etenevät verkon kaaria pitkin vastaanottajille.
4. Kukin verkon solmu lukee samaansa viestit.

Oleellista on myös se, mitä tietoa solmuilla on käytettävissään alkutilanteessa. Usein oletetaan, että kullekin solmulle on annettu yksilöllinen tunniste.

Hajautetun algoritmin analysoinnissa kiinnitetään huomiota nimenomaan kommunikointiin. Algoritmin aikavaatimus voidaan ilmoittaa esimerkiksi synkronisten kommunikointikierrosten lukumääränä (Peleg 2000, luku 2.3, malli ”LOCAL”).

Jos solmuilla on yksilölliset tunnisteet ja jos aikavaatimusta mitataan synkronisten kommunikointikierrosten määrässä, useimmat laskennalliset ongelmat voidaan ratkaista triviaalisti ajassa O(|V|): kootaan tieto syötteestä yhteen solmuun, ratkaistaan ongelma perinteisellä keskitetyllä algoritmilla, ja välitetään lopuksi tieto ratkaisusta kullekin solmulle. Haasteelliseksi ongelmat muuttuvat esimerkiksi seuraavissa tapauksissa:

• Pyritään ratkaisemaan ongelma alilineaarisessa määrässä laskentakierroksia.
• Kiinnitetään huomiota kommunikointikierrosten määrän lisäksi myös viestien kokoon.
• Solmuilla ei ole yksilöllisiä tunnisteita.
• Halutaan tehdä algoritmista vikasietoinen.

Syksyn 2007 seminaarissa keskityttiin nimenomaan viimeiseen kohtaan, vikasietoisuuteen. Tämänkertaisessa seminaarissa tarkastellaan kolmea muuta kohtaa.

Suhde rinnakkaislaskentaan. On hyvä tehdä selvä ero hajautetun laskennan ja rinnakkaislaskennan välillä. Tässä rinnakkaislaskennalla tarkoitetaan laskennallisen ongelman ratkaisemista esim. monella suorittimella varustetulla tietokoneella tai PRAM-mallissa.

Oleellisimpia eroja hajautetun ja rinnakkaislaskennan välillä on se, että rinnakkaislaskennassa koko syöte on kaikkien suorittimien käsiteltävissä. Hajautetussa laskennassa puolestaan tiedon siirtäminen verkon laidalta toiselle kestää pitkään.

Hajautetussakin algoritmissa on toki usein paljonkin rinnakkaisuutta: eri solmut tekevät laskentaa samanaikaisesti tai vaihtavat keskenään viestejä samanaikaisesti. Tehokas hajautettu algoritmi tarjoaakin usein myös tehokkaan rinnakkaisalgoritmin. Toisaalta jotkin hajautetut algoritmit on esitetty alunperin rinnakkaislaskennan näkökulmasta.

Työmuodot

Ennen I periodin alkua jaetaan seminaaritöiden aiheet.

I periodin aikana kukin osallistuja perehtyy omaan aiheeseensa ja laatii aiheesta kirjoitelman. Kirjoitelman ulkoasun osalta noudatetaan samoja ohjeita kuin tieteellisen kirjoittamisen kurssilla ja pro gradu -töissä. Kirjoitelman pituus on kansilehti + tiivistelmäsivu + sisällysluettelo + 10–15 sivua. Kirjoitelma palautetaan sähköpostitse PDF-muotoisena tiedostona. Kirjoitelmien ensimmäiset versiot tulevat intranetiin kaikkien osallistujien luettavaksi ennen väliviikkoa.

I periodin aikana seminaarin vastuuhenkilö pitää muutaman esitelmän, joissa johdatellaan aihepiiriin ja myös kerrotaan alan tuoreesta tutkimuksesta.

II periodin aikana kukin osallistuja pitää yhden esitelmän kirjoitelmansa aiheesta. Esitelmän kesto on 35 minuuttia, tämän lisäksi on varattu 10 minuuttia kysymyksille ja keskustelulle. Esitelmässä käytettävät välineet voi valita itse niissä puitteissa, mitä seminaaritilassa on mahdollista. Esiintyjä itse huolehtii, että tekniikka on kunnossa ja esitelmä saadaan alkamaan ajallaan.

Aktiivinen osallistuminen esitelmien jälkeiseen keskusteluun on osa seminaarin suoritusta. Laitoksen seminaariohjeen mukaisesti hyväksyttävään suoritukseen vaaditaan läsnäolo vähintään 3/4 kokoontumiskerroista.

II periodin aikana osallistujat antavat myös vertaispalautetta muiden kirjoitelmista. Kukin laatii kirjallisen arvion kolmesta kirjoitelmasta; seminaarin vastuuhenkilö valitsee arvioijat. Vastuuhenkilö myös välittää arviot kirjoittajille anonyymeinä; kirjoittajat eivät saa tietää arvioijien nimiä. Arviossa on tarkoitus keskittyä erityisesti rakentavaan palautteeseen, joka auttaa kehittämään kirjoitelmaa. Arvio on paljasta tekstiä (ei siis esim. PDF-tiedosto).

II periodin lopussa palautetaan kirjoitelmista viimeistelty versio. Tässä versiossa on tarkoitus huomioida mm. vertaispalautteessa saadut kommentit ja esitelmien jälkeisessä keskustelussa esiin nousseet asiat. Viimeistellyt versiot palautetaan II periodin lopulla, ja ne tulevat intranetiin kaikkien osallistujien luettavaksi.

Kaikki em. osasuoritukset vaikuttavat arvosteluun.

Aiheluettelo

Tässä luettelossa on ehdotuksia seminaaritöiden aiheeksi. Luettelossa on yleensä annettu muutama keskeinen lähdeartikkeli kustakin aihepiiristä. Pääpaino on 1980- ja 1990-lukujen kuuluisilla tuloksilla; tuoreempaa työtä löytää esim. etsimällä artikkeleita, jotka viittaavat näihin klassisiin töihin.

Monissa tapauksissa alkuperäisartikkelien ideat ovat ehtineet muutaman vuosikymmenen aikana virtaviivaistua paljonkin. On hyvä lukea alkuperäisartikkelien ohella myös esim. tuoreita katsausartikkeleita, oppikirjoja (esim. Lynch 1996, Peleg 2000) ja luentomateriaaleja (esim. Wattenhofer 2009). Näistä löytyy myös hyvin lisäviitteitä.

Kaikkea luettelossa mainituista lähteistä löytyvää asiaa ei tietenkään ole tarvetta käsitellä seminaarikirjoitelmassa eikä varsinkaan esitelmässä. Joissain aiheissa (esim. B5) keskeinen haaste onkin valita oleellisimmat ja mielenkiintoisimmat asiat.

Luettelon järjestys vastaa suunniteltua esitysjärjestystä. Aihepiireissä A ja B keskitytään lähinnä synkronisiin järjestelmiin. Asynkronisten järjestelmien erityispiirteisiin tutustutaan aihepiirissä C.

0. Johdantoa hajautettuun päätöksentekoon.

Aihe 01: Informaation arvo hajautetussa päätöksenteossa.

• Papadimitriou ja Yannakakis (1991): yksinkertainen koordinointipeli, jossa on pakattava esineitä lokeroihin.

A. Verkon värittäminen ja riippumattomat joukot.

Aihe A1: Johdantoa ja sovelluksia.

• Työn on tarkoitus toimia johdantona aiheille A2–A4.
• Ongelmien esittely: verkon värittäminen ja maksimaaliset riippumattomat joukot.
• Mikä yhteys näillä ongelmilla on hajautettujen algoritmien näkökulmasta? Miten verkonväritysalgoritmia voi soveltaa maksimaalisten riippumattomien joukkojen etsimiseen? Entä päinvastoin?
• Miksi verkon värittäminen on keskeinen ongelma hajautettujen algoritmien alalla? Jos käytettävissä on algoritmi verkon värittämiseen (tai maksimaalisten riippumattomien joukkojen etsimiseen), mitä muita ongelmia voidaan tämän jälkeen ratkaista helposti?
• Ks. esim. Peleg (2000), luvut 7.1 ja 8.1–8.2; Luby (1986); Linial (1992), luku 5.

Aihe A2: Satunnaisalgoritmeja.

• Lynch (1996), luku 4.4. Peleg (2000), luku 8.4. Dubhashi ym. (2007), luvut 13.3 ja 13.4.1.
• Luby (1986): yksinkertainen satunnaisalgoritmi maksimaalisen riippumattoman joukon hakemiseen.
• Tyypillisesti satunnaisalgoritmit ovat kohtalaisen yksinkertaisia, mutta niiden analysointi vaatii jonkin verran todennäköisyyslaskennan tuntemista.

Aihe A3: Deterministisiä algoritmeja.

• Näissä algoritmeissa käytetään solmujen yksilöllisiä tunnisteita symmetrian rikkomiseen.
• Peleg (2000), luvut 7.2–7.4. Cormen ym. (1990), luku 30.5.
• Cole ja Vishkin (1986): esittelee tekniikan, jonka avulla voidaan 3-värittää n-sykli synkronisella algoritmilla ajassa O(log* n).
• Barenboim ja Elkin (2009): esimerkki viimeaikaisesta tutkimuksesta; paljon viitteitä aiempaan työhön.

Aihe A4: Mahdottomuustuloksia.

• Peleg (2000), luku 7.5.
• Linial (1992): keskeinen alarajatulos, joka osoittaa, että n-sykliä ei voi värittää synkronisella algoritmilla ajassa o(log* n). Vrt. kohdassa A3 mainittu vastaava ylärajatulos (Cole ja Vishkin 1986).
• Czygrinow ym. (2008): alarajatulos maksimikokoisen riippumattoman joukon approksimoinnille n-sykleissä.
• Tämä aihe on kohtalaisen matemaattinen.

B. Muita verkko-ongelmia.

Aihe B1: Virittävät puut.

• Pienimmän virittävän puun etsiminen.
• Lynch (1996), luvut 4.2 ja 4.4. Peleg (2000), luvut 5.5–5.6 ja 24. Dubhashi ym. (2007), luku 13.6.
• Gallager ym. (1983): ongelman ratkaiseminen yleisissä verkoissa.
• Lotker ym. (2003): esimerkki viimeaikaisesta työstä. Tässä ongelmaa tarkastellaan täydellisessä verkossa; yksi kommunikointikierros riittäisi tällöin ongelman ratkaisemiseen. Kiintoisaksi ongelma muuttuu, kun rajoitetaan solmujen välittämien viestien kokoa.

Aihe B2: Spannerit.

• Virittävien puiden lisäksi muunkinlaiset yhtenäiset, virittävät aliverkot ovat kiinnostavia. Verkon G virittävää aliverkkoa H sanotaan spanneriksi, jos lyhin polku minkä tahansa solmuparin välillä on verkossa H enintään vakiokertoimen verran pidempi kuin verkossa G. Ideana on se, että kommunikointi aliverkon H kaaria pitkin ei ole merkittävästi kalliimpaa kuin kommunikointi alkuperäisessä verkossa – virittävässä puussahan näin ei välttämättä ole. Yleensä kiinnostavaa on löytää mahdollisimman pieni spanneri: esimerkiksi spanneri, jossa on vähän kaaria ja jossa solmujen asteluvut ovat pieniä.

Aihe B3: Dominoivat joukot.

• Pienen dominoivan joukon etsiminen.
• Peleg (2000), luku 8.3. Dubhashi ym. (2007), luku 13.2.
• Kutten ja Peleg (1998): deterministinen algoritmi.
• Jia ym. (2002): satunnaistettu approksimointialgoritmi.

Aihe B4: Pariutukset.

• Suuren tai maksimaalisen pariutuksen etsiminen.
• Hańćkowiak ym. (2001). Panconesi ja Rizzi (2001).

Aihe B5: Verkon ositukset.

• Verkon jakaminen pienempiin aliverkkoihin (network decomposition). Verkon solmujen osittaminen (partition) ja ryvästäminen (clustering).
• Työssä on tarkoitus tarkastella kahta kysymystä: (1) ositusten löytäminen hajautetulla algoritmilla, ja (2) ositusten hyödyntäminen hajautetuissa algoritmeissa.
• Peleg (2000), luvut 11–14, 20–22 ja 25.2.
• Awerbuch ym. (1989). Awerbuch ja Peleg (1990).

Aihe B6: Verkko-ongelmat anonyymeissa verkoissa.

• Verkkoa sanotaan anonyymiksi, jos solmuilla ei ole yksilöllistä tunnistetta. Mitä tällaisessa verkossa voi laskea deterministisellä hajautetulla algoritmilla?
• Lynch (1996), luku 3.2.
• Angluin (1980). Yamashita ja Kameda (1996).

Aihe B7: Ei-approksimoituvuustuloksia.

• Kuhn ym. (2004).

C. Asynkroniset hajautetut järjestelmät.

Aihe C1: Aika asynkronisessa järjestelmässä.

• Asynkroniset hajautetut järjestelmät.
• Aika hajautetussa järjestelmässä. Kausaliteetti ja ajan suhteellisuus. Kellojen synkronointi.
• Lynch (1996), luku 18.
• Lamport (1978).

Aihe C2: Laskenta asynkronisessa järjestelmässä.

• Synkronisen hajautetun algoritmin simulointi asynkronisessa järjestelmässä.
• Lynch (1996), luku 16. Peleg (2000), luvut 6 ja 25.1.
• Awerbuch (1985).

D. Erilaisia hajautettuja järjestelmiä.

Aihe D1: Soluautomaatit hajautettujen algoritmien näkökulmasta.

• Soluautomaatit voi tulkita yksinkertaisiksi esimerkeiksi hajautetuista järjestelmistä.
• Soluautomaatissa laskenta etenee synkronisesti. Solmuilla ei ole yksilöllisiä tunnisteita. Verkko G on esim. ääretön kaksiulotteinen hila.
• Varsinainen hajautettu algoritmi on tässä tapauksessa sääntö, joka määrää solmun (”solun”) uuden tilan sen naapurien nykyisten tilojen perusteella.

Aihe D2: Lajitteluverkot.

• Lajitteluverkotkin voi tulkita hajautetuksi järjestelmäksi.
• Lajitteluverkkojen tutkimuksessa asetelma on kuitenkin päinvastainen kuin hajautettujen algoritmien tutkimuksessa: algoritmi on kiinnitetty ja tehtävänä on valita verkon G topologia.
• Lajitteluverkossa kukin solmu vertailee kahdelta naapuriltaan tulevia syötteitä ja järjestää ne suuruusjärjestykseen. Kiintoisa tutkimuskysymys on verkon G topologian valitseminen siten, että esim. verkon syvyys saadaan pidettyä pienenä.
• Cormen ym. (1990), luku 28, tai Cormen ym. (2001), luku 27: johdantoa aihepiiriin. Luvun lopussa lähdeviitteitä.
• Ajtai ym. (1983).

Muita aiheita. Osallistujat voivat ehdottaa myös omaa aihetta. Aiheita voi etsiä esimerkiksi alan viimeaikaisista konferenssijulkaisuista. Keskeisiä hajautettuihin algoritmeihin liittyviä konferensseja ovat PODC, SPAA ja DISC.

Seminaarin vastuuhenkilöltä voi myös kysellä ideoita paremmin omia mielenkiinnonkohteita vastaavista aiheista. Jos innostusta riittää, hajautettujen algoritmien piiristä löytyy myös laitoksella tehtävää tutkimusta sivuavia graduaiheita.

Lähteet

M. Ajtai, J. Komlós, E. Szemerédi (1983):
An O(n log n) sorting network,
Proc. STOC 1983.

D. Angluin (1980):
Local and global properties in networks of processors,
Proc. STOC 1980.

B. Awerbuch (1985):
Complexity of network synchronization,
Journal of the ACM, 32(4):804–823.

B. Awerbuch, A. V. Goldberg, M. Luby, S. A. Plotkin (1989):
Network decomposition and locality in distributed computation,
Proc. FOCS 1989.

B. Awerbuch, D. Peleg (1990):
Sparse partitions,
Proc. FOCS 1990.
Dijkstra-palkinto v. 2008.

L. Barenboim, M. Elkin (2009):
Distributed (Δ+1)-coloring in linear (in Δ) time,
Proc. STOC 2009.

R. Cole, U. Vishkin (1986):
Deterministic coin tossing with applications to optimal parallel list ranking,
Information and Control, 70(1):32–53.

T. H. Cormen, C. E. Leiserson, R. L. Rivest (1990):
Introduction to Algorithms. MIT Press.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2001):
Introduction to Algorithms. Second Edition. MIT Press.

A. Czygrinow, M. Hańćkowiak, W. Wawrzyniak (2008):
Fast distributed approximations in planar graphs,
Proc. DISC 2008.

D. Dubhashi, F. Grandoni, A. Panconesi (2007):
Distributed approximation algorithms via LP-duality and randomization, Teofilo F. Gonzalez (toim.): Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC.

R. G. Gallager, P. A. Humblet, P. M. Spira (1983):
A distributed algorithm for minimum-weight spanning trees,
ACM Transactions on Programming Languages and Systems, 5(1):66–77.
Dijkstra-palkinto v. 2004.

M. Hańćkowiak, M. Karoński, A. Panconesi (2001):
On the distributed complexity of computing maximal matchings,
SIAM Journal on Discrete Mathematics, 15(1):41–57.

L. Jia, R. Rajaraman, T. Suel (2002):
An efficient distributed algorithm for constructing small dominating sets,
Distributed Computing, 15(4):193–205.

F. Kuhn, T. Moscibroda, R. Wattenhofer (2004):
What cannot be computed locally!
Proc. PODC 2004.

S. Kutten, D. Peleg (1998):
Fast distributed construction of small k-dominating sets and applications,
Journal of Algorithms, 28(1):40–66.

L. Lamport (1978):
Time, clocks, and the ordering of events in a distributed system,
Communications of the ACM, 21(7):558–565.
PODC-palkinto v. 2000.

N. Linial (1992):
Locality in distributed graph algorithms,
SIAM Journal on Computing, 21(1):193–201.

Z. Lotker, E. Pavlov, B. Patt-Shamir, D. Peleg (2003):
MST construction in O(log log n) communication rounds,
Proc. SPAA 2003.

M. Luby (1986):
A simple parallel algorithm for the maximal independent set problem,
SIAM Journal on Computing, 15(4):1036–1055.

N. A. Lynch (1996):
Distributed Algorithms. Morgan Kaufmann.

A. Panconesi, R. Rizzi (2001):
Some simple distributed algorithms for sparse networks,
Distributed Computing, 14(2):97–100.

C. H. Papadimitriou, M. Yannakakis (1991):
On the value of information in distributed decision-making,
Proc. PODC 1991.

D. Peleg (2000):
Distributed Computing: A Locality-Sensitive Approach. SIAM.

R. Wattenhofer (2009):
Principles of distributed computing.

M. Yamashita, T. Kameda (1996):
Computing on anonymous networks:
Part I – Characterizing the solvable cases,
IEEE Transactions on Parallel and Distributed System, 7(1):69–89.

Sanastoa

Suomennoksia hajautettuihin algoritmeihin liittyville käsitteille.

Suomennoksia verkkoihin liittyville käsitteille. Lisää suomennoksia löytyy TKK:n verkkoteorian kurssin sanastosta.

Suomessa voi yleensä käyttää sujuvasti samaa sanaa ”verkko” sekä puhuttaessa tietoliikenneverkosta (communication network) että sen mallintamiseen käytettävästä matemaattisesta käsitteestä (graph).

Joidenkin varsin yleisten termien suomentaminen vaatii luovuutta:

• Sana ”input” kääntyy syötteeksi, mutta mitä on ”output” hajautettujen algoritmien yhteydessä? ”Tuloste” on tavallinen käännös perinteisten algoritmien yhteydessä, mutta tuntuu oudolta tässä yhteydessä.
• Verkkoteorian termille ”line graph” ei taida olla mitään vakiintunutta suomennosta. Käännöstä ”kaariverkko” voinee harkita, mutta se on syytä selittää.
• Sanalle ”spanner” en ole yrittänytkään keksiä muuta suomennosta kuin ”spanneri”.