Perché una soglia determinata per la tolleranza bizantina di Guasto di una rete "asincrona"?(dove non può tollerare nemmeno un nodo difettoso)

Question

nella risposta successiva ( Link: https://biin.stackexchange.com/a/ 58908/41513 ), è stato dimostrato che per Accordo bizantino asincrono :

.

"Non possiamo tollerare 1/3 o più dei nodi che sono disonesti o perdiamo SICUREZZA o LIGITÀ. "

Per questa prova, è stata considerata le seguenti condizioni / requisiti:

.

.
1. Il nostro sistema è asincrono .
2. Alcuni partecipanti possono essere dannosi.
3. Vogliamo sicurezza.
4. Vogliamo la rispettibilità.

Una domanda fondamentale è che:

Con considerare la carta nota intitolata: "Impossibilità del consenso distribuito con un unico processo difettoso" ( Link link: https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf ) < / P >.

mostra che:

Nessun protocollo di consenso assoluto completamente asincrono può tollerare anche un unico processo non annunciato di morte ,

Possiamo ancora presumere che la rete sia asincrona? Come in tal caso la rete non può tollerare anche un nodo difettoso.

Answer 1

La risposta ha a che fare con il monitoraggio delle ipotesi precise che vengono effettuate in questi diversi risultati. In breve, mentre entrambi i risultati assumono Asynchrony, la "impossibilità del consenso distribuito con un unico processo difettoso" richiede una forma più forte di rispettiva e determinismo, e che rende impossibile il consenso.

1. Impossibilità di consenso distribuito con un processo difettoso

Questo risultato seminale (di Michael Fischer, Nancy Lynch e Michael Paterson) riguarda il consenso distribuito in cui il sistema non è solo asincrono, ma soddisfa anche:

.

• Determinismo. L'algoritmo di consenso non utilizza alcuna casualità.

• Liveria in ritardi dei messaggi. Non solo i messaggi possono essere ritardati arbitrariamente, ma dobbiamo anche garantire la rispettazione anche in presenza di tali ritardi continui.

Vediamo perché le proprietà di Tehse sono troppo forti e rendiamo impossibile il consenso distribuito.

Considera un esempio: Alice, Bob e Charlie sono amici e vogliono decidere dove incontrarsi per la cena. È possibile che uno dei quali diventi inaspettatamente diventa Awol (o decide che non sono più interessati ad essere più amici) e smette di rispondere ai messaggi. In questo caso, gli altri due possono ancora decidere in un posto dove incontrarsi. Ora cosa dovrebbero fare?

L'approccio ovvio sarebbe quello:

.

Alice decide solo dove andare, e dice a Bob e Charlie.

Ma questo non funziona perché Alice potrebbe essere colui che va awol. Quindi per risolvere questo problema, il prossimo approccio più ovvio potrebbe essere:

.

Sia Alice che Bob dicono a tutti gli altri dove andare. Se tutti sentano da Alice, allora andranno dove dice Alice; Altrimenti, andranno dove dice Bob.

Ma questo ha un nuovo problema. Supponiamo che tu sia Charlie. Se senti da Alice, sai dove andare. Se senti da né di loro, aspetti di sentire. Il problema è quando hai sentito da Bob, ma non ad Alice. Poiché ci sono ritardi di messaggi arbitrari, non puoi impegnarti di andare dove BOB ha detto: Alice avrebbe potuto dire dove andare, e non l'hai ancora ricevuto! Quindi sei completamente bloccato, e se succede che Alice sia diventato Awol, continuerai a aspettare per sempre.

Il problema qui è che non abbiamo modo di abortire la transazione; Nessun modo di dire, "Ok, questo non funziona, è passato troppo tempo e non ho ricevuto un ritardo - Proviamo di nuovo." Algoritmi di consenso in tutto il mondo (il più noto che è il paxos) ha la possibilità che il round fallisca a causa dei ritardi di rete, e in questo caso riprova solo, sperando in ritardo per ritardi di rete più brevi. Inoltre, è possibile aggirare il problema utilizzando protocolli randomizzati che di solito funzionano e vai avanti solo per sempre con probabilità ridotta (o pari zero).

2. Accordo bizantino asincrono in cui meno di $ 1/3 $ dei nodi falliscono

Il post bitcoinse colleghi le lucidature sulla questione della rispettibilità, dicendo solo che è "la capacità di continuare a effettuare progressi". Infatti, il risultato di cui sopra mostra che la forma più forte di questo è impossibile, quindi dobbiamo rilassare le nostre esigenze / ipotesi.

Consideriamo due esempi. In Miguel Castro e "Pratica tolleranza ai guasti bizantini" di Barbara Liskov, raggiungono la loro capacità pratica con meno di un terzo dei nodi in essere difettosi da assumendo che i ritardi del messaggio non continuano a crescere indefinitamente . Come lo stato degli autori:

.

Garantiamo la rispettibilità, I.e., clienti Alla fine ricevere risposte alle loro richieste, fornite al massimo $ \ frac {n-1} {3} $ Le repliche sono difettose e $ ritardo (t) $ non crescere più veloce di $ T $ indefinitamente ... Questa è una sincronia piuttosto debole presupposto che è probabile che sia vero in qualsiasi sistema reale Alla fine fornito errori di rete sono riparati, eppure Ci consente di aggirare il risultato dell'impossibilità in [9].

Qui [9] è il risultato impossibile discusso sopra. In termini semplici per il nostro esempio, evitano il problema di cui sopra con Charlie richiedendo una forma debole di sincronia: Charlie non deve semplicemente continuare a aspettare per sempre, poiché sappiamo che i ritardi del messaggio possono crescere solo terreno, e non indefinitamente. (Ovviamente l'algoritmo effettivo ottiene molto più complesso, ma questo è in parte l'idea concettuale del perché la rispettibilità è possibile.)

In Ran Canetti e Tal Rabin "Accordo bizantino asincrono rapido con resilienza ottimale", usano la casualità per ottenere la loro capacità con meno di $ n / 3 $ guasti del nodo bizantino . Dal loro documento:

.

In questa impostazione, descriviamo una $ (\ lceil \ frac {n} {3} \ rceil- 1) $ --Resilient Byzantine Accordo di accordo. Con Probabilità travolgente Tutti i giocatori non difettosi completano l'esecuzione

del protocollo.Condizionato su evento che tutti i giocatori non difettosi hanno completato il esecuzione del protocollo, lo fanno in costante previsto tempo.

here $ (\ lceil \ frac {n} {3} \ rceil- 1) $ -Resilient significa solo meno di un terzo dei nodi sono bizantine. Nota le parole chiave con una serrabilità schiacciante. in modo che abbiano un algoritmo probabilistico che ha molte possibili "runs", e in modo schiacciante la maggior parte di loro funziona.Si noti che il risultato superiore dell'impossibilità implica che ci deve essere sempre alcuni funziona dove non si verifica la rispettibilità, cioè non c'è consenso:

.

Fischer, Lynch e Paterson's [FLP] Seminal Impossibility Risultato per i protocolli deterministici implica che qualsiasi protocollo (randomizzato) che raggiunge BA deve avere esecuzioni nonteri.