[MWy] Re: dotaz na middleware

[Petr Tuma]

Dobry den,

> ucim se na zkousku z middleware a narazil jsem na zajimavy problem. Kdyz 
> jsem se zamyslel nad CAUSAL ORDERINGEM, zacal jsem si vlastne rikat, k 
> cemu to je? Vzdyt to prece rika jen, ze se musi prijimout nejaka zprava 
> v procesu B az po odeslani procesem A a tranzitivne.
> Taky to samorejme rika, ze udalosti jsou kauzalne po sobe, pokud jsou v 
> jednom procesu spousteny jedna po druhe.
>  
> Prijde mi to slabsi podminka nez treba source ordering a myslim, ze je 
> skoro k nicemu. Pamatuju si, ze jste nam tam ale ukazoval nejake 
> konzistentni a nekonzistentni rezy stavem programu. Na ty se to sice 
> hodi, ale ten nekonzistentni rez prece ani nemuze v praxi nastat nebo ano?
>  
> Vymyslel jsem s kamaradem priklady porusujici causal ordering a jedine, 
> co nas napadlo je:
>  
> SEND( A, X -> B)
> SEND( A, Y -> B)
> RECV(B, Y)
> RECV(B, X)
>  
> Tenhle priklad porusuje source ordering, ale nezda se nam ze by 
> porusoval causal. A nemuzeme s kamaradem prijit na priklad ktery ano, 
> pokud by nemel byt uplne nesmyslny, jako ze B prijme neco co A jeste ani 
> neodeslalo :))

No ... mate a nemate pravdu a je to nejspis moje chyba, ze jsem na to na 
prednasce neupozornil :-( omlouvam se. S definici kauzality je trochu 
problem v tom, ze se zpravidla vztahuje k udalostem:

"Udalost A je kauzalne pred B, pokud A je pred B v jednom procesu nebo A 
je odeslani zpravy M a B je prijem zpravy M, nebo existuje udalost C, 
kde A je kauzalne pred C a C je kauzalne pred B."

Tehle relaci se rika "Lamport's Happens-Before Relation" (a nekdy take 
"Causality Relation") a je to zpravidla ta, ktera se ukazuje, protoze 
dobre vysvetluje intuitivni chapani kauzality. Bohuzel se tyka udalosti 
a nikoliv zprav, takze se primo nehodi pro usporadani zprav. Neprimo je 
mozne ji pouzit nekolika zpusoby:

- Uprava relace tak, aby byla mezi zpravami a nikoliv mezi udalostmi: 
"Zprava A je kauzalne pred B, pokud A je odeslana pred tim, nez B je 
odeslana v jednom procesu, nebo A je prijata pred tim, nez B je odeslana 
v jednom procesu, nebo existuje zprava C, kde A je kauzalne pred C a C 
je kauzalne pred B." Pak se definuje: "Zpravy jsou dorucovany v 
kauzalnim usporadani, kdyz pokud A je kauzalne pred B, pak zadnemu 
procesu neni doruceno B pred A."

- Pouziti stavajici relace a vztazeni usporadani zprav k udalostem 
jejich odeslani: "Zpravy jsou dorucovany v kauzalnim usporadani, kdyz 
pokud odeslani A je kauzalne pred odeslanim B, pak zadnemu procesu neni 
doruceno B pred A."

- Pouziti stavajici relace a vztazeni usporadani zprav k jejich obsahu: 
"Zpravy jsou dorucovany v kauzalnim usporadani, kdyz pokud obsah zpravy 
A informuje o udalosti X a obsah zpravy B informuje o udalosti Y a X je 
kauzalne pred Y, pak zadnemu procesu neni doruceno B pred A." Tohle je 
tak trochu necista definice, protoze skryte predpoklada, ze obsah kazde 
zpravy mimo jine informuje o jejim odeslani.

Formalne nejcistsi je asi ten druhy zpusob z uvedenych tri ... ale 
setkat se muzete se vsemi tremi, nebo i jen z volnym "zpravy jsou 
dorucovany v poradi, ktere neporusuje kauzalni usporadani", coz je 
samozrejme formalne nedostacujici.

Tak, doufam, ze jsem to vysvetlil presne :-) mimochodem, toto byla z 
vasi strany dobra pripominka !

Petr Tuma