Calcular la probabilidad de falla del sistema en una red distribuida

Question

Estoy tratando de crear 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 CS, así que también le doy una oportunidad aquí.

El sistema funciona así: un nodo almacena un archivo (encendido usando códigos de borrado) en R*B remota nodos, donde R es el factor de replicación y B es una constante entera. Los archivos codificados por borrado tienen la propiedad de que el archivo se puede restaurar si al menos b de los nodos remotos están disponibles y devolver su parte del archivo.

El enfoque más simple de 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 Distribución binomial http://bit.ly/dyjwwe

Desafortunadamente, estos dos supuestos pueden introducir un error no no elegible, como se muestra en este documento: 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 lo que sugieren en el documento anterior, Solo más formalmente de lo que acabo de describir). Puede ver este enfoque como un árbol binario con profundidad R*B y cada licencia es una posible combinación de nodos disponibles/no disponibles. La disponibilidad del archivo es lo mismo que la probabilidad que llega a una licencia con los nodos disponibles> = B disponibles. Este enfoque es más correcto pero tiene un costo computacional de Ordo http://bit.ly/cezcap. Además, no se ocupa de la suposición de la independencia del nodo.

¿Ustedes tienen alguna idea de una buena aproximación que introduzca menos error que la distribución binomial-aproumo 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 consiste en (measurement-date, node measuring, node being measured, succes/failure-bit). Con estos datos,, por ejemplo, puede calcular la correlación de la disponibilidad entre los nodos y la varianza de disponibilidad.

Answer 1

Para grande r y b Puede usar un método llamado integración de Monte-Carlo, ver EG Integración de Monte Carlo en Wikipedia (y/o capítulo 3.1.2 de SICP) para calcular la suma. Para pequeños r y b y probabilidades de falla de nodo significativamente diferentes p[i] El método exacto es superior. La definición exacta de pequeña y largo dependerá de un par de factores y se prueba mejor experimentalmente.

Código de muestra específico: Este es un código de muestra muy básico (en Python) para demostrar cómo podría funcionar dicho procedimiento:

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 se ejecuta N pruebas, comprobando si b nodos de r*b Los 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 escala como sqrt(N), es decir, para aumentar la precisión por un factor de dos que necesitas aumentar N por un factor de cuatro. Para 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 tal manera, que respete todas las propiedades del sistema. Ha sugerido un par de extensiones, algunas de las cuales se pueden implementar fácilmente, mientras que otras no. Déjame darte un par de sugerencias:

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

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

2) En el caso de correlacionados p[i] Necesita información adicional sobre el sistema. La situación a la que me refería en mi comentario podría ser una red como esta:

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

En este caso A podría ser el "nodo raíz" y una falla del nodo D podría implicar la falla automática con 100% de probabilidad de nodos F, G, H y J; Mientras que una falla del nodo F Reduciría automáticamente G, H y J etc. Al menos este fue el caso al que me refería en mi comentario (que es una interpretación plausible ya que hablas de una estructura de árboles 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, saltando las ramas inferiores desde el 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 representarse 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 accesibles. Esto no aumentará la complejidad del tiempo del algoritmo, pero obviamente la complejidad del código.

4) La dependencia del tiempo no es una modificación no trivial, pero posible si conoce el MTBF/R (medios medios entre los fallos/reparaciones) ya que esto puede darle las probabilidades p de la estructura de árbol o del lineal no correlacionado p[i] por una suma de exponenciales. Luego tendrá que ejecutar el procedimiento MC en diferentes momentos con los resultados correspondientes para p.

5) Si simplemente tiene los archivos de registro (como se insinúa en su último párrafo) requerirá una modificación sustancial del enfoque que está más allá de lo que puedo hacer en este tablero. Los archivos de registro deberían ser suficientemente minuciosos 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 tendrían que ser sustancialmente más largos que las escalas de tiempo de las fallas y las reparaciones, un supuesto que puede no ser realista en las redes de la vida real.

Answer 2

Suponiendo que cada nodo tenga una tasa de disponibilidad constante, conocida e independiente, me viene a la mente un enfoque de división y conquista.

Di que tienes N nodos.

1. Dividirlos en dos juegos de N/2 nodos.
2. Para cada lado, calcule la probabilidad de que cualquier número de nodos ([0,N/2]) están abajo.
3. Multiplique y sumen 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 manera recursiva y en el nivel superior puede sumar como necesita encontrar con qué frecuencia hay más de un número.

No sé la complejidad de esto, pero si tengo que adivinar, diría en o menos O(n^2 log n)

---

La mecánica de esto se puede ilustrar en un caso terminal. Digamos que tenemos 5 nodos con horarios . Podemos dividir esto en segmentos A con y B con . Luego podemos procesarlos para encontrar los tiempos de "N nodos N" para cada segmento:

Para:

Para B:

Los resultados finales para esta etapa se pueden encontrar multiplicando cada uno de los aestá con cada uno de los b'sy sumando apropiadamente.

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]