Consenso para ordem total de tarefas com prioridade

Abstract

Em sistemas de tempo real, inversão de prioridades é o problema em que há tarefas de alta prioridade críticas que devem ser executadas antes de tarefas de baixa prioridade, mas não conseguem. Em sistemas distribuídos tolerantes a faltas com replicação ativa, cada réplica deve, além de resolver o problema da inversão de prioridade, executar todas as tarefas na mesma ordem para manter a consistência. Os trabalhos existentes que resolvem o problema dependem de premissas fortes como o uso de serviços de consenso, o que faz com que o algoritmo execute com uma complexidade de mensagens trocadas quadrática ou cúbica. O trabalho proposto pretende modificar algoritmos de consenso para resolver o problema de inversão de prioridades sem depender de tais premissas fortes, com complexidade de mensagens linear.<br>

Abstract : In real-time systems, priority inversion is the problem in which there are higher priority tasks that must be executed before lower priority taks, but cannot. In fault tolerant distributed systems with active replication, each replica must, besides solving the problem of priority inversion, execute all requests at the same order to maintain consistency. Current works that solve the problem depend on strong assumptions like the use of consensus services, that causes the algorithm to execute with quadratic or cubic complexity of message transmission. The proposed work aims to adapt consensus algorithms in order to solve the priority inversion problem without depending on such strong assumptions, achieving linear message tranmission complexity.