In che modo le applicazioni distribuite verificano che i dati siano stati elaborati correttamente?

Question

In che modo le applicazioni distribuite verificano che i dati siano stati elaborati correttamente?

#1 da (2 voti)
#2 da (1 voti)

5

Ci sono molti progetti là fuori che si affidano alla sfera pubblica per elaborare i dati per loro, ma mi chiedo come fanno in modo che ogni computer che partecipa abbia elaborato i dati correttamente.

Il primo che viene in mente è il Bitcoin mining. So che la rete Bitcoin ha un modo matematico per verificare che i dati siano stati elaborati correttamente (non ho intenzione di approfondire qui).

Tuttavia, quando penso ad altri progetti, come il progetto SETI @ home , mi chiedo spesso come lo sappiano ogni partecipante si comporta correttamente; in che modo sanno che i dati sono stati effettivamente elaborati o che i risultati restituiti sono accurati. L'unica convalida che posso pensare richiederebbe anche loro di elaborare gli stessi dati, il che significa che il modello distribuito è discutibile.

Il gioco di connettere quattro è già stato risolto, ma diciamo che qualcuno voleva sviluppare un progetto che risolvesse il gioco di connettere quattro utilizzando una rete pubblica distribuita (Internet). Il server invierà una grande quantità di dati a una macchina da elaborare, ad esempio invierà un punto di partenza e la macchina dovrebbe elaborare tutte le schede possibili con una profondità di 5 e utilizzare una formula predeterminata per il punteggio, quindi restituire il miglior passaggio al server.

Come fa il server a sapere che questa è stata la mossa migliore usando l'algoritmo?
Come possiamo garantire che non ci sia un attore canaglia che sta consumando il servizio e che sostituisce l'algoritmo di punteggio predeterminato con uno spazzatura che produce la migliore mossa sbagliata?

distributed-computing

posta m-y 26.07.2015 - 14:40

fonte

2 risposte

Leggi altre domande sui tag distributed-computing

Con una tipizzazione statica sufficientemente avanzata, quali sono i vantaggi dei sistemi di tipo dinamico? [chiuso] Quando dovrei creare progetti separati in JIRA

score 2 · Answer 1

Stai chiedendo di due diversi problemi, verifica dei risultati e errore bizantino .

Per la verifica dei risultati , l'idea generale è di trovare un modo per verificare la risposta più rapidamente di quanto possa essere calcolato . Ci sono due approcci, che chiameremo strong verification e weak verification . Una strong verifica implica una prova che il risultato sia (in) corretto. Ad esempio, questa è una caratteristica che definisce i problemi NP-complete : una risposta richiede tempo esponenziale per calcolare, ma può essere verificato in tempo polinomiale.

Una verifica debole può essere utilizzata in situazioni in cui è impossibile dimostrare la correttezza di un risultato e tenta solo di verificare il risultato entro un intervallo di confidenza accettabile. Si tratta in genere di un approccio euristico, come il metodo di verifica dei risultati di SETI @ Home (come menzionato da MichaelT).

I sistemi

bizantini sono quelli in cui i processi possono fallire in modi arbitrari (anche dannosi). Esistono numerosi metodi per ottenere Tolleranza agli errori bizantini . Il più comune è forse replica della macchina di stato , in cui il passaggio fondamentale è ordinare gli input per garantire che le repliche hanno una visione coerente del mondo.

L'ordinamento degli input è comunemente ottenuto tramite gli algoritmi consenso . Gli algoritmi di consenso sono praticamente ciò che sembrano: un modo per garantire che ci sia un accordo sufficiente su un valore di dati all'interno del sistema prima che venga utilizzato.

L'errore bizantino è un problema complesso e questo è un riassunto molto breve e necessariamente incompleto. Per ulteriori informazioni, utilizzare i collegamenti inclusi e in particolare i riferimenti forniti.

score 1 · Answer 2

L'uso di uno snapshot globale, in combinazione con un algoritmo di analisi può (ed è) utilizzato per questo tipo di verifica.

The Snapshot Algorithm works like this:

The observer process (the process taking a snapshot):
    Saves its own local state
    Sends a snapshot request message bearing a snapshot token to all other processes
A process receiving the snapshot token for the first time on any message:
    Sends the observer process its own saved state
    Attaches the snapshot token to all subsequent messages (to help propagate the 
    snapshot token)
Should a process that has already received the snapshot token receive
a message that does not bear the snapshot token, this process
will forward that message to the observer process. This message was obviously sent before 
the snapshot “cut off” (as it does not bear a snapshot token and thus must have come from 
before the snapshot token was sent out) and needs to be included in the snapshot.

From this, the observer builds up a complete snapshot: a saved state for each process and all messages “in the ether” are saved.

Una volta che tutti gli osservatori hanno generato un'istantanea del loro stato locale, un analizzatore centrale può estrarre queste istantanee, ricostruirle ed eseguirne la verifica.