# Distribuirani sistemi usmeni

## Pitanja

1. (dec2021. 1.) Procesi P1, P2, P3 i P4 dele isti resurs(kriticnu sekciju - KS). Za postizanje uzajamnog iskljucivanja koristi se Ricart-Agrawala algoritam. Proces P1 se trenutno nalazi u KS. Dok jos traje pristup KS, procesi P4, P2 i P3(tim redosledom) izdaju svoje zahteve da udju u istu KS. Pokazati sadrzaj redova cekanja u svakom od procesa po pravilima kako funkcionise algoritam dok:
a. je P1 jos u KS
b. kada je P1 napustio KS

>a.
>Redovi cekanja:
>P1: P4, P2, P3
>P2: P3
>P3:
>P4:
>
>1) P4 salje zahtev i dobija OK od P2 i P3, a nista od P1
>2) P2 salje zahtev i dobija OK od P3 i P4, a nista od P1
>3) P3 salje zahtev i dobija OK od P4, a nista od P1 i P2
>
>b.
>Redovi cekanja:
>P1:
>P2: P3
>P3:
>P4: P2, P3
>
>1) P4 salje zahtev i dobija OK od svih i ulazi u KS
>2) P2 salje zahtev i dobija OK od P1 i P3 a nista od P4
>3) P3 salje zahtev i dobija OK od P1, nista od P2 i P4

2. (dec2021. 2.) U grupi postoji pet repliciranih procesa. Ako mogu nastupiti samo mirne greske, koliko maksimalno procesa moze otkazati a da se ipak dobije korektan rezultat? Ako mogu nastupiti greske vizantijskog tipa, koliko procesa moze maksimalno otkazati a da se ipak dobije korektan rezultat? Sta ako mogu nastupiti greske vizantijskog tipa a procesi moraju postici konsenzus? Koliko u ovom slucaju maksimalno procesa moze otkazati? Svaki odgovor obrazloziti.
> Za sistem se kaze da je n-tolerantan na greske, ako moze podneti n gresaka, a da pri tome nastavi korektno da funkcionise.
> Ako je rec o mirnim greskama, potrebno je n+1 komponenti
> Ako je rec o vizantijskim greskama, potrebno je 2n + 1 komponenti
> Mirne:
> n + 1 = 5 => n = 4
> Vizantijske:
> 2n + 1 = 5 => n = 2
> Da bi sistem bio otporan na Vizantijske greske, mora da > N/2 procesa radi ispravno da bi se konsenzusom izglasao ispravni rezultat. Ovde nam 3 procesa radi ispravno, a 2 mogu da otkazu

3. (dec2021. 3.) Objasniti client centric model konzistencije, varijantu monotona citanja. Dati primer skladista podataka koje je konzistentno i koje nije konzistentno u odnosu na ovaj model konzistencije.

>Ako proces cita vrednost podatka x na jednoj lokaciji, svako novo citanje tog podatka ce vratiti istu ili noviju vrednost, bez obzira na kojoj lokaciji se obavlja citanje
>
>
>Proces na lokaciji L1 cita vrednost x1, koji je rezultat operacije WS(x1) na lokaciji L1, kasnije P cita x sa lokacije L2(R(x2)). Da bi se garantovala konzistentnost, skup operacija WS(x1) se mora propagirati i na L2
>
>Konzistentnost nije garantovana. Nakon citanja x1 sa L1, P cita x2 sa L2, ali je na L2 obavljen samo skup operacija WS(x2) i nema garancije da on sadrzi sve operacije iz WS(x1)

4. (dec2021. 4.) Sta je konzistentni presek? Koje linije na slici dole cine a koje ne cine konzistentni presek? Dati obrazlozenje.
>Konzistentni presek je skup tacaka provere(checkpoints) C, pri cemu za svaka dva dogadaja e i e' vazi:
>(e∈C)^(e'->e)=>e'∈C
>Ovo znaci na primer, ako je proces P zabelezio prijem poruke iz procesa Q, tada u skupu mora postojati i tacka u kojoj je proces Q zabelezio slanje poruke procesu P(poruka je morala da stigne od nekog).
>Koznistentni presek obezbedjuje da se procesi u DS vrate u neko stanje odakle je moguce izvrsiti oporavak.
>
>11-21-31 - JESTE KP - ispunjeni uslovi
>11-22-32 - NIJE KP - jer je S2 zabelezio prijem poruke od S1, ali S1 nije zabelezio slanje iste poruke procesu S2
>12-23-33 - JESTE KP - ispunjeni uslovi
>

5. (dec2021. 5.) Na slici je prikazan Chord P2P.
a. koji je cvor odgovoran za kljuc 13, a koji za kljuc 9?
b. Pretpostavimo da se cvor N15 pridruzuje Chord prstenu tako sto kontaktira cvor N20. Redom napistai korake koji opisuju pridruzivanje cvora N15 prstenu.
>a. Za kljuc 13 je odgovoran N14
>Za kljuc 9 je odgovoran N9
>b.
>1 N15 postavlja svog neposredno prethodnog na NIL
>2 N15 od N20 zahteva da pronadje neposrednog sledbenika N15. N20 vraca da je njegov neposredni sledbenik N18(on se pronalazi standarnim algoritnom za trazenje ili uz pomoc finger tabele)\
>3 N15 obavstava N18 da je on prethodnik za N18
>4 N18 oznacava da je N15 njegov prethodnik
>5 N14(koji je stari prethodnik N18) pokrece protokol za stabilizaciju.
>6 N14 pita N18 ko je njegov prethodnik(to je sada N15)
>7 N14 saznaje da mu je N15 sledbenik na osnovu odgovora N18
>8 N14 obavestava N15 da mu je on novi prethodnik
>9 N15 oznacava da mu je N14 prethodnik
>10 Kraj - pokazivaci na prethodnike i sledbenike su sada korektni
>Ostali ulazi u finger tabele treba da se koriguju, ali protokol moze da pronadje sadrzaje.

6. (okt 2021. 1.) Objasniti razliku izmedju mreznog OS, distribuiranog OS i OS baziranog na middleware.
>Platforma na kojoj su izgradjeni DS su racunarske mreze. Mrezni OS pruza mogucnost korisnicima da pristupe uslugama koje su locirane na nekoj drugoj masini(implementira na primer TCP/IP protokol-stek). Da bi se pojednostavilo pisanje distribuiranih aplikacija i njihova integracija u DS na mrezni OS, moguce je dodati jos jedan softverski sloj - Middleware, sa ciljem da sakrije heterogenost platforma na kojoj sistem izgradjen od aplikacije, i da se sakrije komunikacija, to jest, distribucija
>
>
>Lokalni OS upravlja lokalnim resursima i obezbedjuje komunikaciju sa drugim racunaruma. Middleware ne upravlja radom pojedinacnog cvora u mrezi, to radi lokalni OS. Middleware sistemi nude kompletan skup usluga aplikaciji i ne dozvoljava koriscenje niceg drugog do njihovih interfejsa prema uslugama.

7. (okt 2021. 2.) Tri racunara A, B i C komuniciraju koristeci protokol koji implementira Lamportove vremenske markice. Na pocetku u svim racunarima vrednosti vremenskih markica su 0. Kasnije nastupaju sledeci dogadjaju:
* A salje poruku M1 u B: "Zdravo"
* Nakon sto je primio M1, B salje poruku M2 u C: "A mi se javio"
* Nakon sto je c primio M2, salje poruku M3 u A: "B mi dosadjuje"
(a) Uz svaku od poslatih poruka napisati vrednost vremenske markice sa kojom je poslata:
Send(M1, __)
Send(M2, __)
Send(M3, __)
(b) Nakon ovih dogadjaja poslate su jos tri poruke:
* Nakon sto je primio poruku M3, A salje poruku M4 u B: "C je nedosledan"
* Nakon sto je primio poruku M4, B salje poruku M5 u A: "C mi dosadjuje"
* A prima poruku M5.
Nakon sto su sve poruke poslate i primljene, kolike su vrednosti vremenskih markica u svakom od racunara A, B i C?
(c ) Da li opisani slucaj predstavlja primer relativne ili potpuno uredjene komunikacije?
>
>a.
>Send(M1, 1)
>Send(M2, 3)
>Send(M3, 5)
>b.
>A=>10
>B=>9
>C=>5
>c.
>Relativna - nema multicast-a. U ovom slucaju svaka poruka je posledica prethodne i zbog toga ce svi procesi videti isto uredjenje, medjutim to ne mora biti situacija u opstem slucaju, jer ne postoji mehanizam koji ce obezbediti potpuno uredjenje

8. (okt 2021. 3.) U distribuiranom sistemu klijent koristi RPC za komunikaciju sa serverom. Klijent salje zahtev server(npr operation x()) sve dok ne dobije odgovor od server.
a. Koja RPC semantiku u slucaju greske je u ovom slucaju implementirana?
b. Objasniti kako mora da bude implementiran server da bi se ovakva semantika obezbedila
>jun 2020. 4.

9. (okt 2021. 4.)
a) Ako je PTP organizovan kao Chord i ima N cvorova, u koliko maksimalno koraka se moze pronaci zeljeni sadrzaj ako postoji?
b) U Chord sistemu cvor q je sledbenik cvora p. U toku rada sistema cvor p otkriva da njegov pokazatelj na sledbenika vise nije validan jer je cvor q azurirao pokazatelj na svog prethodnika. Sta je uzrok ovoga?
>a. log2(N) - uz koriscenje finger tabele(distribuirane hash tabele)
>b. Jos jedan cvor se pridruzio sistemu tako da je smesten izmedju cvorova p i q. Zbog ovoga je cvor p azurirao pokazatelj na prethodnika. Sada je neophodno da p pokrene protokol za stabilizaciju.

10. (okt 2021. 5.)
a) Pomocu primera pokazati da nije moguce postici konsenzus izmedju ispravnih procesa ako postoje 3 procesa od kojih jedan ispoljava gresku vizantijskog tipa.
b) Pomocu primera pokazati da je moguce postici konsenzus izmedju ispravnih procesa koji ako postoje 4 procesa od kojih jedan ispoljava gresku vizantijskog tipa
**Napomena:** Obavezno navesti koji uslovi moraju biti zadovoljeni kod postizanja konsenzusa.
>Uslovi koji moraju biti ispunjeni:
>svi ispravni procesi moraju doneti istu odluku (isti rezultat).
>ako je glavni proces ispravan svi ispravni procesi moraju da postuju njegovu odluku (njegov rezultat).
>Problem odgovara problemu vizantijskih generala. Recimo da svaki proces treba da dobije rezultat 0(povlacenje) ili 1(napad).
>a.
>
>runda 1
>1 ima predloge (1, 0, 0)
>2 ima rezultate (1, 0, 1)
>3 ima rezultate (1, 0, \*)
>runda 2
>1 prima vektore (1, 0, 1) i (\*, \*, \*)
>2 prima vektore (1, 0, 0) i (\*, \*, \*)
>3 prima vektore (1, 0, 0) i (1, 0, 1)
>b.
>

11. (okt 2021. 6.) SUN-ov NFS koristi montiranje (mount points) da bi dodelio lokalna imena udaljenim fajlovima.
a. Da li je ovaj metod imenovanja fajlova lokaciono transparentan? Obrazloziti.
b. Da li je lokaciono nezavistan? Obrazloziti.
c. Navesti bar jedan nedostatak koriscenja "mount points" u distribuiranom fajl sistemu.
>a. Jeste jer DFS vodi racuna o preslikavanju lokalnih imena na udaljeno ime masine na kojoj se fajl nalazi. Nakon sto se mount ostvari, klijent ne mora voditi racuna da li pristupa udaljenom ili lokalnom fajlu.
>b. Jeste jer DFS vodi racuna o ovom preslikavanju, sto znaci da se lokalni fajl moze promeniti(promena udaljene putanje ili hosta) a da lokalno ime ostane nepromenjeno. (neophodno je osveziti vezu DFS sa udaljenim serverom kako bi DFS preuzeo novu lokaciju fajla).
>c. Nedostatak je to sto isti fajl moze imati razlicita imena u zavisnosti od klijenta, u zavisnosti od toga gde je u fajl sistemu montiranje izvrseno.

12. (sep 2021. 1.) Kako izgleda poziv Sun RPC kompajlera? Koji fajlovi se dobijaju kao rezultat ovog kompajliranja i sta sadrze? Objasniti na primeru.
> Poziv Sun RPC kompajlera izgleda: rpcgen -c primer.x
> 1. header fajl (primer.h) - sadrzi jedinstveni identifikator interfejsa, definificije tipova, konstantni i prototipova funkcija
> 2. klijent stub (primer_cstub.o) - sadrzi procedure koje ce klijent program pozivati. Ove procedure su zaduzene za pakovanje parametara u poruke, slanje poruka, prijem poruka, izvlacenje rezultata poziva procedure i prosledjivanje klijentu.
> 3. server stub (primer_sstub.o) - Sadrzi procedure koje se pozivaju kada stigne poruka do servera i koje zatim pozivaju odgovarajucu serversku proceduru.

13. (sep 2021. 2.) Tri racunara A, B i C komuniciraju i koriste protokol koji implementira Lamportove logicke casovnike. Na pocetku su svi logicki casovnici u sva tri racunara postavljena na 0. Kasnije nastupaju sledeci dogadjaji:
* A salje poruku M1 u B
* C salje poruku M2 u B
* B prima poruku M2 pre M1
* B odgovara porukom M3 prvo racunaru C, a zatim porukom M4 racunaru A
* Nakon prijema poruke M3, C salje poruku M5 racunaru A
* Nakon prijema poruke M5, A salje poruku M6 racunaru B
* Nakon prijema poruke M6, B salje poruku M7 racunaru A
* Poslednja poruka koju A prima pre poruke M7 je moruka M4
a. Oznaciti kako izgledaju vremenske markice poruka M1 do M7 prilikom slanja
b. Navesti bar jedan par dogadjaja koji su medjusobno uslovljeni, a cija je kauzalnost korektno identifikovana Lamportovim markicama.
c. Da li se dogadjaji kada B salje poruku M4 i kada C salje poruku M5 mogu identifikovati kao konkurentni dogadjaji koriscenjem Lamportovih markica. Objasniti zasto.

>
>a.
>Send(M1, 1)
>Send(M2, 1)
>Send(M3, 4)
>Send(M4, 5)
>Send(M5, 6)
>Send(M6, 8)
>Send(M7, 10)
>b.
>M2->M3 (T(M2) < T(M3)), M3->M5(T(M3) < T(M5))
>c. Ne, jer se razlikuju vrednosti Lamportovih markica. Na osnovu vrednosti markica se ne moze utvrditi koji dogadjaji su konkurentni a koji uslovljeni.

14. (sep 2021. 3.) Casovnik u gradskom tornju u gradu A je bio pokvaren. Casovnik je popravljen, ali sada mora da bude podesen. Voz napusta stanicu u gradu A i odlazi u grad B koji je udaljen 200km. Cetiri sata kasnije voz se vraca sa informacijom da vreme po casovniku u gradu B iznosi 6:15. Ako se koristi Kristijanov algoritam, na koju vrednost treba podesiti casovnik u gradu A?

>tA=?
>tB=6:15
>delta_t=4h
>tA = tB + (delta_t/2) = 8:15

15. (sep 2021. 4.) Nad objektom x obaljene su sledece operacije u distribuiranom skladistu:
* P1: write(x)A
* P2: write(x)B, read(x)C
* P3: read(x)B, read(x)A, write(x)C
* P4: read(x)B, read(x)A
Nacrtati kako izgleda stvarni redosled dogadjaja ako je skladiste podataka sekvencijalno konzistentno.

>

16. (sep 2021. 5.) Koje vrste HDFS demona postoje i koja je uloga svakog od njih? Opisati postupak citanja i postupak upisa kod HDFS.

>U HDFS postoje 2 tipa demona, jedan NameNode(NN) demon i vise DataNode(DN) demona
>DN je odgovoran za citanje podataka u blokovima, primanje naredba od NN i davanje informacija NN-u
>NN se izvrsava na master cvoru. On odrzava fajl sistem namespace i svaka promena njegovih karakteristika je zapamcena od strane NN. NN cuva informacije o tome kako su fajlovi podeljeni nma blokove, koji slave cvorovi cuvaju koje blokove i sam ucestvuje u preslikavanju blokova u cvorove.Takodje cuva informaciju i o vrednosti faktora replikacije. On je centralni kontroler HDFS-a. NN cuva metapodatke fajl sistema, nadgleda ponasanje DN-a i koordinise pristup podacima. Ne cuva podatke nad kojima se vrsi obrada. NN je u direktnoj vezi sa ostalim cvorovima i za komunikaciju sa DN demonima koristi paket odredjene strukture koji se naziva heartbeat
>HDFS upis: klijent je spreman da upuse file.txt u klaster(razbija se na blokove A, B i C), pocevsi od bloka A. Klijent kontaktira NameNode, konsultuje ga, dobija dozvolu od NN i dobija listu od 3 DataNode za svaki blok koji treba biti upusan. NN koristi svoje Rack Awareness podatke da bi uticao na odluku koji DataNode-ovi ce se naci na listi za pojedinacni blok. Kljucno pravilo je da svaki blok podataka, jedna kopija se nalazi u jednom reku, a druge dve kopije u nekok razlicitom od ovog s tim sto su te dve kopije u istom reku. Sve liste koje dobija klijent moraju da postuju ovo pravilo. Za blok A na listi su DN1, DN5 i DN6. Pre nego sto klijent upise blok A fajla file.txt u klaster, on zeli da zna da su svi DataNode-ovi u koje treba da upise spremni da prime blok. Nakon stizanja potvrde, od DN6 do DN5, od DN5 do DN1, i od DN1 do klijenta, klijent je spreman da upise blok A.
> Citanje HDFS: Kad klijent zeli da procita rezultujuci fajl iz HDFS, konsultuje NN i pita za lokacije blokova u rezultujucem fajlu. NN za svaki blok vraca listu DN-ova koji ga sadrze. Klijent bira za svaki blok prvi DN iz list(lokacije blokova su sortirane prema udaljenosti klijenta). Klijent cita blokove sa odgovarajucih DN-ova sekvencijalno, jedan po jedan

17. (jun 2021. 1.) Sta predstavlja transakcija kod distribuiranih informacionih sistema? Koje osobine treba da zadovolji svaka transakcija da bi bila uspesno izvrsena?
>Transakcija predstavlja skup operacije koje se obavljaju kao jedna nedeljiva(atomicna) operacija. Sistem za obradu transakcije obezbedjuje da se ili sve ili nijedna operacija u transakciji bude izvrsena bez greske. Nakon obavljanja transakcije sistem mora da ostane u poznatom, konzistentnom stanju.
>Svaka transakcija mora da zadovolji ACID test pre nego sto se dozvoli modifikacija sadrzaja:
>A(Atomicity) - podrazumeva da se transakcija obavi kompletno ili da se uopste ne obavi
>C(Consistency) - transakcija ne ugrozava skup ogranicenja sistema
>I(Isolation) - transakcije su medjusobno izolovanje
>D(Durability) - kada se transakcija obavi, ne moze se ponistiti.

18. (jun 2021. 2.) Sta se podrazumeva pod pojmom potpuno uredjena grupna komunikacija. Na slikama 1 i 2 prikazano je izvrsenje (slanje i prijem poruka) u tri procesa (P1, P2, P3). Poslate su dve poruke m1(1, 1) i m2(3, 1). Za svaku sliku odgovoriti da li predstavlja "total ordering" ili ne. Obrazloziti odgovore.
>1. Da jer su svi procesi primili poruke m(1, 1) i m(3, 1) u istom redosledu.
>2. Ne jer procesi nisu primili poruke m(1, 1) i m(3, 1) u istom redosledu.

19. (jun 2021. 3.) Koje se tehnike mogu koristiti za postizanje visoke pouzdanosti sistema? Objasniti erasure coding tehniku.

>Moze se koristiti fizicka hardverska redundansa(npr. TMR - Tripple Module Redundancy) ili informacionom redundansom(npr. ABFT tehnika - Algorithm Based Fault Tolerance). Jos jedna tehnika za postizanje otpornosti na greske je Erasure coding. To je tehnika kod koje se skup od k podataka kodira skupom od n, n > k podataka tako da se na osnovu bilo kog skupa od k podataka mogu regenerisati originalni podaci. (n, k) erasue coding omogucava tolerisanje n-k gresaka. Ova tehnika je siroko prihvacena kod HDFS.

20. (jun 2021. 4.) Koje greske mogu nastupiti u klijent-server komunikaciji kod RPC i koje se akcije preduzimaju preduzimaju kada odgovarajuce greske nastupe?

>1
>Klijent nije u stanju da locira server - razlog moze biti otkaz servera ili neodgovarajuca verzija klijent stub-a. Neophodno je da se emituje exception kada se ovakva greska dogodi. Programer mora da napise specijalnu proceduru koja se poziva kada se detektuje odredjenu gresku.
>2
>Zahtev upucen od klijenta na server je izgubljen - klijent treba da startuje casovnik kada posalje zahtev. Ako istekne timeout pre stizanja potvrde ili odgovora, vrsi se retransmisija. Ako zahtev nije bio izgubljen, onda je ili server otkazao ili je izgubljen odgovor od servera. U svakom slucaju, server mora biti u stanju da prepozna retransmisiju.
>3
>Otkaz servera nakon prijema zahteva od klijenta. Moguca su dva resenja: 1 klijent salje zahtev dok ne dobije odgovor (at least one semantika - garantuje da se RPC izvrsi bar jednom, a mozda i vise puta - primenjivop nad idempotentnim funkcijama). 2 Odmah signalizira gresku nakon isteka timeout-a (at most one sematnika - RPC ce se izvrsiti najmanje jednom, a mozda nijednom)
>4
>Odgovor servera klijentu je izgubljen - kod idempotentnih metoda klijent moze samo ponovo poslati zahtev. Za metode koje nisu idempotentne, resenje je da se zahevima dodele redni brojevi pri cemu server vodi racuna o rednim brojevima klijentskih zahteva, mora otkriti duplikad ili da se u zaglavlju poruke postavi RETRANSMISSION bit kako bi se razlikovao originalni zahtev od retransmisije (ovako server ne vodi racuna o rednim brojevima). U obe varijante server mora ponovo poslati poruku klijentu.

21. (jun 2021. 5.) Kada smo govorili o DFS rekli smo da server moze biti projektovan kao stateful u stateless. Pored svakog od sledecih tvrdjenja staviti oznaku tacno (T) ili netacno (F):
a. Zakljucavanje fajla je tesko implementirati kod stateless servera.
b. Lakse je izboriti se sa greskama kod stateful nego kod stateless servera.
c. Implementacija klijentske strane moze biti komplikovanija sa stateful serverom
d. Kod stateless servera, svaki klijentski zahtev mora da sadrzi kompletnu informaciju o zahtevu (npr. ime fajla, offset, itd.)

>a. Zakljucavanje fajla je tesko implementirati kod stateless servera. - T
b. Lakse je izboriti se sa greskama kod stateful nego kod stateless servera. - F
c. Implementacija klijentske strane moze biti komplikovanija sa stateful serverom - F
d. Kod stateless servera, svaki klijentski zahtev mora da sadrzi kompletnu informaciju o zahtevu (npr. ime fajla, offset, itd.) - T

22. (jun 2021. 6.) Sta omogucava uspesan restart servera na kom se izvrsava NameNode demon. Koji su neophodni podaci za funkcionisanje klastera a koje poseduje NameNode i gde i kako se oni skladiste pre i nakon restarta servera?

>Checkpoint - trajno cuvanje matapodataka NN na lokalnom file sistemu. Sve promene se trajno cuvaju u edit log-u. Fajl fsimage cuva snapshot metapodataka fajlsistema.
>U slucaju restarta promene iz edit log-a se primenjuju na poslednju verziju namespace fajla(fsimage) da bi se dobila nova verzija metapodataka fajl sistema. Posto se u klasterima retko vrsi restart, edit logovi mogu narasti mnogo, tako da vreme za restart postaje mnogo dugo.

23. (maj 2021. 1.)
a. Koje su prednosti distribuiranih sistema u odnostu na centralizovane?
b. Zasto je tesko ostvariti sinhronizaciju u DS?
c. Zasto je (nekada) tesko detektovati greske u DS?

>a. DS su ekonomicniji (bolji odnos cene i performasne od velikih racunara)
>brzina - DS moze imati vecu ukupnu moc obrade nego mainframe
>pouzdanost - ako mainframe otkaze - nista ne radi, kod DS moze da otkaze neki deo sistema tako da sistem i dalje radi sa degradiranim performansama
>inkrementalni rast - sistem se moze postupno povecavati dodavanjem novih racunara
>deljenje resursa - omoguceno da vise koristika pristupi zajednickim bazama podataka
>komunikacija - olaksava komunikaciju izmedju ljudi
>efikasno iskoriscenje resursa - opterecenje se rasporedjuje na raspolozive racunare na najefikasniji nacin
>
>b.
>sinhronizacija je teska jer kod DS i generalno kod RM ne postoji pojam o globalnom vremenu - svaka masina ima svoj lokalni casovnik i procesi na razlicitim masinama imaju razlicitu predstavu o vremenu. Problemi mogu nastati kada se radi sa sistemima u realnom vremenu i kod odrzavanja konzistentnosti distribuiranih podataka, koji se cesto bazira na vremenu poslednje modifikacije
>
>c.
>Detekcija gresaka moze biti problem jer je kompleksnost DS mnogo veca od centalizovanog. Softver za DS je teze razviti jer ima vise aktivnih procesa koji medjusobno komuniciraju, pa je debagiranje ovakvog softvera u slucaju greske veoma naporan i vremennski zahtevan posao.

24. (maj 2021. 2.) Pre nego sto klijent uputi RPC poziv serveru, server mora da bude registrovan. Kako se obaljva registrovanje servera? Sta je portmapper? Sta se podrazumeva pod terminom "binding"?

>Da bi se realizovao poziv udaljene procedure neophodno je locirati udaljeni host i odgovarajuci proces na hostu. Ovo predstavlja binding (povezivanje).
>Jedno resenje je staticko povezivanje. Podrazumeva se da klijent zna koji host treba da kontaktira (adresa se nalazi u klijent stub-u). posebni programi (portmapper) na udaljenom hostu pamti preslikavanja imena programa i broj verzije u broj porta.
>Drugo resenje je dinamicko povezivanje - postoji centralizovana BP(smestena u name i directory serverima) koja moze locirati host koji obezbedjuje zeljeni servis. Ovi serveri imena i direktorijuma vracaju adresu server na osnovu "potpisa" procedura (imena i parametara) koja se poziva. Prilikom poziva udaljene procedure kontaktira se server imena koji salje odgovarajucu adresu klijent stub-u. Serverski stub registruje serversku proceduru u serveru imena i direktorijuma prilikom startovanja servera.

25. (maj 2021. 3.) Navesti pravila za implementaciju vektorskih casovnika. Da li se na osnovu vektorskih casovnika moze utvrditi da li su dva dogadjaja medjusobno uslovljena? Obrazloziti odgovor.

>1
>Vektor se inicijalizuje na 0 u svim procesima Vi[j] = 0 , i,j=1,..N
>2
>Proces Pi inkrementira i-ti element vektora u lokalnom vektoru pre nego sto obelezi dogadjaj: Vi[i] = Vi[i] + 1. Poruka se salje iz procesa Pi zajedno sa Vi
>3
>Kada Pj primi poruku poredi lokalni vektor sa primljenim, element po element, i postavlja element u lokalnom vektoru na vecu vrednost Vj(k) = max{Vj(k), Vi(k)}, k=1,2,...,N
>Moze se utvrditi da li su dva dogadjaja uslovljena, uz izmenu da se casovnik inkrementira samo kod slanja poruke. Svaka poruka se prosledjuje aplikaciji tek kada se ispune sledeci uslovi:
>1 tm[i] = Vj[i] + 1 obezbedjuje da Pj primi sve poruke koje je Pi poslao pre slanja ove poruke
>2 tm[k] <= Vj[k] za svako k != i obezbedjuje da proces Pj primi sve poruke koje je primio Pi pre slanja poruke m

26. (maj 2021. 4.) U procesu mnozenja dve matrice koriscena je ABFT tehnika za detekciju i korekciju gresaka. Dobijen je sledeci rezultat:
a. Utvrditi da li je nastala greska u toku izracunavanja
b. Ako je nastupila greska, naci njenu lokaciju
c. Izvrsiti korekciju greske, ako je ona nastupila

>a. Doslo je do greske
>b. Njena lokacija je [2][1] (ako krece od 0) = 3
>c. 3 zameniti sa 2

27. (maj 2021. 5.) Jedna od tehika koja se koristi za oporavak od gresaka je koriscenje tacaka provere. Na slici su prikazana tri procesa koji medjusobno razmenjuju poruke (poruke su oznacene kvadraticima sa brojem unutar kvadratica). Svaki proces nezavisno kreira tacke provere (oznacene od C1 do C9).
a. Definisati konzistentni presek.
b. Ako u procesima P2 i P3 dodje do greske u trenutku koji je oznacen sa "Crash!" da li je moguce izvrsiti oporavak sistema od greske i vratiti ga u konzistentno stanje koriscenjem navedenih tacaka provere. Obrazloziti odgovor.

>a. isto kao dec 2021.
>b Moguce je. Konzistentni presek je C4-C5-C6 zaso sto je za svaka dva dogadjaja e i e' za koji vazi e'->e, gde je e∈C(e je unutar KP) ispunjen uslov e'∈C(e' je u KP). Drugim recima, nijedna poruka nije registrovana kao primljena, bez da je registrovano njeno slanje.

28. (apr 2021. 1.) Objasniti uz pomoc primera sta se podrazumeva pod pristupnom, lokacionom i migracionom transparentnoscu.

>Pristupna trasnparentnost - podacima i resursima se pristupa na jedinstveni nacin bez obzira da li se oni nalaze na lokalnom ili udaljenom racunaru
>Lokacijska transparentnost - korisnik ne zna (i ne mora da zna) gde je fizicki resurs lociran u sistemu
>Migraciona transparentnost - resurs moze promeniti lokaciju, a da klijent to ne primeti

29. (apr 2021. 2.) U distribuiranom sistemu tri procesa P0, P1 i P2 komuniciraju medjusobno. U procesu P0 vektorski casovnik ima vrednost (8, 2, 4). Koja poruka iz procesa P2 moze odmah biti prosledjena aplikaciji u procesu P0 ako je neophodno ocuvati uredjenje medjusobno zavisnih dogadjaja?
a. (8, 2, 6)
b. (9, 3, 5)
c. (1, 1, 5)
d. (4, 1, 3)
Obrazloziti kako se doslo do odgovora.

>a. (8, 2, 6) - ne jer tm[2] != V2(2) + 1
>b. (9, 3, 5) - ne jer tm > V2
>c. (1, 1, 5) - moze jer su oba uslova ispunjena
>d. (4, 1, 3) - ne moze, iz istog razloga kao 1

30. (apr 2021. 3.)
a. Definisati pojmove defekt(fault), greska (error) i otkaz (failure) i navesti primer koji ilustruje ova tri pojma.
b. Distribuirani server se sastoji od 4 replicirana servera. Pouzdanost svakok pojedinacnog servera je 0.9
* Ako je sistem projektovan tako da moze da funkcionise ako je bilo koji od servera u funkciji, kolika je pouzdanost celog sistema?
* Ako je sistem projektovan tako da moze da funkcionise samo ako su sva cetiri servera u funkciji (ispravna), kolika je pouzdanost celog sistema?

>a. Primer: U softverskom sistemu, nekorektna instrukcija koja vrsi dekrementiranje umesto inkrementiranje je defekt, kada se ova instrukcija izvrsi (moze i ne mora da se izvrsi) onda ce se generisati pogresna vrednost, odnosno nastace greska. Ako druge naredbe u programu koriste ovu promenljivu ceo sistem ce odstupati od zeljenog ponasanja.
>b. Ako je sistem projektovan tako da moze da funkcionise ako je bilo koji od server u funkciji, pouzdanost sistema je : P=1-(1-0.9)^4 = 0.9999
>Ako je sistem projektovan tako da moze da funkcionise samo ako su sva cetiri server u funkciji, onda je pouzdanost: P=(0.9)^4 = 0.6561

31. (apr 2021. 4.) Na slici su prikazana tri procesa p1, p2 i p3 koji medjusobno komuniciraju. Oznaciti svaki dogadjaj Lamportovim i vektorskim markicama. Da li je moguce da dva dogadjaja imaju jednake vrednosti Lamportovih markica? Ako je moguce, dati primer. Ako nije obrazloziti odgovor

>P1: (0, 0, 0) a(1, 0, 0) b(2, 0, 0) i(3, 4, 1)
>P2: (0, 0, 0) c(0, 1, 1) d(2, 2, 1) e(2, 3, 1) h(2, 4, 1)
>P3: (0, 0, 0) f(0, 0, 1) g(1, 0, 2) j(2, 3, 3)
>Moguce je da dva dogadjaja imaju jednake vrednosti Lamportovih markica. Na primer, dogadjaji h i j imaju istu vrednost markice

32. (apr 2021. 5.) Definisati kauzalnu konzistenciju. Da li je sledece skladiste podataka kauzalno konzistentno? Obrazloziti odgovor.
> Kod uslovne konzistencije upisi koji su potencijalno uslovljeni se moraju videti u svim procesima u istom redosledu. Konkurentni upisi se mogu videti u razlicitim redosledom u razlicitim procesima
> W(x)a -> W(x)b i ovim redosledom moraju da se prikazu u svim procesima sto nije slucaj u procesu C. Nije kauzalno konzistentno

33. (okt 2020. 1.) Sta se podrazumeva pod skalabilnim distribuiranim sistemom? Objasniti tehnike za postizanje skalabilnosti.

>Skalabilnost DS je jedan od najvaznijih projektantskih zadataka. Skalabilnost se moze posmatrati kroz tri dimenzije
>skalabilnost u odnosu na broj korisnika i resursa
>skalabilnost u odnosu na geografsku udaljenost resursa i korisnika
>administrativnu skalabilnost - sistemom se moze lako upravljati cak i ako se prostire kroz vise administrativnih domena
>Tri tehnike skaliranja
skrivanje komunikacionih kasnjenja - koriste se asinhrone komunikacije umesto sinhronih i download-ovanje deo koda na klijent stranu da bi se ubrzala obrada
Distribucija - podrazumeva da se komponente dele na manje delove, a zatim se ti delovi distribuiraju na vise masina u sistemu
Replikacija - pomaze da se poveca dostupnost i balansira opterecenje u sistemu da bi se postigle bolje performanse

34. (okt 2020. 2.)
a. Objasniti kako se uz pomoc vektorskih casovnika moze ostvariti uredjenje medjusobno zavisnih dogadjaja. Isto kao maj 2021.
b. Isto kao 29.

35. (okt 2020. 3.) Server je repliciran na 20 cvorova. Za odrzavanje konzistencije koristi se protokol baziran na kvorumu.
a. Ako se citanje obavlja samo sa jedne kopije, koliko kopija se mora najmanje mora azurirati u slucaju modifikacije da bi se obezbedila korektnost?
b. Ako se prilikom upisa azurira 11 kopija, koliko najmanje kopija se mora procitati da bi se obezbedila korektnost?
Obrazloziti odgovore

>N=20
>a. NR=1 -> NW=20
>b. NW=11 -> NR=10
>Zbog Giffordove seme, uslovi:
>1 NR + NW > N
>2 NW > N/2

36. (okt 2020. 4.) Na slici je prikazan Chord prsten modula 32. Prikazati kako izgledaju finger tabele svakog cvora.
>P1
>

| Start | Succ |
| -------- | -------- |
| P1+1 | P3 |
| P1+2 | P3 |
| P1+4 | P6 |
| P1+8 | P18 |
| P1+16 | P18 |
>P3
>
| Start | Succ |
| -------- | -------- |
| P3+1 | P6 |
| P3+2 | P6 |
| P3+4 | P18 |
| P3+8 | P18 |
| P3+16 | P24 |
>P6
>
| Start | Succ |
| -------- | -------- |
| P6+1 | P18 |
| P6+2 | P18 |
| P6+4 | P18 |
| P6+8 | P18 |
| P6+16 | P24 |

>P18

| Start | Succ |
| -------- | -------- |
| P18+1 | P24 |
| P18+2 | P24 |
| P18+4 | P24 |
| P18+8 | P1 |
| P18+16 | P3 |

>P24

| Start | Succ |
| -------- | -------- |
| P24+1 | P1 |
| P24+2 | P1 |
| P24+4 | P1 |
| P24+8 | P1 |
| P24+16 | P18 |
37. (okt 2020. 5.) Koja je uloga NameNode cvora kod HDFS? Kako se postize otpornost na greske (fault tolerance) kod HDFS?
> NN sep 2012
> Blokovi kod HDFS se repliciraju na vise cvorova sto omogucava da HDFS bude fault tolerant. Ako zvor koji sadrzi neki blok otkaze, postoje jos dva cvvora koji sadrze taj blok i omogucuju da se izracunavanje obavi bez problema. Faktor replikacije se moze promeniti u Hadoop konfiguraciji ili cak postaviti poseban faktor za svaki individualni fajl.

38. (sep 2020. 1.) Pobrojati redom korake kojima se ostvaruje povezivanje klijenta i servera kod DCE

>1 Registrovanje broja porta servera (procesa) u DCE demonu
>2 Registrovanje servera u direktorijumskom servisu (adresa serverske masine, ime servera i interfejsi koje implementira)
>3 Klijent kontaktira direktorijumski server da dobije adresu server masine (IP adresu) na kojoj se izvrsava server
>4 Klijent kontaktira DCE demon da bi dobio broj porta servera kome zeli da pristupi
>5 Poziv udaljene procedure

39. (sep 2020. 2.) Isto kao dec2021.

40. (sep 2020. 3.) Koje tipove gresaka moze tolerisati sistem koji koristi TMR (trostruku hardversku redundansu)? Obrazloziti.

>TMR obezbedjuje detekciji i korekciju bilo kog tipa greske. Sto se tice Vizantijskih gresaka, moze se tolerisati samo jedan jer je potrebno da vecina(ostale dve komponente) izglasaju ispravan rezultat. TMR se primenjuje u srpezi sa glasacima cija je uloga da se na osnovu izlaza izglasa koji je rezultat ispravan vecinskim glasanjem/

41. (sep 2020. 4.) Konzistencija
a. Sta je striktna konzistencija i zasto je nije moguce postici u distribuiranom sistemu?
b. Definisati sekvencijalnu i kauzalnu konzistenciju. Dati primer koji ilustruje razlike
c. Da li je sledece skladiste kauzalno konzistentno? Obrazloziti odgovor.

>a. Striktna koznistencija je najjaci model konzistencije i definise se kao: Bilo koja operacija nad podatkom X vraca rezultat poslednje write operacije nad X. Definicija je prirodna i ocigledna, ali implicitno usvaja postojanje globalnog vremena, tako da odredjivanje poslednje wirte operacije bude nedvosmisleno. U distribuiranom sistemu nije moguce postici striktnu konzistenciju iz tog razloga. Uzimamo sledeci primer: Proces Pi azurira vrednost x sa 1 na 2, a 1ns kasnije proces Pj cita tu istu promenljivu. Pod pretpostavkom da se koriste opticka vlakna i da su racunari na udaljenosti od 3m, poruka kojom se zahteva azuriranje bi trebalo da se krece 10 puta brze od brzine svetlosti da bi konzistentnost bila ocuvana. Ovo je nemoguce
>b.
>Sekvencijalna konzistencija
>Rezultat bilo kog izvesanja je isti kao da su (read i write) operacije svih procesa na skladistu podataka izvrsene u nekom sekvencijalnom redosledu i operacije svakog pojedinacnog procesa se pojavljuju u ovoj sekvenci u onom redosledu koji je odredjen njihovim programom.
>Kauzalna konzistencija:
>Upisi(write) koji su medjusobno uslovljeni moraju se videti u svim procesima u istom redosledu. Konkurentni upisi se mogu videti u razlicitom redosledu u razlicitom procesu.
>c.
>Nije kauzalno konzistentno. W(x)a -> W(x)b i moraju da se vide po tom redosledu u svim procesima, sto ovde nije slucaj u procesu C.

42. (sep 2020. 5.) Objasniti kako se ostvaruje pridruzivanje cvora u Gnutella mrezi.

>1 Peer cvor X mora prvo pronaci neki drugi peer cvor koji se vec nalazi u Gnutella mrezi. Koristi listu potencijalnih kandidata za koje se zna da su cesto prisutni ili kontaktira Gnutella sajt koji sadrzi takvu listu
>2 X sekvencijalno pokusava da uspostavi TCP konekciju sa peer cvorovima iz list, dok sa nekim ne uspostavi konekciju, npr. Y
>3 Nakon uspostavljanja TCP konekcije X salje Ping poruku Y. Y prosledjuje Ping poruku drugim peer cvorovima u overlay mrezi. Poruka sadrzi i brojac koji se dekrementira pri prolasku kroz savki peer cvor da bi se bujica drzala pod kontrolom.
>4 Svi peer cvorovi koji prime Ping poruku odgovaraju sa Pong porukom. Pong poruka sadrzi IP adresu peer cvora, broj fajlova koje cvor ima na raspolaganju i ukupnu velicinu fajlova u Kbyte.
>5 X moze primiti mnogo Pong poruka. X moze nakon toga uspostaviti nove TCP konekcije i dodati nove potege u overlay mrezu.

43. (jun 2020. 1.) Objasniti razliku između tranzijentnih i perzistentnih komunikacija u distribuiranom sistemu baziranom na midleware sa razmenom poruka.

>Komunikacije mogu biti perzistentne(istrajne), kod kojih se poruka pamti u komunikacijonom serveru koliko je potrebno da bi se isporucila odredistu ili tranzijentne, kod kojih se poruka odbacuje ako komunikacioni server nije u stanju da je isporuci sledecem serveru ili odredistu.
>Kod perzistentne komunikacije sve poruke koje se prenose se pamte u komunikacionom serveru dok se ne isporuce sledecem server izato izvor ne mora biti aktivan nakon sto dostavi poruku i prijemnik ne mora biti aktivan kada izvor salje poruku. E-mail je tipican primer perzistentne komunikacije
>Kod tranzijentne komunikacije poruke se kladiste sako dok se izvorisna i odredisna aplikacija izvrsavaju, a ako komunikacioni server ne moze da isporuci poruku, ona se odbacuje. Ako se agenti ne izvrsavaju, poruke se odbacuiju. Komunikacioni sever je u ovom slucaju store-and-forward ruter

44. (jun 2020. 2.) isto kao okt 2021. 2.

45. (jun 2020. 3.) isto kao apr 2021.

46. (jun 2020. 4.) U distribuiranom sistemu klijent koristi RPC za komunikaciju sa serverom. Klijent šalje zahtev serveru (npr. operation x( )) sve dok ne dobije odgovor od servera.
a. Koja RPC semantiku u slučaju greške je u ovom slučaju implementirana?
b. Objasniti kako mora da bude implementiran server da bi se ovakava semantika obezbedila? Navesti bar dve mogućnosti.

>a. At-least-one sematniku, jer klijent moze vise puta poslati zahtev.
>b. Jedna mogucsnost je da x bude idempotentna operacija i da nije problem da se izvrsi vise puta, a druga mogucnost je da server bude stateful i da vodi racuna o klijentskim zahtevima i da je u stanju da prepozna duplikate. Neophodno je obezbediti da se x ne izvrsi ponovo (ako nije idempotentno)

47. (jun 2020. 5.)Na slici su prikazana 4 distribuirana procesa koji međusobno komuniciraju. Prikazati konzistentni presek koji uključuje događaj j i najmanji mogući broj događaja u ostalim procesima.
>

48. (sep 2018. 1.) Objasniti sledece semantike kod poziva udaljenih procedura:
a. mozda
b. At-least-once
c. At-most-once

>a.
>b. at-least-once(bar jednom) - metode se pozivaju jednom ili vise puta ukoliko se odgovor na prvi poziv ne primi ili istekne timeout. Ova sematnika se koristi za idempotentne metode (mogu se izvrsavati vise puta bez posledica, npr. citanje podataka).
>c. at-most-once(najvise jednom) - metoda se izvrsava jedanput ili nijednom. Ovakva semantika se koristi za metode koje nisu idempotentne(imaju efakte, npr. modifikacija ili dodavanje podataka).

49. (sep 2018. 2.) Vektorski casovnici
a. Navesti pravila za implementaciju vektorskih casovnika.
b. Na osnovu vrednosti vektorskih casovnika koji dogadjaj je prethodio dogadjaju ciji je vektorski casovnik (4, 2, 8, 5)? Dati kratko obrazlozenje
i (3, 1, 7, 7)
ii (5, 1, 6, 2)
iii (4, 2, 8, 4)
iv (4, 3, 8, 5)

>a. Isto kao maj 2021. 3.
>b. iii (4, 2, 8, 4) kod vektoskih casovnika vazi ako je Via <= Vjb onda je a->b, pri cemu je V1 <= V2 <=> V1[k] <= V2[k] (za svako k = 1,...N)

50. (sep 2018. 3.) Koji tipovi gresaka u odnosu na trajanje postoje. Dati primer za svaku od njih. Objasniti razliku izmedju "mirnih" i Vizantijskih gresaka. Koju vrsku gresaka je teze detektovati. Obrazloziti.

>U odnosu na trajanje greske mogu biti:
>prolazne(transient) - pojave se jednom i nestanu, npr. kada istekne time out za prenos poruke, ali nakon ponovnog slanja porukla je uspesno otposlata.
>periodicne (intermittent) - greska se pojavi, zatim nestane, pa se ponovo pojavi. Najnezgodniji tip greske. Primer je greska u mreznom kablu kod koga postoji neki prekid.
>stalne(permanent) - greske koje postoje sve dok se komponenta ne zameni ispravnom. Primer je greska u hard disku, pregorela komponenta, bagoviti softver.
>
>Mirna greska - komponenta prestaje sa radom i ne generise nikakav izlaz ili generise poruku o gresci
>Vizantijske greske - komponenta nastavlja sa radom i generise pogresan rezultat. Ove greske je teze detektovati bas zbog toga sto komponenta nastavlja sa radom bez indikaciaj da postoji greska (osim sto generise pogresan rezultat).

51. (sep 2018. 4.) Tri procesa P1, P2 i P3 pristupaju promenljivama x, y, i z. Svaki proces ima sopstvenu kopiju skladista podataka u kojoj se nalaze promenljive. Inicijalno sve promenljive imaju vrednost 0. U procesima P1, P2 i P3 se izvrsavaju sledece naredbe:
P1
A = 1
x = A
P2
y = x
z = y
P3
print y
print x
print z
Koji rezultati print naredbi nisu moguci pod uslovom da je skladistenje podataka sekvencijalno konzistentno.

>(y, x, z) = (0, 0, 0)moze (0, 0, 1)moze (0, 1, 0)moze (0, 1, 1)moze (1, 0, 0)ne moze (1, 0, 1)ne moze (1, 1, 0)moze (1, 1, 1)moze
52. (sep 2018. 5.) Isto kao okt 2020

53. (okt2 2017. 1.) Sinhronizacija casovnika se vrsi Kristijanovim algoritmom. Poruka sa racunara A je poslata u trenutku 1:10.100 (po lokalnom vremenu racunara A). Server B je primio poruku u 1:15.000(po svom lokalnom vremenu), procesirao zahtev i poslao odgovor u koje stoji vreme 1:15.005, koja je stigla do racunara A u 1:10.150. Na koju vrednost ce biti postavljen casovnik u racunaru A?
>tsA = 1:10.100
>trB = 1:15.000
>tsB = 1:15.005
>trA = 1:10.150
>delta_tA = trA - tsA = 0:0.050
>tA = tsB + (delta_tA/2) = 1:15.030

54. (okt2 2017. 2.) DCE cell directory servis u slucaju RPC omogucava da:
a. klijent pronadje na kom serveru je implementirana udaljena procedura
b. klijentu da pronadje broj porta na koje je implementirana udaljena procedura
c. server obavi prozivku klijenta
d. distribuciju objekta izmedju vise servera

>DCE cell directory se korsti za lociranje servera na kome je implementiran udaljena procedura, a.

55. (okt2 2017. 3.) Sta po definiciji potpuno uredjena grupna komunikacija znaci
a. poruke se isporucuju procesima u FIFO redosledu
b. poruke se isporucuju procesima onako kako su se desile u realnom vremenu
c. poruke se isporucuju procesima u "happen-before" redosledu
d. poruke se isporucuju procesima u istom redosledu

>poruke se isporucuju procesima u istom redosledu, d.

56. (okt2 2017. 4.) Procesi P1, P2 i P3 se konkurentno izvrsavaju. Navesti sve rezultate tri print naredbe, npr. print x=0, print y=0, print z=0, koji nisu moguci pod uslovima sekvencijalne konzistencije
P1
A = 1
x = A
P2
y = x
z = y
P3
print y
print x
print z

>sep 2018. 4.

57. (okt2 2017. 5.) Objasniti problem dve armije i kako se on moze prevazici.

>
>Problem dve armije se ne moze prevazici.
>Dve divizije jedne armije A i B treba da koordinisu napad na drugu armiju C. A i B imaju po 2000 vojnika, a C ima 3000 i ako zajedno napadnu, mogu da pobede C, a u suprotnom gube. A i B su fizicki odvojene i koriste kurira za komunikaciju. A salje poruku B u kojoj kaze "izvrsi napad u zoru". B prima poruku i salje potvrdu - "ok". Kurir stize do A sa potvrdom od B ali tada A zakljucuje da B ne zna da li je A primio potvrdu i nece biti siguran dali da obave napad. A moze odluciti da posalje poruku "primio sam poruku" ali tada A nece biti siguran da li je poruka stigla do B i tako dalje u krug. Ovaj problem se naziva problem problem visestrukiv potvrda i on pokazuje da ukoliko su komunikacije nepouzdane, usaglasavanje dva procesa nikad nije moguce i da se jedino mozemo nadati da ce kominikacioni kanal najcesce pouzdano preneti poruku. Ne postoji protokol koji resava problem nepouzdanih kanala.

58. (sep 2017. 1.) Simbol -> oznacava Lamportovu relaciju "desilo se pre". a i b su dogadjaji. Va je vektorski casovnik duzine n koji predstavlja vreme kad aje dogadjaj a nastupio.
a. Koja karakteristika sistema odredjuje velicinu n?
b. Definisati sta znaci Va=Vb i Va>Vb.
c. Ako je a->b, sta znamo o Va i Vb?
d. Ako ne vazi a->b niti je b->a, sta znamo o Va i Vb?

>a. n = broj procesa u sistemu
>b.
>Va = Vb <=> Va[k] = Vb[k] za svako k=1,...,n
>Va > Vb <=> Va[k] > Vb[k] za svako k=1,...,n
>c. a->b znaci da je Vz < Vb
>d. Nista konkretno, osim da ne vaze relacije Va < Vb i Va > Vb (Va i Vb mogu i ne moraju da budu jednaki)

59. (sep 2017. 2.) Cetiri procesa P1, P2, P3 i P4 pristupaju zajednickoj promenljivoj x. Svaki proces ima sopstvenu kopiju skladista podataka u kojoj se nalazi ova promenjiva
a. Da li je skladiste podataka prikazano na slici kauzalno konzistentno? Obrazloziti
b. Koji je dogadjaj trebalo dodati ili obrisati da bi se odgovor promenio?

>a. Jeste. Ispunjen je uslov da svi procesi vide potencijalno uslovljene upise u istom redosledu. Potencijalno uslovljeni upisi su W(x)1, W(x)2 jer je W(x) -> R(x)1 ^ R(x)1 -> W(x)2. Svi procesi vide prvo 1 kao vrednost x, a zatim 2. Vrednost 3 nije bitna kada se pojavi jer W(x)3 nije uslovljen nekim drugim upisom.
>b. Na primer ovo skladiste ne bi bilo kauzalno konzistentno

| P | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- | ---- | --- | --- | --- | --- | ---- |
| P1 | W(x)1 | | W(x)3 | | | |
| P2 | R(X)1 | W(x)2 | | | | |
| P3 | | | | R(x)3 | R(x)2 | **R(x)1** |
| P4 | R(x)1 | | | R(x)2 | R(x)3 | |

60. (sep 2017. 3.) Isto kao maj 2021.

61. (sep 2017. 4.) Objasniti protokole konzistencije zasnovane na postojanju primarne kopije. Koji je najjaci vid konzistencije koji se ovim protokolima moze postici?

>Kod protokola zasnovanih na postojanju primarne kopije (i backup kopija) write operacija se moze izvrsiti samo na primarnoj kopiji. Kod ovih protokola, svaki podatak X u skladistu podataka ima pridruzeni primar koji je zaduzen za koordinaciju upisa u X. Ukoliko je primar fiksiran, rec je o Remote-write protokolima, a ukoliko se write operacija moze obaviti lokalno, nakon sto je primar pomeri na proces koji je inicirao write, rec je o local-write protokolu
>Kod remote write protokola sve read i write operacije se obavljaju na primaru, a ostale kopije sluze samo kao backup, jer podaci se ne replicirajum vec se nalaze na jednom serveru. Uz modifikaciju moguce je dozvoliti da se read operacije izvrsavaju na bilo kojoj kopiji, a write samo na primarnoj (primary-backup protokol).
>Kod local-write protokola primar kopija migrira izmedju procesa koji zele da obave write operacije. Kada proces zeli da azurira podatak X, on prvo locira primarnu kopiju, pa je prevlaci kod sebe. Prednost ovoga je sto se vise uzastopnih write operacija moze obaviti lokalno. Read operacije se svakako obavljaju lokalno.
>
>Protokoli bazirani na postojanju primarne kopije obezbedjuju laku implementaciju sekvencijalne konzistencije, jer primar obezbedjuje uredjenje svih write zahteva na globalno jedinstven nacin (sve write operacije se vide u istom redosledu).

62. (sep 2017. 5.) Kada nastupi greska u distribuiranom sistemu potrebno je izvrsiti oporavak od greske i vratiti sistem u korektno stanje. Koje strategije za oporavak od greske se koriste u DS? Koje su prednosti i nedostaci ovih strategija?
>1 Povratak u stanje pre nastupanja greske (backward recovery) - sistem se vrati u neko pretkodno korektno stanje koriscenjem tacaka provere (checkpoints), a zatim se nastavlja sa radom. Ova tehnika je jednostavnija za implementaciju i cesce se koristi. Nedostatak je sto belezenje stanja sistema ubacivanjem tacaka provere moze biti veoma skupo, pogotovu ako greske retko nastupaju.
>2 Forward recovery(prelazak u novo stanje) - prevesti sitem u novo korektno stanje nakon cega se moze nastaviti sa radim (npr. erasure coding). Da bu ova tehnika funkcionisala neophodno je predvideti sve potencijalne greske, a kada nastupi greska, mehanizam za oporavak zna sta treba da uradi da bi doveo sistem u naredno korektno stanje

63. (sep 2017. 6.) Neki p2p sistemi koriste centralni server, a neki potpuno eliminisu koriscenje istih. Koje su prednosti a koji su nedostaci ovih arhitektura?

>Kod centralizovanih P2P sistema se koristi jedan ili vise servera koji sadrze centralne direktorijume dge svi cvorovi registruju sadrzaje koje su spremni da dele sa drugim peer cvorovima. Zbog ovoga pronalazenje cvora mreze i zeljenog sadrzaja je dosta jednostavnije u odnosu na distribuirane P2P sisteme. Problem sa ovakvim protokolima lezi u njihovoj slaboj otpornosti na greske, jer je otkaz centralnog cvora fatalan za ceo sistem. Takodje, centralni direktorijum u nekom trenutku moze postati usko grlo jer sa porastom broja korisnika baza koju centralni direktorijum odrzava moze postati ogromna i dobijati veliki broj zahteva. Jos jedan nedostatak ovih sistema lezi u pravima izdavaca. Kada postoji centralni direktorijumski server, zakonskom procedurom se kompanima moze naterati da ugasi server.
>Kod potpuno decentralizovane arhitekture (Gnutella, Chord) svi nedostaci se prevazilaze. Ukoliko je u pitanju nestruktuirana overlay mreza, kao kod Gnutella-e mogu nastati potencijalni problemi sa skaliranjem, jer sa porastom broja korisnika efikasnost sistema opada i operacije trazenja i pridruzivanja postaju skuplje. Ukoliko je rec o npr. Chord protokolu sa struktuiranom overlay mrezom, ove nedostatke je moguce prevazici tako da se obezbedi dobro balansiranje opterecenja ravnomernom distribucijom kljuceva, ali i skalabilnost, jer cena pronalazenja kljuceva raste logaritamski sa porastom broja kljuceva.

64. (maj 2017. 1.) Definisati
a. striktnu konzistenciju
b. sekvencijalnu konzistenciju
c. uslovnu konzistenciju
d. FIFO konzisntenciju
e. Koja od skladista na slici su sekvencijalno konzistentna, uslovno konzistentna i FIFO konzistentna?
>a-c ima
>d - FIFO - upisi koje obavi jedan proces se video od strane drugih procesa po redosledu u kome su izdati ili upisi razlicitih procesa se mogu videti u razlicitom redosledu u razlicitim procesima. Drugim recima, ne postoje nikakve garancije o tome kako razliciti procesi vide upise drugog procesa, osim sto dva ili vise upisa iz istog izvora moraju stici po redosledu.
>e.
>e1 - FIFO konzistencija (upis b posle upisa c), nije kauzalno kinzisentno(upis a mora da se vidi pre upuisa b), nije sekvencijalno (svi upisi se moraju videti u istom redosledu)
>e2 - upisi se svuda vide u istom redosledu -> sekvencijalna, kauzalna i FIFO
>e3 - jeste FIFO(nijedan proces ne obavlja vise od jednog upisa), jeste kauzalna(nema uslovljenih upisa), nije sekvencijalna(upisi a i b se ne vide svuda u istom redosledu)

65. (maj 2017. 2.) Koje vrste replika postoje? Koje se informacije mogu proslediti replikama kada se obavlja azuriranje?

>Replike
>permanentne replike - pocetni skup replika koje formiraju distribuirana skladista podataka
>replike inicirane od strane servera - formiraju se na zahtev vlasnika skladista
>replika inicirana od strane klijenta - klijentski kes
>
>Prosledjuje se
>Samo obavestenje o azuriranju, svodi se na invalidaciji ostalih kopija
>Podaci koji su azurirani. Azurirani podaci se prenose replikama
>Operacije koje su izazvale azuriranje. Ne prenose se podaci, vec operacije koje svaka replika treba da obavi (ovakav prilaz poznat je pod nazivom aktivno repliciranje).

66. (maj 2017. 3.) Fajl je repliciran na N servera. Ako se koristi Griffordov algoritam za postizanje konsenzusa, navesti koji uslovi moraju biti zadovoljeni i sta koji uslov garantuje? Ako je N=10 navesti tri dozvoljene kombinacije read i write kvoruma.

>uslov 1: Nr + Nw > N
>uslov 2: Nw > N/2
>1. kombinacija: Nr = 1, Nw = 10
>2. kombinacija: Nr = 5, Nw = 6
>3. kombinacija: Nr = 3, Nw = 8

66. (maj 2017. 4.) U DS postoje 5 procesa koji treba da se usaglase kod donosenja odluke. Ako dva procesa generisu pogresne rezultate da li je moguce doneti odluku? Ilustrovati primerom sa jednim generalom i 4 porucnika.

>Ne jer je potrebno da broj procesa bude veci od 3m(veci od 6 u ovom slucaju), gde je m broj neispravnih procesa

67. (maj 2017. 5.) Na slici je Choed prsten koji koristi n=2^3 identrifikatora. Punim kruzicima oznaceni su peer cvorovi i njihovi identifikatori. Prikazati kojim cvorovima ce biti dodeljeni objekti sa kljucevima k1=1, k2=3, k3=5, k4=7

>N0 - k4=7
>N1 - k1=1
>N2 -
>N4 - k2=3
>N6 - k3=5

68. (jun 2013. 1.) Sta je funkcija middleware u DS?

>Da bi se pojednostavilo pisanje i razvoj distribuiranih aplikacija, potrebno je obezbediti softversku podrsku koja ce aplikativno programiranje osloboditi detalja vezanih za inteprocesnu komunikaciju, sinhronizaciju, bezbednost itd. Postoji mnogo protokola opste namene koji su od koristi za mnoge aplikacije a ne mogu se kvalifikovati kao transportni protokoli. Ti protokoli ne spadaju u kategoriju middleware protokola i oni pruzaju razlicite usluge aplikaciji, kao sto su autentifikacija (provera identiteta) i autorizacije (prava pristupa), sinhronizacija(vremenska sinhronizacija) u cilju utvrdjivanja redosleda dogadjaja u DS, ali i sinhronizacija kod pristupa deljivim resursima - uzajamno iskljucivanje. Middleware komunikacioni protokoli pruzaju visi nivo komunikacionih usluga (komunikacije je sakrivena iza poziva procedura ili metoda - RPC ili RMI, ili je na raspolaganju skup funkcija za razmenu poruka - MEssage orriented).
69. (jun 2013. 2.) Isto kao okt 2020

70. (jun 2013. 3.) Pobrojati redom aktivnosti koje se izvrsavaju kod poziva udaljene procedure.
>1 Klijent poziva lokalnu proceduru (klijent stub) za klijentski proces ona izgled kao aktuelna procedura koju treba pozvati
>2 Klijentski stub pakuje argumene za udaljenu proceduru(ovo moze ukljuciti i konverziju u standardni format) i gradi jednu ili vise mreznih poruka i poziva lokalni OS (send primitiva za slanje, receive za primanje) - parameter marshaling
>3 Lokalni OS salje poruku udaljenom OS (koriscenjem transportnog protokola)
>4 Udaljeni OS prosledjuje poruku serverskom stub-u. Serverski stub funkcija prima poruku od lokalnog OS(izvrsava receive primitivu), raspakuje je (unmarshakibg) i izvlaci argumene za poziv procedure
>5 Serverski stub poziva zeljenu serversku proceduru i predaje joj parametre koje je primio od klijent(stavlja ih na stack)
>6 Server izvrsava poziv procedure i rezultat vraca stub-u
>7 Serverski stub pakuje rezultat u poruku i poziva svoj lokalni OS(send)
>8 Serverski OS salje poruku klijentskom OS
>9 Lokalni OS prosledjuje poruku klijent stub-u
>10 Klijent stub izvlaci rezultat iz poruke i vraca je klijentskom procesu. Klijent nastavlja sa daljim izvrsenjem

71. (jun 2013. 4.) Izlaz iz IDL kompajlera sastoji se od tri fajla. Koji su to fajlovi i sta sadrze?
>sep 2021. 1.

72. (jun 2013. 5.) Na slici su prikazana tri procesa koji medjusobno komuniciraju. U svakom procesu logicki casovnici su inicijalizovani na nulu. Pokazati kako se uz pomoc Lamportovih vremenskih markica sinhronizuju lokalni casovnici.
>kol 1 2015.

73. (jun 2013. 6.) Pretpostavimo da postoje tri procesa P1, P2 i P3 u grupi. Svaki procesa salje dve poruke svim ostalim procesima u grupi ukljucujuci i samog sebe (multicast) sa sledecim vrednostima vremenskih markica:
- P1 salje poruku m1 sa vremenskom markicom (9, 1) i poruku m2 sa markicom (11, 1)
- P2 salje poruku m3 sa vremenskom markicom (9, 2) i poruku m4 sa markicom (10, 2)
- P3 salje poruku m5 sa vremenskom markicom (10, 3) i poruku m6 sa markicom (12, 3)
Ako je potrebno ostvariti potpuno uredjenu grupnu komunikaciju, u kom redosledu ce svih 6 poruka biti primljeno u svakom procesu?

>m1(9, 1)
>m2(11, 1)
>m3(9, 2)
>m4(11, 2)
>m5(10, 3)
>m6(12,3)
>U svim procesima se smestaju poruke u red i sortiraju se po markicama
>1 m1(9, 1)
>2 m3(9, 2)
>3 m4(10, 2)
>4 m5(10, 3)
>5 m2(11, 1)
>6 m6(12, 3)
>Ovo ce biti prijemni red izvrsenja u svakom procesu

74. (jun 2013. 7.) Za izbor koordinatora se koristi "bully" algoritam. Sta ce se desiti ako dva procesa jednovremenu pokrenu izbor novog koordinatora?
> Oba procesa ce svim procesima sa vecim identifikatorima od sebe pokrenuti izbor(salju election poruke). Proces sa vecim ID ce poslati odgovor na ovu poruku (ok), nakon cega se proces samanjim ID povlaci iz izbora. Algoritam se nastavlja sve dok proces sa najvecim ID ne posalje election poruku i ne dobije odgovor ni od koga, nakon cega sve obavestava da je on novi koordinator.

75. (jul 2020. 1.) Sta je IDL? Koja je njegova uloga u DS?
>IDL (Interface Definition Language) predstavlja poseban jezik koji sluzi za definiciju interfejsa. Definicija interfejsa je slicna deklaraciji prototipa funkcija - sadrzi set funkcija zajedno sa ulaznim parametrima i vrednostima koje vracaju i mogucim izuzecima. Uloga iDL jeste da se kompajlerima intefejsa pomocu RPC kompajlera dobije klijentski i serverski stub-ovi. Oni se dalje mogu povezati sa odgovarajucim stub funkcijama.

76. (jul 2020. 2.) Na slici su prikazana 3 procesa koji medjusobno komuniciraju. U svakom procesu logicki vektorski casovnici su inicijalizovani na 0. Pokazati kako se uz pomocu vektorskih casovnika obavlja sinhronizacija medjusobno zavisnih dogadjaja. Prikazati vrednost vektorskih casovnika kod slanja i prijema svake poruke. Takodje, oznaciti poruke koje su baferovane prilikom prijema i trenutak kad se prosledjuju aplikaciji.
>

77. (jul 2020. 3.) Na slici su prikazana tri konkurentna procesa. Inicijalne vrednosti promenljivih x, y, i z su 0. Ako proces P1 generise izlaz 00, proces P2 izlaz 11, a proces P3 izlaz 10, da li je dobijeni rezultat korektan sa stanovista sekvencijalne konzistencije? Da li je dobijeni rezultat korektan sa stanovista kauzalne konzistencije? Obrazloziti
>P1 00
>P2 11
>P3 10

>x = 1 P1
>print(y, z) - P1
>z = 1 P3
>print(x, z) P2
>print(x, u) P3
>y = 1 P2
>Jeste sekvencijalno konzistentno
>Kauzalno konzistentno bi bilo u bilo kom slucaju obzirom da nema upisa koji su medusobno uslovljeni

78. (jul 2020. 4.) Da li je sledeca tvrdnja tacna: Protokol baziran na postojanju primarne kopije (i backup kopija) je otporniji na otkaze od protokola baziranih na kvorumu? Obrazloziti

>Netacno, protokol baziran na postojanju primarne kopije u slucaju otkazivanja primara mora da pokrece election kako bi se izabrao novi primar, dok se kod protokola baziranih na kvorumu mora da otkaze N/2 masina kako sistem ne bi funkcionisao ispravno.

79. (jul 2020. 5.) dec 2021. 5.

80. (kol1 2019. 1.) a. definisati sekvencijalnu konzistenciju b. Procesi P1, P2 i P3 se konkurentno izvrsavaju. Inicijalno su vrednosti promenljivih postavljene na 0. Nakon okoncanja procesa, koje vrednosti promenjivih u, v, w nisu moguce pod uslovima sekvencijalne konzistencije?

>(u, v, w) = (0, 0, 0)ok (0, 0, 1)ok (0, 1, 0)ok (0, 1, 1,)ok (1, 0, 0)ne (1, 0, 1)ok (1, 1, 0)ne (1, 1, 1)ok

81. (kol 2018. 1.) Na slici su ti procesa koja medjusobno komuniciraju. Za svaki dogadjaj dati vrednost: a. Lamportovih vremenskih markica b. Vektorskih casovnika
c. Sta je tacno u Lamportovom sistemu logickih casovnika (zaokruziti odgovor):
i If a -> b then C(a) < C(b) ili
ii If C(a) < C(b) then a -> b

>
>c. if a -> b then C(a) < C(b)