Pr-1st-1.1-m02-Slajd50

Podstawowy model k spośród r

W podstawowym modelu k spośród r, z pasywnym procesem $P_i$ skojarzony jest zbiór warunkujący ${{𝒟}}_i$, liczba naturalna $k_i$, $1\le k_i\le |{{𝒟}}_i|$, oraz liczba $r_i=|{{𝒟}}_i|$. W modelu tym proces staje się aktywny tylko wówczas, gdy uzyska wiadomości od co najmniej $k_i$ różnych procesów ze zbioru warunkującego ${{𝒟}}_i$. Model spośród k spośród r jest uogólnieniem modelu AND oraz modelu OR. Istotnie, model ten redukuje się do modelu AND, gdy $k_i=r_i$ , a do modelu OR, gdy $k_i=1$. Model k spośród r, odpowiada na przykład ubieganiu się o bufory w sieciach komunikacyjnych, w których przesyłane wiadomości składają się z wielu ($k$) pakietów. Jeżeli w tym wypadku pojedynczy pakiet pamiętany może być w buforze jednostkowym, to przesłanie wiadomości wymaga zarezerwowania w następnym węźle puli $k$ równoważnych buforów z ogólnej ich liczby $r$ , w celu przesłania do nich wiadomości składającej się z $k$) pakietów. Model k spośród r wykorzystywany jest również w systemach replikowanych baz danych, w których stosowany jest algorytm głosowania do zarządzania współbieżnością (ang. quorum based concurrency control algorithm). W algorytmach tych transakcje realizujące odczyt muszą odczytać $k^r$ kopii spośród $r$ , a transakcje realizujące zapis, muszą uzyskać dostęp do $k^w$ kopii spośród $r$, przy czym $k^r+k^w>r$ oraz $2k^w>r$.

<< Poprzedni slajd | Spis treści | Następny slajd >>