Modelización de la concurrencia en sistemas distribuidos multiagente: autómatas cooperativos

Abstract

[EN] The main objective of Doctoral Thesis "Modelling Concurrency in Distributed Multi-Agent Systems: Cooperating Automata" is the definition and extension of a model conceived to describe multi-agent systems that combines desirable features of the "Petri Nets" and "Automata Theory". Another goal is the definition of an automated analysis mechanism over the model in order to simplify those systems in subsystems to detect critical parts even before the end of the modelling phase. The last objective of the Doctoral Thesis is to develop some software tools in order to help designers with the edition, analysis and provide simulation of the systems modelled.

The expressive power of the model of the Cooperating Automata (CA) when describing concurrent systems has been swoen as one of the contributions of the Thesis. The model has been compared with other similar proposals in the literature such as "Parallel Finite Automata", "Team Automata" and "Reference Nets". Some convertion algorithms between AC and these proposal has been presented also.

Another contribution of the author is an extension of the original model, the Extended Cooperating Automata (ECA), which aims to improve usability and reduce the state diagram of automatons without sacrificing any of the desirable features of the original model. This extension has been defined adding clarity and readability to the resulting models and a more natural approach to represent common situations without the use of the full model of the Cooperative Automata because, in this case, some properties such as boundedness are undecidable.

The ECA model expressive power is completely equivalent to the original model. However, systems modelled with ECA are quite simple compared to the same systems modelled with CA. The same translations between systems shown before are now simplified. And another conversion two-ways algorithm between CA and ECA has been also described.

The complexity of new systems, and consequently their respective models, has been increasing constantly. In this sense, simplifying but also detecting problems as bottlenecks is crucial at early stages of the design. Doing so over the implementation or implantation phases may duplicate the budget of the whole construction of a given system. Some relations between ECA model parts has been defined in order to perform this authomatic analysis. i.e. Linking relation between an automaton and a transaction rule, Concurrency relation between two automata, and Competition relation between two transaction rules.

These relations are defined with four levels of certainty from the weakest to the strongest. The weakest relations can be obtaied automatically at design time. An algorithm of calculus can be applied to these relations in order to identify different threads, critical parts of the system and even superfluous or unifiable elements. This analysis can be performed regardless of heuristic knowledge about the system. An example of this analysis (applied over a system where the names of rules, controllers, actions and statements have been coded to conceal this heuristic) has been included also.

Finally, two software tools are presented, the first is a support system for modeling with ECA, which guides the designer with the description of the different parts that comprise the model. It includes syntax check and also can perform the a priori analysis automatically during the design stage. This tool presents a report of the analysis results. The second tool is an extended simulator capable to simulate both AC systems as ACE. The simulator provide non-determinism choice of rules and/or automata during execution.

[ES] La Tesis Doctoral "Modelización de la concurrencia en sistemas distribuidos multiagente: autómatas cooperativos" tiene como objetivo final la definición y extensión de un modelo para la descripción de sistemas multiagente que aúne características deseables de las "Redes de Petri" y la "Teoría de Autómatas", así como la definición de un mecanismo automatizable de análisis sobre los sistemas descritos con este modelo que permite la simplificación de los mismos en sub-sistemas y la detección de partes críticas antes incluso de finalizar el modelado. También como objetivo se persigue dotar al sistema de un software de ayuda que automatice las partes de diseño, de análisis y de simulación de los sistemas descritos.

Como aportaciones de la Tesis Doctoral se muestra la potencia expresiva del modelo de los Autómatas Cooperativos (AC) a la hora de describir sistemas concurrentes, además partiendo del modelo de los AC se realiza una comparativa de los mismos con otros modelos presentes en la literatura, como son los "Autómatas finitos Paralelos", los "Autómatas Team", y las "Redes de referencias", presentando en su caso mecanismos semiautomáticos de conversión entre los Automatas Cooperativos y ellos.

En la Tesis Doctoral también se define una extensión del modelo original cuyo objetivo es de mejorar su usabilidad y reducir el diagrama de estados de los autómatas sin renunciar a ninguna de las características deseables del modelo original, pero añadiendo, sin embargo, mayor claridad y legibilidad a los modelos resultantes y una manera más natural de enfocar situaciones habituales sin necesidad del uso del modelo completo de los Autómatas Cooperativos dado que en este caso no hay decibilidad sobre determinadas propiedades como la de acotamiento.

Los, así llamados, Autómatas Cooperativos Extendidos (ACE), cuya equivalencia expresiva con el modelo original es completa, permiten simplificar en gran medida y a tal efecto se muestran las simplificaciones resultantes en las conversiones entre sistemas desarrolladas anteriormente, así como un algoritmo de conversión entre el modelo AC original y el extendido.

Una vez realizada la extensión se plantea la necesidad de realizar un análisis de los sistemas modelados identificando partes críticas y subprocesos durante las etapas más temprana del diseño y que este análisis fuera, dentro de lo posible, automático. Para realizar dicho análisis se definen formalmente las relaciones existentes entre las distintas componentes del modelo. Más concretamente las relaciones de vinculación entre autómatas y reglas, las de concurrencia de autómatas en reglas y las de competencia de reglas por autómatas. Dichas relaciones se definen con cuatro niveles de certidumbre siendo la más débil la que puede obtenerse automáticamente en tiempo de diseño. Una vez explicadas las relaciones propone un algoritmo de cálculo que permite identificar tanto los subprocesos, las partes críticas del sistema e incluso los elementos supérfluos o unificables, independientemente del conocimiento heurístico que sobre el sistema a modelar se tenga. Un ejemplo de este cálculo presenta sobre un sistema tipo donde los nombres de reglas, autómatas, acciones y estados han sido codificados para ocultar dicha heurística.

Finalmente se presentan dos herramientas software, la primera es un sistema de ayuda para el modelado con los Autómatas Cooperativos Extendidos, que guia al diseñador en la descripción de las diferentes partes de las que consta el modelo verifica la sintaxis del mismo y parte de la lógica del mismo y a su vez permite realizar el análisis a priori antes mencionado de forma automática en cualquier momento del diseño, presentando un informe del resultado del mismo. La segunda es un simulador a su vez extendido para simular tanto sistemas AC como ACE y que permite el uso de no determinismo en la elección tanto de reglas como de autómatas.

[CA] La Tesi Doctoral "Modelització de la concurrència en sistemes distribuïts multiagent: autòmats cooperatius" té com a objectiu final la definició i extensió d'un model per a la descripció de sistemes multiagent que uneix característiques desitjables de les "Xarxes de Petri" i la "Teoria d'Autòmats", així com la definició d'un mecanisme automatitzable d'anàlisi sobre els sistemes descrits amb aquest model que permet la simplificació dels mateixos en sub-sistemes i la detecció de parts crítiques abans fins i tot de finalitzar el modelatge. També com a objectiu es persegueix dotar al sistema de programes d'ajuda que automatitzen les parts de disseny, d'anàlisi i de simulació dels sistemes descrits.

Com a aportacions de la Tesi Doctoral es mostra la potència expressiva del model dels Autòmats Cooperatius (AC) a l'hora de descriure sistemes concurrents, a més, partint del model dels AC, es realitza una comparativa dels mateixos amb altres models presents en la literatura, com són els "Autòmats finits Paral·lels", els "Autòmats Team", i les "Xarxes de referències", presentant si escau mecanismes semiautomàtics de conversió entre els Autòmats Cooperatius i ells.

En la Tesi Doctoral també es defineix una extensió del model original que el seu objectiu és de millorar la seua usabilitat i reduir el diagrama d'estats dels autòmats sense renunciar a cap de les característiques desitjables del model original, però afegint, no obstant açò, major claredat i llegibilitat als models resultants i una manera més natural d'enfocar situacions habituals sense necessitat de l'ús del model complet dels Autòmats Cooperatius atès que en aquest cas no hi ha decibilidad sobre determinades propietats com la d'acotament.

Els, així anomenats, Autòmats Cooperatius Estesos (*ACE), l'equivalència expressiva dels quals amb el model original és completa, permeten simplificar en gran mesura i a aquest efecte es mostren les simplificacions resultants en les conversions entre sistemes desenvolupades anteriorment, així com un algorisme de conversió entre el model AC original i l'estès.

Una vegada realitzada l'extensió es planteja la necessitat de realitzar una anàlisi dels sistemes modelats identificant parts crítiques i sub-processos durant les etapes més primerenca del disseny i que aquesta anàlisi fora, en la mesura del possible, automàtic. Per a realitzar aquesta anàlisi es defineixen formalment les relacions existents entre les diferents components del model. Més concretament les relacions de vinculació entre autòmats i regles, les de concurrència d'autòmats en regles i les de competència de regles per autòmats. Aquestes relacions es defineixen amb quatre nivells de certitud sent la més feble la que pot obtenir-se automàticament en temps de disseny. Una vegada explicades les relacions proposa un algorisme de càlcul que permet identificar tant els *sub-processos, les parts crítiques del sistema i fins i tot els elements innecesaris o unificables, independentment del coneixement heurístic que sobre el sistema a modelar es tinga. Un exemple d'aquest càlcul presenta sobre un sistema tipus on els noms de regles, autòmats, accions i estats han sigut codificats per a ocultar aquesta heurística.

Finalment es presenten dues eines software, la primera és un sistema d'ajuda per al modelatge amb els Autòmats Cooperatius Estesos, que ajuda al dissenyador en la descripció de les diferents parts de les quals consta el model verifica la sintaxi del mateix i part de la lògica del mateix i al seu torn permet realitzar l'anàlisi a priori abans esmentat de forma automàtica en qualsevol moment del disseny, presentant un informe del resultat del mateix. La segona és un simulador al seu torn estès per a simular tant sistemes AC com ACE i que permet l'ús de no determinisme en l'elecció tant de regles com d'autòmats.