Calcul de la probabilité de défaillance du système dans un réseau distribué

Question

J'essaie de créer un modèle mathématique de la disponibilité d'un fichier dans un système de fichiers distribué. J'ai posté cette question sur Mathoverflow, mais cela pourrait aussi bien être classé comme une question CS, donc je donne également une chance ici.

Le système fonctionne comme ceci: un nœud stocke un fichier (encoé à l'aide de codes d'effacement) à R * B Remotes nœuds, où R est le facteur de réplication et B est une constante entière. Les fichiers codés d'effacement ont la propriété selon laquelle le fichier peut être restauré IFF au moins B des nœuds distants est disponible et renvoie sa partie du fichier.

L'approche la plus simple est de supposer que tous les nœuds distants sont indépendants les uns des autres et ont la même disponibilité p. Avec ces hypothèses, la disponibilité d'un fichier suit la distribution binomiale, c'est-à-dire Distribution binomiale http://bit.ly/dyjwwe

Malheureusement, ces deux hypothèses peuvent introduire une erreur non bizarre, comme le montre cet article: http://deim.urv.cat/~llus.pamies/uploads/main/icpp09-paper.pdf.

Une façon de surmonter l'hypothèse que tous les nœuds ont la même disponibilité est de calculer la probabilité de chaque combinaison possible de nœud disponible / non disponible et de prendre la somme de tous ces résultats (qui est en quelque sorte ce qu'ils suggèrent dans le document ci-dessus, Juste plus formellement que ce que je viens de décrire). Vous pouvez voir cette approche comme un arbre binaire avec une profondeur R * B et chaque congé est une combinaison possible de nœuds disponibles / non disponibles. La disponibilité du fichier est la même chose que la probabilité que vous arrivez à un congé avec> = b les nœuds disponibles. Cette approche est plus correcte mais a un coût de calcul de Ordo http://bit.ly/cezcap. De plus, il ne traite pas de l'hypothèse de l'indépendance des nœuds.

Avez-vous des idées d'une bonne approximation qui introduit moins d'erreur que la distribution binomiale à l'aproximation mais avec un meilleur coût de calcul que http://bit.ly/d52mm9 http://bit.ly/cezcap?

Vous pouvez supposer que les données de disponibilité de chaque nœud sont un ensemble de tuples consistant en (measurement-date, node measuring, node being measured, succes/failure-bit). Avec ces données, vous pouvez par exemple calculer la corrélation de la disponibilité entre les nœuds et la variance de disponibilité.

Answer 1

Pour grand r et b Vous pouvez utiliser une méthode appelée intégration Monte-Carlo, voir par exemple Intégration de Monte Carlo sur Wikipedia (et / ou le chapitre 3.1.2 de SICP) pour calculer la somme. Pour petit r et b et des probabilités de nœud de nœud significativement différentes p[i] La méthode exacte est supérieure. La définition exacte de petit et grand dépendra de quelques facteurs et est mieux éprouvé expérimentalement.

Exemple de code spécifique: Il s'agit d'un exemple de code très basique (en python) pour démontrer comment une telle procédure pourrait fonctionner:

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 fonction correspond au cas de test binomial et s'exécute N tests, vérifiant si b nœuds hors de r*b Les nœuds sont vivants avec une probabilité d'échec de p. Quelques expériences vous convaincront que vous avez besoin de valeurs de N Dans la gamme de milliers d'échantillons avant de pouvoir obtenir des résultats raisonnables, mais en principe, la complexité est O(N*r*b). La précision du résultat évolue comme sqrt(N), c'est-à-dire, pour augmenter la précision d'un facteur de deux, vous devez augmenter N par un facteur de quatre. Pour suffisamment grand r*b Cette méthode sera clairement supérieure.

Extension de l'approximation: Vous devez évidemment concevoir le cas de test tel, qu'il respecte toutes les propriétés du système. Vous avez suggéré quelques extensions, dont certaines peuvent être facilement mises en œuvre tandis que d'autres ne le peuvent pas. Permettez-moi de vous donner quelques suggestions:

1) Dans le cas de distincts mais non corrélés p[i], les modifications du code ci-dessus sont minimes: dans la tête de fonction, vous passez un tableau au lieu d'un seul flotteur p Et vous remplacez la ligne if random.random()<p: alivenum += 1 par

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

2) dans le cas de corrélé p[i] Vous avez besoin d'informations supplémentaires sur le système. La situation à laquelle je faisais référence dans mon commentaire pourrait être un réseau comme ceci:

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

Dans ce cas A pourrait être le "nœud racine" et une défaillance du nœud D pourrait impliquer la défaillance automatique avec une probabilité de nœuds à 100% F, G, H et J; Alors qu'une défaillance du nœud F ferait automatiquement abattre G, H et J etc. Au moins, c'était le cas auquel je faisais référence dans mon commentaire (qui est une interprétation plausible car vous parlez d'une structure d'arbres de probabilités dans la question initiale). Dans une telle situation, vous auriez besoin de modifier le code qui p fait référence à une structure d'arbres et for j in ... traverse l'arbre, sautant les branches inférieures du nœud actuel dès qu'un test échoue. Le test résultant est toujours de savoir si alivenum >= b Comme avant, bien sûr.

3) Cette approche échouera si le réseau est un graphique cyclique qui ne peut pas être représenté par une structure d'arbre. Dans un tel cas, vous devez d'abord créer des nœuds graphiques morts ou vivants, puis exécuter un algorithme de routage sur le graphique pour compter le nombre de nœuds uniques et accessibles. Cela n'augmentera pas la complexité temporelle de l'algorithme, mais évidemment la complexité du code.

4) La dépendance temporelle est une modification non triviale mais possible si vous connaissez le MTBF / R (moyen-temps entre les failures / réparations) car cela peut vous donner les probabilités p de la structure d'arbre ou du linéaire non corrélé p[i] par une somme d'exponentiels. Vous devrez alors exécuter le procédure MC à différents moments avec les résultats correspondants pour p.

5) Si vous avez simplement les fichiers journaux (comme indiqué dans votre dernier paragraphe), cela nécessitera une modification substantielle de l'approche qui est au-delà de ce que je peux faire sur ce tableau. Les fichiers de journaux devraient être suffisamment approfondis pour permettre de reconstruire un modèle pour le graphique réseau (et donc le graphique de p) ainsi que les valeurs individuelles de tous les nœuds de p. Sinon, la précision ne serait pas fiable. Ces fichiers logarithmiques devraient également être considérablement plus longs que les échelles de temps des échecs et des réparations, des hypothèses qui peuvent ne pas être réalistes dans les réseaux réels.

Answer 2

En supposant que chaque nœud a un taux de disponibilité constant, connu et indépendant, une approche de division et de conquête me vient à l'esprit.

Dire que tu as N nœuds.

1. Les diviser en deux ensembles de N/2 nœuds.
2. Pour chaque côté, calculez la probabilité que n'importe quel nombre de nœuds ([0,N/2]) sont en panne.
3. Multiplier et les résumer selon les besoins pour trouver la probabilité que n'importe quel nombre ([0,N]) de l'ensemble complet est en panne.

L'étape 2 peut être effectuée de manière récursive et au niveau supérieur, vous pouvez résumer comme vous devez trouver la fréquence à laquelle plus qu'un nombre est en baisse.

Je ne connais pas la complexité de cela mais si je dois deviner, je dirais à ou en dessous O(n^2 log n)

---

La mécanique de ceci peut être illustrée sur un cas terminal. Dites que nous avons 5 nœuds avec des heures de hauteur . Nous pouvons diviser cela en segments A avec et B avec . Nous pouvons ensuite les traiter pour trouver les temps "n nœuds" pour chaque segment:

Pour un:

Pour b:

Les résultats finaux de cette étape peuvent être trouvés en multipliant chacun des aavec chacun des b«S et résumer de manière appropriée.

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]