Fault-tolerant stochastic distributed systems

Daniel de Matos Silvestre

Key information

Authors:

Daniel de Matos Silvestre (Daniel de Matos Silvestre)

Supervisors:

Carlos Jorge Ferreira Silvestre (Carlos Jorge Ferreira Silvestre); Joao Pedro Cordeiro Pereira Botelho Hespanha (João Pedro Cordeiro Pereira Botelho Hespanha)

Published in

December 20, 2017

Abstract

A presente tese de doutoramento desenvolve técnicas de projecto de sistemas distribuídos tolerantes a falhas, focando em particular algoritmos nos quais as acções de cada nó e as interacções entre nós têm carácter estocástico. O objectivo principal é detectar e identificar falhas por forma a melhorar a tolerância a falhas do tipo crash em sistemas distribuídos, bem como detectar a presença de agentes maliciosos à procura de explorar e tomar o controlo do sistema. A análise proposta considera agentes maliciosos e soluções computacionais utilizáveis no contexto da detecção de falhas. No presente estudo, abordam-se falhas do tipo crash, onde o componente afectado pela falha deixa de funcionar completamente, que são tratadas através da introdução de decisões estocásticas em sistemas determinísticos distribuídos. O objectivo da análise é garantir a convergência bem como determinar a velocidade a que o sistema atinge a solução estacionária. O caso de uma rede social (exemplo de dinâmica dependente do estado) e de um algoritmo de consenso (dinâmica dependente do tempo) são estudados, sendo provada convergência, tornando-os robustos à perda de pacotes na rede, atrasos, competição por acesso ao meio partilhado e, em particular, a agentes que deixam de funcionar e/ou perdem conectividade. Para um modelo de falhas mais genérico que o tipo crash, este trabalho recorre a Set-Valued Observers (SVOs) como ferramenta para detectar falhas no pior cenário, i.e., quando um agente malicioso pode seleccionar a sequência de comunicações mais desfavorável e injectar um sinal de magnitude arbitrária. Para outros tipos de falhas, em que os nós não se comportam de acordo com as distribuições de probabilidade do modelo, é introduzido o conceito de Stochastic Set-Valued Observers (SSVOs) que produzem um intervalo de confiança que contém o estado do sistema com uma probabilidade pré-definida. Para um algoritmo de consenso é demonstrado como é possível explorar a estrutura do problema de forma a diminuir a complexidade computacional da solução. O resultado principal é a remoção no modelo das interacções que não têm impacto nos conjuntos estimados. A principal desvantagem dos SVOs clássicos no contexto de detecção de falhas é o seu peso computacional. Recorrendo a uma factorização coprima à esquerda, para sistemas lineares com parâmetros variantes no tempo, mostra-se como reduzir a sua complexidade computacional. Selecionando apropriadamente a factorização é possível ainda considerar sistemas detectáveis (i.e., sistemas não observáveis mas cuja componente não observável é estável). Este resultado é de particular importância no domínio dos Cyber-Physical Systems (CPSs). Estas técnicas são complementadas com estratégias do tipo event- e self-triggered que permitem reduzir a frequência de envio das medidas dos sensores. As mesmas podem ser utilizadas para tomar decisões de quando executar a rotina dos SVOs ou utilizar aproximações, comprometendo a precisão, para ganhar em tempo computacional, mantendo a convergência das estimativas destes observadores. O desenvolvimento desta estratégias é fundamental uma vez que a redução de utilização dos recursos da rede é essencial para garantir a aplicabilidade da detecção de falhas com base em SVOs no domínio dos Networked Control Systems (NCSs). The present doctoral thesis discusses the design of fault-tolerant distributed systems, placing emphasis in addressing the case where the actions of the nodes or their interactions are stochastic. The main objective is to detect and identify faults to improve the resilience of distributed systems to crash-type faults, as well as detecting the presence of malicious nodes in pursuit of exploiting the network. The proposed analysis considers malicious agents and computational solutions to detect faults. Crash-type faults, where the affected component ceases to perform its task, are tackled in this thesis by introducing stochastic decisions in deterministic distributed algorithms. Prime importance is placed on providing guarantees and rates of convergence for the steady-state solution. The scenarios of a social network (state-dependent example) and consensus (time-dependent example) are addressed, proving convergence. The proposed algorithms are capable of dealing with packet drops, delays, medium access competition, and, in particular, nodes failing and/or losing network connectivity. The concept of Set-Valued Observers (SVOs) is used as a tool to detect faults in a worst-case scenario, i.e., when a malicious agent can select the most unfavorable sequence of communications and inject a signal of arbitrary magnitude. For other types of faults, it is introduced the concept of Stochastic Set-Valued Observers (SSVOs) which produce a confidence set where the state is known to belong with at least a pre-specified probability. It is shown how, for an algorithm of consensus, it is possible to exploit the structure of the problem to reduce the computational complexity of the solution. The main result allows discarding interactions in the model that do not contribute to the produced estimates. The main drawback of using classical SVOs for fault detection is their computational burden. By resorting to a left-coprime factorization for Linear Parameter-Varying (LPV) systems, it is shown how to reduce the computational complexity. By appropriately selecting the factorization, it is possible to consider detectable systems (i.e., unobservable systems where the unobservable component is stable). Such a result plays a key role in the domain of Cyber-Physical Systems (CPSs). These techniques are complemented with Event- and Self-triggered sampling strategies that enable fewer sensor updates. Moreover, the same triggering mechanisms can be used to make decisions of when to run the SVO routine or resort to over-approximations that temporarily compromise accuracy to gain in performance but maintaining the convergence characteristics of the set-valued estimates. A less stringent requirement for network resources that is vital to guarantee the applicability of SVO-based fault detection in the domain of Networked Control Systems (NCSs).