Cálculo de la probabilidad de falla del sistema en una red distribuida

Question

Estoy intentando construir un modelo matemático de la disponibilidad de un archivo en un sistema de archivos distribuido. Publiqué esta pregunta en MathOverflow, pero esto también podría clasificarse como una pregunta de CS, así que le doy una oportunidad aquí también.

El sistema funciona así: un nodo almacena un archivo (codificado usando códigos de borrado) en los nodos remotos r * b, donde r es el factor de replicación yb es una constante entera. Los archivos con código de borrado tienen la propiedad de que el archivo puede restaurarse si al menos b de los nodos remotos están disponibles y devuelve su parte del archivo.

El enfoque más simple para esto es suponer que todos los nodos remotos son independientes entre sí y tienen la misma disponibilidad p. Con estos supuestos la disponibilidad de un archivo sigue la distribución binomial, es decir Binomial distribution http://bit.ly/dyJwwE

Por desgracia, estas dos suposiciones pueden introducir un error no neligible, como lo demuestra el presente trabajo: http://deim.urv.cat/~lluis.pamies/uploads/Main/icpp09-paper.pdf.

Una forma de superar la suposición de que todos los nodos tienen la misma disponibilidad es calcular la probabilidad de cada posible combinación de nodo disponible/no disponible y tomar la suma de todos estos resultados (que es más o menos lo que sugieren en el documento anterior, más formalmente de lo que acabo de describir). Puede ver este enfoque como un árbol binario con profundidad r * b y cada permiso es una combinación posible de nodos disponibles/no disponibles. La disponibilidad del archivo es la misma que la probabilidad de que llegue a un permiso con> = b nodos disponibles. Este enfoque es más correcto pero tiene un costo computacional de Ordo http://bit.ly/cEZcAP. Además, no se trata de asumir la independencia del nodo.

¿Tienen alguna idea de una buena aproximación que introduce menos errores que la distribución binomial-aproximación pero con un mejor costo computacional que http://bit.ly/d52MM9 http://bit.ly/cEZcAP?

Puede suponer que los datos de disponibilidad de cada nodo son un conjunto de tuplas que consisten en (measurement-date, node measuring, node being measured, succes/failure-bit). Con estos datos, podría, por ejemplo, calcular la correlación de la disponibilidad entre los nodos y la varianza de disponibilidad.

Answer 1

Para grandes r y b puede utilizar un método llamado integración Monte-Carlo, consulte p. Ej. Monte Carlo integration on Wikipedia (y/o el capítulo 3.1.2 del SICP) para calcular la suma. Para las pequeñas r y b y las probabilidades de falla de nodo significativamente diferentes p[i], el método exacto es superior. La definición exacta de small y large dependerá de un par de factores y es mejor probarla experimentalmente.

código de ejemplo específico: Este es un código muy básico de la muestra (en Python) para demostrar cómo tal procedimiento podría trabajar:

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 función corresponde al caso de prueba binomial y corre N pruebas, comprobando si b nodos de r*b nodos están vivos con una probabilidad de falla de p. Algunos experimentos lo convencerán de que necesita valores de N en el rango de miles de muestras antes de que pueda obtener resultados razonables, pero en principio la complejidad es O(N*r*b). La precisión del resultado se escala como sqrt(N), es decir, para aumentar la precisión en un factor de dos, necesita aumentar N por un factor de cuatro. Para un tamaño suficientemente grande r*b, este método será claramente superior.

Extensión de la aproximación: Obviamente necesita diseñar el caso de prueba de manera que respete todas las propiedades del sistema. Ha sugerido un par de extensiones, algunas de las cuales pueden implementarse fácilmente mientras que otras no. Déjeme darle un par de sugerencias:

1) En el caso de distintos pero no correlacionado p[i], los cambios del código anterior son mínimas: En la cabeza de la función se pasa una matriz en lugar de un solo flotador p y se reemplaza la línea if random.random()<p: alivenum += 1 por

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

2) En el caso de correlacionadas p[i] necesita información adicional sobre el sistema. La situación me refería en mi comentario podría ser una red de este tipo:

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

En este caso A podría ser el "nodo raíz" y un fallo de nodo D podría implicar la pérdida automática con un 100% de probabilidad de nodos F, G, H y J; mientras que una falla del nodo F derribaría automáticamente G, H y J etc. Al menos este era el caso al que me refería en mi comentario (que es una interpretación plausible ya que usted habla sobre una estructura arbórea de probabilidades en la pregunta original) . En tal situación, necesitaría modificar el código que p se refiere a una estructura de árbol y for j in ... atraviesa el árbol, omitiendo las ramas inferiores del nodo actual tan pronto como falla una prueba. La prueba resultante sigue siendo si alivenum >= b como antes, por supuesto.

3) Este enfoque fallará si la red es un gráfico cíclico que no puede ser representado por una estructura de árbol. En tal caso, primero debe crear nodos gráficos que estén muertos o vivos y luego ejecutar un algoritmo de enrutamiento en el gráfico para contar la cantidad de nodos únicos y alcanzables. Esto no aumentará la complejidad de tiempo del algoritmo, pero obviamente la complejidad del código.

4) La dependencia del tiempo es una modificación no trivial, pero posible si conoce el mtbf/r (mean-times-between-failures/repairs) ya que esto puede darle las probabilidades p de la estructura del árbol o el lineal no correlacionado p[i] por una suma de exponenciales. Luego deberá ejecutar el procedimiento MC en diferentes momentos con los resultados correspondientes para p.

5) Si solo tiene los archivos de registro (como se insinuó en su último párrafo) requerirá una modificación sustancial del enfoque que está más allá de lo que puedo hacer en este foro. Los archivos de registro deberían ser lo suficientemente detallados para permitir reconstruir un modelo para el gráfico de red (y por lo tanto el gráfico de p) así como los valores individuales de todos los nodos de p. De lo contrario, la precisión no sería confiable. Estos archivos de registro también necesitarían ser sustancialmente más largos que las escalas temporales de fallas y reparaciones, supuestos que pueden no ser realistas en las redes de la vida real.

Answer 2

Suponiendo que cada nodo tiene una tasa de disponibilidad constante, conocida e independiente, un enfoque de dividir y conquistar viene a la mente.

Supongamos que tiene N nodos.

1. Dividirlos en dos conjuntos de nodos N/2.
2. Para cada lado, calcule la probabilidad de que haya disminuido el número de nodos ([0,N/2]).
3. Multiplique y sume estos según sea necesario para encontrar la probabilidad de que cualquier número ([0,N]) del conjunto completo esté inactivo.

El paso 2 se puede hacer de forma recursiva y en el nivel superior puede sumar la necesidad de encontrar la frecuencia con la que se caen más de un número.

que no conocen la complejidad de esto, pero si tiene que adivinar, diría que en o por debajo O(n^2 log n)

---

La mecánica de este se pueden ilustrar en un caso terminal. Supongamos que tenemos 5 nodos con tiempos de subida . Podemos dividir esto en los segmentos A con y B con . Podemos entonces procesar estos para encontrar el "N nodos up" veces para cada segmento:

Para A:

Para B:

Los resultados finales de esta etapa se puede encontrar multiplicando cada uno de los a 's con cada uno de los b' s y sumando de manera apropiada.

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]