Brevet FR2967274A1 — publié le 20120511

Procédé de détermination d'un équipement « leader » dans un environnement asynchrone comprenant une pluralité d'équipements électroniques Le domaine de l'invention est celui des systèmes informatiques comprenant une pluralité d'équipements électroniques dialoguant entre eux et devant être capables de continuer à assurer un minimum de fonctions jugées critiques, y compris en mode dégradé. Le procédé selon l'invention s'applique tout particulièrement aux logiciels gérant le système de visualisation des cockpits d'aéronefs et participant notamment à la prise de décision liée aux reconfigurations graphiques des affichages en cas de panne ou de dysfonctionnement. Un tel système est généralement composé de plusieurs unités de calcul et d'affichage relié entre elles par un réseau de communication asynchrone. La figure 1 représente un exemple d'un tel système. Le système de la figure 1 comporte cinq unités de visualisation, deux unités de type PFD (Primary Flight Display), deux unités de type ND (Navigation Display) et une unité centrale de type EWD (Engine Warning Display). Chaque unité est responsable d'afficher une configuration d'image sur une visualisation donnée en respectant des règles spécifiées lors de la définition du système. On citera, par exemple, comme règles : - au moins une configuration de type « Primary Flight Display » ou « PFD » affichée par demi-cockpit ; - une configuration de type « Engine and Warning Display » ou EWD sur le calculateur central ; ... Ces règles ont pour objectif de garantir l'affichage des informations nécessaires à la réalisation des tâches du pilote et du copilote en cas de panne d'une unité ou en cas de sélection d'une autre image par l'un des deux utilisateurs. Afin de veiller au bon respect de ces règles, un composant logiciel est mis en place pour vérifier l'état global du système et prendre les décisions qui s'imposent. Le résultat de cette décision est donc issu de la collaboration des différents équipements du système. Cette collaboration se fait par des échanges au sein d'un système connecté par un réseau de communication asynchrone. On entend par système asynchrone un système dont les échanges de données entre les noeuds qui le constitue sont émis et analysés selon une référence de temps différente et un rythme qui varie selon les noeuds. On entend par « noeud » toute interconnexion du système et de façon plus générale tout équipement du système. Il existe alors des contraintes de performances strictes et restrictives sur les prises de décision qui doivent être effectuées dans un temps de l'ordre de 150 millisecondes. En cas de panne, le système propose la meilleure solution compte tenu de l'état du système et du type de panne. Il peut s'agir d'une panne d'une unité ou d'une panne d'une connexion du réseau, l'objectif étant de conserver un bon de niveau de disponibilité du système permettant de réagir correctement aux interactions du pilote et du copilote. Par ailleurs, même en cas de panne, le comportement global du système doit être déterministe afin de garantir la certification du système. Enfin, dans le cas extrême d'une panne systématique qui conduirait à l'isolement de chaque équipement, l'équipage doit pour autant pouvoir continuer d'interagir individuellement avec chaque équipement. L'équipage peut ainsi comparer les résultats locaux et continuer d'assurer au mieux le contrôle de l'aéronef. Il est donc nécessaire que le logiciel soit capable de déterminer la meilleure répartition possible des configurations d'affichage sur les visualisations. Le choix de répartition doit vérifier : Un niveau de performance borné de la sélection d'une solution ; Un niveau de disponibilité important même dans le cas où chaque équipement est isolé ; Un calcul de solution déterministe quelque soit le niveau de panne , Une approche simple de mise oeuvre afin de garantir la certification du système. En fonction de l'état du système qui comprend les postes de commande ou « control panel », le réseau de communication, les calculateurs, les afficheurs,..., un algorithme décide de la distribution des formats de type PFD (Primary Flight Display), ND (Navigation Display), EWD (Engine Warning Display), DMAP (Digital MAP) sur l'ensemble des calculateurs du cockpit et doit garantir, comme il a été dit, certaines propriétés du type « au moins un format PFD par demi-cockpit ». Auparavant, les règles étaient traitées localement par chaque unité ou « Display Unit » ou « DU ». Une synchronisation a posteriori était donc nécessaire pour garantir la cohérence du besoin système comme, par exemple, une distribution correcte des formats sur le cockpit. La phase de synchronisation pose un problème de cohérence du système des données car elle ne peut être traitée que localement avec un ordre de traitement des états différents d'un calculateur à l'autre compte-tenu des asynchronismes existant entre les différents équipements. Ainsi, l'interprétation successive des changements d'état d'un calculateur à l'autre peut, par déviation, aboutir à une incohérence du résultat final. Le résultat est corrigé ensuite par le biais de la synchronisation mais le système peut passer par une phase transitoire qui n'est pas satisfaisante d'un point de vue opérationnel. Aussi, dans un système composé de plusieurs équipements, il est classique d'utiliser un déploiement centralisé de l'algorithme de prise de décision. Un leader est élu au sein du groupe d'équipements. On entend par élection d'un leader dans un système distribué, le mécanisme de désignation d'un processus en tant qu'organisateur d'une tâche distribuée sur un ensemble d'unités de calcul. Les membres du système communiquent entre eux pour décider qui sera le chef. Le leader exécute alors les prises de décisions autant que nécessaire puis distribue le résultat de chaque prise de décision aux autres membres du groupe. La figure 2 illustre de façon schématique ce principe. Les cinq unités d'un système et notées A, B, C, D et L sont dirigés par le leader L qui attribue aux autres unités A, B, C et D les tâches à effectuer. En cas de panne, le groupe doit élire un autre leader. Des recherches dans ce domaine ont démontré que le processus d'élection d'un leader dans un système distribué asynchrone ne peut pas être borné en temps. Le processus d'élection d'un leader est en effet plus compliqué à résoudre qu'un consensus dans le cas d'un système asynchrone. Dans un système distribué, le principe du consensus représente l'action d'harmonisation du groupe en cas de panne. Un protocole permettant le consensus doit satisfaire les propriétés suivantes : Terminaison : tout processus correct doit décider d'une valeur, Validité : si tous les processus décident de la même valeur v, alors chaque processus correct décide v. Intégrité : chaque processus décide d'au plus une valeur, et s'il décide d'une valeur v, alors v doit avoir été proposée par un autre processus. On se reportera sur ce point aux travaux de L.S.Sabel, K.Marzullo, Election vs. Consensus in asynchronous systems, Cornell University, 1995. II a été également démontré formellement que la résolution d'un consensus est impossible à borner en cas de panne d'un seul processus dans un système asynchrone, publication de M.J.Fischer, N.A.Lynch, M.S.Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM, Vol. 32, 1985. D'une manière plus générale, il est impossible de trouver un consensus en présence de x fautes pour des systèmes ayant moins de 3x+1 noeuds, publication de M.J.Fischer, N.A.Lynch, M.Merritt, Easy impossibility proofs for distributed consensus problems, ACM, 1985. Des solutions plus élaborées existent pour traiter les cas de panne. Ainsi, la publication de C.Fetzer, F.Cristian, A highly available local leader election service, IEEE, 1999 démontre qu'il est possible de partitionner un système complexe en sous-systèmes stables plus petits sur lesquels on applique toujours les même principes d'élection et de consensus. Cependant, ces solutions présentent les inconvénients suivants : Elles ne sont que le support aux algorithmes d'élection ou de consensus qui conservent toute leur complexité protocolaire et qui se traduisent par un grand nombre d'échanges de messages ; La propagation sur les noeuds ne permet pas que les échanges de messages au sein d'un système asynchrone soient totalement ordonnés. Les messages doivent donc être datés ; La datation des messages nécessite la mise en oeuvre de la synchronisation d'une horloge globale : il y a augmentation des flux de données entre les noeuds du système ; Elles se basent sur le principe de stabilité des partitions qui est lui-même le résultat d'un consensus ; Dans les systèmes orientés messages ou conversationnels, c'est- à-dire des systèmes où le client émettant des requêtes vers l'ordinateur, celui-ci choisit s'il doit ou non d'y répondre ainsi que le moment où il doit fournir la réponse, il est plus difficile d'identifier le pire cas de fonctionnement qui correspond à l'activation possible de toutes les branches du logiciel liées à ces messages. Ce pire cas doit pourtant être envisagé pour la phase finale de certification. Au final, l'objectif des systèmes fortement centralisés basés sur l'élection ou le consensus est réellement la supervision d'un ensemble de noeuds en vu d'une collaboration pour la réalisation collective d'une tâche déterminée. Dans un environnement certifiable à forte contrainte de performance, la mise en ceuvre d'une telle solution pose les problèmes suivants : Complexité de mise en oeuvre et volume des échanges qui pénalisent la performance sur les échanges de données ; Absence de déterminisme due à la difficile identification du pire cas d'activation des traitements des messages ; Latences importantes dues aux échanges de messages en « va-et-vient » importants ; Dans le cas d'un cockpit d'aéronef, il est préférable de garantir la disponibilité et la réactivité unitaire de chacun des écrans d'affichage plutôt que de garantir la décision globale du système qui ne satisfait pas aux contraintes de réactivité. En cas de pannes multiples, c'est bien l'équipage qui joue le rôle du leader en contrôlant les différents équipements. Le procédé de sécurisation selon l'invention repose sur le principe de la désignation d'un équipement « leader» pour partager l'état global du système, centraliser le calcul et distribuer ensuite le résultat sur le système en supprimant la phase de synchronisation. Cependant, le mode de désignation du « leader » et le fonctionnement sécurisé du système repose sur des mécanismes nouveaux propres au procédé selon l'invention qui permettent de garantir la disponibilité de la fonction de reconfiguration centralisée en cas de perte ou d'isolation d'une partie du système. Plutôt que d'utiliser le principe de l'élection du leader qui est difficile à résoudre dans un environnement asynchrone, le procédé selon l'invention consiste essentiellement à : sélectionner le leader du système ou les leaders des sous-systèmes en fonction de listes prédéterminées établies pour le système et les sous-systèmes possibles en fonction de pannes simples, doubles ou multiples pouvant surgir dans le système ; vérifier les informations issues du leader sélectionné par les équipements ou noeuds du système ou des sous-systèmes ; changer de leader sélectionné en cas de panne avérée dudit leader. Plus précisément, l'invention a pour objet un procédé de sécurisation aux pannes d'un système électronique comportant une pluralité d'équipements reliés entre eux par un réseau de communication asynchrone, ledit système comportant au moins un équipement dit « leader principal», ledit « leader principal » assurant l'organisation et/ou la distribution des tâches effectuées par les autres équipements, caractérisé en ce que chaque équipement possède une liste prédéterminée de « leaders de remplacement », le « leader de remplacement » étant sélectionné en cas de perte du « leader principal » vu d'un équipement. Le rôle du « leader de remplacement » est de distribuer les résultats de son « leader principal » ou même de réaliser le calcul s'il se sélectionne lui même comme « leader principal ». Avantageusement, les équipements dépendant d'un « leader » contrôlent le bon fonctionnement dudit leader en surveillant le 25 « vieillissement » des signaux émis par ledit leader. Avantageusement, la validité des signaux reçus par un équipement et issus de son « leader» est vérifiée par ledit équipement. Préférentiellement, le système électronique peut, soit d'origine, soit à la suite d'une panne, comporter plusieurs sous-systèmes 30 indépendants, chaque sous-système comportant un « leader». De façon préférée, le système est le système de visualisations d'un cockpit d'aéronef, les équipements sont des calculateurs de bord et/ou des afficheurs ou « Display Unit », le ou les « leaders » ayant pour tâches principales d'assurer le respect des règles de gestion des différentes 35 configurations/reconfigurations d'affichage sur les afficheurs. L'invention sera mieux comprise et d'autres avantages apparaîtront à la lecture de la description qui va suivre donnée à titre non limitatif et grâce aux figures annexées parmi lesquelles : La figure 1 déjà commentée représente un système e visualisation de cockpit à cinq équipements ; La figure 2 déjà commentée représente le principe de supervision du fonctionnement d'un système par un équipement leader ; La figure 3 représente un système à cinq équipements selon 10 l'invention comprenant un leader central, le système étant en mode de fonctionnement nominal ; La figure 4 représente l'état du système précédent en cas de panne d'interconnexion du leader ; La figure 5 représente l'état du système précédent en cas de 15 panne générale du leader. Comme il a été dit, il existe des systèmes électroniques comportant une pluralité d'équipements reliés entre eux par un réseau de communication asynchrone. 20 Le procédé s'applique tout particulièrement aux systèmes asynchrones temporisés qui sont les plus représentatifs des systèmes asynchrones. Ce sont des systèmes dont on sait borner le temps maximum entre l'envoi d'un message par un noeud et la réception de ce même message par un autre noeud du système. 25 Généralement, le système est « réactif », c'est-à-dire que chaque noeud du système réagit de manière continue aux signaux transmis par les autres noeuds. On dit encore que l'environnement est maître de l'interaction, le système réagissant de façon continue aux stimuli externes en produisant des réponses instantanées. Chaque noeud possède la même horloge 30 matérielle qui temporise leur comportement en unités de temps. Généralement, la fréquence du cycle est de 25Hz ou 30Hz ou 50Hz ou 60Hz. On peut ainsi vérifier la validité d'un signal, c'est à dire l'âge de la dernière donnée reçue. II n'y a pas nécessairement de cycle global au système, chaque noeud peut fonctionner de manière indépendante et ne se 35 synchronise pas avec les autres noeuds du système. Dans ce qui suit, on considère que : La visibilité est symétrique : soient deux équipements A et B du système, on considère que si A voit B par le réseau alors B voit A également par ce même réseau, L'erroné est transitif : soient trois équipements A, B et C, on considère que si B envoie des données erronées à A, alors il envoie également des données erronées à C. Cependant, les cas asymétriques et non transitifs sont possibles notamment par le biais des réseaux de secours présents en général pour garantir un haut niveau de disponibilité. Ce sont des cas particuliers qui ne modifient pas les principes exposés ci-dessous, en cela que le « leader » sélectionné par un sous-système isolé n'est plus celui qui calcul la décision mais qui distribue le résultat de son propre « leader » si il ne s'est pas sélectionné lui-même. Dans un certain nombre d'applications, le système doit assurer un fonctionnement minimal, y compris en cas de panne. Une méthode de sécurisation du système consiste à utiliser un déploiement centralisé de l'algorithme de prise de décision, la décision se faisant à partir de l'état de l'environnement du système. Un leader est alors élu au sein du groupe d'équipements. Le procédé de sécurisation selon l'invention d'un système électronique de ce type comporte également la désignation d'un leader. Cependant, à la différence des procédés précédents, cette désignation repose sur un certain nombre de principes simples exposés ci-dessous. Ainsi, ce procédé est robuste aux pannes jusqu'à une disponibilité locale de la fonction de calcul de décision, robuste aux pannes byzantines, déterministe et certifiable. On entend par panne byzantine toute panne engendrant un comportement s'écartant des spécifications. Tel est le cas d'un système se déclarant sain par un moyen donné mais fournissant des résultats faux par ailleurs. Le procédé selon l'invention sélectionne par défaut un leader particulier dans le système. Après la phase de démarrage, une fois que l'ensemble du système est stabilisé, c'est ce leader qui est en charge de calculer puis d'émettre le résultat du calcul de la décision vers les autres noeuds du système. Par exemple le système représenté en figure 3 représente un système de visualisations de cockpit à 5 unités d'affichage notés respectivement OL, IL, CD, IR et OR. L'unité CD est l'unité « Leader» et contrôle les autres équipements au moyen de deux sous-réseaux ségrégués, le premier comportant les unités OL, IL et CD et le second sous-système comportant les unités OR, IR et CD. Le nceud CD est un cas particulier qui fait arbitrairement partie des sous-réseaux de gauche ou de droite. Le premier principe du procédé selon l'invention permet d'assurer la disponibilité globale de la fonction de décision en cas de panne dans le système. En cas de panne, il est possible qu'un leader ne puisse plus être considéré comme valide pour tout ou partie du système. Ce défaut de validité peut intervenir pour différentes raisons : La connexion réseau est coupée entre le leader et certains équipements ; Le leader n'émet plus de signaux : il est en panne ou éteint ; Le leader émet des messages corrompus. Pour permettre l'émergence d'autres leaders dans les sous-réseaux issus de ces pannes, une liste ordonnée et prédéterminée des leaders sélectionnables est partagée par les noeuds du système. Cette liste peut-être différente pour chacun des sous-réseaux. Ainsi, à titre de premier exemple, si une panne d'interconnexion intervient entre le leader CD et l'équipement IL dans le système de la figure 3, le leader CD est séparé du sous-système de gauche constitué des unités IL et OL comme on le voit sur la figure 4. II reste cependant visible du sous-système de droite constitué des unités CD, IR et OR. Si le défaut subsiste, il y a vieillissement des signaux reçus par les équipements OL et IL en provenance de CD. Au bout de i unités de temps, OL et IL considèrent que CD est éteint ou en panne. OL et IL sélectionnent alors un nouveau leader et c'est l'unité IL qui est le suivant dans la liste. Pour les unités IR et OR, il n'y a pas d'impact, CD reste leur leader respectif. A titre de second exemple, si le leader CD de la figure 3 tombe en 35 panne, de la même manière, il y a vieillissement des signaux reçus par les équipements OL, IL, IR et OR en provenance de CD. Au bout de j unités de temps, OL, IL, IR et OR considèrent que CD est éteint ou en panne. OL et IL sélectionnent leur nouveau leader qui est l'unité IL. IR et OR sélectionnent leur nouveau leader qui est l'unité IR. Ainsi, dans cet exemple, deux nouveaux sous-réseaux émergent. La validité des signaux transmis entre les noeuds est vérifiée, par exemple par un code de Hamming, soit directement au niveau du bus de liaison physique, soit au niveau de la surveillance du leader. Un signal non valide n'est pas considéré comme transmis et l'âge des données reçues augmente tout naturellement. Le second principe du procédé selon l'invention permet la sécurisation globale du système. Afin d'éviter le risque de panne byzantine pouvant amener à la propagation d'une erreur sur l'ensemble du système, chaque décision, calculée puis transmise par le leader, est vérifiée par les autres noeuds du système. Il ne s'agit pas ici de reproduire le calcul effectué par le leader à partir de l'état du système, on se contente simplement de vérifier la validité de la décision en regard des cas possibles calculables par le système. On garantit ainsi que chaque noeud reste dans un état valide vis à vis de la décision éventuellement incorrecte de son leader. Si un leader a un comportement byzantin sur plus de k unités de temps, un autre leader est sélectionné. Ce procédé possède les propriétés et les avantages suivants : Déterminisme : quelle que soit la panne, on sait calculer avec 25 exactitude l'état du système ; En temps borné : le temps maximum pour la prise de décision est borné ; Robuste aux pannes : le système fonctionne de la même façon sur les sous-ensembles issus des pannes ; 30 Robuste aux comportements byzantins : un comportement anormal ne se propage pas sur le système ; Certifiable : la solution est déterministe, elle est vérifiable simplement et son pire cas est équivalent au cas nominal. REVENDICATIONS1. Procédé de sécurisation aux pannes d'un système électronique comportant une pluralité d'équipements reliés entre eux par un réseau de communication asynchrone, ledit système comportant au moins un équipement dit « leader principal», ledit « leader principal » assurant l'organisation et/ou la distribution des tâches effectuées par les autres équipements, caractérisé en ce que chaque équipement possède une liste prédéterminée de « leaders de remplacement », le « leader de remplacement » étant sélectionné en cas de perte du « leader principal » vu d'un équipement. 2. Procédé de sécurisation aux pannes d'un système électronique selon la revendication 1, caractérisé en ce que les équipements dépendant d'un « leader » contrôlent le bon fonctionnement dudit leader en surveillant le « vieillissement » des signaux émis par ledit leader. 3. Procédé de sécurisation aux pannes d'un système électronique selon la revendication 1, caractérisé en ce que la validité des signaux reçus par un équipement et issus de son « leader » est vérifiée par ledit équipement. 4. Procédé de sécurisation aux pannes d'un système électronique selon la revendication 1, caractérisé en ce que le système électronique peut, soit d'origine, soit à la suite d'une panne, comporter plusieurs sous-systèmes indépendants, chaque sous-système comportant un « leader». 25 5. Procédé de sécurisation aux pannes d'un système électronique selon l'une des revendications précédentes, caractérisé en ce que le système est le système de visualisations d'un cockpit d'aéronef, les équipement sont des calculateurs de bord et/ou des afficheurs ou « Display 30 Unit », le ou les « leaders » ayant pour tâches principales d'assurer le respect des règles de gestion des différentes configurations/reconfigurations d'affichage sur les afficheurs. 20