Calcolo della probabilità di guasto del sistema in una rete distribuita

Question

Sto cercando di creare un modello matematico della disponibilità di un file in un sistema di file distribuito. Ho pubblicato questa domanda su MathOverflow, ma questo potrebbe anche essere classificato come una domanda CS, quindi anche qui ci sto provando.

Il sistema funziona in questo modo: A Node memorizza un file (encorato usando i codici di cancellazione) a R*B Remotes nodi, dove R è il fattore di replica e B è una costante intera. I file codificati per la cancellazione hanno la proprietà che il file può essere ripristinato IFF almeno B dei nodi remoti è disponibile e restituire la sua parte del file.

L'approccio più semplice a questo è supporre che tutti i nodi remoti siano indipendenti l'uno dall'altro e abbiano la stessa disponibilità p. Con queste ipotesi la disponibilità di un file segue la distribuzione binomiale, cioè Distribuzione binomiale http://bit.ly/dyjwwe

Sfortunatamente queste due ipotesi possono introdurre un errore non accomodante, come mostrato da questo documento: http://deim.urv.cat/~lluis.pamies/uploads/main/icpp09-paper.pdf.

Un modo per superare il presupposto che tutti i nodi abbiano la stessa disponibilità è di calcolare la probabilità di ogni possibile combinazione di nodo disponibile/non disponibile e prendere la somma di tutti questi risultati (che è una specie di ciò che suggeriscono nell'articolo sopra, Solo più formalmente di quello che ho appena descritto). Puoi vedere questo approccio come un albero binario con profondità R*B e ogni congedo è una possibile combinazione di nodi disponibili/non disponibili. La disponibilità del file è la stessa cosa della probabilità che si arriva in congedo con> = b nodi disponibili. Questo approccio è più corretto ma ha un costo computazionale di Ordo http://bit.ly/cezcap. Inoltre, non si occupa dell'assunzione dell'indipendenza del nodo.

Ragazzi, avete idea di una buona approssimazione che introduce meno errori rispetto all'apertura binomiale di distribuzione ma con un migliore costo computazionale rispetto a http://bit.ly/d52mm9 http://bit.ly/cezcap?

Si può presumere che i dati di disponibilità di ciascun nodo siano un insieme di tuple costituite da (measurement-date, node measuring, node being measured, succes/failure-bit). Con questi dati è possibile ad esempio calcolare la correlazione della disponibilità tra i nodi e la varianza di disponibilità.

Answer 1

Per grande r e b È possibile utilizzare un metodo chiamato Monte-Carlo Integration, vedi EG Integrazione di Monte Carlo su Wikipedia (e/o capitolo 3.1.2 di SICP) per calcolare la somma. Per piccolo r e b e probabilità significativamente diverse di fallimento del nodo p[i] Il metodo esatto è superiore. La definizione esatta di piccolo e di grandi dimensioni Dipenderà da un paio di fattori ed è meglio provato sperimentalmente.

Codice di esempio specifico: Questo è un codice di esempio molto semplice (in Python) per dimostrare come potrebbe funzionare tale procedura:

def montecarlo(p, rb, N):
    """Corresponds to the binomial coefficient formula."""
    import random
    succ = 0

    # Run N samples
    for i in xrange(N):
        # Generate a single test case
        alivenum = 0
        for j in xrange(rb):
            if random.random()<p: alivenum += 1
        # If the test case succeeds, increase succ
        if alivenum >= b: succ += 1
    # The final result is the number of successful cases/number of total cases
    # (I.e., a probability between 0 and 1)
    return float(succ)/N

La funzione corrisponde al caso del test binomiale e funziona N test, controllando se b nodi da r*b I nodi sono vivi con una probabilità di fallimento di p. Alcuni esperimenti ti convinceranno che hai bisogno di valori N nella gamma di migliaia di campioni prima di poter ottenere risultati ragionevoli, ma in linea di principio la complessità è O(N*r*b). L'accuratezza dei risultati scale come sqrt(N), cioè aumentare la precisione di un fattore due devi aumentare N con un fattore di quattro. Per sufficientemente grande r*b Questo metodo sarà chiaramente superiore.

Estensione dell'approssimazione: Ovviamente devi progettare il caso di test in modo tale che rispetta tutte le proprietà del sistema. Hai suggerito un paio di estensioni, alcune delle quali possono essere facilmente implementate mentre altri non possono. Lascia che ti dia un paio di suggerimenti:

1) Nel caso di distinto ma non correlato p[i], le modifiche del codice sopra sono minime: nella testa della funzione si supera un array anziché un singolo galleggiante p e sostituisci la linea if random.random()<p: alivenum += 1 di

if random.random()<p[j]: alivenum += 1

2) Nel caso di correlazione p[i] Hai bisogno di ulteriori informazioni sul sistema. La situazione a cui mi riferivo nel mio commento potrebbe essere una rete come questa:

A--B--C
   |  |
   D  E
   |
   F--G--H
      |
      J

In questo caso A potrebbe essere il "nodo radice" e un fallimento del nodo D potrebbe implicare il guasto automatico con probabilità del 100% di nodi F, G, H e J; mentre un fallimento del nodo F abbatterebbe automaticamente G, H e J ecc. Almeno questo era il caso a cui mi riferivo nel mio commento (che è un'interpretazione plausibile poiché parli di una struttura albero di probabilità nella domanda originale). In tale situazione è necessario modificare il codice p si riferisce a una struttura ad albero e for j in ... Attraversa l'albero, saltando i rami inferiori dal nodo corrente non appena un test fallisce. Il test risultante è ancora se alivenum >= b Come prima, ovviamente.

3) Questo approccio fallirà se la rete è un grafico ciclico che non può essere rappresentato da una struttura ad albero. In tal caso, è necessario prima creare nodi grafici che siano morti o vivi e quindi eseguire un algoritmo di routing sul grafico per contare il numero di nodi unici e raggiungibili. Ciò non aumenterà la complessità del tempo dell'algoritmo, ma ovviamente la complessità del codice.

4) La dipendenza del tempo è una modifica non banale, ma possibile se si conosce MTBF/R (medio-tradizioni/riparazioni) poiché questo può darti le probabilità p della struttura ad albero o del lineare non correlato p[i] da una somma di esponenziali. Dovrai quindi eseguire la procedura MC in momenti diversi con i risultati corrispondenti per p.

5) Se hai semplicemente i file di registro (come accennato nel tuo ultimo paragrafo), richiederà una sostanziale modifica dell'approccio che è al di là di ciò che posso fare su questa scheda. I file di log dovrebbero essere sufficientemente accurati per consentire di ricostruire un modello per il grafico della rete (e quindi il grafico di p) così come i singoli valori di tutti i nodi di p. Altrimenti, l'accuratezza sarebbe inaffidabile. Questi file log dovrebbero anche essere sostanzialmente più lunghi delle scale temporali di guasti e riparazioni, un presupposti che potrebbero non essere realistici nelle reti della vita reale.

Answer 2

Supponendo che ogni nodo abbia un tasso di disponibilità costante, noto e indipendente, mi viene in mente un approccio di divisione e conquista.

Dì che hai N nodi.

1. Dividerli in due serie di N/2 nodi.
2. Per ciascun lato, calcola la probabilità che qualsiasi numero di nodi ([0,N/2]) sono giù.
3. Moltiplicarli e somma questi necessari per trovare la probabilità che qualsiasi numero ([0,N]) del set completo è giù.

Il passaggio 2 può essere eseguito in modo ricorsivo e al livello superiore è possibile sommare in quanto spesso più di un numero di numero è in calo.

Non ne conosco la complessità, ma se devo indovinare, direi o sotto O(n^2 log n)

---

La meccanica di questo può essere illustrata su una custodia terminale. Supponiamo che abbiamo 5 nodi con tempi superiori . Possiamo dividerlo in segmenti A insieme a e B insieme a . Possiamo quindi elaborarli per trovare i tempi "N nodi" per ogni segmento:

Per un:

Per b:

I risultati finali per questa fase possono essere trovati moltiplicando ciascuno dei aè con ciascuno dei be sommando in modo appropriato.

v[0] = a[0]*b[0]
v[1] = a[1]*b[0] + a[0]*b[1]
v[2] = a[2]*b[0] + a[1]*b[1] + a[0]*b[2]
v[3] =             a[2]*b[1] + a[1]*b[2] + a[0]*b[3]
v[4] =                         a[2]*b[2] + a[1]*b[3]
v[5] =                                     a[2]*b[3]