Accordo di due generali

Question

Accordo di due generali

#1 da (6 voti)
#2 da (0 voti)

6

Sto cercando di capire un protocollo di accordo su un canale inaffidabile. Fondamentalmente due parti (A e B) devono accettare di fare qualcosa, quindi è il problema di due generali .

Poiché non esiste una soluzione a prova di proiettile, sto cercando di farlo.

A invia continuamente un messaggio con la sequenza 1
Quando B riceve seq 1 risponde continuamente con la sequenza 2
A questo punto A riceve seq 2 quindi inizia a inviare seq 3
...

La mia domanda. Quando possono le due parti concludere che possono intraprendere l'azione? Ovviamente non posso impostare una condizione: " esegui dopo aver ricevuto 10 messaggi " poiché l'ultimo mittente non avrà alcuna certezza che il messaggio 10 sia arrivato - torna al punto di partenza.

Che ne dici di un'altra idea:

Continua a comunicare in questo modo per un periodo di tempo predefinito. Alla fine di quel periodo entrambe le parti hanno un'idea dell'affidabilità del canale. Sarebbe accettabile?

_{Inizialmente l'ho pubblicato in StackOverflow ma qualcuno ha suggerito che la sicurezza potrebbe essere un posto migliore.}

protocols session-management

posta user1079062 03.12.2011 - 17:26

fonte

2 risposte

Leggi altre domande sui tag protocols session-management

Utilizzo di TPM per la crittografia dell'intero disco? C'è un modo per usare Nuget in modo sicuro?

score 6 · Answer 1

Le parti non possono mai concordare pienamente in una situazione in cui un messaggio può o non può essere ricevuto da una delle parti perché ci sarà sempre una differenza di stato tra le due parti.

Questo è anche l'enigma del "cellulare della fidanzata che ha smesso di funzionare". La soluzione migliore consiste nell'avere un protocollo concordato che viene seguito in modo da sapere che l'altra parte sta probabilmente eseguendo una serie limitata di attività ragionevoli che terminano con un protocollo failsafe. In quanto a sicurezza, è necessario assicurarsi che gli fail-safe aggiornati non creino condizioni in cui il precedente failsafe non risulta in una soluzione.

Inoltre, non è possibile trovare una soluzione ideale perché esiste una prova di impossibilità che afferma che non esiste una soluzione ideale. Vedere la parte inferiore di Voce di Wikipedia con problemi di due generali che hai citato e i suoi riferimenti. La tana del coniglio continua a includere tolleranza agli errori bizantina e i relativi articoli correlati.

score 0 · Answer 2

My question. When can the two parties conclude that they can take the action ? Obviously I can't set a condition: "do it after receiving 10 messages" since the last sender won't have any certainty that message 10 arrived - back to square one.

In realtà, possono avere la certezza che il messaggio 10 è arrivato supponendo che i messaggi siano ordinati. Vedete, quando arriva il messaggio 11, allora sappiamo che il messaggio 10 è arrivato (quindi erano in grado di comporre il messaggio 11).

Se i due generali ottengono X messaggi in avanti e indietro, allora possono essere sicuri che entrambi hanno visto i messaggi precedenti meno uno (o due?) round di avanti e indietro.

Se si verifica un errore per l'arrivo di uno dei messaggi (timeout o arrivo di messaggi fuori sequenza), il processo può riavviarsi con un nuovo primo messaggio.