Algorithme «Bad Apple» ou processus bloque le bac à sable partagé

Je cherche un algorithme pour gérer le problème suivant, que j'appelle (pour l'instant) l'algorithme "bad apple".

Le problème

J'ai N processus en cours d'exécution dans M bacs à sable, où N >> M.
Il est impossible de donner à chaque processus son propre bac à sable.
Au moins un de ces processus se comporte mal et fait tomber l'ensemble du bac à sable, tuant ainsi tous les autres processus dans le même bac à sable.

S'il s'agissait d'un seul processus mal comporté, je pourrais utiliser une simple bissection pour mettre la moitié des processus dans un bac à sable et l'autre moitié dans un autre bac à sable, jusqu'à ce que je trouve le mécréant.

La question

Si plusieurs processus se comportent mal - y compris la possibilité qu'ils soient tous mal comportés - cet algorithme naïf "fonctionne"? Est-il garanti de fonctionner dans des limites raisonnables?

Simplifications

Par souci d'argument, supposons qu'un mauvais processus fait tomber son bac à sable instantanément, et qu'un bon processus ne le fait jamais.

algorithms Roger Lipscombe
la source

Dans quelle mesure le processus mal conduit fera-t-il tomber le bac à sable? Je veux dire - pouvons-nous supposer un temps fini où nous savons avec certitude que le sandbox donné ne fonctionne que des processus "propres" parce qu'il ne s'est pas planté?

SF.

Malheureusement non: le fait qu'un bac à sable ne plante pas pendant 5 minutes ne signifie pas que tous les processus se comportent bien, mais cela nous donne plus de confiance dans ce fait.

Roger Lipscombe

... mais pour les besoins de cette question, nous pourrions approximer en accordant un temps fini, je suppose.

Roger Lipscombe

Vous devez atomiser ce que vous considérez comme un processus «réussi» et «échoué». S'il s'exécute 5 minutes sans échec, il pourrait toujours être techniquement une mauvaise pomme, mais comme le problème d'arrêt, vous n'aurez jamais 100% de certitude quand il passe sans faire de lignes dures dans le sable.

Neil

On dirait que vous êtes sur la bonne voie. S'il existe de nombreux processus et plusieurs mauvaises pommes, vous devrez peut-être utiliser une grande valeur de M ou des groupes inégaux pour pouvoir isoler les bonnes pommes connues, puis conserver le bien connu dans un bac à sable et continuer à diviser les processus inconnus entre vos autres bacs à sable jusqu'à ce que vous ayez identifié les individus. Plus vous avez de bacs à sable, plus cela ira vite. Comme l'a souligné @Neil, il s'agit d'un gros O de l'algorithme de base M de N, donc l'augmentation de M réduira vos essais.

GlenPeterson

Réponses:

Si vous trouviez une mauvaise pomme, vous pouvez appliquer l'algorithme:

Divisez N en M groupes
Effectuez le test sur chaque groupe.
Si la taille du groupe est supérieure à 1, revenez à l'étape 1, en remplaçant N par le nombre d'éléments du mauvais groupe.

De même, si vous trouviez la seule "bonne" pomme, le même algorithme s'applique, mais plutôt le bon groupe.

Cet algorithme a un taux de performance O (log_M (N)) mais cela dépend du fait qu'il n'y a qu'une seule mauvaise pomme.

Si vous ne savez pas combien il y a de bonnes / mauvaises pommes, vous pouvez utiliser l'algorithme suivant:

For each M processes in N
  Test M processes

C'est le pire des cas, mais il s'exécute dans le O(N/M)temps (ou O(N)selon que vous considérez une seule passe comme un seul test ou comme un ensemble de tests effectués en parallèle). Tout bien considéré, ce n'est en aucun cas une mauvaise approche.

Il peut y avoir des algorithmes qui fonctionnent mieux que cela, mais cela nécessite que vous sachiez combien de mauvaises pommes / bonnes pommes il y a dans le lot. Ne connaissant pas ce facteur, bien que je ne puisse pas le prouver, je serais prêt à parier que vous ne pouvez pas faire mieux que le dernier algorithme répertorié ci-dessus.

J'espère que cela pourra aider!

Edit : D'un point de vue pratique, je comprends que certaines de ces opérations ne sont pas faciles à effectuer. C'est vrai, cependant, la triste réalité est que vous ne pouvez pas déterminer la mauvaise pomme strictement à partir de laquelle les processus s'exécutaient sur le bac à sable qui s'exécutait à ce moment sans être au moins d'activer ou de désactiver les processus. Si la question concerne l'algorithme, je pense avoir répondu à cela. Si la question porte sur la façon de gérer une situation comme celle-ci, alors la question conviendrait peut-être mieux au superutilisateur SE.

Neil
la source

Malheureusement, je ne peux pas "tester" les processus; tout ce que je sais, c'est que l'un des bacs à sable s'est écrasé et qu'il a été causé par un ou plusieurs des processus qui s'y trouvent.

Roger Lipscombe

Le problème est qu'après avoir bissecté l'ensemble, les deux partitions peuvent contenir de mauvaises pommes. Ce qui me fait penser que j'ai besoin de plus qu'une simple partition ...

Roger Lipscombe

@RogerLipscombe Vous essayez d'appliquer un algorithme à un scénario réel. Bien sûr, vous ne pourrez pas tester les processus un par un, et il peut s'avérer difficile de tester ces processus sur différentes machines, cependant, si vous voulez aller au fond des choses, vous allez doivent trouver un moyen d'une manière ou d'une autre. Si vous insérez des variables qui ne peuvent pas être résolues, vous ne pourrez tout simplement pas trouver un algorithme qui puisse localiser avec précision la ou les mauvaises pommes.

Neil

OK, donc par "test", vous voulez simplement dire "laissez-les courir assez longtemps pour avoir confiance" ...?

Roger Lipscombe

@RogerLipscombe Je suppose que oui. Cela peut prendre plus de temps, mais c'est vous qui devez déterminer le temps d'attente. Sachant cela et en suivant cet algorithme, vous pourriez techniquement trouver toutes les mauvaises pommes. Cependant, il peut être plus rapide de simplement regarder le journal des événements de Windows pour les plantages.

Neil