1.3 pakao Flashcards
(12 cards)
Koja je osnovna razlika između sinhronih i asinhronih distribuiranih sistema ?
Sinhroni sistemi imaju poznatu gornju granicu vremena potrebnu procesoru da izvrši jedan logički
korak i poznatu gornju granicu brzine drixa časovnika . Asinhroni sistemi nemaju ni jednu od
prethodno navedenih osobina. Distribuirani sistemi su inherentno asinhroni, ali postoje tzv.
sinhronizatori koji im obezbeđuju apstrakciju sinhronih sistema .
Navedite i objasnite različite modele otkaza procesa i linkova
Modeli otkaza procesa:
o Zaustavljanje usled otkaza (Fail-stop): Proces koji inače funkcioniše ispravno, otkaže od
jednog trenutka pa nadalje. Ostali procesi mogu da registruju da je otkazao .
o Raspad (Crash): Proces otkaže od jednog trenutka pa nadalje, ali ostali procesi nemaju
saznanje o tom otkazu .
o Propušteni prijem: Proces povremeno propušta prijem nekih poruka koje su mu poslate.
o Propušteno slanje: Proces povremeno propušta slanje nekih poruka koje je trebalo da
pošalje .
o Generalni propust: Proces povremeno propušta prijem i/ili slanje nekih poruka .
o Vizan8jski ili maliciozni otkaz sa auten8fikacijom: Proces ispoljava proizvoljno
ponašanje, ali tvrđnje o primljenim porukama od korektnih procesa mogu se
autenEfikovaE upotrebom elektronskog potpisa .
o Vizan8jski ili maliciozni otkaz: Proces ispoljava proizvoljno ponašanje, ali se bilo koje
njegove tvrdnje ne mogu autenEfikovaE .
Modeli otkaza linkova:
o Raspad (Crash): Link prestaje da prenosi poruke.
o Propust (Omission): Link prenosi neke poruke, a neke ne.
o Vizan8jski otkaz: Link ispoljava proizvoljno ponašanje, uključujući kreiranje
nenamenskih poruka ili menjanje regularno poslaEh poruka .
Koja je uloga razapinjućeg stabla (spanning tree) u distribuiranim algoritmima i kako se
koriste operacije brodkasta i konvergekasta na njemu?
Razapinjuće stablo je korisno za distribuciju (preko brodkasta) I sakupljanje (preko
konvergekasta) informacija ka/sa svih čvorova u mreži .
* Brodkast algoritam:
o BC1: Koren šalje informacije koje se difuzno upućuju na sve njegove potomke .
o BC2: Kada čvor (koji nije koren) primi informaciju od svog roditelja, on je kopira i šalje
svojim potomcima .
* Konvergekast algoritam: Prikuplja informacije sa svih čvorova u korenski čvor da bi se u njemu
izračunala neka globalna funkcija . Inicira se u čvorovima koji su listovi, obično kao odgovor na
brodkast zahtev .
o CVC1: Čvor list šalje informaciju svom roditelju .
o CVC2: Srednji čvor (nije list, nije koren): Kada se prime informacije od svih potomaka,
one se objedinjene šalju roditelju .
o CVC3: Korenski čvor: Kada se primi informacija od svih čvorova potomaka, izvršava se
potrebna globalna funkcija .
Zašto je izbor lidera važan u distribuiranim sistemima?
Izbor lidera je potreban u mnogim distribuiranim sistemima i algoritmima jer algoritmi u opštem
slučaju nisu kompletno simetrični , pa neki procesi moraju imati vodeću ulogu da bi inicirali
algoritam.
Drugi razlog je sprečavanje višestruke inicijacije algoritma , čime se štede resursi .
Originalno ispitno pitanje: Distribuirani sistem sadrži 6 servera (S1-S6) na kojima se čuvaju podaci
(Q, R, S). Podaci se čuvaju na sledećim serverima: S1 – Q, R, S; S2 – R; S3 – Q, R; S4 – Q, S; S5 – S;
S6 – R, S. Za pristup podacima se korisE protokol većine . Ako pretpostavimo da transakcija T1
zahteva podatak S na serveru S2 i da podatak S nije zaključan, opisaE korake kako se ovaj podatak
otključava i zaključava primenom protokola većine.
Prvo, idenEfikujemo koji serveri čuvaju podatak S: S1, S4, S5, S6 . Podatak S na serveruS2 nije
relevantan jer S2 ne sadrži podatak S, već samo R .
* Koraci zaključavanja (primenom protokola većine / kvoruma):
1. Transakcija T1, koja želi da pristupi podatku S, mora da formira kvorum servera koji drže kopiju
podatka S. U ovom slučaju, to su S1, S4, S5, S6 (ukupno 4 servera). Da bi dobila pristup, T1
mora da dobije dozvolu od većine servera u tom skupu. Većina od 4 servera je 3 (obično c ei l (
N/ 2) ili f l oor ( N/ 2) + 1 za neparne N ili N/ 2 + 1 za parne N sa striktnom većinom) .
2. T1 šalje REQUEST poruke (npr., REQUEST( T1, S) ) prema serverima S1, S4, S5, S6 .
3. Kada server (npr. S1) primi REQUEST poruku za podatak S od T1, ukoliko podatak S nije
zaključan i server nije poslao REPL Y nekom drugom sajtu za taj podatak, on šalje REPLY poruku
nazad transakciji T1 i stavlja zahtev T1 u svoj red čekanja . U suprotnom, ako je podatak
zaključan ili je već poslao REPL Y , zahtev T1 se stavlja u red čekanja .
4. Transakcija T1 ulazi u kriEčnu sekciju (tj. zaključava podatak S) tek nakon što primi REPLY
poruke od većine servera (3 od 4) koji poseduju podatak S .
- Koraci otključavanja:
1. Kada T1 završi sa korišćenjem podatka S (izađe iz kriEčne sekcije), ona šalje RELEASE poruku
svim serverima koji su bili deo kvoruma i koji su joj dali dozvolu (npr., S1, S4, S5, S6) .
2. Kada server (npr. S1) primi REL EASE poruku od T1, on uklanja zahtev T1 iz reda čekanja i šalje
REPL Y poruku sledećem zahtevu u redu (ako postoji) . Ako je red prazan, server ažurira svoje
stanje tako da nije poslao REPL Y od kada je primio poslednju REL EASE poruku .
Koja su osnovna svojstva distribuiranog uzajamnog isključivanja ?
Prinudno uzajamno isključivanje: Istovremeno je samo jednom procesu dozvoljen ulazak u
njegovu kriEčnu sekciju, između svih procesa koji imaju kriEčne sekcije za isE resurs ili deljeni
objekat .
Sloboda od zastoja/izgladnjivanja: Ne sme se dozvoliE procesu koji zahteva pristup kriEčnoj
sekciji da na nju čeka beskonačno dugo (nema uzajamnog blokiranja ili gladovanja) .
Otkaz ne-kri8čne sekcije: Proces koji se zaustavlja u svojoj sekciji koja nije kriEčna mora to da
uradi bez uEcaja na ostale procese .
Ulazak bez kašnjenja: Kada nijedan proces nije u kriEčnoj sekciji, bilo kom procesu koji zahteva
ulazak u svoju kriEčnu sekciju mora se dozvoliE ulazak bez kašnjenja .
Nema pretpostavki o brzinama: Ne prave se pretpostavke koje se odnose na relaEvne brzine
procesa ili broj procesora .
Konačno trajanje CS: Proces ostaje unutar svoje kriEčne sekcije samo konačno dugo .
Koja je glavna razlika između centralizovanog i distribuiranog algoritma za uzajamno
isključivanje?
Centralizovani algoritam: Jedan čvor je određen za kontrolni (upravljački) čvor. Ovaj čvor
upravlja pristupom svim deljenim objekEma, i samo on odlučuje o raspodeli resursa. Sve
neophodne informacije sakupljene su u kontrolnom čvoru. Glavni nedostatak je što ukoliko dođe
do otkaza kontrolnog čvora, ruši se mehanizam uzajamnog isključivanja .
Distribuirani algoritam: Svi čvorovi imaju jednak nivo informacija u proseku i svaki čvor ima samo
delimičnu sliku ukupnog sistema, pa odluke mora da donosi na osnovu Eh informacija . Svi čvorovi
su podjednako odgovorni za konačnu odluku. Otkaz nekog čvora, u opštem slučaju, nema za
posledicu rušenje čitavog sistema . Ne postoji zajednički generator takta na nivou celog sistema.
Objasnite podelu distribuiranih algoritama uzajamnog isključivanja i navedite po jedan
primer.
Distribuirani algoritmi uzajamnog isključivanja dele se na:
Algoritmi bez upotrebe tokena: Između sajtova se razmenjuju dve ili više rundi poruka kako bi se
odredilo koji sajt će sledeći ući u kriEčnu sekciju. Sajt ulazi u kriEčnu sekciju kada neka lokalna
tvrdnja postane isEnita .
Primeri: Lamportov algoritam i Ricart-Agrawalin algoritam .
Algoritmi na bazi kvoruma: Svaki sajt traži dozvolu da uđe u kriEčnu sekciju od podskupa sajtova
(kvoruma). Kvorumi se formiraju tako da, kada dva sajta konkurentno traže pristup, najmanje
jedan sajt prima oba zahteva i postaje odgovoran za dodeljivanje ekskluzivnog prava pristupa .
Primer: Maekawin algoritam .
Algoritmi na bazi tokena: Između sajtova se deli jedinstven token. Sajtu je dozvoljen ulazak u
kriEčnu sekciju samo ako poseduje token, a on ga drži dok ne završi izračunavanja u kriEčnoj
sekciji.
Primeri: Suzuki-Kasamijev algoritam i Raymondov algoritam .
Zašto je konsenzus problem u distribuiranim sistemima?
Konsenzus je problem jer su distribuirani sistemi po prirodi nepouzdani . Poruke mogu da kasne,
izgube se ili dupliraju, a čvorovi mogu da padnu, restartuju se ili se ponašaju nepredvidivo . Ne
postoji centralni autoritet koji bi komandovao svim čvorovima, pa se sve odluke moraju donosiE
dogovorom (konsenzusom) . Dodatni izazovi uključuju probleme sa mrežom (tolerancija parEcija)
i sinhronizaciju vremena i poruka u asinhronim sistemima .
Koja su tri glavna algoritma za postizanje konsenzusa pomenuta u izvorima i navedite
ključne prednosE i nedostatke svakog?
Tri glavna algoritma su Paxos, Rax i PBFT (Practical Byzantine Fault Tolerance).
Paxos:
Osnovni princip: Konsenzus posEgnut kroz skup predloga i potvrda među čvorovima . Cilj je
izabraE jednu vrednost koju većina prihvata .
Prednos8: Dokazan je u teoriji i praksi za visoko nepouzdane sisteme . Teoretski je najosnovniji.
Nedostaci: Složeniji je za implementaciju , može biE neefikasan u nekim slučajevima .
Ra@:
Osnovni princip: Dodeljuje lidera koji koordinira konsenzus između čvorova [General
knowledge, although not explicit in source, implied by “jednostavniji za razumevanje”].
Prednos8: Jednostavniji je za razumevanje i implementaciju u poređenju sa Paxosom .
Nedostaci: Potencijalne slabosE ako lider zakaže ili postane preopterećen .
PBFT (Prac8cal Byzan8ne Fault Tolerance):
Osnovni princip: Konsenzus se posEže čak i u prisustvu zlonamernih (Vizan8jskih) čvorova .
Prednos8: Visoka tolerancija na zlonamerne čvorove .
Nedostaci: Ograničena skalabilnost . Pogodan je za zatvorene (permissioned) mreže .
Objasnite faze komunikacije u Paxos algoritmu .
Paxos algoritam uključuje tri osnovne uloge: Proposer (predlagač) , Acceptor (prihvatač) i Learner
(učenik) .
* Faza 1: PREPARE – Proposer bira broj predloga i šalje Prepare poruke Acceptorima .
ODGOVOR NA PREPARE – Acceptors šalju Promise poruke Proposeru, i mogu poslaE prethodno
prihvaćenu vrednost ako postoji .
(Nakon ovih faza, u Paxos algoritmu slede ACCEPT- REQUEST i ACCEPT faze, gde
Proposer šalje predlog vrednosE, a Acceptors je prihvataju ako nije bilo novijih predloga. Learners
saznaju konačnu vrednost kada većina Acceptora prihvaE istu vrednost ).
Koji su ciljevi pos8zanja konsenzusa u distribuiranim sistemima?
Ciljevi posEzanja konsenzusa su:
Razumevanje uloge konsenzusa u distribuiranim sistemima .
Pregled najvažnijih algoritama za posEzanje konsenzusa .
Diskusija o implementacijama i izazovima .
Istraživanje novijih istraživanja i budućih trendova .
Održavanje integriteta podataka (osiguravanje konzistentnosE podataka u celoj mreži) .
Sprečavanje konflikata podataka (rešavanje sukoba između čvorova) .
Osiguranje pouzdanos8 sistema (pružanje otpornosE na kvarove i gubitke podataka) .
