Täs­tä klik­kaa­mal­la saat en­sim­mäi­sen pro­to­kol­lan ra­ken­teen pa­lau­te­laa­tik­koon.

Teh­tä­vä:
Vuo­rot­te­le­van bi­tin pro­to­kol­la

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Täs­sä teh­tä­väs­sä tu­tus­tu­taan pik­kui­sen sii­hen, mi­ten vai­keaa on suun­ni­tel­la luo­tet­ta­via tie­to­lii­ken­ne­jär­jes­tel­miä, ja mi­ten ää­rel­li­set au­to­maa­tit voi­vat ol­la sii­nä avuk­si. Tar­vi­taan pal­jon muu­ta­kin kuin mi­tä täs­sä ker­ro­taan, jo­ten tä­mä teh­tä­vä an­taa asias­ta liian yk­sin­ker­tai­sen ku­van. Täs­sä esi­tet­tä­vät asiat an­ta­vat kui­ten­kin suun­taa.

  1. Huo­no tie­to­lii­ken­ne­pro­to­kol­la
  2. Vuo­rot­te­le­va bit­ti
  3. Ikui­sen sil­mu­kan vält­tä­mi­nen
  4. Lo­puk­si

Huo­no tie­to­lii­ken­ne­pro­to­kol­la

[huo­non pro­to­kol­lan ra­ken­ne] Ohei­nen ku­va ha­vain­nol­lis­taa yh­tä pe­rus­on­gel­maa, jo­ka tie­to­lii­ken­ne­jär­jes­tel­mien suun­nit­te­li­joi­den on täy­ty­nyt rat­kais­ta. Ta­voit­tee­na on vä­lit­tää vies­te­jä ku­van va­sem­mas­ta reu­nas­ta oi­keaan reu­naan. Ku­vas­sa on esi­mer­kin vuok­si kah­ta eri vies­tiä: a ja b. Lä­he­tys­pai­kas­ta vas­taan­ot­to­paik­kaan on epä­luo­tet­ta­va ka­na­va (ku­vas­sa D), jo­ka toi­si­naan vä­lit­tää vies­tin pe­ril­le kun­nol­la, mut­ta toi­si­naan vää­ris­tää sen tai huk­kaa ko­ko­naan. Esi­mer­kik­si sa­la­man­is­ku voi häi­ri­tä se­kä kaa­pe­leis­sa et­tä ra­dio­teit­se kul­ke­via vies­te­jä. Myös vas­tak­kai­seen suun­taan on epä­luo­tet­ta­va ka­na­va (ku­vas­sa K).

Täs­sä teh­tä­väs­sä kä­si­tel­lään vies­tien ka­toa­mi­sen on­gel­maa. Vies­tien vää­ris­ty­mi­sen va­ral­le on ke­hi­tet­ty omat, täy­sin toi­sen­lai­set tek­niik­kan­sa. On myös mui­ta on­gel­mia, joil­le on omat rat­kai­sun­sa. Esi­mer­kik­si In­ter­ne­tis­sä vies­ti pil­ko­taan osiin, jot­ka saat­ta­vat kul­kea eri reit­te­jä. Ne voi­vat saa­pua pe­ril­le vää­räs­sä jär­jes­tyk­ses­sä. Täs­sä teh­tä­väs­sä ole­te­taan, et­tä ka­na­vas­sa vies­tit voi­vat ka­do­ta, mut­ta mi­tään muu­ta epä­toi­vot­tua niil­le ei voi siel­lä ta­pah­tua. Ne ei­vät esi­mer­kik­si vää­ris­ty, kah­den­nu tai tu­le pe­ril­le vää­räs­sä jär­jes­tyk­ses­sä.

[kuit­taus­ka­na­va il­man vuo­rot­te­le­vaa bit­tiä] Ohei­nen ku­va näyt­tää ka­na­van K NFA:na. Saa­tuaan vies­tin ta­pah­tu­mal­la kV se jo­ko an­taa sen eteen­päin ta­pah­tu­mal­la kK tai huk­kaa sen siir­ty­mäl­lä ta­kai­sin al­ku­ti­laan ε-kaar­ta pit­kin. Al­la on sa­ma NFA syö­tet­ty­nä Math­Checkil­le si­ten vää­rin, et­tä mu­ka­na on yk­si kaa­ri lii­kaa. Kos­ka Math­Check tul­kit­see isot kir­jai­met ti­lo­jen ni­mik­si, ta­pah­tu­mat on kir­joi­tet­tu pie­nil­lä kir­jai­mil­la. Jot­ta ta­pah­tu­mien ni­met erot­tui­si­vat toi­sis­taan pit­kis­sä jo­nois­sa, nii­hin on lai­tet­tu lop­puun pis­te. Ko­kei­le en­sin val­mis­ta vas­taus­ta. Sit­ten pois­ta yli­mää­räi­nen kaa­ri ja ko­kei­le uu­del­leen.

tai

Mil­tä ka­na­va D näyt­tää NFA:na? Mie­ti en­sin it­se ja vaik­ka piir­rä pa­pe­ril­le, tai voit kir­joit­taa sen al­la ole­vaan vas­taus­ruu­tuun. Sit­ten kat­so vas­taus täs­tä[da­ta­ka­na­va il­man vuo­rot­te­le­vaa bit­tiä].

tai

Lä­he­tys­pai­kas­sa si­jait­se­va käyt­tä­jä lä­het­tää vies­tin mat­kaan ta­pah­tu­mal­la a tai b. Lä­he­tys- ja vas­taan­ot­to­pai­kas­sa on oh­jel­mat L ja V, jot­ka kes­kus­te­le­vat kes­ke­nään ka­na­vien D ja K vä­li­tyk­sel­lä vies­tien vä­lit­tä­mi­sek­si luo­tet­ta­vas­ti vas­taan­ot­ta­val­le käyt­tä­jäl­le. Jär­jes­tel­mä luo­vut­taa vies­tin sil­le ta­pah­tu­mal­la aV tai bV. Har­maa laa­tik­ko edel­lä ol­lees­sa ku­vas­sa il­mai­see si­tä, et­tä käyt­tä­jät nä­ke­vät vain nä­mä nel­jä ta­pah­tu­maa a, b, aV ja bV. Tä­tä nä­kö­kul­maa kut­su­taan jär­jes­tel­män tuot­ta­mak­si pal­ve­luk­si.

Olet­taen, et­tä vies­te­jä voi ol­la mat­kal­la ker­ral­laan enin­tään yk­si, esi­tä ihan­teel­li­sen jär­jes­tel­män tuot­ta­ma pal­ve­lu NFA:na. vas­taus[ihan­teel­li­nen pal­ve­lu, ka­pa­si­teet­ti 1]

tai

Olet­taen, et­tä vies­te­jä voi ol­la mat­kal­la ker­ral­laan enin­tään kak­si, esi­tä ihan­teel­li­sen jär­jes­tel­män tuot­ta­ma pal­ve­lu NFA:na. Täs­sä vai­hees­sa pal­jas­tan ki­kan, jol­la voit sääs­tää vai­vo­ja­si: jos ti­la ei ole lop­pu­ti­la, ja sii­hen tu­lee ja sii­tä läh­tee vain yk­si kaa­ri, voit jät­tää an­ta­mat­ta sil­le ni­men ja sen si­jaan kir­joit­taa t.l.S, mis­sä t. on tu­le­van kaa­ren ni­mi, l. on läh­te­vän kaa­ren ni­mi ja S on seu­raa­van ti­lan ni­mi. Math­Check sal­lii mui­ta­kin ly­hen­nys­temp­pu­ja, mut­ta jos nii­tä käyt­tää ko­vin pal­jon, niin saat­taa hä­mär­tyä min­kä­lai­nen NFA syn­tyy. vas­taus[ihan­teel­li­nen pal­ve­lu, ka­pa­si­teet­ti 2]

tai

Ka­na­vaa D kut­su­taan da­ta­ka­na­vak­si. Kun L on saa­nut lä­het­tä­väl­tä käyt­tä­jäl­tä vies­tin a tai b, se lä­het­tää sen da­ta­ka­na­vaa pit­kin ta­pah­tu­mal­la aL tai bL. Jos da­ta­ka­na­va ei huk­kaa si­tä, se tu­lee V:lle ta­pah­tu­mal­la aD tai bD, jon­ka jäl­keen V an­taa sen vas­taan­ot­ta­val­le käyt­tä­jäl­le ta­pah­tu­mal­la aV tai bV.

Vies­tien ka­toa­mi­sen va­ral­ta käy­te­tään kuit­taus­ta ja tar­vit­taes­sa uu­del­leen­lä­he­tys­tä. V lä­het­tää jo­kai­ses­ta L:ltä saa­mas­taan vies­tis­tä vas­taus­vies­tin ka­na­vaa K pit­kin. Tä­tä vies­tiä sa­no­taan kuit­tauk­sek­si. Lä­he­tet­tyään vies­tin L odot­taa kuit­taus­ta jon­kin ai­kaa. Jol­lei kuit­taus saa­vu si­nä ai­ka­na, L lä­het­tää vies­tin uu­del­leen ja al­kaa taas odot­taa kuit­taus­ta. Esi­tä L NFA:na. vas­taus[lä­he­tin il­man vuo­rot­te­le­vaa bit­tiä]

tai

Esi­tä V NFA:na. vas­taus[vas­taan­otin il­man vuo­rot­te­le­vaa bit­tiä]

tai

Tä­män­kal­tais­ta sään­nös­töä, jo­ka ker­too mi­ten eril­lis­ten osien on teh­tä­vä yh­teis­työ­tä, kut­su­taan pro­to­kol­lak­si. Käym­me nyt lä­pi esi­mer­kin pro­to­kol­lam­me toi­min­nas­ta. Jot­ta si­nun oli­si hel­pom­pi seu­ra­ta mi­tä ta­pah­tuu, täs­tä klik­kaa­mal­la saat L:n, D:n, V:n ja K:n NFA:t se­kä yleis­ra­ken­teen nä­ky­viin pa­lau­te­laa­tik­koon. Jär­jes­tel­män ti­lat il­moi­te­taan nel­jäl­lä nu­me­rol­la jär­jes­tyk­ses­sä L:n ti­la, D:n ti­la, V:n ti­la ja K:n ti­la. Esi­mer­kik­si jos L on al­ku­ti­las­saan, D on oi­keas­sa reu­nas­sa, V on ala­reu­nas­sa ja K on oi­keas­sa reu­nas­sa, niin ti­la on 1342.

Aluk­si kaik­ki ovat ti­las­sa 1 eli ko­ko jär­jes­tel­män ti­la on 1111. Kir­joi­ta pa­pe­ril­le tai teks­ti­tie­dos­toon ”1111”. Ta­pah­tu­ma a siir­tää L:n ti­las­ta 1 ti­laan 2. Kos­ka a ei ole mui­den osien aak­kos­tois­sa, ne py­sy­vät ti­las­sa 1. Sik­si jär­jes­tel­män ti­la on nyt 2111. Kir­joi­ta ”a 2111”, niin et­tä kaik­kiaan lu­kee ”1111 a 2111”, ja jat­ka kir­joit­ta­mis­ta esi­mer­kin ete­ne­mi­sen mu­kaan. Seu­raa­vak­si aL siir­tää L:n ti­las­ta 2 ti­laan 3 ja D:n ti­las­ta 1 ti­laan 2 mui­den osien py­syes­sä pai­koil­laan. Jär­jes­tel­män ti­la on nyt 3211.

Nyt on kol­me vaih­to­eh­toa mi­tä voi ta­pah­tua seu­raa­vak­si: aD vie ti­laan 3121, εL vie ti­laan 2211 (Käy­täm­me ala­in­dek­siä ker­to­maan, min­kä osan ε-kaa­res­ta on ky­se.) tai εD vie ti­laan 3111. Uu­del­leen­lä­he­tyk­sen ha­vain­nol­lis­ta­mi­sek­si va­lit­sem­me niis­tä vii­mek­si mai­ni­tun. Seu­raa­vak­si εL vie ti­laan 2111, jos­sa on jo ol­tu. Nyt­kin aL vie ti­laan 3211. Täs­tä jat­kam­me si­ten, et­tä sa­no­ma pää­see pe­ril­le, sii­tä lä­he­te­tään kuit­taus ja se­kin pää­see pe­ril­le ja lue­taan. Siis seu­raa­vat ta­pah­tu­mat ja ti­lat ovat aD 3121 aV 3141 kV 3112 kK 1111.

Pa­pe­ril­la tai tie­dos­tos­sa pi­täi­si lu­kea tä­mä1111 a 2111 aL 3211 εD 3111 εL 2111 aL 3211 aD 3121 aV 3141 kV 3112 kK 1111. Kun sii­tä poi­mi­taan käyt­tä­jil­le nä­ky­vät ta­pah­tu­mat eli jouk­koon {a, b, aV, bV} kuu­lu­vat ta­pah­tu­mat, saa­daan a aV. Siis yk­si a lä­he­tet­tiin, se me­ni yh­te­nä kap­pa­lee­na pe­ril­le, ja jär­jes­tel­mä pa­la­si al­ku­ti­laan. Tä­mä on toi­vot­tua käyt­täy­ty­mis­tä.

Tar­kas­te­lem­me seu­raa­vak­si ti­lo­jen ja ta­pah­tu­mien jo­noa 1111 b 4111 bL 5311 bD 5131 bV 5141 kV 5112 εK 5111 εL 4111 bL 5311 bD 5131 bV 5141 kV 5112 kK 1111. Sii­tä poi­mit­tu käyt­tä­jil­le nä­ky­vien ta­pah­tu­mien jo­no on tä­mäb bV bV. On­ko se toi­vot­tua käyt­täy­ty­mis­tä? vas­tausEi ole. Yh­teen ker­taan lä­he­tet­ty b tu­li pe­ril­le kah­te­na.

Pro­to­kol­la voi myös jää­dä ikui­seen sil­muk­kaan täl­lä1111 a 2111 aL 3211 εD 3111 εL 2111 aL 3211 εD 3111 εL 2111 aL 3211 εD 3111 εL 2111 … ta­val­la. Lu­vus­sa Ikui­sen sil­mu­kan vält­tä­mi­nen mie­tim­me, mi­tä täl­le voi teh­dä.

Pro­to­kol­la voi jo­pa ede­tä al­ku­ti­las­ta al­ku­ti­laan si­ten, et­tä lä­he­tet­ty­jen vies­tien jou­kos­sa on yk­si b, mut­ta yh­tään b:tä ei tu­le pe­ril­le. Mi­ten? vas­taus1111 a 2111 aL 3211 aD 3121 aV 3141 εL 2141 aL 3241 kV 3212 kK 1211 aD 1121 aV 1141 b 4141 bL 5341 εD 5141 kV 5112 kK 1111.

Seu­raa­vis­sa lu­vuis­sa kor­jaam­me nä­mä viat.

Vuo­rot­te­le­va bit­ti

Jos L:n lä­het­tä­mä vies­ti saa­vut­taa V:n mut­ta V:n ta­kai­sin­päin lä­het­tä­mä kuit­taus ka­toaa tai vii­väs­tyy, L ei saa tie­toa vies­tin pe­ril­le­me­nos­ta ja sik­si lä­het­tää sen uu­del­leen. Jos myös uu­si lä­he­tys me­nee V:lle saak­ka, edel­li­sen lu­vun V an­taa myös sen käyt­tä­jäl­le, jol­loin käyt­tä­jä saa sa­man vies­tin kah­des­ti. Tä­män es­tä­mi­sek­si V:lle täy­tyy an­taa jo­kin kei­no erot­taa, on­ko L:ltä tul­lut vies­ti uu­si vies­ti vai ai­kai­sem­man vies­tin uu­del­leen­lä­he­tys.

Vuo­rot­te­le­van bi­tin pro­to­kol­las­sa tä­mä teh­dään vuo­rot­te­le­val­la bi­til­lä (alternating bit). L liit­tää jo­kai­seen V:lle lä­het­tä­mään­sä vies­tiin yli­mää­räi­sen bi­tin, jon­ka ar­vo on 0 tai 1. Al­ku­pe­räi­seen vies­tiin lii­tet­tä­vän bi­tin ar­vo on eri kuin edel­li­seen al­ku­pe­räi­seen vies­tiin lii­te­tyn bi­tin ar­vo, ja uu­del­leen lä­he­tet­tä­vään vies­tiin lii­tet­tä­vän bi­tin ar­vo on sa­ma kuin sa­man vies­tin en­sim­mäi­seen lä­he­tyk­seen lii­te­tyn bi­tin ar­vo. V muis­taa vii­mek­si käyt­tä­jäl­le vä­lit­tä­mään­sä vies­tiin lii­te­tyn bi­tin ar­von, ja sen pe­rus­teel­la vält­tää vä­lit­tä­mäs­tä sa­man vies­tin toi­seen ker­taan. Myö­hem­min kä­si­tel­tä­väs­tä syys­tä myös kuit­tauk­siin lii­te­tään bit­ti, jon­ka ar­vo on sa­ma kuin kui­ta­tun vies­tin bi­tin. Aluk­si vuo­rot­te­le­van bi­tin ar­vo on 0.

Esi­tä L NFA:na. vas­taus[vuo­rot­te­le­van bi­tin pro­to­kol­lan lä­he­tin]

tai

Mi­kä me­ni­si pie­leen, jos V ei lä­het­täi­si kuit­tauk­sia niis­tä L:n lä­het­tä­mis­tä vies­teis­tä, jois­sa on vää­rä bi­tin ar­vo? vas­tausL lä­het­täi­si sa­maa vies­tiä uu­del­leen lo­put­to­mas­ti, kos­ka ei kos­kaan sai­si kuit­taus­ta sil­lä bi­tin ar­vol­la, jo­ta se odot­taa. Pro­to­kol­la pyö­ri­si hyö­dyt­tö­mäs­sä sil­mu­kas­sa ikui­ses­ti.

Esi­tä V NFA:na. vas­taus[vuo­rot­te­le­van bi­tin pro­to­kol­lan vas­taan­otin]

tai

Täs­tä klik­kaa­mal­la saat L:n, D:n, V:n ja K:n nä­ky­viin. Tä­mä pro­to­kol­la on yk­si­suun­tai­nen vuo­rot­te­le­van bi­tin pro­to­kol­la. Vuo­rot­te­le­van bi­tin pro­to­kol­lan (kak­si­suun­tai­seen tie­don­siir­toon so­vel­let­tu­na) jul­kai­si­vat K.A. Bartlett, R.A. Scantlebury ja P.T. Wilkinson vuon­na 1969. Al­ku­pe­räis­jul­kai­su ja leh­den sii­hen sa­mal­la jul­kai­se­ma pa­lau­te ovat yh­teen­sä vain 3 si­vua pit­kät. Ne löy­ty­vät tääl­tä.

Jol­lei kuit­tauk­sis­sa oli­si vuo­rot­te­le­vaa bit­tiä, pro­to­kol­la huk­kai­si sa­no­mia. Sen osoit­ta­mi­sek­si kor­vaam­me kV0:n ja kV1:n kV:llä se­kä kK0:n ja kK1:n kK:lla, ja käy­täm­me K:sta vain ti­lo­ja 1 ja 2. An­na esi­merk­ki ti­lo­jen ja ta­pah­tu­mien jo­nos­ta, jo­ka vie al­ku­ti­las­ta al­ku­ti­laan, jos­sa ta­pah­tuu ai­na­kin yk­si b, ja jos­sa ei tu­le pe­ril­le yh­tään bV:tä. vih­je 1Lu­vun 1 lo­pus­sa näy­tet­tiin, mi­ten b voi­daan hu­ka­ta. vih­je 2Kun pro­to­kol­la on hu­kan­nut b:n, lä­he­tä a:ta ja väl­tä ε-kaa­ria, niin pro­to­kol­la pää­tyy lo­pul­ta al­ku­ti­laan­sa. vas­taus1111 a 2111 aL0 3211 aD0 3121 aV 3141 εL 2141 kV 2152 aL0 3252 kK 6251 aD0 6141 b 9141 bL1 (10)541 εD (10)141 kV (10)152 kK 1151 a 2151 aL0 3251 aD0 3141 kV 3152 kK 6151 a 7151 aL1 8451 aD1 8161 aV 8181 kV 8112 kK 1111

[ihan­teel­li­nen pal­ve­lu, ka­pa­si­teet­ti 1] Jos kuit­tauk­sis­sa on vuo­rot­te­le­va bit­ti, niin pro­to­kol­lan tuot­ta­ma pal­ve­lu on ohei­sen NFA:n mu­kai­nen. Niin­pä sil­tä osin kuin asiaa voi tut­kia ää­rel­li­sil­lä au­to­maa­teil­la, tä­mä pro­to­kol­la on vir­hee­tön. Se on to­det­tu se­kä au­to­maat­ti­ses­ti et­tä ih­mis­voi­min päät­te­le­mäl­lä.

Ku­va ei kui­ten­kaan ker­ro ko­ko to­tuut­ta, sil­lä NFA:t ei­vät pys­ty pal­jas­ta­maan kai­ken­lai­sia vir­hei­tä. Ne ei­vät huo­maa vir­hei­tä, jois­sa ulos ei tu­le mi­tään vää­rää, mut­ta oi­keat vies­tit lak­kaa­vat kul­ke­mas­ta. Lu­vus­sa Huo­no tie­to­lii­ken­ne­pro­to­kol­la esi­tet­ty pro­to­kol­la saat­taa jää­dä ikui­seen sil­muk­kaan. Vuo­rot­te­le­van bi­tin pro­to­kol­la on al­tis sa­mal­le on­gel­mal­le. Seu­raa­vas­sa lu­vus­sa rat­kai­sem­me sen niin hy­vin kuin sen voi rat­kais­ta. Si­tä en­nen päät­te­lem­me, mik­si vuo­rot­te­le­van bi­tin pro­to­kol­la ei kos­kaan an­na ulos vää­rää vies­tiä.

L:ssä on ko­ko ajan vuo­rot­te­le­va bit­ti. D:ssä jo­ko ei ole mi­tään tai on yk­si vies­ti, jos­sa on vuo­rot­te­le­va bit­ti. V:ssä on ko­ko ajan vuo­rot­te­le­va bit­ti. K:ssä jo­ko ei ole mi­tään tai on yk­si vies­ti, jos­sa on vuo­rot­te­le­va bit­ti. Osoi­tam­me, et­tä näi­den bit­tien muo­dos­ta­mas­sa jo­nos­sa on ko­ko ajan kor­kein­taan yk­si epä­tyh­jä koh­ta, jos­sa bi­tin ar­vo on eri kuin edel­li­ses­sä epä­tyh­jäs­sä koh­das­sa. Jo­no voi ol­la esi­mer­kik­si 1100, 0ε00 tai 0ε1ε (ε tar­koit­taa tyh­jää ka­na­vaa), mut­ta ei voi ol­la 1101 ei­kä 010ε.

Lau­se 1 L:n, D:n (jos epä­tyh­jä), V:n ja K:n (jos epä­tyh­jä) bit­tien muo­dos­ta­ma jo­no on ko­ko ajan muo­toa 0⋯0, 0⋯01⋯1, 1⋯1 tai 1⋯10⋯0.

To­dis­tus. Käy­täm­me in­va­riant­ti­päät­te­lyä, eli osoi­tam­me, et­tä väi­te on voi­mas­sa aluk­si, ei­kä mi­kään, mi­tä pro­to­kol­la te­kee, voi saa­da väi­tet­tä pois voi­mas­ta.

Aluk­si jo­no on 0ε0ε.

D:n, V:n ja K:n NFA:is­ta on help­po kat­soa, et­tä mi­kään niis­tä ei kos­kaan vä­li­tä vies­tiä eteen­päin eri bit­ti­ar­vol­la kuin oli vii­mei­sim­mäs­sä sen saa­mas­sa vies­tis­sä. L ot­taa uu­den bit­ti­ar­von käyt­töön vas­ta kun se on saa­nut K:sta kuit­tauk­sen edel­li­sel­lä bit­ti­ar­vol­la. Juu­ri en­nen kuin L lu­kee tä­män kuit­tauk­sen, L:n ja K:n bit­ti­ar­vot ovat sa­mat.

Jos jo­nos­sa oli­si sil­lä het­kel­lä mo­lem­pia bit­ti­ar­vo­ja, sii­nä oli­si se­kä koh­ta, jos­sa 0:n pe­räs­sä on 1 et­tä koh­ta, jos­sa 1:n pe­räs­sä on 0. Kos­ka tar­koi­tuk­sem­me on osoit­taa, et­tä L:n toi­min­to ei voi saa­da väi­tet­tä pois voi­mas­ta, meil­lä on lu­pa olet­taa, et­tä väi­te on sil­lä het­kel­lä voi­mas­sa. Sik­si jo­nos­sa ei voi ol­la kah­ta vaih­dos­koh­taa, jo­ten jo­nos­sa on vain yh­tä bit­ti­ar­voa. Kun L ot­taa uu­den bit­ti­ar­von käyt­töön, syn­tyy yk­si vaih­dos­koh­ta, mut­ta edel­lä mai­ni­tus­ta syys­tä se on jo­non ai­noa. □ 

Olem­me osoit­ta­neet, et­tä jo­nos­sa on kor­kein­taan yk­si koh­ta, jos­sa bi­tin ar­vo vaih­tuu. Seu­raa­vak­si päät­te­lem­me tä­tä hyö­dyn­täen, et­tä pro­to­kol­la ei kos­kaan an­na ulos vää­rää vies­tiä.

Lau­se 2 V an­taa kun­kin al­ku­pe­räi­sen vies­tin ulos kor­kein­taan ker­ran, ja jos al­ku­pe­räi­nen vies­ti huk­kuu, niin V ei an­na enää mi­tään ulos.

To­dis­tus. L kä­sit­te­lee käyt­tä­jäl­tä saa­man­sa vies­tit yh­den ker­ral­laan. L ei ota seu­raa­vaa vies­tiä kä­sit­te­lyyn en­nen kuin edel­li­nen on kä­si­tel­ty. Kun­kin vies­tin L kä­sit­te­lee seu­raa­vas­ti. L lä­het­tää sen ker­taal­leen ja sen jäl­keen uu­del­leen ja uu­del­leen, kun­nes L saa kuit­tauk­sen sa­mal­la bit­ti­ar­vol­la.

Jos yk­si­kään L:n lä­het­tä­mä vies­tin ko­pio ei saa­vu V:lle, pro­to­kol­la jää ikui­seen sil­muk­kaan, jos­sa ei ta­pah­du mi­tään hyö­dyl­lis­tä. Täs­sä ta­pauk­ses­sa vies­ti ka­toaa, mut­ta V ei kui­ten­kaan an­na ulos mi­tään vää­rää, kos­ka se ei an­na ulos enää mi­tään.

Jos ai­na­kin yk­si niis­tä saa­puu V:lle, niin V vä­lit­tää käyt­tä­jäl­le niis­tä en­sim­mäi­sen, jon­ka se saa, ja vain sen. Täs­sä ta­pauk­ses­sa vies­ti tu­lee käyt­tä­jäl­le oi­kein ja vain yh­te­nä kap­pa­lee­na. Sen jäl­keen pro­to­kol­la jo­ko jää ikui­seen sil­muk­kaan jos­sa käyt­tä­jäl­le ei an­ne­ta enää mi­tään (kuin­ka?)Näin käy jos kaik­ki kuit­tauk­set hä­viä­vät, tai kaik­ki tai yh­tä vail­le kaik­ki da­ta­vies­tit hä­viä­vät, yh­tä vail­le kaik­ki kuit­tauk­set hä­viä­vät, ja L ei lue si­tä yh­tä vaan siir­tyy ai­na uu­del­leen­lä­he­tyk­seen., tai siir­tyy ti­laan, jos­sa se on val­mis seu­raa­van vies­tin vä­lit­tä­mi­seen.

On help­po näh­dä, et­tä pro­to­kol­la ei voi jou­tua ti­lan­tee­seen, mis­sä yk­si­kään osa ei voi teh­dä mi­tään. Jos D ei ole ti­las­sa 1, niin se voi siir­tyä ε-kaar­ta pit­kin ti­laan 1. Jos L on ti­las­sa 1 tai 6, niin se voi teh­dä a:n ja b:n. Jos se on ti­las­sa 2, 4, 7 tai 9, niin jo­ko D ei ole ti­las­sa 1, jol­loin D voi teh­dä jo­ta­kin; tai L voi teh­dä aL0:n, bL0:n, aL1:n tai bL1:n. Jos L on ti­las­sa 3, 5, 8 tai 10, niin L voi siir­tyä ε-kaar­ta pit­kin.

Ikui­sen sil­mu­kan vält­tä­mi­nen

Jos jom­pi­kum­pi ka­na­va on kauan poik­ki ja jo­kin vies­ti on vä­lit­tä­mät­tä, niin vuo­rot­te­le­van bi­tin pro­to­kol­la pyö­rii sil­mu­kas­sa kun­nes yh­teys taas toi­mii. Useis­sa so­vel­luk­sis­sa oli­si pa­rem­pi, et­tä L an­tai­si pe­rik­si muu­ta­man lä­he­tys­yri­tyk­sen jäl­keen ja an­tai­si lä­het­tä­väl­le käyt­tä­jäl­le vir­he­il­moi­tuk­sen. Sik­si ke­hi­täm­me mo­ni­mut­kai­sem­man pro­to­kol­lan li­sää­mäl­lä ta­pah­tu­mat ok ja err, joil­la L ker­too käyt­tä­jäl­le, sai­ko se kuit­tauk­sen vai luo­vut­ti­ko.

Kun L on pa­laut­ta­nut err ja myö­hem­min tu­lee uu­si a tai b, kum­paa vuo­rot­te­le­van bi­tin ar­voa L:n tu­lee käyt­tää sil­le? vas­tausKum­pi­kaan vaih­to­eh­to ei toi­mi ai­na oi­kein. Olet­ta­kaam­me, et­tä edel­li­nen vies­ti lä­he­tet­tiin bi­tin ar­vol­la 0 ja et­tä 0 oli sii­nä ti­lan­tees­sa oi­kea ar­vo. Jos se ei kos­kaan saa­pu­nut V:lle as­ti, niin mi­tä V te­kee saa­des­saan seu­raa­vak­si vies­tin bi­tin ar­vol­la 0? En­tä bi­tin ar­vol­la 1? Kat­so jat­ko­vas­taus 1. Jos se saa­pui V:lle as­ti, niin mi­tä V te­kee saa­des­saan seu­raa­vak­si vies­tin bi­tin ar­vol­la 0? En­tä bi­tin ar­vol­la 1? Kat­so jat­ko­vas­taus 2. jat­ko­vas­taus 1Kos­ka 0 oli oi­kea bi­tin ar­vo edel­lis­tä vies­tiä lä­he­tet­täes­sä, V odot­ti sil­loin vies­tiä bi­tin ar­vol­la 0. Kos­ka sel­lais­ta ei tul­lut, V odot­taa yhä vies­tiä bi­tin ar­vol­la 0. Sel­lai­sen se vä­lit­tää käyt­tä­jäl­le ja bi­tin ar­vol­la 1 va­rus­tet­tua vies­tiä ei vä­li­tä. Mo­lem­mis­sa ta­pauk­sis­sa se kui­ten­kin lä­het­tää kuit­tauk­sen sil­lä bi­tin ar­vol­la, jo­ka vies­tis­sä oli, jot­ta L sai­si tie­don, et­tä sen uu­del­leen lä­het­tä­mis­tä ei tar­vit­se jat­kaa. jat­ko­vas­taus 2Kos­ka V sai edel­li­sen vies­tin, V odot­taa seu­raa­vak­si vies­tiä bi­tin ar­vol­la 1. Niin­pä V kä­sit­te­lee nol­lan ja yk­kö­sen päin­vas­toin kuin edel­li­ses­sä vas­tauk­ses­sa: vä­lit­tää 1-vies­tin käyt­tä­jäl­le mut­ta 0-vies­tiä ei vä­li­tä.

Tä­mä on­gel­ma rat­keaa ot­ta­mal­la käyt­töön yh­teys­pyyn­tö­vies­tit y0 ja y1, jois­sa on vuo­rot­te­le­va bit­ti, mut­ta ei hyö­ty­kuor­maa. V ei vä­li­tä kum­mas­ta­kaan mi­tään käyt­tä­jäl­le ja vas­taa mo­lem­piin kuit­tauk­sel­la, jos­sa on sa­ma bi­tin ar­vo. Kun L ei tie­dä kum­paa bi­tin ar­voa sen pi­täi­si käyt­tää, se lä­het­tää yh­teys­pyyn­tö­vies­tin vii­mek­si käyt­tä­mäl­lään bi­tin ar­vol­la. Jos sii­hen tu­lee kuit­taus, L vaih­taa bi­tin ar­voa ja lä­het­tää da­ta­vies­tin.

Kos­ka häi­riöt voi­vat ol­la ti­la­päi­siä, saat­taa ol­la edul­lis­ta lait­taa L lä­het­tä­mään yh­tey­den­pyyn­tö­vies­ti muu­ta­maan ker­taan en­nen luo­vut­ta­mis­ta. Vas­taa­vas­ti jos yh­teys saa­daan, L:n kan­nat­taa lä­het­tää da­ta­vies­ti muu­ta­maan ker­taan en­nen luo­vut­ta­mis­ta. Piir­räm­me ku­viin kui­ten­kin vain yh­den yri­tyk­sen kum­mas­ta­kin, jot­ta ku­vis­ta ei tu­li­si liian iso­ja. Sa­mas­ta syys­tä käy­täm­me täs­sä lu­vus­sa vain yh­tä vies­tiä a (siis b jää pois).

Mil­tä V näyt­tää NFA:na? Mie­ti en­sin it­se ja vaik­ka piir­rä pa­pe­ril­le, tai voit kir­joit­taa sen al­la ole­vaan vas­taus­ruu­tuun. Sit­ten kat­so vas­taus täs­tä[it­se­synk­ro­noi­van pro­to­kol­lan vas­taan­otin].

tai

L:n suun­nit­te­lu saat­taa vaa­tia sin­nik­kyyt­tä. Sil­tä va­ral­ta et­tä ha­luat yrit­tää, al­la on vas­taus­laa­tik­ko. Jo­ka ta­pauk­ses­sa kat­so lo­puk­si vas­taus täs­tä[it­se­synk­ro­noi­van pro­to­kol­lan lä­he­tin].

tai

Ku­van piir­tä­mi­nen tä­män pro­to­kol­lan tuot­ta­mas­ta pal­ve­lus­ta on han­ka­laa sik­si, et­tä lä­he­tin voi an­taa pe­rik­si en­nen­ai­kai­ses­ti, jol­loin en­sin tu­lee err ja vas­ta sit­ten aV. Voi jo­pa käy­dä niin, et­tä lä­he­tin eh­tii sii­nä vä­lis­sä ot­taa uu­den a:n ja eh­tii vas­ta­ta sil­le­kin err.

Lo­puk­si

Jär­jes­tel­män käyt­täy­ty­mi­nen voi­daan tut­kia au­to­maat­ti­ses­ti muo­dos­ta­mal­la tu­lo­au­to­maat­ti ja ana­ly­soi­mal­la si­tä ta­val­la tai toi­sel­la. Voi­daan esi­mer­kik­si li­sä­tä pro­to­kol­laan käyt­tä­jiä edus­ta­va DFA, jo­ka lä­het­tää vies­te­jä ja tar­kas­taa, et­tä ulos tu­lee kul­loin­kin se mi­kä vii­mek­si lä­he­tet­tiin. Se me­nee lop­pu­ti­laan sil­loin ja vain sil­loin, kun ulos tu­lee vää­rä vies­ti. Pro­to­kol­lan mui­den osien kaik­ki ti­lat muu­te­taan lop­pu­ti­loik­si. Jos pro­to­kol­la ei kos­kaan an­na ulos mi­tään vää­rää, tu­lo­au­to­maa­tin hy­väk­sy­mä kie­li on ∅. Jos pro­to­kol­la an­taa ulos jo­tain vää­rää, tu­lo­au­to­maa­tis­ta voi­daan lu­kea ti­lo­jen ja ta­pah­tu­mien jo­no, jo­ka joh­taa vir­hee­seen.

Ha­lut­tu käyt­täy­ty­mi­nen voi­daan myös il­mais­ta loo­gi­si­na kaa­voi­na. Osa­taan teh­dä oh­jel­mia, jot­ka tar­kas­ta­vat, to­teut­taa­ko tu­lo­au­to­maat­ti kaa­vat. Jol­lei to­teu­ta, nyt­kin tar­kas­tin an­taa ti­lo­jen ja ta­pah­tu­mien jo­non, jo­ka joh­taa vir­hee­seen. Voi­daan myös laa­tia ver­tai­lu­koh­de DFA:na ja tes­ta­ta, käyt­täy­tyy­kö tu­lo­au­to­maat­ti vä­hin­tään yh­tä hy­vin kuin se. Jär­jes­tel­mä voi käyt­täy­tyä ver­tai­lu­koh­det­ta pa­rem­min esi­mer­kik­si si­ten, et­tä ver­tai­lu­koh­de si­säl­tää err-haa­ran, mut­ta jär­jes­tel­mä ei kos­kaan va­lit­se si­tä.

Täl­lai­set me­ne­tel­mät ovat ke­hit­ty­neet hy­vin pit­käl­le. Yk­si nii­den on­gel­ma on se, et­tä tu­lo­au­to­maa­tit ovat usein val­ta­via. Tu­lo­au­to­maat­tia ei kui­ten­kaan yleen­sä tar­vit­se muo­dos­taa ko­ko­naan, vaan tun­ne­taan me­ne­tel­miä muo­dos­taa pie­nem­piä au­to­maat­te­ja, jot­ka säi­lyt­tä­vät tie­don jär­jes­tel­män mah­dol­li­ses­ta vir­heel­li­ses­tä käyt­täy­ty­mi­ses­tä. Täs­sä on vuo­si­kym­men­ten ai­ka­na edis­tyt­ty hui­mas­ti. Va­li­tet­ta­vas­ti on­gel­ma ei to­den­nä­köi­ses­ti tu­le kos­kaan täy­sin rat­kea­maan sik­si, et­tä vir­hei­den et­si­mi­nen jär­jes­tel­mäs­tä on PSPACE-ko­va teh­tä­vä. Tä­mä syy vai­kut­taa kaik­kiin vir­hei­den et­si­mi­sen me­ne­tel­miin, ei siis pel­käs­tään tu­lo­au­to­maat­te­ja käyt­tä­viin.

Toi­nen on­gel­ma on se, et­tä jär­jes­tel­mäl­tä ha­lu­tun pal­ve­lun tun­nis­ta­mi­nen on us­ko­mat­to­man vai­keaa. Kat­ta­vaa ja vir­hee­tön­tä ku­vaus­ta sii­tä, mi­tä sen pi­tää teh­dä ja mi­tä se ei saa teh­dä, ei usein­kaan osa­ta laa­tia. Jos jär­jes­tel­mä te­kee jo­tain höl­möä, niin sen ta­pah­dut­tua osa­taan kyl­lä sa­noa, et­tä ei sen näin pi­tä­nyt teh­dä. Vai­keam­paa on kiel­tää ne höl­möy­det, joi­ta jär­jes­tel­mä ei vie­lä ole teh­nyt.

Vuon­na 2017 sat­tu­nut ta­paus on hy­vä esi­merk­ki täs­tä vai­keu­des­ta. Pyö­rä­tuo­lis­sa is­tu­va hen­ki­lö ha­lu­si mak­saa 74,50 eu­ron hin­tai­set tal­vi­ken­gät an­ta­mal­la 4,50 eu­roa ra­haa ja Ke­lan myön­tä­män mak­su­si­tou­muk­sen, jon­ka ylä­ra­ja oli 70 eu­roa. Kas­sa kiel­täy­tyi, kos­ka oh­jeis­sa lu­ki, et­tä os­tos ei saa ylit­tää mak­su­si­tou­muk­sen ar­voa. Oh­jeen tar­koi­tus ei ol­lut kiel­tää täl­lais­ta yh­dis­tel­mä­mak­sua, vaan var­mis­taa, et­tä kaup­pa ei hy­väk­sy mak­su­si­tou­mus­ta sen ylä­ra­jaa suu­rem­mas­ta sum­mas­ta. Ta­paus oli asiak­kaal­le ka­ma­la ja sai kau­pan huk­ku­maan vi­ha­pos­tiin. Ta­pauk­ses­sa ei ol­lut ky­se oh­jel­moin­ti­vir­hees­tä vaan sii­tä, et­tä ih­mis­ten nou­da­tet­ta­vak­si tar­koi­tet­tuun oh­jee­seen ei osat­tu kir­joit­taa si­tä mi­tä ha­lut­tiin.

Toi­si­naan on mah­dol­lis­ta kor­va­ta tu­lo­au­to­maa­tis­sa muut kuin ulos­päin nä­ky­vät ta­pah­tu­mat ε:lla, muo­dos­taa pie­ni sa­man kie­len hy­väk­sy­vä NFA, ja näyt­tää se ku­va­na. Ku­vas­ta voi­daan tul­ki­ta jär­jes­tel­män käyt­täy­ty­mis­tä sil­loin­kin kun ei etu­kä­teen osa­ta sa­noa tar­kas­ti, mi­ten sen tu­li­si käyt­täy­tyä. Ku­va saa­daan au­to­maat­ti­ses­ti, mut­ta se on har­voin niin pie­ni, et­tä ih­mi­nen pys­tyy tul­kit­se­maan si­tä.

On­gel­mak­si on muo­dos­tu­nut myös se, mi­tä tar­koi­te­taan, kun sa­no­taan, et­tä kak­si jär­jes­tel­mää tuot­taa sa­man pal­ve­lun. Sil­tä osin kuin on ky­se sii­tä, voi­ko jär­jes­tel­mä teh­dä mi­tään vää­rää, se ei ole on­gel­ma: jär­jes­tel­mät tuot­ta­vat sa­man pal­ve­lun jos ja vain jos nii­den ulos­päin nä­ky­viin ta­pah­tu­miin ra­joi­te­tut NFA-esi­tyk­set hy­väk­sy­vät sa­man kie­len. Ti­lan­ne mut­kis­tuu kui­ten­kin hy­vin pal­jon, jos ha­lu­taan tut­kia jät­tää­kö jär­jes­tel­mä te­ke­mät­tä asioi­ta jot­ka sen pi­tää teh­dä. Tä­mä on joh­ta­nut sy­väl­li­siin ma­te­maat­ti­siin tut­ki­muk­siin, joil­la ei en­si nä­ke­mäl­tä luu­li­si ole­van mi­tään te­ke­mis­tä jär­jes­tel­mien vir­hei­den et­si­mi­sen kans­sa. Hy­vä esi­merk­ki sii­tä on tä­mä ny­kyi­sin il­mai­nen kir­ja.

Näis­tä on­gel­mis­ta huo­li­mat­ta me­ne­tel­mät pys­ty­vät tar­kas­ta­maan jär­jes­tel­miä huo­lel­li­sem­min kuin mi­hin ih­mi­nen yleen­sä pys­tyy päät­te­le­mäl­lä. Siel­lä, mi­hin ne so­vel­tu­vat, ne löy­tä­vät vir­heet kat­ta­vam­min kuin mi­hin tes­taa­mi­nen pys­tyy. Siel­lä­kään, mi­hin ne so­vel­tu­vat, ne ei­vät kor­vaa tes­taa­mis­ta, vaan täy­den­tä­vät si­tä, kos­ka ne ovat tes­taa­mis­ta pal­jon ras­kaam­pia. Kos­ka tie­to­ko­neen si­säl­lä ole­van mik­ro­pii­rin vaih­ta­mi­nen eh­jään on han­ka­laa, mik­ro­pii­rien val­mis­ta­jat käyt­tä­vät tä­män­kal­tai­sia me­ne­tel­miä var­mis­ta­maan, et­tä mik­ro­pii­rit ovat mah­dol­li­sim­man vir­heet­tö­miä. Oh­jel­mis­to­val­mis­ta­jat ei­vät käy­tä, kos­ka oh­jel­mien ei tar­vit­se ol­la mah­dol­li­sim­man vir­heet­tö­miä, sil­lä ne voi­daan päi­vit­tää ne­tin kaut­ta.