Confiabilidade das redes de workflow: classificação, decidibilidade e análise

Resumo Redes de workflow, uma classe particular de redes de Petri, tornaram-se uma das maneiras padrão de modelar e analisar workflows. Normalmente, são usadas como uma abstração do workflow que é utilizada para verificar a chamada propriedade de confiabilidade. Essa propriedade garante a ausência de livelocks, deadlocks e outras anomalias que podem ser detectadas sem conhecimento de domínio. Vários autores propuseram noções alternativas de confiabilidade e sugeriram o uso de linguagens mais expressivas, por exemplo, modelos com cancelamentos ou prioridades. Este artigo fornece uma visão geral das diferentes noções de confiabilidade e investiga-as na presença de diferentes extensões de redes de workflow. Mostraremos que as oito noções de confiabilidade descritas na literatura são decidíveis para redes de workflow. No entanto, a maioria das extensões tornará todas essas noções indecidíveis. Esses novos resultados mostram os limites teóricos da verificação de workflows. Além disso, discutimos algumas das abordagens de análise descritas na literatura.