Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log...

41
Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori in un anello, le performance del protocollo (+) (-) (=) (nessun prec.)

Transcript of Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log...

Page 1: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Facciamo un piccolo test

• Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.)

• Aumentando il numero di identificatori in un anello, le performance del protocollo(+) (-) (=) (nessun prec.)

Page 2: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

• Dato l’anello in figura mostrare i passi della procedura lookup da 56 a 38

• Mostrare la tabella dei finger del nodo 48• Quanti messaggi impiega la procedura lookup?(2) (O(m)) (log N-1) (nessun prec)Giustificare la risposta m=6

18

10

nodi

risorse

21

24

4851

5654

3838

42

2628

Facciamo un piccolo test

35

Page 3: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Facciamo un piccolo test• Chernoff Bound

Siano X1, X2, …,Xn prove ripetute indipendenti tali che per 1 ≤ i ≤ n, Pr[Xi=1]=pi, Pr[Xi=0]=1-pi con 0 < pi < 1.

Se

allora

Inoltre se >2e-1 4,43, allora

n

i i

n

ii pXEXX

11

0,][,

)1()1(])1(Pr[

eX

)1(2),( F

Page 4: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

• Supponiamo di lanciare 6000 volte un dado “perfetto” a sei facce:– Quale è la probabilità di beccare il 3 almeno 2001 volte?– Quanto vale ?

(100) (1000) (600) (nessuna delle precedenti)

– Quanto vale ? (2000)(2)(1)(1000)(nessuna delle precedenti)– Quale formula applicare?– Se invece del 3 consideriamo il 4, cambia qualcosa?

Facciamo un piccolo test

Page 5: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

• Supponiamo estrarre una carta da un mazzo di 40 carte napoletane (ripetiamo l’esperimento 400 volte)– Quale è la probabilità di beccare il 7 “bello” almeno 61

volte?– Quanto vale ?

(100) (10) (40) (nessuna delle precedenti)

– Quanto vale ? (5)(2)(1)(1000)(nessuna delle precedenti)– Quale formula applicare?

Facciamo un piccolo test

Page 6: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Join e StabilizationCrea Anello Vuoto

Join n=N26,

n’=qualunque nodo attivo

Stabilizen=N26n=N21

Page 7: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Join e Stabilization

• Altre operazioni periodiche ma utilizzate con frequenza minore sono fix.finger e check.predecessor

Page 8: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Join• Abbiamo visto che la procedura join appena definita

non completa l’aggiornamento di tutti i link necessari.

• Al fine di aggiornare tutti i link del nodo sono necessari alcuni runs di stabilize (che comprende inoltre la notify) e m (O(log N) whp) runs della procedura fix.finger (sia da parte del nodo che ha effettuato la join sia da parte di altri nodi che devono aggiornare uno dei finger al nuovo nodo)– Chord non è simmetrico (Se un nodo n ha un finger su n’

non è detto che n’ ha un finger su n)• Non è possibile avvertire i nodi che devono aggiornare i fingers

• E’ inoltre necessario far migrare le risorse al nuovo responsabile (il protocollo Chord non gestisce questo problema e lo rimanda all’applicazione).

Page 9: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Join

• La correttezza dei link al successore basta a garantire la correttezza delle lookup

• Lazy Join– Inizializza solo il successore– Periodicamente verifica successore e

predecessore– Periodicamente (ma meno spesso)

rinfresca il contenuto della tavola dei finger

Page 10: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Join e Lookup

• Cosa succede alla lookup a seguito di operazioni di Join?– L’operazione di Join è completamente

terminata -> nessun problema– L’operazione di Join è parzialmente

terminata -> la lookup potrebbe essere rallentata

– L’operazione di Join è incompleta (puntatori errati oppure le risorse si trovano in una posizione inconsistente rispetto ai link nella rete) -> la lookup potrebbe fallire

Page 11: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Vale il seguente lemma:

Se al tempo t esiste una path tra x ed y, allora per ogni t’>t ci sara’ una path tra x ed yPer induzione sul tempo.

Supponiamo che dopo t il nodo n effettua una join tra p e s due nodi nella path da x a y. L’arco tra p ed s non viene toccato dalla join e quindi permane.

Supponiamo avvenga una stabilize.

Consideriamo il momento in cui il nodo p cambia successore (stabilize di p) da s ad n. Questo avviene perchè p ha contattato s ed s gli ha detto di n. Inoltre p<n<s.

x p s y

n

Chord: Risultati Join

Page 12: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

s ha saputo di n ad un tempo precedente e questo può essere avvenuto solo perchè s è stato un successore diretto di n (cioè dopo la stabilize di n).

Per ipotesi induttiva se esisteva un path tra n ed s, esiste un path tra n ed s in tutti gli istanti successivi.

In particolare nell’istante in cui p cambia il successore. Essendo p<n<s il cambiamento del successore di p non influisce in alcun modo sulla path tra p ed s.

Inoltre anche dopo il cambiamento esiste una path tra p ed s.

x p s y

n

Chord: Risultati Join

Page 13: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Tutti le path tra x ed y, che utilizzavano l’arco tra p ed s, erano tali che p ed s erano interni ad x y. Ma tutti i nodi aggiunti all’arco p s sono interni a p s ed a maggior ragione interni ad x y.

Se un nodo è capace di risolvere una query, sarà sempre capace di farlo in futuro

Ad un tempo prefissato dopo l’ultima join i puntatori al successore saranno corretti per tutti i nodi

Chord: Risultati Join

Page 14: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

E’ possibile mostrare il seguente teorema:

Se ogni operazione di join è alternata con quella di stabilizzazione, allora dopo un fissato tempo dall’ultima join i puntatori al successore formano un ciclo su tutti i nodi della rete.

Chord: Risultati Join

Page 15: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

E’ possibile mostrare il seguente teorema:

Se abbiamo una rete stabile con N nodi ed effettuiamo N join alla rete, e se tutti i puntatori ai successori sono corretti, allora il Lookup di una risorsa avrà necessità di O(log N) hops con alta probabilità.

In altre parole se il tempo richiesto per aggiustare tutti i fingers è minore del tempo richiesto dalla rete per raddoppiare in taglia allora la lookup non viene asintoticamente rallentata.

Chord: Risultati Join

Page 16: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Dim

Se utilizziamo i vecchi finger arriviamo in O(log N) hops al vecchio predecessore della risorsa. In media ogni due nodi contattati uno è vecchio e quindi ha la tabella di routing corretta.

Se i successori dei nuovi nodi sono corretti, in al più O(log N) passi la risorsa sarà raggiunta.

Chord: Risultati Join

Page 17: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Failure and Replication

• Abbiamo detto che la correttezza del routing è garantita dal fatto che ogni nodo conosce in ogni istante il proprio successore

• Tuttavia questa invariante può essere compromessa dal fatto che i nodi possono “cadere”

• Per migliorare la robustezza del protocollo ogni nodo utilizza una lista di r successori (di solito r=log N)

• Quando il successore di un nodo n cade, n sostituisce tale successore con la seconda entry nella tabella dei successori e successivamente provvede a ricercare il successore r-esimo.

• In particolare, è possibile “rompere” il sistema solo se tutti e r i successori di un nodo cadono quasi contemporaneamente

Page 18: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Failure and Replication

• Assumiamo che p sia la probabilità che un nodo cade all’istante t. La probabilità che r successori cadono contemporaneamente è pr

• La presenza della tabella dei successori richiede alcuni cambiamenti nel protocollo:– La procedura stabilize si deve preoccupare di mantenere

corretta la tabella dei successori• Il nodo n copia la tabella dei successori dal suo

successore s ignora l’ultima entry e aggiunge in testa a tale tabella il proprio successore s

• Quando qualche successore fallisce il nodo n contatta il primo successore vivo s’ e successivamente ripristina la tabella dei successori utilizzando la tabella di s’

Page 19: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Failure and Replication

– E possibile inoltre modificare la procedura closest preceding finger in modo da valutare oltre alla tabella dei fingers anche i successori. (si ottengono miglioramenti ma il costo della lookup rimane O(log N))

– Inoltre è necessario modificare la procedura lookup (findsuccessor) che fallisce se incontra un successore down (la procedura infatti viene rilanciata dopo un breve intervallo di tempo, che dovrebbe servire a ripristinare il link al successore)

Page 20: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Failure and ReplicationRisultati

• Assumiamo che la lista dei successori è lunga r=(log N)

• Teorema– In una rete inizialmente stabile, se

assumiamo che ciascun nodo cade con probabilità ½, allora la lookup sarà corretta

DimAffinchè la lookup sia corretta è necessario

che l’anello non sia rotto. L’anello si rompe con probabilità (1/2)r=1/Nk se r= k log N

Altamente improbabil

e

Page 21: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Failure and ReplicationRisultati

• Assumiamo che la lista dei successori è lunga r=(log N)

• Teorema– In una rete inizialmente stabile, se assumiamo

che ciascun nodo cade con probabilità ½, allora WHP la lookup impiega O(log N) msg

Dim sketchSe ogni nodo è caduto con probabilità 1/2 , ogni due link ne

funziona almeno 1, Se il finger di cui abbiamo necessità è caduto possiamo

usare un finger più corto: invece di dimezzare la distanza la riduciamo a circa ¾ della distanza precedente. Ma log4/3 N = O(log N).

Page 22: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Failure and Replication• Consisten Hashing

– Il fatto che l’assegnazione degli ID avviene utilizzando consistent hashing, non è possibile per un avversario creare dei nodi in una posizione prefissata del ring.

• Non è possibile appropriarsi di una risorsa• Non è possibile rompere l’anello utilizzando r nodi fittizi

• Siccome abbiamo visto che gli r successori di un nodo n cadono contemporaneamente con bassissima probabilità è naturale pensare a questi nodi per le repliche delle risorse gestite dal nodo n.– Altre possibilità

• Diverse funzioni hash• Repliche in posizioni speculari (Es r repliche) (ID, ID+2m/r mod 2m, ID+2 2m/r mod 2m, , ID+(r-1) 2m/r mod

2m)

Page 23: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Leave• Siccome il protocollo descritto finora è corretto

anche in caso di fallimenti per i nodi potremmo gestire la leave come un fallimento, tuttavia è preferibile, per migliorare le prestazioni del sistema, adottare alcuni accorgimenti, quando un nodo si disconnette volontariamente dalla rete– Il nodo che lascia la rete

• trasferisce le proprie risorse al suo successore• notifica ai propri vicini (predecessore e successore)

che sta uscendo dal sistema. In particolare comunica il predecessore al suo successore e il successore al suo predecessore, in questo modo i due vicini possono connettersi senza utilizzare la stabilize/notify

Page 24: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Realistic Analysis

• Il sistema appena descritto è un sistema dinamico particolarmente difficile da analizzare analiticamente (senza esemplificazioni). In particolare tutte le dimostrazioni analizzate partono da una configurazione stabile, tuttavia:

“a Chord ring will never be in a stable state; instead, joins and departures will occur continuously, interleaved with the stabilization algorithm. The ring will not have time to stabilize before new changes happen.”

Page 25: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Chord: Valutazione

• Lookup veloci in sistemi di grandi dimensioni

• Variazione contenuta del costo di lookup

• Robusto rispetto a molti tipi di fallimento

• Gli esperimenti confermano i risultati teorici

Page 26: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

il costo è O(log N) come previsto dalla teoria

la costante è 1/2

Number of Nodes

Avera

ge M

ess

ag

es

per

Looku

p

Chord: Valutazione

Page 27: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Conclusioni

• A differenza dei sistemi precedenti, Chord si adatta ad ambienti dinamici (tipici dei sistemi P2P)

• Based on theoretical work (Consistent Hashing)

• Proximity-based routing• Chord è uniforme (routing greedy è ottimale)• Chord non è simmetrico

– Alcune procedure causano utilizzo di banda anche se non ci sono cambiamenti nella rete

• La Join costa O(log2 N)

Page 28: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Riferimenti

• http://www.pdos.lcs.mit.edu/chord/• http://www.napster.com/• http://www.gnutella.com/• http:// www.openp2p.com/• S. Ratnasamy, S. Shenker, and I. Stoica. “Routing

algorithms for DHTs: Some open questions”. In 1st International Peer To Peer Systems Workshop (IPTPS’02).

• I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, H. Balakrishnan, “Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”. In IEEE/ACM Trans. on Networking, 2003.

Page 29: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

• Partendo dalla figura, descrivere la procedura Join

• Descrivere le varie tecniche di replicazione e analizzarne vantaggi e svantaggi

• In una rete inizialmente stabile, se assumiamo che ciascun nodo cade con probabilità ½, allora la lookup impiega

(N) (½ log N) (m) (nessuna prec.)

Facciamo un piccolo test

ac

b

Page 30: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Una chiave (risorsa) è memorizzata nel primo nodo che segue in senso orario

32

90

123 20

5

ID a 7-bit

0IP=“198.10.10.1”

101

60Chiave=“LetItBe”

Consistent Hashing [Karger et al 97]

Page 31: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Consistent Hashing [Karger et al 97]

Page 32: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Consistent Hashing [Karger et al 97]

• Nasce come una tecnica per replicare i dati nei sistemi C/S

• Problema: memorizzare una copia dei dati messi a disposizione dal Server su un pool di Client– Load balancing– Fast recovery

• Le funzioni Hash mappano chiavi (risorse) in interi.

Page 33: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Consistent Hashing [Karger et al 97]

• Con N Client una possibile funzione è

x -> ax+b (mod N)

• Cosa accade se varia N?– Buona parte dei dati va riposizionata

• Se la usassimo in un sistema P2P?– N varia continuamente– nessuno sa precisamente quanto vale N

Page 34: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

x -> ax+b (mod N)

• In particolare se varia N:– è assicurato un bilanciamento sul numero

di dati per posizione– molti dati devono cambiare posizione– il numero di posizioni che un dato può

potenzialmente raggiungere non è limitato

Consistent Hashing [Karger et al 97]

Page 35: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Consistent Hashing [Karger et al 97]

• Desiderata– Vogliamo che quando N varia (cioè un

nodo entra o esce dal sistema)• la quantità di dati che viene rimappata nel

sistema è bassa• le posizioni in cui un generico dato (risorsa)

è mappato sono limitate• i dati vengono assegnati in maniera

bilanciata su tutti i nodi

Page 36: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Consistent Hashing [Karger et al 97]

In altre parole, per definizione un Consistent Hashing deve godere di opportune proprietà:

Bilanciamento

Monotonicità

Spread

Carico

Page 37: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

• Sia I l’insieme delle risorse e B l’insieme delle possibili posizioni

• Ovviamente le possibili configurazioni del sistema sono 2B

• Quello che cerchiamo è una funzione f:2B I -> B

• Se V è una configurazione (V2B) è ovvio che f(V,id) V, per qualsiasi id

Consistent Hashing [Karger et al 97]

Page 38: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Bilanciamento:

Per ogni sottoinsieme V di posizioni (nodi) ed |I| dati, il numero di dati per ogni posizione è O(|I|/|V|) con alta probabilità.

Monotonicità:

Se al variare di N le posizioni (i nodi) disponibili passano da V1 a V2 con V1 V2, la migrazione dei dati deve avvenire solo verso posizioni appartenenti a V2\V1, ma non a V1 .

Se V1 V2, f(V2, i) V1 allora f(V1, i) = f(V2, i)

Consistent Hashing [Karger et al 97]

I dati si devono

muovere solo se è

necessario

Page 39: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Spread:

Al variare di N, il numero di posizioni che un dato può assumere è limitato.

Carico:

Al variare di N, il numero di dati che una posizione accoglie è limitato.

Consistent Hashing [Karger et al 97]

Page 40: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

Funzioni Hashing Consistenti esistono ?

Siano K(x) ed N(x) due funzioni casuali che hanno come codominio l’intervallo [0,1).

Definiamo la seguente funzione Hash:

Utilizziamo K(x) per mappare le chiavi

Utilizziamo N(x) per mappare i nodi

F: La chiave i viene memorizzata nel nodo j se la differenza

|K(i)-N(j)| è la minima su tutti i nodi j.

Consistent Hashing [Karger et al 97]

Page 41: Sistemi P2P Facciamo un piccolo test Quanti successori ha un nodo nel protocollo Chord? (m) (1) (log N) (nessun prec.) Aumentando il numero di identificatori.

Sistemi P2P

0 1

F precedentemente definito:

Bilanciamento ?

Monotonicità ?

Spread ?

Carico ?

Consistent Hashing [Karger et al 97]