Tesis > Documento


Ver el documento (formato PDF)   Hirsch, Dan Francisco.  "Modelos de transformación de Grafos para estilos de arquitectura de software"  (2003)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
La evolución de los sistemas de software y la creciente complejidad de sus procesos de desarrollo han hecho necesario establecer pasos de diseño bien definidos que permitan reducir el gap entre requerimientos e implementaciones. En esta dirección, en años recientes, un área importante de la investigación ha tratado con las Arquitecturas de Software. Básicamente, una arquitectura de software es una descripción de alto nivel de un sistema complejo, con un nivel adecuado de abstracción que permite capturar del dominio del problema los componentes, a partir de los requerimientos, que serán diseñados detalladamente más adelante. Un Estilo de Arquitectura de Software es una clase de arquitecturas que exhiben un patrón común. Si la reusabilidad y la clasificación de arquitecturas son objetivos principales para permitir que los diseñadores exploten el trabajo previo, la identificación de una arquitectura de un sistema dentro de un estilo específico requiere lenguajes expresivos y bien fundados para representar estilos. Los requerimientos de los sistemas modernos imponen nuevas características a la descripción de las arquitecturas de software. Estos incluyen la distribución, la concurrencia, la reconfiguración y la movilidad. Por lo tanto, es necesario desarrollar el lenguaje de estilos que soporte estas características y por consiguiente su semántica formal. Entonces, la descripción de un estilo de arquitectura de software debe incluir la estructura de los tipos de componentes y sus interacciones, los patrones de comunicación, y las leyes que gobiernan la reconfiguración y/o la movilidad en la arquitectura. Siguiendo esta línea de investigación, es nuestro objetivo contribuir a la formalización de modelos para la descripción de arquitecturas y estilos de arquitectura de software. Esta tesis presenta un marco formal para la descripción de estilos de arquitectura de software basado en los sistemas de transformación de grafos. Una gramática de grafos caracteriza una clase de grafos que comparten características estructurales y está compuesta por un conjunto de reglas de reescritura llamadas producciones. Inicialmente, los grafos representan las configuraciones estáticas de las arquitecturas y las gramáticas representan los estilos. Luego, podremos incluir producciones que especifiquen las interacciones en mntime entre componentes, la reconfiguración y la movilidad. Las arquitecturas de sistemas pueden ser controladas de manera centralizada a través de un coordinador o administrador, o pueden ser sistemas denominados self organising en los cuales la coordinación está distribuida localmente entre los componentes. Los sistemas que tenemos en mente son distribuidos, lieterogéneos y móviles, y por lo tanto elegimos una estrategia self organising. En particular, para describir estilos elegimos utilizar gramáticas libres de contexto para Recscritura de Hiperejes (Hyperedge Replacement (HR) granunars) y gramaticas HR de Sincronización (Synchronized HR (SHR) grammars) para modelar la comunicación y la coordinación entre componentes. Un hipereje es un elemento atómico con una etiqueta (de un alfabeto con rango) y con tantos tentáculos como el rango de su etiqueta. Un conjunto de nodos y un conjunto de liiperejes forman un hipergrafo si cada lripereje esta conectado, por sus tentáculos, con sus nodos de enlace (attachmcnt nodos). Los Hiperejes corresponden a los componentes y sus nodos de enlace son sus puertos de conmnicación con otros componentes. Una producción HR reescribe un solo hipereje en un hipergrafo cualquiera. Entonces, para modelar la coordinación de los componentes de la arquitectura combinamos reescritura de grafos con condiciones de sincronización, obteniendo los sistemas SHR. Las producciones sincronizadas se especifican agregando condiciones en los nodos que permiten coordinar varias reescrituras, determinando la manera en que los componentes interactúan y se reconfiguran. Las producciones para (la etiqueta de) un hipereje determinado representan las posibles evoluciones para un determinado tipo de componente del estilo. Las producciones de una gramática se agrupan en tres conjuntos: el primer conjunto contiene las producciones HR para la construcción de todas las posibles configuraciones iniciales del estilo. El segundo conjunto contiene las producciones SHR que modelan la evolución de la comunicación para cada tipo de componente, y el tercer conjunto contiene las producciones SHR para la reconfiguración de la estructura del estilo. Las producciones de la comunicación requieren sincronización pero no pueden cambiar la estructura topológica del grafo. Con respecto a literatura anterior. esta tesis presenta una extensión de los sistemas SHR con la adición de movilidad de nombres (name mobility como en π-calculus). Esta extensión permite aumentar substancialmente el poder expresivo del método para la representación de sistemas complejos móviles y reconfigurables, mantieniendo al mismo tiempo la capacidad de describirlos de una manera descentralizada y distribuida. Representamos a los liipergrafos y los sistemas SHR en forma textual usando syntactic judgements. Esto permite una clara separación entre reescritura y coordinación, y la introducción de varios mecanismos de sincronización como adecuadas álgebras (móviles) de sincronización. Específicamente, presentamos las reglas de inferencia al estilo SOS para las álgebras de sincronización Hoare (CSP) y Milner (CCS, π-calculus). Sin embargo. en nuestra propuesta extendemos las álgebras de proceso permitiendo la sincronización simultánea de cualquier número de participantes. Las condiciones de sincronización para movilidad se resuelven vía unificación. Como resultado importante y evidencia formal del poder expresivo del método, presentamos un resultado de correspondencia que prueba que SHR con sincronización de Milner subsume al π-calculus. Para esto, definimos una traducción donde una transición en π-calculus se representa como una transición del correspondiente syntactic judgement traducido (es decir, un paso de reescritura). Puesto que π-calculus está equipado con una semántica interleaving y sólo sincronizaciones entre pares de elementos, la prueba es una correspondencia completa entre π-calculus y una versión restringida de los sistemas SHR. En la segunda parte de la tesis continuamos usando gramáticas HR (sin sincronización) para describir estilos e introducimos un enfoque específico basado en teoría de tipos para describir las reconfiguraciones de estilos (llamadas transformaciones). Las nociones de reconfiguración y movilidad implican modificaciones a la estructura de la arquitectura cambiando componentes y conexiones. Estas modificaciones que un sistema puede sufrir conducen a la pregunta de cómo podemos asegurar que los cambios sean consistentes con el estilo al cual pertenece el sistema. Por analogía, podemos pensar en los estilos como tipos para las instancias de arquitectura y en derivaciones HR como pruebas de tipo. Las reconfiguraciones deben preservar los tipos: en terminología de la teoría de tipos esta propiedad se llama subject reduction. Nuestro método consiste en definir transformaciones sobre pruebas de tipo, en lugar que sobre grafos: mientras que cortar y pegar pruebas de tipo resulten nuevamente en pruebas de tipo, la propiedad de subjet reduction está garantizada. La formalización se efectúa representando grafos y producciones como términos de un cálculo λ tipado, donde un paso de derivación HR corresponde a aplicación seguido por reducción β. Entonces, las transformaciones se especifican como reescritura de términos (de alto orden): si todas las reglas de reescritura transforman pruebas de tipo en pruebas de tipo, entonces todas las posibles reescrituras satisfacen subject reduction. El uso de cálculo λ introduce la idea de reescritura de grafos de alto orden, permitiendo la parametrización del proceso de diseño con características de componentes y conectores que podrían ser especificados más adelante, manteniendo la garantía de consistencia. La principal diferencia del método para reconfiguración usando SHR con respecto al que utiliza transformaciones, es que SHR es más dinámico, ya que es aplicable a sistemas abiertos en ejecución sin control global, a excepción de la sincronización. Por el otro lado, el método con transformaciones puede ser útil para trabajar al nivel de diseño estático, es decir, cambiar los pasos del diseño del sistema para producir un sistema diverso pero consistente. De todas maneras, el último método puede ser aplicado para especificar clases muy generales de reconfiguraciones y movilidad (como se demuestra en los ejemplos de la tesis), pero requiere un conocimiento global de la estructura del sistema. Los diferentes temas introducidos en la tesis son acompañados por ejemplos específicos que permiten clarificar las diversas construcciones y demostrar su poder expresivo, y por un caso de estudio de un sistema remoto de asistencia médica que es utilizado a lo largo de toda la tesis.

Abstract:
The evolution of software systems and the increased complexity of their developing processes have led to the necessity of establishing well defined design steps to close the gap between requirements and implementations. In this direction, in recent years a main research area has concerned Software Architectures. Basically, a software architecture is a high-level description of a complex system, with an adequate level of abstraction that enables capturing, from its requirements, the components of the problem domain to be later designed in more detail. A Software Architecture Style is a class of architectures exhibiting a common pattern. If reusability and classification of architectures are main goals to allow designers to exploit previous work, the identification of a system architecture within a specific style requires expressive and well founded languages to represent styles. The requirements of modern systems impose new characteristics to the description of software architectures. These include distribution, concurrency, reconfiguration and mobility. Therefore, it is necessary to develop the style language and its formal semantics accordingly. Thus, the description of a software architecture style must include the structure of component types and of their interactions, the communication patterns, and the laws governing reconfiguration and/or mobility changes in the architecture. In this line of research our goal is to contribute to the formalization of models for the description of software architectures and of software architecture styles. This thesis presents a formal framework based on graph transformation systems for the description of software architecture styles. A graph grammar characterizes a class of graphs that share structural characteristics and it is composed of a set of rewriting rules called productions. At first, graphs represent the static configurations of architectures and grammars represent styles. Later we will be able to include productions specifying runtime interactions among components, reconfiguration and mobility. System architectures can be managed in a centralized manner by an explicit coordinator or administrator, or can be self organising indicating that coordination management is distributed locally among components. The systems we have in mind are distributed, heterogeneous and mobile, thus we choose a self-organising approach. In particular, we choose context-free Hyperedge Replacement (HR) grammars to describe styles and Synchronized HR (SHR) grammars to model communication and coordination among components. A hyperedge is an atomic item with a label (from a ranked alphabet) and with as many tentacles as the rank of its label. A set of nodes together with a set of hyperedges form a hypergraph if each hyperedge is connected, by its tentacles, to its attachment nodes. Hyperedges correspond to components and their attachment nodes are their communication ports with other components. A HR production rewrites a single hyperedge into an arbitrary hypergraph. Then, to model the coordination of the architecture components we combine graph rewriting with synchronizing conditions obtaining SHR systems. We specify synchronized productions by adding conditions on nodes which allow to coordinate several rewritings, thus determining how components interact and are reconfigured. The productions for a given hyperedge (label) represent the possible evolutions for a given component type of the style. The productions of a grammar are grouped in three sets: the first set contains the HR productions for the construction of all possible initial configurations of the style. The second set contains the SHR productions that model the communication evolution for each component type and the third set contains the SHR productions for the reconfiguration of the style structure. The communication productions require synchronization but cannot change the topological structure of the graph. With respect to previous literature, this thesis presents an extension of SHR with the addition of name mobility (as in π-calculus). This extension allows us to substantially increase the expressive power of the approach for representing complex mobile and reconfigurable systems, still maintaining the ability of describing them in a decentralized, distributed way. We represent hypergraphs and SHR systems in textual form using syntactic judgements. This allows the clear separation of rewriting and coordination and the introduction of various synchronization mechanisms as suitable (mobile) synchronization algebras. Specifically, we present the inference rules in the SOS style for Hoare (CSP) and Milner (CCS, π-calculus) synchronization algebras. However, we extend process algebras in that we allow synchronizations of any number of partners at the same time. Constraint conditions for mobility are solved via unification. As an important outcome and a formal evidence of the expressive power of the approach. we present a correspondence result proving that SHR with Milner synchronization subsumes π-calculus. We define a translation where a transition in the π-Calculus is represented as a transition of the corresponding translated judgement (i.e. a rewriting step). Since π-calculus is equipped with an interleaving semantics and only with two partner synchronizations, we prove a complete correspondence between π-calculus and a restricted version of SHR systems. In the second part of the thesis we continue using HR grammars (without synchronization) for describing styles and we introduce a specific, type-based approach for describing style reconfigurations (called transformations). The notions of reconfiguration and mobility imply changes to the architecture structure by changing components and connections. These modifications that a system may suffer lead to the question of how we assure that changes are consistent with the style the system belongs to. By analogy, we can think of styles as types for the architecture instances and of HR derivations as typing proofs. Reconfigurations must preserve types: in type theory terminology, this property is called subject reduction. Our approach is to define transformations on typing proofs rather than on graphs: as long as cutting and pasting typing proofs still yields typing proofs, subject reduction is guaranteed. The formalization is done by representing both graphs and productions as terms of a typed λ-calculus,where a HR derivation step corresponds to application followed by β-reduction. Then, transformations are specified as (higher order) term rewritings: if all the term rewriting rules transform typing proofs into typing proofs, then all the possible rewritings satisfy subject reduction. The use of λ-calculus introduces the idea of higher order graph rewriting, allowing to parameter-ize the design process with component and connector features which could be specified later, still guaranteeing consistency. The main difference of the approach for reconfiguration using SHR with respect to the one using transformations, is that SHR is more dynamic in the sense that it applies to running open-ended systems without global control except for synchronization, whereas the approach with transformations may be useful for working at the level of blueprints, i.e. it rearranges the design steps of the system to produce a different but consistent system. Thus, the latter method can be applied to specify very general kinds of reconfigurations and mobility (as it is shown in the thesis examples), but it requires a global knowledge of system structure. The different topics introduced in the thesis are accompanied by specific examples to clarify the various constructions and to show their expressive power, and by a case study of a remote medical care system that is used all along the thesis.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Modelos de transformación de Grafos para estilos de arquitectura de software     =    Graph transformation models for software architecture styles
Autor : Hirsch, Dan Francisco
Director : Montanari, Ugo
Yankelevich, Daniel
Año : 2003
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Computación (DC)
Grado obtenido : Doctor en Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_3569_Hirsch
Idioma : Español
Area Temática : 
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34