Algoritmi Paraleli și Distribuiți PDF

Algoritmi Paraleli și Distribuiți Algoritmi pentru sisteme tolerante la defecte Prof. Ciprian Dobre [email protected]  Fiabilitate la nivelul proceselor ▪ De obicei mascam defectarea proceselor prin replicare ▪ Organizam procesele in grup...

Algoritmi Paraleli și Distribuiți Algoritmi pentru sisteme tolerante la defecte Prof. Ciprian Dobre [email protected]  Fiabilitate la nivelul proceselor ▪ De obicei mascam defectarea proceselor prin replicare ▪ Organizam procesele in grupuri, un mesaj trimis grupului fiind livrat tuturor membrilor acelui grup ▪ Daca un membru se defecteaza, un altul ii ia locul Comunicatie: diferenta intre Egalitate (a) vs. Ierarhie (b)  3 La cursul practic... failure models o Pana in acest punct, modelele presupuse pentru sisteme distribuite imperfecte au constat din: 1. Fail-recover faults o Un nod se defecteaza si nu mai raspunde la mesaje o Alte noduri pot detecta defectul prin timeout-uri: “if 127.0.0.10 doesn’t respond in 100ms, it’s down” o … dar nodurile respective pot reveni in operatie 2. Delayed / lost messages o Mesajele intre noduri pot fi arbitrar intarziate sau pierdute, dar nu corupte o Ne putem folosi imaginatia. Ce facem daca… Node 3 o reteaua incepe sa corupa mesaje? o un atacator intercepteaza si modifica date in trafic? Node Node 1 2 o unele noduri sunt… malitioase?  4 Toleranta la defecte bizantine o Defectul bizantin: Orice fel de defect la care ne putem gandi, precum… o coruperea de mesaje o noduri ce se comporta diferit functie de context (ex., comunica unor noduri informatii diferite) o nodurile conspira intre ele pentru a cauza distrugeri  5 “ How can you make a reliable computer service? […] It may be difficult if you can’t trust anything and the entire concept of happiness is a lie designed by unseen overlords of endless deceptive power. The Saddest Moment, James Mickens  Agreement algorithms ▪ In sistemele distribuite, avem diverse cazuri cand procesele au nevoie sa ajunga la un acord : ‒ Leader election ‒ Commit ‒ Synchronize ▪ Distributed Agreement: toate procesele non-faulty ajung la consens intr-un numar finit de pasi ▪ Procese perfecte, canale faulty: problema celor doua armate ▪ Procese faulty, canale perfecte: problema generalilor Bizantini  33 Distributed consensus o Un numar de noduri ajung la un acord despre o valoare o Orice nod se poate defecta sau recupera/reveni in orice moment de timp Node Node 1 2 Node Node 3 4  34 Algoritmul raft pentru consens o Raft este un algoritm dovedit a functiona corect, si care asigura strong consistency o Exista si alti algoritmi pentru stabilirea consensului, cel mai renumit fiind paxos  35 Raft consensus algorithm Replicare master – slave o Unul dintre noduri este ales master (sau leader), ceilalti sunt followers Node 1 Transfer 10€ to Bob Client says: Node Client 2 transfer 10€ to Bob ok Node 3  36 Raft consensus algorithm Replicare master – slave o Furnizeaza o ordonare globala scrierilor provenind din partea clientilor – putem reconcilia scrieri concurente o Clientii ce contacteaza noduri follower sunt redirectionati Node 1 Node Transfer 10€ to 2 Bob Node Client 3 Not a leader; contact node 2  37 Raft consensus algorithm Defectarea liderului o Liderul trimite periodic mesaje heartbeat (alive) tuturor nodurilor follower o Daca un nod follower nu mai primeste mesaje heartbeat, presupune ca leaderul s-a defectat si initiaza o alegere o O alegere este castigata daca un nod primeste voturi pozitive din partea unui cluster majoritar de noduri  38 Raft consensus algorithm Mesaje Heartbeat Haven’t heard from the leader for 2 sec… Something is wrong Follower  40 Raft consensus algorithm Alegere lider O alegere finalizata cu succes: 2 din 3 noduri sunt de acord cu noul lider Vote for Vote for me for me for term 20 term 20 Candidate Follower Vote granted Used to be leader for term 19  41 Raft consensus algorithm Aducerea nodurilor outdated la zi o Unul din follower iese offline pentru 10 minute – cum il re-aducem intr-o stare consistenta? o Inregistram toate scrierile intr-un “indexed log", pe care il replicam o Contine momentul cand o inregistrare a fost scrisa Index Term Contents 0 1 SET food pizza 1 1 SET language c++ 2 1 SET food pickles 3 5 SET answer_to_life 42 … ….  42 Raft consensus algorithm Replicarea Logului Hey, are you there? Leader Yeah, my last index is #149 Follower You’re missing entries 150 to 203.. Here they are…  43 Raft consensus algorithm Aplicarea intrarilor din log o Intrarile din Log de obicei conduc la modificari ale unei baze de date (cunoscuta si ca state machine) o La un moment dat, aceste modificari trebuie aplicate in state machine Entry #13 State SET food pickles machine  44 Raft consensus algorithm Replicarea State Machine o Nu e sigur sa aplicam o intrare imediat, din moment ce exista situatii (rare) cand un alt lider (subsecvent) poate cere roll back o Intrarile din Log sunt considerate a fi comise doar cand o majoritate de noduri le-au aplicat o Odata ce o intrare a fost comisa, se garanteaza ca nu va mai fi retrasa si poate fi aplicata sigur in state machine o Doar nodurile care au toate intrarile comise pot participa ca posibili lideri in alegeri  19... Ne reintoarcem la defecte... o Raft nu este considerat a fi un protocol “byzantine fault tolerant” – diverse oportunitati pentru un nod malitios sa cauzeze probleme o Un lider byzantine poate modifica cererile clientilor Nod e1 Transfer 10€ to Bob Clien Nod Client says: transfer t e2 20€ to Nick lol ok Nod e3  20 Probleme cu raft… o Un nod bizantin poate f. usor sa pretinda ca este lider, si toate celelalte noduri il vor crede o Nu trebuie sa dovedeasca ca a castigat alegerile! I’m leader for term 5. Here’s evil log entries 49-57… Nod Nod e2 e1 ok  21 Probleme cu raft…... sau in mod continuu sa declanseze alegeri, ne-permitand aparitia vreunui alt lider– clusterizarea devine useless (my way or the highway) Election timeout – vote for me in term 19. Vote granted. Election timeout – vote for me in term 20. Vote granted. Election timeout – vote for me in term 21. Vote granted.  22 Diverse cause ale defectelor bizantine o Cauze benigne ▪ Coruperea unor pachete pe retea, a datelor pe disc ▪ Un memory bitflip complet aleatory cauzeaza un nod sa se comporte imprevizibil bool isLeader; // gets hit by cosmic ray ▪ Un bug rar in cod (as if) cauzeaza un nod sa nu respecte protocolul o Cauze malitioas ▪ Un atacator modifica traficul inter-node ▪ Un atacator preia abuziv un nod  23 Posibile contra-masuri o Semnaturi criptografice, checksums: pot ajuta la autentificarea si verificarea integritatii mesajelor si datelor o ECC (Error-Correcting Code) memory: poate detecta si uneori repara eventuale erori la nivelul memoriei o E extrem de dificil sa asiguram protectia impotriva tuturor tipurilor de defecte… unele protocoale exista ▪ dar toate au limitarile lor  24 Reality check o Este necesar un asemenea nivel de paranoia? o Cand rulezi 50.000 de servere in productie, ce se intampla cand unul “goes byzantine”? o Ar putea acesta sa distruga functionarea sistemului ca ansamblu? poate… o O idee buna sa asiguram protectia macar impotriva unor defecte bizantine  Rezolvarea prin replicare... ▪ Replicam un proces si replicile la nivelul grupului intr-un singur grup ▪ Cate replici vom crea? ▪ Tipuri de defecte ale proceselor  crash: procesul devine nefuncțional  byzantine: procesul trimite mesaje cu un conținut arbitrar ▪ Un sistem se numeste k fault-tolerant daca poate supravietui si functiona chiar si cu k procese defecte ‒ Pentru defectele de tip crash (a faulty process halts, but is working correctly until it halts) o k+1 replici ‒ Pentru defectele Byzantine (a faulty process may produce arbitrary responses at arbitrary times) o 2k+1 replici Problema celor doua armate  27 Paradoxul celor doi generali o Doua armate au inconjurat un oras o Generalii acestora trebuie sa decida impreuna daca sa atace sau sa mearga in retragere o Ei comunica prin mesageri, care insa pot fi interceptati o Ambii generali trebuie sa ajunga la aceeasi decizie  28 Destul de usor, nu? We attack tomorrow at dawn. Did they get my message? I can’t attack just yet. Agreed, we attack tomorrow at dawn. Did they get the confirmation? If not, they won’t attack… Confirmation has been received. Did they get my confirmation? If not, they won’t attack…  29 Probabil ca nu… I confirm receiving the confirmation. Did they get my last message? If not, they won’t attack… I confirm receiving the confirmation. Did they get my last message? If not, they won’t attack… …  30 Paradoxul celor doi generali o Nu exista un protocol care sa garanteze ca ambii generali (noduri) sunt 100% siguri asupra deciziei pe care celalalt o va lua ▪ Exista demonstratii stiintifice o Dupa 500 confirmari, ambii pot fi destul de siguri ca amandoi vor ataca (sau, vor lua aceeasi decizie) o Dar “destul de siguri” nu garanteaza 100% siguranta Varianta simplificata a demonstratiei: ▪ Presupunem ca exista un protocol care asigura ca dupa schimbul a N mesaje, se garanteaza siguranta in luarea deciziei ▪ Al N-lea mesaj ar putea fi pierdut… deci, doar primele N-1 mesaje inseamna ca au fost suficiente pentru a garanta siguranta in luarea deciziei ▪ Deci, trebuie sa existe un protocol care schimba doar N-1 mesaje ▪ Concluzia: exista un protocol care schimba in final 0 mesaje o Exista protocoale ce mitigheaza nesiguranta data de trimiterea mesajelor, folosind reincercari, ACK-uri si timeouturi o TCP … Problema generarilor bizantini      32 Problema generalilor Bizantini o Generalizare a problemei celor doi generali o N generali (noduri) trebuie sa decida asupra unei decizii de atac sau retragere pe baza votului majoritatii o Unii generali pot fi in secret tradatori, si vor incerca sa manipeze votul… o Scop: atingerea consensului intre noduri oneste o #1 wants to attack o #3 wants to retreat I vote that we I vote that we 1 retreat 2 attack 3 o #1 receives retreat votes from #2 and #3 o #3 receives attack votes from #1 and #2 o Result: #3 attacks alone, #1 retreats  Problema generalilor bizantini Fie v(i) – informația comunicată de către Generalul cu numărul i Fiecare General folosește o metodă pentru a combina valorile v(1), v(2),..., v(n) într-un plan de acțiune Dacă decizia care poate fi luată este atac sau retragere, v(i) este opțiunea Generalului i dintre cele două variante, iar decizia finală pentru fiecare General se bazează pe votul majoritar (dintre cele n valori) Generalii își comunică unii altora valorile v(i) Generalii trădători pot trimite valori diferite celorlalți Generali Fiecare General ia decizia finală bazată pe aceeași mulțime v(1), v(2),..., v(n)  Problema generalilor bizantini Restrângem abordarea problemei la modul în care un General își trimite valoarea celorlalți Generali Termenii problemei se schimbă: un General comandant trimite ordinul Locotenenților, obținându-se astfel problema: Problema Generalilor Bizantini:  Un General comandant trebuie să trimită un ordin celor n – 1 Locotenenți astfel încât:  𝐼𝐶1 : Toți Locotenenții loiali se supun aceluiași ordin  𝐼𝐶2 : Dacă Generalul comandant este loial, atunci fiecare Locotenent loial se supune ordinului Generalului comandant 𝐼𝐶1 , 𝐼𝐶2 – interactive consistency conditions Se observă că, pentru un Comandat loial, 𝐼𝐶1 rezultă din 𝐼𝐶2 ; totuși, Comandantul nu este în mod necesar loial  Problema generalilor bizantini Evenimentele sunt următoarele:  Comandantul trimite ordinul tuturor Locotenenților  Un Locotenent trimite celorlalți Locotenenți mesajul primit de la Comandant  După primirea mesajului de la Comandant și a copiilor de la ceilalți Locotenenți, un locotenent decide prin vot majoritar ce decizie va lua  Problema generalilor bizantini Exemplul 1 𝐶𝑜𝑚𝑎𝑛𝑑𝑎𝑛𝑡 atac atac atac atac atac 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡1 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡2 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡3 atac X X atac 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡3 este trădător 𝑋 ∈ {𝑎𝑡𝑎𝑐, 𝑟𝑒𝑡𝑟𝑎𝑔𝑒𝑟𝑒} Oricare ar fi mesajul transmis de trădător, cei doi Locotenenți loiali vor lua aceeași decizie (atac)  Problema generalilor bizantini Exemplul 2 𝐶𝑜𝑚𝑎𝑛𝑑𝑎𝑛𝑡 atac X retragere atac retragere 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡1 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡2 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡3 retragere X X atac 𝐶𝑜𝑚𝑎𝑛𝑑𝑎𝑛𝑡𝑢𝑙 este trădător 𝑋 ∈ {𝑎𝑡𝑎𝑐, 𝑟𝑒𝑡𝑟𝑎𝑔𝑒𝑟𝑒} Oricare ar fi mesajul transmis de trădător, toți Locotenenții vor lua aceeași decizie X  Problema generalilor bizantini Dificultatea problemei constă în faptul că:  Dacă Generalii (Locotenenții) pot trimite doar mesaje orale, atunci nu există soluție decât pentru cazul în care 2/3 din Generali sunt loiali Un mesaj oral este aflat complet sub controlul emițătorului, deci un trădător poate trimite orice mesaj Mesajul trimis este atac / retragere Următoarele exemple: nu există soluție pentru 3 Generali, din care un trădător  Problema generalilor bizantini Exemplul 3 𝐶𝑜𝑚𝑎𝑛𝑑𝑎𝑛𝑡 atac atac atac 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡1 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡2 retragere 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡2 este trădător  Problema generalilor bizantini Exemplul 4 𝐶𝑜𝑚𝑎𝑛𝑑𝑎𝑛𝑡 atac retragere atac 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡1 𝐿𝑜𝑐𝑜𝑡𝑒𝑛𝑒𝑛𝑡2 retragere 𝐶𝑜𝑚𝑎𝑛𝑑𝑎𝑛𝑡𝑢𝑙 este trădător Bitcoin / blockchain consensus  42 Ce este bitcoin? o O valuta ce nu este influentata de nicio autoritate centrala, bazata pe criptografie si nu pe increderea intre oameni o O retea distribuita de noduri ce proceseaza tranzactii, puternic rezilienta la atacuri bizantine ▪ Oricine poate rula propriul nod bitcoin ▪ … ceea ce inseamna ca nimeni nu e considerat de incredere  43 Scurt istoric o Noiembrie 2008: “Satoshi Nakamoto” publica lucrarea despre un “peer-to- peer electronic cash system” o Ianuarie 2009: Reteaua bitcoin apare online, cu “Satoshi” fiind cel care mineaza primul block  44 Adrese Bitcoin o Oricine poate genera o adresa pornind de la o pereche public-private key Public: 1DwAdnHZ3w2Ecww6SPZZaGNMXVuWbdGZNY Secret: L3H8Yz7YPshSHw5yjTH72cYy12UnUerFnzd8wjEDyhsYXSbhWU5q o Oricine are o adresa publica poate trimite bitcoins la acea adresa o Pentru a-i cheltui, trebuie sa stiti partea secreta a cheii  45 O tranzactie bitcoin (super simplificata) o Intrari: iesirile unor tranzactii anterioare ▪ Iesirea #2 tranzactiei 3b96bb7e197e... ▪ Iesirea #1 tranzactiei e1afd89295b68… ▪ Iesirea #6 tranzactiei e79fc1dad370e… o Iesiri ▪ 0.1 BTC catre adresa 1HmxmBAX413yGY2LDoEN8FHBok61aT4w2d ▪ 0.2 BTC catre adresa 1Hozk3UFZDsGGd7PENAVgy3ouFHzvsCFJ7 o Semnaturi ce dovedesc ownership-ul adreselor de intrare  46 E suficient? Nu! I want bread, here’s a transaction to your address with 0.1 BTC Buyer Seller OK, here’s your bread o Vanzatorul trebuie sa poata verifica ca tranzactia este valida o Sursele de intrare pot sa nu existe, sau cumparatorul poate ca nu are dreptul de a le cheltui (invalid signature)  47 Blockchain-ul bitcoin (super simplificat) o Un log replicat al tuturor tranzactiilor bitcoin de la inceputul timpului o Fiecare block contine o lista a tranzactiilor semnate, dar si hash-ul SHA256 al unui bloc anterior Block #0 Block #1 … List of List of transacti transacti ons … ons … SHA256: 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f  48 Este de ajuns? Inca nu I want bread, here’s a transaction to your address with 0.1 BTC, which I added to my blockchain Buyer Seller OK, using my blockchain I verified your input sources are valid, here’s your bread o Noua tranzactie trebuie sa ajunga in blockchain-ul tuturor nodurilor bitcoin o Toate nodurile din retea trebuie sa fie constiente de tranzactie, altfel vanzatorul nu poate folosi monedele  49 Transaction broadcasting “I declare I want to send 0.1 BTC from 12vEsiYhQ3iUJK2Mpt5eLq2cgxewQLw4tr to 16yZiBEmG3AKSUkHm3oHo3PUMPUWUe72tv, and here’s a signature to prove I own these bitcoins. Please add my transaction to your blockchains” Bitcoin Bitcoin node node Buyer Bitcoin Bitcoin node node  50 Este de ajuns? Poate… I want bread, here’s a transaction to your address with 0.1 BTC. I have broadcasted it already Buyer Seller OK, indeed the transaction reached my blockchain, my closest node confirms it. Here’s your bread o Nu este sufficient ca un singur nod confirma tranzactia o Vanzatorul trebuie sa fie sigur ca intreaga retea o confirma ▪ daca nu, nu va mai putea cheltui monedele in viitor  51 Reaching blockchain consensus o Nodurile Bitcoin vor primi tranzactia intr-o ordine posibil diferita o Este critic ca nodurile sa ajunga la un acord asupra ordinii o Si nu, eventual consistency nu mai functioneaza aici o Double-spending: Doua tranzactii ce consuma aceiasi sursa de intrare (cineva vinde pe aceeasi bani de doua ori) – doar prima tranzactie poate fi valida o Toate nodurile trebuie sa ajunga la consens asupra tranzactiei care e prima, respectiv care trebuie eventual invalidata  52 Blockchain forks o Prin definitie, “adevaratul” blockchain este cel mai lung o Un nod onest notificat de un blockchain mai lung trebuie sa comute pe folosirea acestuia imediat Block Block Block #238 #239 #240 Block #237 Block Block #238 #239 o Tranzactiile din blocurile ramase “orfane” sunt retrase/anulate  53 Blockchain forks (2) o “Longest blockchain wins”: toate nodurile bitcoin converg rapid catre un blockchain comun o Cu cat sunt mai multe blocuri adaugate pe chain, cu atat mai improbabil e ca tranzactiile noastre sa fie retrase o In plus, extra blocuri servesc unor confirmari suplimentare prin care nodurile bitcoin confirma tranzactia noastra ▪ Aceste blocuri confirma validitatea tranzactiei ▪ si confirma ca tranzactia face parte din cel mai lung blockchain cunoscut de respectivele noduri  54 E suficient? Aproape… I want bread, here’s a transaction to your address with 0.1 BTC. I have broadcasted it already Buyer Seller OK, indeed the transaction reached my blockchain with 15 added confirmations. Here’s your bread o Vanzatorul poate confirma criptografic ca sunt alte 15 blocuri valide adaugate dupa cel cu tranzactia curenta ▪ aproape sigur ca orice fork de aici incolo va contine tranzactia… sau nu?  55 Un atac bizantin Ceva lipseste… urmatorul atac ar putea avea success: 1. Publish a transaction, which is added to block #190 2. Wait for 20 confirmations 3. Seller is reasonably sure the network reached consensus on this transaction 4. Seller gives you bread 5. Publish a new blockchain, forking from node #189 with 30 empty blocks after it 6. Network switches to your blockchain, since it’s longer 7. You get to keep both the bread and the coins  56 Proof of work o Solutia la scenariul anterior: sa facem costisitoare operatie de adaugare a unor noi blocuri o Orice hash SHA256 al unui bloc trebuie sa inceapa cu un anuimit numar de zero-uri, altfel nodurile oneste il vor rejecta o Singura metoda pentru a produce un bloc consta in forta bruta ▪ Formatul de bloc contine un contor exact pentru acest scop, ce influenteaza rezultatul aplicarii SHA256 ▪ Acesta trebuie incrementat pana cand reusim sa generam un SHA256 valid ▪ In alte variante de monede virtuale exista si alte versiuni ale Proof-of- Work  57 Atacuri 51% o Nodurile Bitcoin constant incearca adaugarea de noi blocuri – exista recompense pentru cele care reusesc o Un atacator trebuie sa le poata intrece pentru a produce blocuri mai rapid decat restul retelei combinat o Acest lucru este posibil doar de catre atacatori ce detin peste 50% din totalul puterii computationale de generare a SHA256 a intregii retele ▪ Un astfel de atac devine extrem de scump  58 “SHA256 computation arms race” o Cele mai bune CPU-uri: 10 – 100 milioane de hash-uri per sec o Cele mai bune GPU-uri: 100 – 1000 milioane de hash-uri per sec Hardware specializat pe minare de bitcoin: FPGA, ASIC o Un ASIC lansat in 2012: 60,000 M hashes / s o Un ASIC in 2019: 14 T hashes / s Antminer S9 o Un ASIC astazi (2022): 112 T Hashes / s WhatsMiner M30S++  A Bitcoin mine in Quebec, Canada. Creating new coins is highly energy intensive, requiring hundreds of specialised computers to run almost 24/7. (Image: Christinne Muschi / Alamy) A Bitcoin mine built next to a hydropower station in Sichuan, southwest China. Many facilities connect directly to power stations like these to make use of cheap excess electricity generated during the rainy season. (Image: Alamy)  Distributed Commit - slide-uri suplimentare -  Distributed Commit ▪ Scop: fie toti membrii unui grup decid asupra efectuarii unei operatii, fie niciunul nu efectueaza operatia ▪ Atomic transaction: o tranzactie ce se efectueaza cu totul sau deloc ▪ Defecte: ‒ Cele de tip Crash ce pot fi recuperate ‒ Defecte de comunicatie detectabile prin timeouturi ▪ Observatii: ‒ Commit-ul necesita un set de procese sa ajunga la un acord… ‒ …similar problemei generalilor Bizantini … ‒ … dar solutia este mult mai simpla deoarece avem ipoteze/constrangeri mai puternice  O tranzactie bancara distribuita openTransaction join participant closeTransaction A a.withdraw(4);. join BranchX T participant Client B b.withdraw(3); T = openTransaction BranchY a.withdraw(4); join c.deposit(4); participant b.withdraw(3); d.deposit(3); C c.deposit(4); closeTransaction D d.deposit(3); BranchZ  One-phase Commit ▪ Protocolul one-phase commit ‒ Un site este desemnat ca si coordinator ‒ Coordinatorul instiinteaza toate celelalte procese daca efectueaza sau nu local o opearatie ‒ Schema aceasta insa nu este fault tolerant  Transaction Processing (1) S1 F1 coordinator T_Id client flag: init …. P1 27 Open transaction T_write F1,P1 join F2 T_write F2,P2 S2 T_Id T_write F3,P3 flag: init Close transaction participant P2 27 …. S3 F3 T_Id participant flag: init P3 2745  Transaction Processing (2) F1 Close coordinator T_Id client init committed wait done …. doCommit ! canCommit? P1 27 Open transaction T_read F1,P1 T_write F2,P2 Yes HaveCommitted T_Id T_write F3,P3 committed ready init Close transaction P2 27 …. Yes HaveCommitted T_Id committed ready init P3 2745  Two Phase Commit (2PC) Coordinator Participants send VOTE_REQ to all send vote to coordinator if (vote == no) decide abort halt if (all votes yes) decide commit send COMMIT to all else decide abort send ABORT to all who voted yes halt if receive ABORT, decide abort else decide commit halt  Two-Phase Commit a) Masina de stari finite pentru coordonator, in 2PC. b) Masina de stari finite pentru un participant.  Two-Phase Commit actions by coordinator: write START _2PC to local log; multicast VOTE_REQUEST to all participants; while not all votes have been collected { wait for any incoming vote; if timeout { write GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants; exit; } record vote; } if all participants sent VOTE_COMMIT and coordinator votes COMMIT{ write GLOBAL_COMMIT to local log; multicast GLOBAL_COMMIT to all participants; } else { write GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants; }  Two-Phase Commit actions by participant: write INIT to local log; wait for VOTE_REQUEST from coordinator; if timeout { write VOTE_ABORT to local log; exit; } if participant votes COMMIT { write VOTE_COMMIT to local log; send VOTE_COMMIT to coordinator; wait for DECISION from coordinator; if timeout { multicast DECISION_REQUEST to other participants; wait until DECISION is received; write DECISION to local log; } if DECISION == GLOBAL_COMMIT write GLOBAL_COMMIT to local log; else if DECISION == GLOBAL_ABORT write GLOBAL_ABORT to local log; } else { write VOTE_ABORT to local log; send VOTE ABORT to coordinator; }  Two-Phase Commit actions for handling decision requests: while true { wait until any incoming DECISION_REQUEST is received; read most recently recorded STATE from the local log; if STATE == GLOBAL_COMMIT send GLOBAL_COMMIT to requesting participant; else if STATE == INIT or STATE == GLOBAL_ABORT send GLOBAL_ABORT to requesting participant; else skip; Steps taken by participant process for handling incoming decision requests.