# Lezione 27 - 20/11/2024
triste oggi.

continuiamo transazioni capo.

caso di sistema di transazioni distribuito, abbiamo un insieme di operazioni provenienti da transazioni diverse, e il sistema deve garantire la proprietà di isolamento.

dobbiamo capire come fare la schedulazione di queste operazioni mantenendo l'isolamento.

procediamo facendo le ipotesi di iniziare a lavorare su una macchina sequenziale, poi vedremo il caso distribuito, quindi quella che è una sola schedulazione diventeranno diverse schedulazioni su macchine diverse.
Un altra semplificazione che facciamo è di non prendere in considerazioni le transazioni possano essere abortite, quindi supponiamo di lavorare con assunzioni che terminano con commit, poi dopo vedremo il caso generale. Cominciamo

Abbiamo detto che la proprietà di isolamento vuol dire che le transazioni non sono influenzate dalle altre transazioni. le schedulazioni seriali sono sicuramente isolate, perchè le operazioni sono fatte una dopo l'altra, non si mescolano. Quedto ci serve perchè noi abbiamo un problema di equivalenza tra risultato di una schedulazione seriale e il risultato di una schedulazione concorrente.

Se ci sono n transazioni, allora n! saranno il numero di schedulazioni seriali, ma se consideriamo il mescolamento di operazioni, ne avremmo molte di più, e solo quelle seriali sarebbero un poccolo sottoinsieme.

Abbiamo un modello ora, dobbiamo capire il concetto di equivalenza.

esempio
ogni transazione legge una var e poi la incrementano.
Vediamo 3 possibili schedulazioni (successioni di operazioni di lettura e scrittura, prima leggo e poi scrivo).
La prima è una schedulazione seriale, le altre due non lo sono, es schedule 3 avrà una x=5 per la terza, quindi gia si vede che non va bene.
Dobbiamo cercare di esprimere ciò in maniera formale per spiegare l'equivalenza.

Ci serve il concetto di **View Equivalent**
abbiamo relazioni di:
- leggi da: partiamo da operazioni di lettura, e per ognuna di queste andiamo a vedere quali sono le ultime operazioni di scrittura fatta su quella variabile, può riguardare anche la stessa transazione.

Quindi per la schedulazione, numeriamo tutte le relazioni leggi da.
Un altra cosa da guardare sono le scritture finali su una variabile.
A questo punto, possiamo dire che due schedulazioni sono view-equivalent se hanno le stesse relazioni leggi da e le stesse scritture finali sulle variabili.

esempio
es in schedule 2, r1(x) legge da w2(x) ecc.

Quindi, dato che abbiamo dei modelli sicuramenti validi, ossia le schedulazioni seriali, ed abbiamo un modo per confrontare due schedulazioni tra di loro, allora una schedulazione diremo che è isolata se è view equivalent a una delle schedulazioni seriali. se non ne trovo nessuna view equivalent non è isolanta.
Chiamimamo view-serializabile tutte le schedulazioni che sono view-equivalent a una seriale.

abbiamo trovato un insieme che oltre a quelle seriali sono isolate.

adesso quindi abbiamo un criterio per dire se una schedulazione va bene o no.

in questo esempio schedule 2 non è vsr perchè non è view equivalent a schedule 1, con r1(x) che legge da w2(x), che non troveremo in nessuna seriale. Le relazioni leggida non dipendono dall'ordine in cui sono eseguite le schedulazioni seriali (importante).
in schedule3, abbiamo r3(x) che legge da w2(x).

le schedulazioni vsr sono il sottoinsieme più ampio di schedulazioni isolate, le seriali fanno parte di queste; quindi un sistema di controllo della concorrenza che sarebbe in grado di generare un insieme di schedulazioni vsr sarebbe il migliore possibile, perchè ci farebbe ottenere il massimo della concorrenza e scarterebbe meno schedulazioni da quelle corrette. Questo è utile saperlo per valutare il tradeoff della capacità dello schedulatore di trovare schedulazioni isolate e il tempo che ci mette a trovarle, a un certo punto magari preferiamo uno schedulatore che ci mette meno tempo.

Tutto bello questo concetto di equivalenza, ma per capire anche se una schedulazione è buona o no, dobbiamo anche guardare la complessità dell'algoritmo (vedere se sono view equivalent è poco oneroso, tempo polinomiale), ma se questo poi lo molteplichiamo per n!, a quel punto il problema non è più risolvibile in tempo polinomiale, e quindi questo è solo un criterio di riferiemnto e non lo possiamo implementare, perchè è un problema NP completo, ed inoltra lavora a cose già fatte, ossia và a vedere la schedulazione dopo che già è stata eseguita, quindi già prodotta, e potremmo accorgerci che la schedulazione non è buona dopo che è stata eseguita. dovrebbe esse n*n! esplode, n! è la complessità
Ce lo teniamo come criterio ideale di isolamento, ma non è applicabile perchè ha complessità computazionale come un problema NP, e lavora a schedulazione gia eseguita.

prima di abbandonare questo criterio teorico, vediamo un esempio in cui, se lo applichiamo alle anomalie viste prima, sono 4 ma ci basta vederne solo tre, perche una è provocata dall'abort di una delle transazioni, ma qu' abbiamo ipotesi che non c'è abort, quindi quella la skippiamo.

S3 è view equivalent a S4.
S5 ad S6.
anomaly 4 sarebbe s9.

cerchiamo un criterio più utilizzabile.

eccolo qua **conflict-equivalent**
due schedulazioni sono conflict equivalent se hanno esattamente gli stessi conflitti. Un conflitto in una schedulazione è una coppia di operazioni non necessariamente consecutive (da transazioni diverse) sulla stessa variabile. quindi guardiamo la schedulazione e dobbiamo trovare due operazioni sulla stessa variabile relativa a transazioni diverse (read1(x) e write2(x) tipo), quindi ora il termine di paragone è prendere tutti i conflitti di una schedulazione e confrontarla con i conflitti di un altra (anche l'ordine è importante, read e write è diverso da write read).

guarda come si sta trovando i conflitti per ogni variabile su transazioni diverse.
S10 e S11 hanno gli stessi conflitti, quindi possiamo dire che sono conflict equivalent.
che ci serve il conflict-equivalent? come abbiamo ragionato prima, abbiamo il criterio di equivalenza lo usiamo per paragonare una schedulazione campione con tutte le possibili schedulazioni seriali, e se trovo una conflict-equivalent con una seriale (ne sono n!) allora la schedulazione è conflict serializabile ed è isolata.

conflict equivalent e view equivalent sembrano simili, devo comunqeu fare n! confronti, ma c'è una differenza: le schedulazioni conflict equivalent isolate, sono un sottoinsieme proprio delle schedulazione isolate rispetto alla view equivalent, quindi in realtà è peggio rispetto a view equivalent perchè ne scarto di più. Se csr è un sottonismee di vsr, ci sono delle schedulazioni vsr che non sono csr, quindi è buona, allora viene scartata, quindi è peggio.
Ma allora se è peggio perchè lo usiamo? perchè a differenza del vsr, per capire se una schedulazione è csr ci mettiamo meno tempo, non dobbiamo verificare con le n! schedulazioni, ci aiuta uno strumento che è un grafo di conflitto.
Prendiamo la schedulazione da testare, e guardiamo solo i conflitti su quella schedulazione, e ogni volta che trovo un conflitto disegno un arco tra i nodi che rappresentano le transazioni, quindi graficamente ogni conflitto sulla schedulazione produce un arco orientato (orientato perchè l'ordine tra read e write è importante), se il conflitto già ci sta è inutile che ridisegnamo l'arco. Si dimostra che se disegnamo il grafo dei conflitti, e verifico che tale grafo è aciclico, allora la schedulazione è conflict serializable.
Abbiamo fatto un passo avanti quindi, non dobbiamo fare confronti con n! schedulazioni seriali, ma risolviamo con un algoritmo con un algortimo che cerca cicli in un grafo di n nodi, che ha complessità polinomiale.

guarda capo ha disegnato il grafo dei conflitti.
S11 è seriale. (operazioni in sequenza tutte della stessa transazione).
S10 è conflict serializable ed isolata.

se guardiamo il grafo, oltre ad essere acicliclo, il percorso che tocca tutti i nodi senza richiudersi troviamo anche la seriale (potrebbe servirci averla chissa).

Rimane il problema che anche questo criterio lavora a posteriori, non va bene (vigile che fa andare le macchine a un incrocio e le fa ripartire da zero poi).
Quindi anche questo è una sorta di criterio teorico, ce ne serve uno ancora meno preciso ma che possa essere usato dal controllore della concorrenza in diretta. prima di vedere ciò vediamo un esempio.

S1 è seriale, quindi sia VSR che CSR.
S2 non è vsr, e non è nemmeno csr, se disegniamo il grafo dei conflitti troviamo ciclo tra 1 e 2.
S3 anche qui troviamo 2 1 e 2 1, ciclo.
S4 è vsr, le relazioni leggi da sono mantenute, e fa solo le scritture alla fine, però incappa nella non conflict serializable.
ancora c'è un ciclo tra 1-2 e 2-1.
quindi questa sarebbe scartata dal criteroio csr.

Vediamo se blocca anche le anomalie: una cosa che ci interessa è la completezza sicuramente ma ci preme che non faccia passare le anomalia, ossia non faccia passare le schedulazioni non isolate.

S7 non è csr.
S8 non è csr.
w2(z) e r1(z) e r1(y)-w2(y) ciclo 1-2 e 2-1. non è csr.

Abbiamo quindi trovato due criteri, uno meno accurato ma più veloce, ma comunque entrambi lavorano a posteriori, ci serve ora un criterio che sia in grado di lavorare man mano che arrivano le operazioni da transazioni diverse.

### Two-phase locking: 2PL
immergiamoci nel criterio che è collegata agli insiemi che già abbiamo trovato, ma a differenza di quei due criteri questo lavora in tempo reale.

Si basa su due meccanismi per funzionare:
- le transazioni prima di effettuare un operazione di lettura su una variabile devono chiedere il permesso di leggere quella variabile ad un gestore della concorrenza; quindi ogni transazione prima di leggere x chiede un permesso di lettura, e il gestore gli dirà di si oppure non risponde, r_lock
- se le transazioni vogliono fare un op di scrittura, devono chiedere il permesso w_lock al gestore, anche qui il gestore o gli da il permesso o non rispnode.
La differenza tra questi due permessi è che, r_lock può essere shared, ossia il gestore

r_lock è condiviso, w_lock è esclisivo.
questo per ogni variabile.

quindi r_lock posso darli a più operazioni, w_lock a una sola.

Quindi il primo criterio da rispettare è prima di leggere o scrivere è leggere e scrivere, ovvimaente i permessi di scrittura sono più complicati da ottenere.

Se ho una lettura seguita da una scrittura, è inutile che chiedo prima r_lock e poi w_lock, chiedo direttametne w_lock senza che chiedo r_lock.

Il gestore di chiama lock manager, tiene traccia dello stato.

il lock manager lavora come un automa a stati finiti, tramite una tabella. per ogni variabile, esso ha un automa a stati finiti in cui quella variabiel o è libera (non ho dato permessi di lettura e scrittura), o è bloccata in lettura (r_locked vuol dire che ho dato 1 o più permessi in lettura), oppure w_locked ossia ho dato 1 permesso in scrittura (per la scritutra non posso darne più di una).

Sulle righe della tabella ho le richieste, e dato una richiesta e lo stato, nella casella trovo il permesso e lo stato successivo.
es. free e r_lock, la richiesta è ok e porto la risorsa nello stato r_locked.
free e w_lock, restituisco ok e porto la risorsa nello stato w_locked.
se è unlock error.

colonna r_locked, se mi arriva r_lock glielo do, se mi arriva w_lock non glielo posso dare ma rimango in stato r_locked. se mi arriva un unlock di un permesso (di lettura), lo stato prossimo depends vuol dire che dipende da quanti permessi in lettura ho dato, avrò un contatore che decrementa se faccio unlock, quando arirva a zero la colonna torna a zero.

colonna w_locked.
se mi arriva r_lock e w_lock non posso dare permessi, devo rimanere in w_locked, l'unica cosa che ci porta in un nuovo stato è fare l'unlock.

Quindi il lock mangaer, per ogni variabile x,y,z avrà una tabella di questo tipo.
Quel NO che sarebbe rifiuto di permesso, non è un messaggio di rifiuto, ma vuol dire che la transazione che fa la richiesta viene messa in attesa, e quella richiesta poi verrà sbloccata quando la variabile torna disponibile.

perche si chiama 2phase? perchè le transazioni per poter eseguire le proprie operazioni, devono acquisire tutti i permessi necessari, si chiama di salita, in cui la transazioni richiede i permessi di tutte le variabili, e solo quando la transazione ha ottenuto tutti i permessi che gli servono, allora può fare le operazioni, e dopo che le ha fatte rilascia tutti i permessi.

se seguiamo questo approccio, otteniamo schedulazioni isolate, e non lo fa a posteriori.

### Lezione 28 - 26/11/2024

dopo aver visto sincronizzazione con tecniche per risolvere problemi trasversali a tutte le app distribuite, quì ora affrontiamo un problema di sincronizzazione molto specifico per sistemi transazionali (molto diffusi), per i quali si sono sviluppati sincronizzazioni ad hoc.
Per questi sistemi ci interessa la proprietà di isolamento delle transazioni, in particolare di mischiare operazioni di transazioni diverse, e la loro esecuzione mischiata dovrebbe essere sempre equivalente a una schedulazione seriale delle transazioni.

Quindi, le schedulazioni seriali sono sicuramente isolate (se ci sono n transazioni, n! sono isolate), e qualsiasi transazione a essa equivalente è anche essa isolata. L'obiettivo della parte del sistema transazionale deve fare in modo che le schedulazioni (seq di operazioni) deve risultare equivalente a una delle possibili schedulazioni seriali.

Abbiamo visto che vuol dire schedulazioni equivalenti, vedendo due tipi di equivalenza, view-equivalence (stessi relazioni leggi da per le variabili e scritture finali) e conflict-equivalent (le transazioni hanno gli stessi conflitti di lettura e scrittura, in cui è importante anche l'ordine).

Avendo a disposizione questi criteri di equivalenza, possiamo valutare le schedulazioni, nonostante questi criteri lavorino entrambi a posteriori, ossia se una schedulazione ha già prodotto risultati, il criterio ci dice se essa è buona o no.
Inoltre, la view equivalence è più accurato, ci permette di ottenere il sottoinsieme più grande di schedulazioni isolate (ne scartiamo di meno rispetto a conflict equivalence e altri) e quindi garantirebbe il massimo della concorrenza (produttività, si misura in numero di transazioni al secondo che vanno a commit) oltre all'isolamento.

View-equivalent fa riferimento a 1 possibile schedulazione seriale, view-serializable le confronta tutte, ed oltre a lavorare a posteriore, ma è un algoritmo a complessità computazionale non polinomiale, addirituttra è un problema NP-hard, quindi non è applicabile è solo un modello teorico.
Il criterio conflict equivalent e conflict serializable invece lavora in tempo polinomiale, usando il grafo dei conflitti.

Vedremo che le tecniche che lavorano in tempo reale entrambe si baseranno sul concetto di conflitto, quindi producono delle schedulazioni conflit serializable (2pl e timestamp).
In realtà producono un sottoiniseme delle conflict serializable, quindi scartano delle schedulazioni che sarebbero conflict serializable buone. vedremo hanno anche altri difetti.

Ricordiamo che stiamo ancora usando due ipotesi semplificative, ossia che stiamo lavorando in sequenziale, quindi i dati stanno tutti sulla stessa macchina, ed il controllore della concorrenza è unico e lavora sulla stessa macchina, e si occupa di produrre le schedulazioni. L'altra ipotesi è che supponiamo inizialmente che tutte le transazioni che nascono non vadano mai in abort ma sempre in commit. Quindi per ora non ci preoccupiamo se alcune delle transazioni falliscono. Poi rimuovere questa ipotesi di commit projection e poi vedremo passando a un sistema transazionale distribuito, con dati su macchine diverse, ed in cui le richieste di lettura e scrittura di una determinata trasnazioni sono gestite su macchine diverse con controllori di concorrenza diversi, che vedremo saranno coordinati in qualche modo.

La prima tecnica sequenziale in real time che vediamo è il 2PL.
Quì, quando bisogna fare delle operazioni, bisogna chiedere dei permessi in lettura e scrittura per le variabili. Se devo prima leggere e poi scrivere, chiedo direttamente il permesso di scrittura (x+x+1). La scrittura è esclusiva la posso dare solo a una operazione, rlock lo posso dare a più operazioni.
Quindi bisogna chiedere i permessi, e non posso effettuare le operazioni di una transazione se non ho ottenuto tutti i permessi che mi servono, quindi abbiamo fase di salita in cui ottengo i permessi, poi l'esecuzione (costante) e poi fase di discesa in cui rilascio i permessi.

Quì abbiamo il lock manager, che a fronte di una richiesta confronta una tabella, quindi quando arriva una richiesta o fornisce un permesso o mette in attesa una transazione, quindi è come se per ogni variabile mantiene un automa a stati finiti, in cui riporta stato prossimo e uscita.

Alla fine verrà prodotta una schedulazione conflict serializable, quindi transazioni isolate.
Alcune risorse possono esssere shared con gli altri, altre sono esclusive e stanno bloccando qualche transazione.

A questo punto il controllore della concorrenza in uscita mi darà una schedulazione conflict serializable. sulla slide fa una specie di dim per assurdo, in cui suppone di partire da una schedulazione che non è conflict serializable, ma che sia l'output di un 2pl.
Una schedulazione non conflict serialzable ha sicuramente un ciclo per definizione, quindi nell'esempio
t1 t2 ... tn t1
c'è un ciclo tra tn e t1

nota che t2 è in attesa che w1(x) rilasci la risorsa, ma esso lo farà solo al termine della seconda fase di 2pl. Ecco quindi che il controllore della concorrenza tenterà sempre di mettere in sequenza le schedulazioni in conflitto, quindi se ho
t1 t2 .. tn
se t2 ha un conflitto t3, non capiterà mai che ci sia un conflitto tra t3 e t1, perchè t1 ha già finito, oppure non ci sarà mai t1 t2 t1, il 2pl tende a serializzare le operazioni di transazioni che hanno generato un conflitto, e quindi se c'è un ciclo nel grafo dei conflitti e non è CSR, allora questa schedulazione non può nemmeno essere prodotta da 2pl, e quindi il sottoinnsieme di schedulazioni 2pl sono anche csr.

Sotto come vedi Invece, può capitare che esiste una schedulazione csr che non può mai essere generata da un 2pl.
c'è un conflitto 1-2 su x e 3-1 su y, il grafo è aciclico quindi csr, ma questa sequenza non può mai uscire dal 2pl, ad esempio w1(x) e r2(x) come conflitto, vuol dire che le operazioni di t2 avverranno sempre dopo tutte le operazioni di t1. quindi questa vieen scartata da 2pl, e quindi il sottoinsieme 2pl sta dentro il sottoinsieme csr.
Quindi 2pl produce delle schedulazioni csr ma ne scarta molte.

cerchiamo di capire intuitivamente perchè produce schedulazioni csr.
r1(x) e w2(x) e w1(x) r2(x) producono comuqnue il conflitto, la transazione che viene dopo che ha prodotto il conflitto viene bloccata, e viene sbloccata solo quando la prima transazione ha completatato la sua fase di salita e ha completato le sue operazioni, finche non rilascia i permessi. QUindi questo sistema quando si creano conflitti tra due transazioni le serializza, ciò non vuol dire che 2pl produce tutte schedulazioni seriali, ma mette in sequenza solo le transazioni che generano conflitti, e ciò fa si che i conflitti nella schedulazione prodotta sono ancora presenti però non produrranno mai un grafo di conflitti con un ciclo (se ci fosse il ciclo, il conflitto potrebbe esserci tra t1 t2 t1, ma questo non può accadere con 2pl, se c'è stato conflitto t1 t2, non potrà mai esserci t2 t1, perchè t1 è gia completata).

Quindi abbiamo trovato un sistema semplice e veloce, che lavora in real time e non troppo computaz complesso.
Proviamo a rimuovere la prima ipotesi in cui tutte le schedulazioni vanno a buon fine, però dobbiamo fare attenzione, dobbiamo aggiungere un vincolo al 2pl (strict 2pl), in cui i locks, ossia i permessi, vengono rilasciati solo dopo il commit o l'abort, quindi bisogna aspettare la fine della transazione, ciò implica un rallentamento nel sistema ma comunque il sistema produce schedukazioni isolate.
Ovviamente se togliamo ipotesi che non vanno in abort, le anomalie di tipo dirty read e ghost update devono essere bloccate da questo tipo di sistema:
a questa non potevamo applicare le tecncihe precedenti, ora possiamo.
qui t1 termina con un abort, e t2 legge un valore dirty, ossia non corretto perchè t1 dopo abort avrebbe dovuto fare un rollback, quindi t2 legge un valore errato.
Questa situazione non può capitare nello strict 2pl, perchè:
t1 ha una richiesta di scrittura su x, quindi chiede un w_lock, e poi quando t2 fa anche lei r_lock o w_lock perchè deve scrivere, essa viene bloccata, quindi la sequenza in figura non si verificherà mai; t1 termina la fase di salita, prova a fare le operazioni e va in abort, fa rollback e ripristina la situazione iniziale, poi rilascia il permesso w_lock(x), e poi t2 può iniziare a acquisire il suo w_lock(x) e eseguire l'operazione. NOn ci sono anomalie con s2pl.

Vediamo per ghost update.
t1 legge y non modificato, e il valore di z modifciato, e quindi il controllo del vincolo fallisce.

t1 ha bisogno di 3 lock in lettura
t2 ha bisogno di 2 lock in scrittura.

t1 prende rlock(x), t2 prende w_lock(y).
poi t1 fa r_lock(y), e questa è la anomalia, t1 vuole leggere y, e quindi deve essere messo in attesa. Quindi ora c'è un conflitto tra t2 e t1, e quindi t1 deve aspettare che t2 finisca tutte le sue operazioni, quindi alla fine le operazioni di t2 vengono prima di quelle di t1 da quel punto in poi.

ricapitolando, produce un sottoinsieme di schedulazioni csr, ma non seriali.

### concurrenty control based on timestamps

Vediamo un altra tecnica alternativa a 2pl, anche se sono equivalenti per accuratezza. Le schedulazioni prodotte da questi due sistemi non stanno uno dentro l'altro, quindi non possiamo dire che uno è peggio di un altro.

Anche questo produce schedulazioni conflict serializable.

Questa tecnica si basa su timestamp associato a una singola transazione, che sarà associato poi a tutte le richieste di lettera e scrittura di quella transazione. Il gestore della concorrenza ora vede richieste+timestamp. Il gestore ora deve rispettare l'ordine dei timestamp, ma non vuol dire eseguirle in maniera seriale in ordine di timestamp, ma vedremo che anzichè mettere in attesa le transazioni anomale come in 2pl, ma quì il sistema produce l'abort della transazione e la fa ripartire con un nuovo timestamp.

Lo stato delle variabile memorizzato dal gestore della concorrenza cono rtm e wtm, che sono numeri mantenuti per ogni variabile.
rtm(x) rappresenta il timestamp della trasnazione con timestamp più alto che ha effettuato una lettura più alto, quindi questo valore memorizza la transazione memorizza il timestamp della transazione che timestamp maggiore di tutte, lo stesso per wtm(x) relativo alle operazioni di scrittura. non sono permessi.
es. 5 10 15 12, rtm o wtm memorizzano 15

Guardano questi valori, il gestore decide se le operazioni sono lecite o no, e quì non dobbiamo aspettare la fine delle acquisizioni dei permessi.

se ho timestamp 15, non posso leggere ciò che ha scritto una transazione con timestamp 20 che viene dopo di me, quindi se si verifica una violazione di ordine, la richiesta viene rifiutata e la trasnazioen viene abortita e fatta ripartire con un timestamp superiore.
se arriva una richiesta di scrittura, il tempo viene confrontato con entrambi i valori, mentre le letture solo con rtm. Se il tempo è minore viene fatto l'abort, ma anche con rtm, c'è qualcuno che ha gia letto.
es. scrivo x con timestamp 8, ma t2 con timestamp 10 ha gia letto x, e quindi violerei l'ordine logico dei timestamp, quindi abort.
le letture devo confrontare wtm
le scritture entrambi. 2
funziona anche toglieno hp di commit projection, quindi che possono andare in abort, si bufferizzano le scritture.

La tecnica produce schedulazioni csr (grafo aciclico).
es. read(x) < wtm(x), es 5 legge x ma 10 ha già scritto x, e nella schedulazione avremmo w10(x) e r5(x), che è un conflitto scrittura-lettura, e questo meccanismo tollera i conflitti solo se sono in ordine dei timestamp, ma quando ne arriva uno che viola l'ordine, elimina quella transazione.
oppure ci sono dei conflitti write-write x. es. w12(x) w5(x), quindi conflitto fuori ordine, oppure write-read, r(12x) w5(x).

quindi l'obiettivo dello schedulatore è avere un grafo dei conflitti in cui i timestamp delle transazioni è in ordine crescente, e questo garantisce che non ci sono cicli.

Questo meccanisom è oneroso perchè fa abort di molte transazioni.

Per cercare di combattere il problema di uccidere molte transazioni, c'è un altra versione dell'algoritmo, che prevede di fare diverse copie delle variabili, e quando vengono scritte le variabili, si memorizzano ad esempio la x che ha scritto 5, la x scritta da 10 ecc. Questo comporta che è come se non avessimo più wtm(x) dato che ho copie diverse, e quindi il criterio di abort per le letture non esiste più, e quindi le letture non generano mai abort, ovviamente busogna prendere la versione giusta memorizzata. Le uniche operazioini che continuaano a produrre abort sono le scritture, con ts< rmt(x).
costi aggiutnuivi di memoria però riduciamo gli abort.

dobbiamo capire qiali sono le migliori tra le due che abbiamo visto.


### Lezione 29 - 26/11/2024
siamo arrivati a due tecniche che generano schedulazioni csr quindi isolate e che possiamo usare nei sistemi transazionali commerciali.

vsr garantirebbe il massimo della concorrenza.
csr è sottonisieme proprio di vsr.
poi abbiamo 2pl e ts che sono sottoinsieme di csr, pero notiamo che non stanno uno dentro l'altro.


vediamo qualche esempio per mostrare che questo diagramma ha senso capo.

S fa parte di csr e ts ma non in 2pl.

t1-t2-t3-t4-t5 è seriale e conflict equivalent con S.

Perchè S non è in 2pl?
appena troviamo un conflitto, come r1(x)-w2(x), e sappiamo che 2pl risolve il conflitto serializzando le operazioni delle due transazioni, quindi w2(x) viene messa in attesa e potrà essere eseguie solo dopo tutte le operazioni di t1. Quindi questa sequenza viene impedita da 2pl, quindi non fa parte di quel sottoinsieme.
Perchè S appartiene all'insieme TS? supponiamo i timestamp siano i pedici delle operazioni, se guardiamo x abbiamo r1,w2,r3, su y abbiamo r1,w2,w4,w5, se guarviamo v abbiamo r1,w3,r4, e quindi notiamo che in conflitti sono tutti ordinati in senso crescente sulla stessa variabile.

Vediamo il contrario, ossia una schedulazione 2pl ma non in ts (ultima in figura), si vede che non rispetta i conflitti in senso crescente, ma rispetta 2pl.

Se infine prendiamo quella sia ts che 2pl, quella è seriale e rispetta tutto.

Confronto 2pl e ts: lo facciamo con i difetti dei due metodi: i timestamp uccide le transazioni e non le mette in attesa. Se rimoviamo l'hp di commit projection, queste attese peggiorano le cose in entrambi i sistemi.
Inoltre, il 2pl ha un grande difetto che ancora non abbiamo detto, ossia quando i processi/transazioni vengono messe in attesa che dipendono da un altro processo concorrento, possono verificarsi degli stalli (deadlocks), e quindi per come si sono verificare le richieste di w_lock e r_lock per transazioni diverse, si crea una situazione per cui tutte le transazioni sono messe in attesa, e ognuno aspetta il rilascio di un permesso da parte di un altro, ma queste stesse transazioni per poter rilasciare devono almeno arrivare alla fine della fase di salita, e quindi sono bloccate, nessuna può prendere tutti i permessi che gli servono (attesa ciclica tra transazioni), e quindi nessunoo può fare unlock di permessi, e il sistema và in deadlock. Ovviamente non è detto che si veridichi sempre, non dipende da come sono fatte le transazioni, ma da come si mescolano le richieste di permessi.
esempio deadlocks

Che possiamo fare per risolvere deadlock??
- introduciamo un timeout di attesa, al termine facciamo ripartire le transazioni.
- deadlock detection: periodicamente il sistema va a verificare se all'interno delle transazioni si è creata attesa circolare. si crea un grafo e si taglia il ciclo che si forma nel grafo. lavora a deadlock in corso, quindi non uccidiamo transazioni.
- deadlock prevention: la concessione di una risorsa non viene fatta secondo l'automa solo, controllo se tale concessione può portare a un deadlock, quindi l'automa non è sufficiente.

Abbiamo visto il caso di sistema sequenziale, adesso vediammo il caso distribuito.
transaction manager si occupa dell'atomicità, ci attacca indici o timestamp ecc, e invia le operazioni di lettura e scrittura agli scheduler.
Adesso i dati sono su macchine diverse. Supponiamo il transaction manager sia centralizzato, e questo invierà le richeiste di lettura e scrittura (con un pedice o un timestamp), e queste richieste a controllori della concorrenza diversi su macchine diverse.
Quindi ora, anzichè avere una sola schedulazioni, ne abbiamo tante quante sono le macchine che gestiscono i dati. Tutti gli schedulatori produrranno una sequenza di operazioni di lettura e scrittura sulle proprie variabili. Quindi ora le oeperazioni, anziche un solo pedice adesso ne avranno 2, il secondo pedice è l'indice della macchina su cui quella macchina deve operare.
es t1: la macchina 1 si occupa di x, la macchina 2 si occupa di y.
Quindi localmente per uno schedulatore non cambia molto, deve sempre produrre una schedulazione corretta, solo che ora ne avremo una per ogni macchina.

Quindi ora, per lo schedulatore 'distribuito', possiamo usare le tecniche già viste? per un singolo schedulatore si, possiamo usare 2pl e timestamps, ma dobbiamo capire se gli schedulatori locali, se producono una schedulazione che è GLOBALMENTE isolata.
vediamo con un esempio
t1 e t2, x su macchina 1 e y su macchina 2.
S1 e S2 lavorano bene localmente, sono addirittura seriali, però se disegniamo il grafo dei conflitti globale, abbiamo dei conflitti 1-2 e 2-1, quindi il grafo e ciclico e la schedulazione non è csr. Quindi globalmente il sistema non verifica proprietà isolamento.
Quindi non sta funzionando propriamente, ci vuole una sorta di coordinazione tra gli schedulatori.

per ottenere l'isolamento globale di un sistema transazionale con dati e schedulatori distribuiti, tutto quello che abbiamo visto funziona, ci vuole che la fase di salita non può essere vista come fase di salita su una singola macchina, quindi la fase di salita del 2pl deve essere considerata globalmente, quindi esecuzione di operazioni e commit e rilascio di risorse, si può fare solo quando quella transazione ha acquisito tutti i permessi su tutte le macchine.

considera S1 e S2
arrivano w_lock su x e y su S1 e S2, poi su S1 arriva una w_lock su x da parte di t2, ma la t2 viene messa in attesa da parte della macchina 1, e viene anche messo in attesa t1 sulla macchina 2.
Quindi che succedeeebbe? se non facciamo il controllo globale, t1 scrite su x, rilascia il w_lock che viene dato a t2 in S1, analogo in S2. Se invece, mentre siamo in attesa, t2 su macchina1 e t1 su macchina 2, restano in attesa, perchè non hanno i permessi sull'altra macchina, quindi deadlock, e quindi non generiamo schedulazioni che sono globalmente non isolate.

le tecniche sono invariate, ma la fase di salita deve tener conto di che succede sulle altre macchine.

Per la tecnica sui timestamp, pure continua a funzionare ma solo se i timestamp non sono generati localmente ma in maniera globale.

fine slide transazioni, voliamo a deadlock

### Deadlocks
vedremo cos è, capire quando ci andiamo, tecniche per prevenirlo.

Una situazione di deadlock è una situazione in cui ci sono risorse, alcune di queste limitate, e poi ci sono dei processi/thread/transazioni, che per portare avanti la loro elaborazione, devono poter acquisire un certo numero di risorse di tipi diversi. Quindi un processo o uina transazione in sequenza chiede le risorse che gli servono, in un ordine che dipende dall'applicazione o da cosa il processo deve fare con le risorse. Inoltre, alcune di queste risorse, devono essere usate in mutua esclusione, ad esempio una w_lock(x), è un permesso che può essere dato uno alla volta, quindi ci sono risorse che sono utilizzabili solo in mutua esclusione.

Normalmente quindi, in un processo, relativo a una risorsa, c'è una sequenza:
richiesta, uso e release. IN fase di richiesta può essere negata e portare il sistema in attesa, o portare al fallimento del processo che ha fatto la richiesta.
Quindi i processi sono coloro che hanno bisogno delle risorse, e in un sistema distribuito abbiamo processi con sequenze di richieste, utilizzo e rilascio di risorse, e qualcuno che le risorse le gestisce
Alcune risorse possono essere tolte a un processo che le ha già ottenute, quindi il sistema di gestione ha la possibilità di togliere una risorsa a un processo che la sta usando, oppure ci sono risorse che non posso essere tolte a un processo a cui sono state assegnate perchè potrebbero portare al fallimento del processo.

Def formale di deadlcok: abbiamo un insieme di processi/thread/transazioni, che eseguono richieste per risorse, uso e utilizzo, e se in un determinato istante della loro esecuzione, in cui ognuno di essi sta aspettando un evento, che è tipicamente un evento di rilascio, quindi ognuno aspetta qualcosa da un altro processo dell'insieme, per poter proseguire nell'elaborazione.
Quindi è una attesa da parte dei processi in un insieme in cui ognuno aspetta qualcosa da qualcun altro. nessun processo in tale situazione può proseguire, rilasciare risorse, essere svegliato

Quali sono le condizioni affinche si verifichi un deadlock:
ci sono 3 precondizioni che se si verificano il sistema POTREBBE andare in deadlock, non ci và per forza, per andarci per forza deve esserci la 4 condizione. sono una sorta di 3 condizioni abilitanti.
- una o più risorse devono essere usate in mutua esclusione: es in 2pl ci sono w_lock da gestire in mutua esclusione.
- hold and wait: un processo può chiedere un altra risorsa senza rilasciare uqelle che ha già ottenuto. (se le rilasciasse sempre il sistema non andrebbe mai in deadlock). quindi c'è accumulo di risorse senza rilascio e richiesta di nuove risorse. in 2pl succede questo nella fase di salita, le transazioni accumulano risorse e le rilasciano solo alla fine.
- no preemption condition: il sistema non può togliere una risorsa a un processo che l'ha acquisita senza provocare danni. anche qui il 2pl rispetta questa condizione, se ho dato un w_lock non glielo posso togliere. se gliela togliesse e la vuole dare a un altro, verrebbe meno il discorso che porta a produrre una schedulazione csr.

quindi queste 3 sono condizioni necessarie ma non sufficienti per portare il sistema in deadlock, non sufficienti perche non è detto che succeda sempre o per forza.

INfine, la 4 condizione, quando si genera tra i processi una situazione circolare, che mette il sistema in blocco.
quando si verifica anche la 4 quindi, il sistema và in deadlock. questo succede nel 2pl anche.

Quali sono le strategie in generale per avere a che fare con un deadlock(non per forza nelle transazioni, in generale)?

- ignora
- detection e recovery gia visto
- dynamic avoidance
- prevention, andiamo a rimuovere una di quelle 3 precondizioni cosi non si verifica

Prima tecnica, ad esempio quando si verifica una situazione di deadlock in un s.o, non c'è una soluzione, bisogna far ripartre la macchina. 
nsa cacat pop rocco

Seconda tecnica, ragioniamo a posteriori
verifica se ci sono cicli nel grafo
boh
sulla sinistra c'è una possiible schedulazione
quando si arriva alla fine che C richiede R, che è ancora occupato, si verifica deadlock, un ciclo nel grafo.

simile a 2pl, si verificano le 3 condizioni e potrebbe capitare o no che si verifichi la 4

quindi questo metodo col grafo è un metodo per fare una detection, e il controllore della concorrenza si costruisce questo grafo e a ogni cambiamento verifica che ci sono cicli.

Non necessariamente il ciclo deve includere tutti i processi, anche un sottoinsieme vale comem deadlock.

fin ora abbianmo ragionato con una sola copia di una risorsa.
Ci sono situazioni in cui di una risorsa ci sono più copie, comunque si può verificare deadlock e possiamo usare algoritmi per verificare se il deadlock c'è o non c'è
C e R matrici, A ed E vettori
C è nxm, con n processi e m risorse, e su ogni riga indica ogni processo quante risorse di tipo 1 ha, di tipo 2 ha, ecc, quindi è una matrice di attuale allocazione di risorse sui processi.
Nella matrice R invece ci sono quali sono le risorse che ancora non ha ottenuto ma di cui ha bisogno per completare l'elaborazione, quindi richieste che non ha ancora fatto ma che dovrà fare
Il vettore A sono le risorse disponili, il vettore E le risorse assegnate. E è l'unica struttura statica, le altre cambiano dinaimciamente. possiamo usarle per vedere se il sistema sta in deadlock

esempio di detection con strutture dati
4 risorse e 3 processi, p1 ha uno scanner, p2 ha 2 nastri ecc
l'algoritmo va a guardare la matrice R, cerca una riga che ha dimesnione minore o uguale di A, e se la trova, prende tale riga i-esima di C e la somma ad A, e quella diventa la nuova A e poi va avanti. Se si riesce a soddisfare tutti i rpocessi, il sistema non è in deadlock.
nell'esempio, dire riga< A , vuol dire che quel processo può completare la sua elaborazione

in questo caso nessuna delle 3 righe di R è minore di A, quindi siamo in deadlock.

### Lezione 30 - 27/11/2024
stanco.
stam a 4 di noi

per avere un deadlock abbiamo 3 condizioni abilitanti al deadlock e una quarta che si può verificare o meno in base a come avvengono le richieste.
- mutua esclusione per le risorse
- processi che chiedono più risorse, e quando ne hanno ottenuta una non la rilasciano
- le risorse una volta assegnate non la possiamo togliere
- si verifica una catena circolare in cui ogni processo aspetta il rilascio di una risorsa da parte di un altro processo.

Se si verificano, come in 2pl, ci servono contromisure.

Le contromisure sono di tipo detection, per verificare se il sistema sta in deadlock o no, il modeling consisnte nel disegnare contiunamente un grafo, con le risorse che rappresentano la situazione attuale del sistema, e i processi che usano le risorse o aspettano.
Questo grafo si può analizzare ad ogni richiesta o al rilascio di una richiesta, se nel grafo si verifica un ciclo vuol dire che quei processi stanno in deadlock, e ci vuole un modo per rompere il ciclo facendo riavviare un processo ad esempio.

Ci sono più tecniche per stabilire se il deadlock c'è o meno un sistema, e una volta rilevato l'unica cosa che si può fare, se non posso togliere risorse, devo far ripartire un processo o fare qualche rollback.

Un altra strategia che si può usare in un sistema che ha le prime 3 condizioni rispettare, è quella di ad esempio portarlo ad uno strato precedente senza farlo ripartire per forza.
Quindi detection vuol dire controllare dinamicamente il deadlock e poi usare una strategia di recovery.

Ci sono poi altre strategie che lavorano PRIMA che si verifichi il deadlock, lavorando su una concessione di risorse più ragionata. Chi gestisce le risorse, a fronte di una richiesta non deve neccessariamente concederla, ma deve capire se quella richiesta può portare il sistema in una situazione pericolosa, quindi cerchiamo di evitare che il sistema vada in deadlock soppesando attentamente le singole richieste dei processi, perchè se quella richiesta porta il sistema in uno stato pericoloso, non la soddisfiamo. Esempio: algoritmo del banchiere, una banca può finanziare dei fornitori per la attività; le risorse limitate sono i soldi, e a fronte di richieste da parte dei clienti, il banchiere in base al budget ecc, deve tenere traccia dello stato del sistema e capire se quella richiesta può essere soddisfata o se porta il sistema in uno stato pericoloso.

abbiamo 4 imprenditori A,B,C,D, ognuno fa le richieste sulla colonna MAX. L'idea è che ognuno può restituire le risorse che prende solo dopo che gli sono state assegnati, le usa e poi le restituisce (2phase). Quindi il banchiere, nella prima fase può distribuire i suoi 10 milioni di euro ad esempio come in figura b, in cui la disponibilità del banchiere rimane di 2, ne ha prestati 8, ma nessuno dei 4 clienti ha raggiunto la sua richiesta, e quindi nessuno può restituire niente; questo stato però il banchiere lo considera sicuro, quindi potrebbe non portare al deadlock, infatti il banchiere potrebbe dare i suoi ultimi 2 milioni a C, che arriva a 4, li usa e poi li restituisce, quindi il sistema può continuare l'esecuzione, non và in stallo. Se invece il banchiere fa l'errore, come in figura c, ha 1 milione libero, quindi lo stato del sistema è in deadlock, perchè pure se lo dà a qualcuno nessuno riesce ad arrivare al minimo necessario per usare e restituire le risorse.

Quindi la logica dell'algoritmo è, ogni volta che bisogna rilasciare una risorsa, dobbiamo vedere il sistema in che stato si porta col rilascio di risorse, se il sistema si porterebbe in deadlock, la richiesta non dovrebbe essere soddisfatta.

Quindi le strategie sono: o aspettare che il deadlock si verifichi e poi con la detection e recovery risolvere in maniera più drastica, oppure si segue questa strada in cui bisogna tenere traccia di tutte le richieste.

Vediamo la strategia definitiva: cercare di neutralizzare qualcuna delle precondizioni, se questo è possibile, in particolare una delle prime 3.

- rimuovere la mutua esclusione non è percorribile, dipende da con che risorse si lavora, a volte si può lavorare con delle code per le richieste, quindi assegnare quella risorsa a più processi contemporanemaente, se la mutua esclusione è gestita con una sorta di attesa in coda.
- hold and wait: la soluzione è one-shot, non chiediamo una risorsa alla volta ma le chiediamo tutte insieme, quindi o me le dai tutte o aspetto. anche la strategia di rimuovere questa condizione non è sempre applicabile, perchè non sappiamo inizialmente un processo di quante risorse ho bisogno.
- togliere una risorsa da un processo che la sta usando ancora una volta dipende da una risorsa.
- la condizione più semplice da neutralizzare, è la quarta. Attraverso un regolamento tra peocessi che chiedono risorse, si può annullare l'attesa circolare si può fare assegnando alle risorse un id. Quindi i processi, quando hanno bisogno di più risorse, devono chiedere le risorse in ordine di id. se mi servono le risorse 2,3,4 devo chiedere prima 2,poi 3 e poi 4. C'è quindi una sorta di disciplina dei processi nel chiedere le risorse.
i<j, A può chiedere j, ma B non può chiedere i.

in questo modo possiamo risolvere il deadlock perchè non si creano cicli nel grafo.

vedremo nelle reti di petri modellando un sistema distribuito, come un sistema può soffire di deadlock, e quindi avremo uno strumento potente per analizzare una delle peggiori debolezze di un sistema distribuito.

### Replicazione e Consistenza

Simile a quanto visto in un esempio con lamport, con dei database che generavano copie di dati, e l'obiettivo di quell'applicazione, nonostante le richieste venissero da processi diversi, era di far si che tutte le repliche dei dati raggiungersero rapidamente uno stato di consistenza, e questo lo ottenvamo con lamport e un protocollo a scambio di messaggi, in cui tutti i processi che operavano su una copia locale, eseguissero a tempo opportuno tutte le operazioni in un certo ordine, ciò portava le repliche in stati consistenti. QUindi l'obiettivo è la REPLICAZIONE DELLA CONSISTENZA.

Questo lo vogliamo per prestazioni e affidabilità, quindi replichiamo i dati (database o datastore) su più nodi: miglioro le prestazioni perchè lavoro in locale e non devo contattare un server centralizzato; replicare i dati ovviamente mi aumenta l'affidabilità, perchè avrò più copie di dati nel mio sistema, se perdo una copia ne ho un altra. Questi sono i vantaggi, il problema è che, le repliche che sono modificate localemtne da processi diversi, a un certo punto devono portarsi in uno stato consistente, ad esempio se ho una omodifica di un dato su una macchina A, la stessa modifica a un certo punto deve essere fatta anche sulle altre copie, quindi bisogna propagare le modifiche.
Questo è il problema della consistenza, ho più copie di un dato su cui operano processi differenti, e vogliamo riuscire a raggiungere la consistenza delle repliche.
Ci sono tanti tipi di consistenza, il modello di riferimento teorico è questo: ci sono più copie uguali di un data store, e ci sono dei processi che generano operazioni su quel data store (letture, scritture).
La consistenza quindi richiede che le modifiche di una copia si riportino anche sulle altre.

Il concetto di consistenza è un pò vago, possiamo partire da un concetto ideale che non è realizzabile fisicamente.
Il modello di consistenza ideale è che ogni qual volta il processo1 modifica x, allora questa modifica immediatamente viene vista da tutti gli altri processi e da tutte le altre repliche, come se le scritture si propagassero istantaneamente; ovviamente è ideale e irrealizzabile, dobbiamo accontentarci di qualcosa di implementabile, tramite tecniche o protocolli reali.

Sono state introdotti dei parametri che misurano l'inconsistenza tra due copie di dati, quindi per dire che due copie possono essere molto o poco consistenti tra loro.
Ci sono degli indici che ci consentono di avere una misura arbitraria di quanto le copie, a fronte di operazioni locali, si discostano tra loro in termini di consistenza. Sicuramente le operazioni avranno dei timestamp, ci saranno operazioni che una copia ha visto e che un altra no, si riescono a contare le transazioni che sono state eseguite su una macchina rispetto a un altra, e riusciamo a calcolare queste misure. Tali parametri ci servono per dire che l'inconsistenza è tollerabile finchè non raggiungono un determinato valore, quindi per esempio non voglio aggiornare immediatamente le copie, ma quando mi accorgo che le copie di dati si stanno allontanando troppo, superando un valore soglie, procedo col riallineare le repliche di dati.

Il concetto di consistenza si applica a un'unità di consistenza (conit), e la scelta di tale unità và a influenzare i criteri basati su queste soglie.

I modelli di consistenza migliori sono quelli indipendente dall'applicazione, quindi indipendenti dai processi, ma sono modelli di consistenza legati ai dati.
Quindi i modelli di consistenza centrati sui dati sono i più rigorosi e difficili da implementare.
Questi modelli sono una sorta di contratto tra il datastore distribuito e replicato e le applicazioni, cioè, questo modello fornisce all'app delle garanzie sulla consistenza, e chi scrive l'applicazione, quando deve usare il modello replicato e consistenzte, saprà come si comportano le letture e scritture, e ciò vedremo influenzerà anche il progetto.
Quindi questo modello fa rifemento a cosa si può offrire ai processi, assicurando un modello di consistenza.
strict consistency, ogni volta che si legge un dato, leggi il risultato dell'ultima operazione di scrittura che si è verificata su una qualsiasi delle repliche. Anche se dire l'ultima scrittura di un dato non ha senso, non c'è un orologio globale.
Quindi, dobbiamo passare a un modello basato sui dati che sia però realizzabile.

Il primo che vediamo è il modello di conssitenza sequenziale, che garantisce all'utente che le operazioni di scrittura sui dati, che avvengono su macchine diverse, vengono viste da tutti nello stesso ordine; quindi il datastore distribuito ci garantisce un'esecuzione delle operazioni di scrittura in un ordine condiviso con tutte le repliche, l'ordine può essere arbitrario ma basta che sia lo stesso per tutti.
uno scrive a e b sulla propria replica, e poi p3 e p4 sulla propria replica leggono due volte consecutive la variabile x, quindi entrambi vedono la scrittura p2 e poi p1, oppure potevano anche leggere p1 e p2, basta che entrambi seguano lo stesso ordine.
Nella figura b invece vediamo che succede in un sistema distribuito che non fornisce un modello di consistenza sequenziale, p3 vede prima la scrittura di p2 e poi p1, mentre p4 vede prima la scrittura di p1 e poi di p2.

Vedremo tramite dei protocolli come si ottiene questa sequenzializzazione di scrittura.
Questo modello come influenza le applicazioni? vediamo un esempio con 3 processi, che lavorano sui dati replicati ma fanno operazioni diverse.
ognuno prima scrive x,y,z, dopodichè leggono e stampano le altre due variabili. quindi scrivoono una varibaile e leggono le altre due e le stampano.
Se questi 3 processi vengono eseguiti su un datastore replicato e distributo, che ci garantisce un modello di consistenza sequenziale, certe stampe non le vedremo mai.
sotto vediamo 4 possibili sequenze di scritture sulle variabili, e tutte hanno come effetto, in cui tutti vedono la stessa sequenza di scrittura, indipnendetemente da chi le ha fatte prima e dopo.

vedi (a), 001011, le prime due cifre sono y e z stampate da p1, mentre p2 fà la scrittura su y dopo la scrittura su x, vedrà 10 ossia vede la scrittura di x ma non di z, infine p3, scrive z, e siccome la sua è l'ultima scrittura, vedrà le scritture precedenti su x e y.
signature rappresenta l'outpuit finale.
le 4 sequenze sono giuste, ma non può mai capitare che i 3 processi stampano tutti 00, significherebbe che le 3 operazioni di scrittura, ognuno le ha viste in un ordine qualsiasi.
Anche quell'altra 001001 non va bene e non la possiamo mai vedere, perchè x stampa 00 perchè è il primo, p2 stampa 10, quindi ha visto la scrittura su x ma non su z, ma quando arriva p3, che però vede 01, che vede la modifica di p2 ma non vede la modifica di p1, e quindi vuol dire che il vincolo di consistenza sequenziale non è rispettato, quindi le signature. QUindi in questo caso, delle 2^64 possibili stampe, queste non sono tutte possibili.
Quindi questo modello mette in ordine le scritture, poi vedremo come, tramite tecniche e protocolli, per fare la sequenzializzazione.

Ci sono altri modelli data-centric, un altro è il CAUSAL Consistency. Quì, il data store ci assicura un ordine condiviso solo su un sottoinsieme di operazioni di scrittura, in particolare le scritture che hanno in mezzo una lettura.
p3 vede prima le scritture di p1 e poi di p2, p4 il contrario.

nagg capit sta correndo come un pazzo.

rispetto al sequenziale, questo modello è più rilassato, ordina solo alcune scritture su macchine diverse.

infine, un ultimo modello sui dati, è il modello FIFO consistency, che è il più semplice da realizzare, che si preoccuppa di far vedere alle altre repliche, che le operazioni di scrittura che nascono su una singola macchina vengono viste dalle altre repliche nello stesso ordine. Vengono propagate nell'ordine con cui vengono eseguite e non serve l'ordine condiviso ??
sta a corre nagg capit che cambia rispetto al primo.

quà le signature possono essere qualsiasi, le 2^64 sono tutte possibili.

due processi su due repliche.
il primo scrive su x e poi vede y, se non vede modifiche su y, uccide p2. p2 fa il contrario. se prendiamo queste 4 operazioni e le mischiamo, escono 6 sequenze(how??), e in nessuna delle 6 sequenze vengono uccisi entrambi.

quindi i modelli di consistenza basati sui dati offrono un servizio/garanzia all'applicazione:
- ordinamento condiviso di come nascono le scritture
- ordinamento condiviso di per scritture seguite da letture boh
- ordinamento di come nascono le scritture su una macchina

Dopodichè, ci sono modelli di consistenza non continui come i precedenti, in cui, tramite meccanismi di sincronizzzazione, il sistema forza la propagazione delle modifiche, quindi periodicamente o in base a qualche criterio, ad esempio quando la misura di inconsistenza tra due repliche, viene avviata la propagazione dell'aggiornamento delle repliche, quindi i modelli sono basati su una sincronizzazione esplicita.

Torniaom a vedere ancora un modello data-centric, e capiamo come il gestore del datastore può garantirci la consistenza. Il più vantaggioso che abbiamo visto è il sequenziale.
Un modo per implementarlo è:
c'è un datastore replicato, e quando un client chiede di leggere una variabile la legge sulla sua copia locale, mentre quando un client chiede di fare una scrittura (w1) in figura, questa deve essere gestita in maniera tale che le scritture siano eseguite nello stesso ordine sulle altre repliche; il modo più semplice è centralizzare le scritture. per ogni variabile, possiamo avere una replica responsabile di una variabile, e la replica che riceve una scrittura, deve propagare la richiesta di scrittura al PRIMARY server che si occupa di quella variabile, tramite scambio di messaggi.
Quando facciamo convogliare tutte le scritture su una variabile sulla stessa macchina, poi il primary server le serializza, ad esempio le mette in un ordine in cui arrivano i messaggi, e tale ordine vale per tutti. Dopodichè il primary server manda un messaggio per far propagare il nuovo valore della variabile moodificata, ogni server in teoria mantiene una tabella cosi da sapere chi è il primary server di quale variabile.
Quindi abbiamo ottenuto uin modello di consistrnza sequenziale tramite un protocollo che si basa sul concetto di primary server.

Una variante di questo protocollo, prevede che il primary server non è stabilito all'inizio e resta invariato, ma può succedere che il server che è oggetto di una richiesta di scrittura, diventa lui temporaneamente il primary server per quel dato. Quindi quando una replica riceve una modifica di un dato, chiede all'attuale primary di quel dato server di diventare lui l'attuale primary server per quel dato, ecco quindi che i primary server cambiano dinamicamente. Il motivo è che cosi riduciamo il numero di messaggi, dopo che sono state fatte le modifiche si fa comunque la propagazione.
Questo si usa molto anche quadno le repliche lavorano in modalità disconnessa in locale. In una situazione del genere, mentre prima avevo una tabella statica per le associazioni, qui i primary server cambiano continuamente, e devo conservare queste modifiche.

Questo protocollo ci consente di offrire un modello di consistenza sequenziale.
L'altro modo per realizzarlo invece è usando lamport, in cui propaghiamo l'operazione stessa e non il risultato, quindi ciò che trasferiamo alle repliche non sono il nuovo valore dei dati, ma trasferisco proprio le operazioni alle repliche.
ack di lamport ecc, ognuno prende le richieste di modifca, le ordina, e quell ordine vale per tutti, qunidni le scritture che nascono su macchine diverse, vengono viste da tutti nella stessa sequenza.
Nel momento in cui quindi distribuiamo le operazioni, otteniamo sempre un modello di consistenza sequenziale. Ci possono essere danni collaterali di modifiche multiple.

QUello che ci interessa è che il modello di conssitenza sequenziale, per quanto complicato, è implementabile.

prox volta vedremo consistenza lato client, fin ora abbiamo visto dal punto di vista dei dati. alcuni modelli saranno customizzati sulle richieste dello specifico processo o del client.

### Lezione 31 - 4/12/2024
fine consistenza

### Lezione 32 - 4/12/2024
reti di petri

### Lezione 33 - 10/12/2024
esercitazione reti di petri

### Lezione 34 - 11/12/2024
eccomi sono tornato dall'america.

aviabilità è il tempo che il sistema è attivo
parametri

affidabilità, relability


sistema più o meno affissabile in baso al numero di guasti

La manutenibilità è la probabilità M(t) che il sistemamalfunzionante possa essere riportato al suo correttofunzionamento entro il periodo t. Essa è strettamente correlata con la disponibilità poiché tantopiù è breve l'intervallo di ripristino del correttofunzionamento (anche in modo automatico), tanto piùelevata sarà la probabilità di trovare il sistema funzionante
ad un dato istante temporale.
Per il valore estremo M(0) = 1.0, il sistema in oggetto sarà
sempre disponibile.

fault causa il failure.
si può provare a eliminare i fault per prevenire i failure.
oppure si interviene sui failure quando si verificano



se il sistema non è in grado di tollerare i guasti

boh vabbe recuperale

### Blockchain

hanno come applicazione principale bitcoin o comunque altri sistemi di pagamento elettronico senza un unità centrale.

Il sistema distribuito qui ha lo scopo di avere un distributed libro mastro qualcosa. libro mastro sarebbe un librone in cui vengono registrate tutte le operazioni commerciale. normalmente in un ssitema centralizzato si tiene traccia di tutte le operazioni, mentre ora il sistema è distribuito.
Partiamo da uno stato inziiale, memorizziamo la sequenza di transazioni commerciali dal punto iinziale, allora saremo in grado in qualsiasi momento di identificare lo stato del sistema corrente. Quindi ogni stato corrente è identificato da stato iniziale + operazioni che portano allo stato corrente, e le trovo da questo libro mastro (nagg cpt come si chiama in inglese).

Il blockchain è il tentativo di ottenere questo sistema spiegato con un libro mastro ma in maniera distribuita, quinid non ho tutto memorizzato in un unico posto, ma in maniera distribuita. quindi, ho tante copie di questo librone e le cose si complicano. tutti sono in grado di sapere le informazioni nel distributed reger.
Viene certificato quindi che se io sto dando dei soldi a qualcuno, che io quei soldi veramente li ho. dato che ora tutte le transazioni sono registrate, quindi tutti sanno se i soldi che io sto pagando li ho o li ho già dati a qualcun altro.
Blockchain quindi parte da un applicazione relativa a uno scambio di monete elettroniche, anche se poi in realtà poi al posto di transazioni economiche possiamo metterci anche altre applicazioni che funzionano in maniera simile.

dobbiamo capire come si fanno i cambiamenti di stato e memorizzazione di sequenza di operazioni, in qualcosa che può essere in ogni momento acceduto da ogni componente del sistema. quindi ci vuole la possibilità di tutti di consulatre tale distributed reger distribuito.
bitcoin white paper spiega come avviene il commercio elettronico con blockchain.

La blockchain si basa su:
- sistemi peer-to-peer e protocolli relativi per entrare nella rete, autenticarsi, uscire ecc.
- sistema transazionale decentralizzato con proprietà di atomicità.
- sistemi di crittografia asimmetrica, quindi le transazioni sono firmate in qulache modo, e gli altri devono poter capire se le transazioni sono firmate o no.
- la cosa più onerosa da ottenere, tramite dei meccanismo di consenso, è ottenere un log condiviso di transazioni, quindi una sequenza di transazioni che devono essere verificate (con crittografia), e che poi devono risultate definitive nella catena di transazioni. Questo consenso, si basa sul concetto di proof of work, quinid macchine che lavorano per produrre un log file distribuito e immutabile.

quindi l'obiettivo delle blockchain è consetire di, a partire da uno stato inziiale e registrando tutti i trasferimenti, consetire a tutti di sapere qual è lo stato attuale del sistema. nel bitcoin lo stato attuale è conoscere quali sono i wallet ecc di tutti gli utenti ad esempio, quiindi posso sapere se un utente in quel momento quei bitcoin li ha o no.
Nel caso del bitcoin quindi la blockchain permette di conoscere quanti bitcoin ci sono in ogni wallet, chi è il propietario tramite delle chiavi (il proprietario del wallet non è identificato per forza da una persona reale, ma deve avere una chiave pubblica e privata, possono anche esserci trasferimenti anonimi).

Quindi dato uno stto iniziale, devo registrare le transazioni, però non esiste nessuna autorità centrale per creare il distributed reger distribuito. ovviamente dobbiamo otteenre uno stesso risultato che avremmo con un sistema commerciale centralizzato.
sicuramente risolviamo il problema del single point of failure, inoltre se avessimo un solo sistema centralizzato, ci sarebbe un potere di controllo su tutte le operazioni troppo elevato, potrebbe decidere di bloccare un conto o impedire delle operazioni lecite.

se qualcuno prova a modificare una vecchia transazioni (per esempio per trovarsi bitcoin nel proprio portafoglio), questa viene scoperta subito perchè viene propagata a catena nelle transazioni successive, e viene impedita. si fa con algoritmi di hasing

ncia facc chiu

la cosa complicata è stabilire nella catena qual è il prossimo blocco, ossia quando un blocco di transazioni si può inserire nel log distribuito. questo riguarda il meccanismo di consenso.

si usano sistemi di crittografia asimmetrica, ogni wallet ha una chiave privata e pubblica, e ciò consente l'autenticazione e non ripudio. ed anche algoritmi di hash, in cui se la firma è sufficientemente lunga, rendono impossibile ottenere una transazione diversa da quella memorizzate che produca la stessa firma.

vediamo il processo blockchain riassunto
transazione ha un mittente destinatario, viene firmata in qualche modo da chi trasferisce i soldi, le transazioni vengono raccolte in un blocco di transazioni, e attraverso il meccanismo di consenso, vengono 'appese' alla blockchain. quindi la blockchian è fatta da tanti blocchi, collegate tra di loro.
i peer che si impegnano a costruire e a rendere immutabile la catena, vanno in competizione tra di loro e si chiamano miner, e vengono retribuiti, quindi chi vince la gara (in termini di computazione) viene retribuito attraverso dei nuovi bitcoin per esempio, quindi questo è un modo per coniare nuovi soldi nel sistema, quindi questo è un modo per crearne nuove soldi. povero pianeta
una blockchain pubblica

### Lezione 35 - 11/12/2024
a vulim frni basta

scambio di moneta elettronica bitcoin.

le sfide principali in questo ambito sono:
- autenticazione: solo il proprietario della moneta elettronica può trasferirlo. si usa la crittografia asimmetrica, con chiave pubblica e privata associata al wallet. solo chi ha la chiave privata può firmare una transazione che trasferisce bitcoin tra wallet.
- non si possono duplicare le risorse, in questo caso i soldi/bitcoin
- minting: possibilità di creare in maniera controllata nuovi soldi nel sistema, ovviamente non esiste un sistema centrale che mette nuovi soldi nel sistema, le operazioni vengono fatte da dei peer.

vediamo nel dettaglio.

Public key signatures:
alice firma un messaggio, garantisce autenticazione e non ripudabilità di una transazione

No double-speniding: non posso spendere la stessa moneta due volte. La soluzione è un global ledger, ossia la sequenza di transazioni avvenuta nel sistema a partire da una iniziale.

Minting. remureazione. i miner si occupano di convalidare e allungare la blockchain. essi lo sfanno tramite una sfida impegnativa dal punto di vista computazionale. Chi vince la sfida, consolida il prossimo blocco nella catena e viene remunerato con la moneta.
La sfida da vincere è che, dato un blocco di transazioni (sostanzialmente un file) e dato un algortimo di hashing predefinito per rendere impossibili le collissioni, il proof of work consiste nell'aggiungere a questo file con tutte le transazioni, dei pezzi casuali di dati, per ottenere una firma che ha certe caratteristiche, ad esempio con un certo numero di zeri iniziali, quindi devo produrre un hash che rispetti la richiesta.

ogni volta la sfida è con difficoltà diversa.
Dato x blocco di transazioni, bisogna generare un hash del blocco, ma tale hash deve essere minore di t, ossia per esempio avere tot zeri iniziali nell'hash, più t è piccolo più la richiesta è complicata, bisogna procedere a forza bruta.
applicato l'hash a questo blocco x, però ci aggiungiamo quell y, chi riesce a rispettare il vincolo viene remunerato
ovviamente ci sono problemi di sincronizzazione
minting è il lavoro di coniare, mining è il lavoro di costuire la catena.

se fosse centralizzato queste operazioni sarebbe semplici.

vediamo deep.

Bitcoin è un insieme di architettura p2p, protocolli, e meccanismi per memorizzare un insieme di transizioni a partire da un blocco iniziale, che è il nodo di genesi del 2009.
ognuno può avere il proprio wallet e scaricare il libro distribuito leggendo tutta la storia.

vediamo la singola transazione.

ancora non è un blocco di blockchain.

Vediamo la transazione, owner1 ha ricevuto un bitcoin, quindi ha una transazione che contiene il trasferimento da owner0 a owner1. Adesso owner1 ha questo bitcoin e lo vuole spendere, ad esempio lo vuole mandare a owner2.
La transazione che trasferisce da owner1 a owner2 contiene: chiave pubblica del destinatario, transazione che dimostra che io quei soldi li ho, ne faccio un hash per la nuova transazione che sto facendo, e firmo l'hash con la mia chiave privata, quindi chi trasferisce deve firmare la transazione. nella foto devi guarda la transazione in mezzo. l'hash è una stringa di 256 bit.
quindi ogni bitcoin è legato a una catena di transazioni.
ad esempio se me ne arrivano 100 e ne voglio spendere 10, devo fare due transazioni, una per spenderne 10 e l'altra per tenermi gli altri per dimostrare che sono miei.
il problema sta se io prendo quella transazione e usarla due volte, nel problema del double spending, quindi le transazioni devono essere memorizzate, così non li uso due volte.

l'hash e la firma ci garantiscono che la transazione non può essere modificata.

quando si iniziano ad accumulare bitcoin, dobbiamo vddere come cleare questo libro mastro, quindi i blocchi di transazione.
abbiamo una sequenza di blocchi di transazioni che si sono verificate in sequenza, ed i blocchi sono collegati uno agli altri, questo li rende una catena. Sono collegati sempre tramite hashing. l'algoritmo di hashing dell'ulitmo blocco entra a far parte del nuovo blocco, insieme alle transazioni e al pezzo legato alla sfida. quindi facciamo hash di tutto il blocco, la sfida è aggiungere il pezzo per produrre l'hash dell'ultimo blocco creato, e deve essere minore di un certo valore (avere delle proprietà ecc).
Ammesso che la catena evolva in maniera tranquilla, dato che sono collegati tra loro tramite hash del blocco precedente ci garantisce che se prendiamo un blocco, e ci cambio una transazione dentro, allora cambierebbe l'hash del blocco per via delle collissioni, ma se cambia l'hash del blocco produce un effetto a catena sui blocchi successivi, quindi non può accadere.

Per il meccanismo di consenso, ossia decidere qual è il prossimo blocco e quali transazioni ci vanno dentro.
i miner acquisiscono le transazioni, le verificano, e poi parte il proof of work, ossia di ottenere un hash per un nuovo blocco che soddisfi quei vincoli.

come conio nuova moneta? il blocco, oltre ad avere un pezzo che il miner aggiunge per vincere la sfida, nelle transazioni viene aggiunta una transazione che gli assegna la ricompensa, quindi la creazione del bitcoin avviene nel senso che il miner, quando fa la sua sfida, ci mette pure la transazione della sua remunerazione, quindi se poi vince la sfida si trova quei soldi nel wallet.

Perchè sta sfida è cosi impegnativa? sicuramente per rallentare un pò l'aggiunta di denaro nel sistema.

la sfida è di questo tipo, il blocco sarà una stringa di byte, si aggiunge un numero appeso alla stringa, e ci esce un hash che ha 4 zeri iniziali.

la parte più complicata del protocollo è proprio il conseguimento del consenso, possono esserci più miner che vincono la sfida, oppure a parità c'è chi vince con un valore più piccolo e vince, oppure chi mette nel blocco più transazioni, ma ciò che rende vincente un nuovo blocco e che ci dà il consenso, è:
supponiamo nella rete si arriva al punto in cui si creano più blocchi, ogni miner riesce a vincere la sfida del proprio blocco, e poi i miner scommettono se possono crearsi delle catene innestate?
vince la catena su cui c'è stato più lavoro.
il consenso quindi è legato al fatto che i miner puntano sullo stesso blocco su cui vogliono costruire il prossimo blocco, quindi più miner puntano su un blocco è più è probabile che essa si allunghi e diventi quella del libro mastro distribuito.

quindi i miner sono incentivati a tenere il sistema in funzione, ma anche ad andare su una catena che è più promettente, altrimenti lavorano inutilmente.

Come viene memorizzato un blocco e come si fa la verifica. Posso lavorare su tutto il libro mastro, oppure per salvare spazio, che non richiede di conoscere tutte le transazioni di un blocco, c'è un algoritmo di hashing applicato ad una sorta di labero, quindi le transazioni di un blocco rappresentano le foglie dell'albero, e ci sono hash innestati, quindi alla fine viene memorizzato un hash finale del nodo di transazione.


se sono interessato a nodi figli, se voglio controllare la transazione Td, non mi servono tutte le transazioni del blocco, ma applico l'hash a Td, poi mi serve hash di Hc e Hd (fratelli), e poi lo combino con l'hash di AB, e infine lo combino con l'hash di tutto il ramo dx dell'albero, e infine lo controndo con l'hash finale della radice.

il punto debole sono i consumi di energia.

smart contract sono pezzi di codice che si possono eseguire e possono portare il sistema in un nuovo stato.
il meccanismo di consenso e creazione di un nuovo blocco è oneroso.

in altre blockchain tipo ethereum, la proof of work si chiama proof of stake, si fa una scommessa su un blocco, e se quello và a buon fine c'è la remunerazione, è meno oneroso. chi ha più monete è favorite.