GSP (uvod u distribuirane sisteme)

Kao i mnogo drugih ljudi, nalazim se u nezgodnoj situaciji da često koristim gradski prevoz u Beogradu. Situacija je nezgodna na raznorazne načine, ali mene lično ponajviše bockaju sitne, u principu beznačajne, iracionalnosti putnika. Ovaj tekst će se baviti jednom takvom iracionalnošću. Slobodno skočite na poslednji pasus za skraćenu verziju teksta.

Distribuirani sistem je (laički rečeno) stvarno mnogo računara upregnutih da zajedno rešavaju jedan problem. Kada imate veliki zadatak koji se neće u razumnom roku završiti na jednom računaru, skroz ima smisla da uposlite više računara da rade istovremeno, i da preko mreže razmenjuju međurezultate i eventualno se sinhronizuju. (fun fact: pojedinačni računar u distribuiranom sistemu se zove "čvor" - termin očigledno treba da nas asocira na čvorove mornarskih mreža, a ne na čvorove u stablima ... zašto stabla uopšte imaju "čvorove"? mislim čvorovi u stablima jesu nezgodni za sečenje, ali to je prilično tanak izgovor; i pored toga, čvor u fizičkoj mreži se na engleskom i dalje zove "knot", dok se čvor u ovakvom sistemu na engleskom zove "node" ... jezici su blesavi)

Prirodno, čvorovi u distribuiranom sistemu svi imaju apsolutno identično ponašanje i neće zastraniti od njega. Pošto čvorovi, prirodno, moraju da komuniciraju i da zajedno donose odluke, posmatranje ovakvog sistema neizbežno liči na veštačku simulaciju neobične demokratije - demokratije u kojoj niko ne posmatra svoj lični interes, već isključivo kolektivni.

Postavka problema 

 

Posmatraćemo distribuirani sistem sa $N$ čvorova (instance $c_1, c_2, ..., c_n$), i sa ograničenim brojem ($M$) resursa $S$ (instance $s_1, s_2, ...s_M$), gde je zauzimanje resursa isključujuća operacija - u jednom trenutku, samo jedan čvor može da koristi jednu instancu resursa. Sistem teži da maksimizuje upotrebu $S$, s time da cena zauzimanja/oslobađanja resursa $T(s_x)$ može da varira zavisno od situacije, i zbirnu cenu ($T_{sum}$) ćemo gledati da minimizujemo na nivou izvršavanja čitavog sistema.

Resurse ćemo tretirati tako da su uvek dati u parovima¹. Shodno tome ćemo obeležiti resurse kao $s'_x$ i $s''_x$, gde je $'$ oznaka za resurs koji se lakše zauzima, i $''$ oznaka za resurs koji se teže zauzima.

Cene zauzimanja / oslobađanja su uvek $0$, osim kada je već zauzet resurs $s'_x$, a mi zauzimamo / oslobađamo resurs $s''_x$, u kom slučaju ćemo imati cenu $1$. Formalno:
\[
T(s'_{x}) = 0 \\
T(s''_{x}) =
\begin{cases}
0  \text{ u slučaju da je }s'_{x} \text{ slobodno} \\
1 \text{ u slučaju da je }s'_{x} \text{ zauzeto}
\end{cases}
\]

Ovako formirana cena ilustruje činjenicu da oba čvora moraju da ulože dodatni trud kada se dešava zauzimanje resursa $s''_x$ ako je $s'_x$ već zauzet.

Razmatraćemo čvor $c_k$, koji je u prilici da zauzme resurs $s'_x$ ili $s''_x$. Situacije kada je samo jedan od ova dva resursa slobodan su trivijalne, pošto želimo da maksimizujemo upotrebu $S$ - zauzećemo slobodan resurs, kolika god da je cena $T$.

Strategija 0: ne zauzimanje resursa

 

Ovu strategiju možemo trivijalno da odbacimo, pošto nam je prvi prioritet maksimizacija upotrebe $S$.

Strategija A: zauzimanje $s'_x$

 

Kada čvor $c_k$ zauzme resurs $s'_x$, ukupna cena koju će eventualna naknadna zauzimanja resursa $s''_x$ direktno² zavisi od broja tih dodatnih zauzimanja. Konkretno, za $p$ dodatnih zauzimanja, ukupna cena će u najgorem slučaju biti:
\begin{equation}
T_{sum} = 2 * p
\end{equation}
Ovo je zbog toga što jedno zauzimanje i oslobađanje koštaju zbirno $2$. Ako imamo $p$ zauzimanja i oslobađanja, to je jasno $2*p$. Eventualno smo mogli da izbegnemo poslednje oslobađanje tako što smo mi prvi oslobodili $s'_x$, ali to je zanemarljivo.

Strategija B: zauzimanje $s''_x$

Kada čvor $c_k$ zauzme resurs $s''_x$, ukupna cena koju će eventualna naknadna zauzimanja resursa $s''_x$ je u najgorem slučaju:
\begin{equation}
T_{sum} = 1
\end{equation}
Jasno, ova cena će biti plaćena u situaciji da je resurs $s'_x$ zauzet u trenutku kada $c_k$ oslobađa svoj resurs. U suprotnom, cena je $0$.

Poređenje strategija

Ključno je primetiti da su najgori slučajevi strategije B identični sa strategijom A, glede plaćene cene ($T_{sum} = 1$). Kod svih drugih slučajeva, strategija B daje optimalniji rezultat - što je $p$ veće, to je B bolje. Za ovaj sistem čak nije bitno kako modelujemo slučajnu promenljivu $p$³, pošto B nema nikakvu zavisnost od $p$.

Primena i zaključak

Ova diskusija je prilično jednostavna, i primena u stvarnosti bi bila za očekivati, ali nije loše pomenuti dodatne faktore, koji postaju značajni ako dozvolimo (iracionalnu) pohlepu čvorova:

• $c_k$ može da računa na to da će zauzimanjem bližeg resursa smanjiti verovatnoću da drugi čvorovi uopšte pokušaju da zauzmu dalji resurs - u praksi se⁴ ovo pokazuje kao validno. Lokalna cena koju $c_k$ plaća se na ovaj način minimizuje, ali sistem pati, pošto ovo ide na uštrb traćenja resursa $S$.
• $c_k$ može da iz svojih pojedinačnih razloga ima potrebu da što brže oslobodi resurs. Ovo je ponovo iracionalno - ako je lokalna brzina cilj, $c_k$ nije trebalo uopšte da zauzima $S$.
• itd.

Ako sedite do prolaza u autobusu, a sedište do prozora je slobodno, iz inata ću da vas popreko pogledam dok se ne pomerite da prođem. Potom ću da sednem pored vas, i čak i ako nisam došao do kraja puta, pre naredne stanice ću da ustanem i da dođem do izlaza. Onda ću se vratiti na isto sedište, uz isti mrki pogled. Uradiću to za svaku stanicu do odredišne.

---

1 U stvarnosti postoje retki izuzeci kada je neki resurs dat pojedinačno, ali ovo neće uticati na naše cene, tj. za resurs s_x koji nije u paru, uvek važi Z(s_x)=0, O(s_x)=0.
2 Linearno, da budemo precizni.
3 Mada jeste interesantno pitanje, koje valja razmotriti zbog sličnih problema - verovatno Poasonova raspodela.
4 Empirijskom analizom. Imam tabelu.