Registro:
Documento: | Tesis Doctoral |
Disciplina: | computacion |
Título: | Modelos de transformación de Grafos para estilos de arquitectura de software |
Título alternativo: | Graph transformation models for software architecture styles |
Autor: | Hirsch, Dan Francisco |
Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
Lugar de trabajo: | Departamento de Computación (DC)
|
Publicación en la Web: | 2017-03-01 |
Fecha de defensa: | 2003 |
Fecha en portada: | 2003 |
Grado Obtenido: | Doctorado |
Título Obtenido: | Doctor en Ciencias de la Computación |
Departamento Docente: | Departamento de Computación |
Director: | Montanari, Ugo; Yankelevich, Daniel |
Idioma: | Español |
Formato: | PDF |
Handle: |
http://hdl.handle.net/20.500.12110/tesis_n3569_Hirsch |
PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n3569_Hirsch.pdf |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n3569_Hirsch |
Ubicación: | COM 003569 |
Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Hirsch, Dan Francisco. (2003). Modelos de transformación de Grafos para estilos de arquitectura de software. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n3569_Hirsch |
Resumen:
La evolución de los sistemas de software y la creciente complejidad de sus procesos dedesarrollo han hecho necesario establecer pasos de diseño bien definidos que permitanreducir el gap entre requerimientos e implementaciones. En esta dirección, en añosrecientes, 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 nivelde un sistema complejo, con un nivel adecuado de abstracción que permite capturardel dominio del problema los componentes, a partir de los requerimientos, que serándiseñados detalladamente más adelante. Un Estilo de Arquitectura de Software es unaclase de arquitecturas que exhiben un patrón común. Si la reusabilidad y la clasificaciónde arquitecturas son objetivos principales para permitir que los diseñadores exploten eltrabajo previo, la identificación de una arquitectura de un sistema dentro de un estiloespecífico requiere lenguajes expresivos y bien fundados para representar estilos. Los requerimientos de los sistemas modernos imponen nuevas características a ladescripció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 lenguajede 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 estructurade los tipos de componentes y sus interacciones, los patrones de comunicación, y lasleyes que gobiernan la reconfiguración y/o la movilidad en la arquitectura. Siguiendoesta línea de investigación, es nuestro objetivo contribuir a la formalización de modelospara 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 desoftware basado en los sistemas de transformación de grafos. Una gramática de grafoscaracteriza una clase de grafos que comparten características estructurales y está compuestapor un conjunto de reglas de reescritura llamadas producciones. Inicialmente,los grafos representan las configuraciones estáticas de las arquitecturas y las gramáticasrepresentan los estilos. Luego, podremos incluir producciones que especifiquen las interaccionesen mntime entre componentes, la reconfiguración y la movilidad. Las arquitecturas de sistemas pueden ser controladas de manera centralizada a travésde un coordinador o administrador, o pueden ser sistemas denominados self organisingen los cuales la coordinación está distribuida localmente entre los componentes. Lossistemas que tenemos en mente son distribuidos, lieterogéneos y móviles, y por lo tantoelegimos una estrategia self organising. En particular, para describir estilos elegimosutilizar 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. Unhipereje es un elemento atómico con una etiqueta (de un alfabeto con rango) y contantos tentáculos como el rango de su etiqueta. Un conjunto de nodos y un conjuntode 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 componentesy 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 reescriturade grafos con condiciones de sincronización, obteniendo los sistemas SHR. Lasproducciones sincronizadas se especifican agregando condiciones en los nodos que permitencoordinar varias reescrituras, determinando la manera en que los componentesinteractúan y se reconfiguran. Las producciones para (la etiqueta de) un hipereje determinadorepresentan las posibles evoluciones para un determinado tipo de componentedel estilo. Las producciones de una gramática se agrupan en tres conjuntos: el primerconjunto contiene las producciones HR para la construcción de todas las posibles configuracionesiniciales del estilo. El segundo conjunto contiene las producciones SHR quemodelan la evolución de la comunicación para cada tipo de componente, y el tercer conjuntocontiene las producciones SHR para la reconfiguración de la estructura del estilo. Las producciones de la comunicación requieren sincronización pero no pueden cambiarla 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). Estaextensión permite aumentar substancialmente el poder expresivo del método para larepresentación de sistemas complejos móviles y reconfigurables, mantieniendo al mismotiempo la capacidad de describirlos de una manera descentralizada y distribuida. Representamos a los liipergrafos y los sistemas SHR en forma textual usando syntacticjudgements. 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 alestilo SOS para las álgebras de sincronización Hoare (CSP) y Milner (CCS, π-calculus). Sin embargo. en nuestra propuesta extendemos las álgebras de proceso permitiendo lasincronización simultánea de cualquier número de participantes. Las condiciones desincronización para movilidad se resuelven vía unificación. Como resultado importante y evidencia formal del poder expresivo del método, presentamosun resultado de correspondencia que prueba que SHR con sincronización de Milner subsume al π-calculus. Para esto, definimos una traducción donde una transiciónen π-calculus se representa como una transición del correspondiente syntactic judgementtraducido (es decir, un paso de reescritura). Puesto que π-calculus está equipado conuna semántica interleaving y sólo sincronizaciones entre pares de elementos, la prueba esuna 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 paradescribir las reconfiguraciones de estilos (llamadas transformaciones). Las nociones dereconfiguración y movilidad implican modificaciones a la estructura de la arquitecturacambiando componentes y conexiones. Estas modificaciones que un sistema puede sufrirconducen a la pregunta de cómo podemos asegurar que los cambios sean consistentes conel estilo al cual pertenece el sistema. Por analogía, podemos pensar en los estilos comotipos 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 tiposesta propiedad se llama subject reduction. Nuestro método consiste en definir transformacionessobre pruebas de tipo, en lugar que sobre grafos: mientras que cortar y pegarpruebas de tipo resulten nuevamente en pruebas de tipo, la propiedad de subjet reductionestá garantizada. La formalización se efectúa representando grafos y produccionescomo términos de un cálculo λ tipado, donde un paso de derivación HR corresponde aaplicación seguido por reducción β. Entonces, las transformaciones se especifican comoreescritura de términos (de alto orden): si todas las reglas de reescritura transformanpruebas de tipo en pruebas de tipo, entonces todas las posibles reescrituras satisfacensubject reduction. El uso de cálculo λ introduce la idea de reescritura de grafos dealto orden, permitiendo la parametrización del proceso de diseño con características decomponentes y conectores que podrían ser especificados más adelante, manteniendo lagarantía de consistencia. La principal diferencia del método para reconfiguración usando SHR con respecto alque utiliza transformaciones, es que SHR es más dinámico, ya que es aplicable a sistemasabiertos en ejecución sin control global, a excepción de la sincronización. Por el otrolado, el método con transformaciones puede ser útil para trabajar al nivel de diseñoestático, es decir, cambiar los pasos del diseño del sistema para producir un sistemadiverso pero consistente. De todas maneras, el último método puede ser aplicado paraespecificar clases muy generales de reconfiguraciones y movilidad (como se demuestraen los ejemplos de la tesis), pero requiere un conocimiento global de la estructura delsistema. Los diferentes temas introducidos en la tesis son acompañados por ejemplos específicosque 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 esutilizado a lo largo de toda la tesis.
Abstract:
The evolution of software systems and the increased complexity of their developing processeshave led to the necessity of establishing well defined design steps to close the gapbetween requirements and implementations. In this direction, in recent years a mainresearch area has concerned Software Architectures. Basically, a software architecture isa high-level description of a complex system, with an adequate level of abstraction thatenables capturing, from its requirements, the components of the problem domain to belater designed in more detail. A Software Architecture Style is a class of architecturesexhibiting a common pattern. If reusability and classification of architectures are maingoals to allow designers to exploit previous work, the identification of a system architecturewithin a specific style requires expressive and well founded languages to representstyles. The requirements of modern systems impose new characteristics to the descriptionof software architectures. These include distribution, concurrency, reconfiguration andmobility. Therefore, it is necessary to develop the style language and its formal semanticsaccordingly. Thus, the description of a software architecture style must include thestructure of component types and of their interactions, the communication patterns,and the laws governing reconfiguration and/or mobility changes in the architecture. Inthis line of research our goal is to contribute to the formalization of models for thedescription of software architectures and of software architecture styles. This thesis presents a formal framework based on graph transformation systems forthe description of software architecture styles. A graph grammar characterizes a class ofgraphs that share structural characteristics and it is composed of a set of rewriting rulescalled productions. At first, graphs represent the static configurations of architecturesand grammars represent styles. Later we will be able to include productions specifyingruntime interactions among components, reconfiguration and mobility. System architectures can be managed in a centralized manner by an explicit coordinatoror administrator, or can be self organising indicating that coordination managementis 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 amongcomponents. A hyperedge is an atomic item with a label (from a ranked alphabet) andwith as many tentacles as the rank of its label. A set of nodes together with a set ofhyperedges form a hypergraph if each hyperedge is connected, by its tentacles, to itsattachment nodes. Hyperedges correspond to components and their attachment nodesare their communication ports with other components. A HR production rewrites asingle hyperedge into an arbitrary hypergraph. Then, to model the coordination of thearchitecture components we combine graph rewriting with synchronizing conditions obtaining SHR systems. We specify synchronized productions by adding conditions onnodes which allow to coordinate several rewritings, thus determining how componentsinteract and are reconfigured. The productions for a given hyperedge (label) representthe possible evolutions for a given component type of the style. The productions of agrammar are grouped in three sets: the first set contains the HR productions for theconstruction of all possible initial configurations of the style. The second set containsthe SHR productions that model the communication evolution for each component typeand the third set contains the SHR productions for the reconfiguration of the style structure. The communication productions require synchronization but cannot change thetopological structure of the graph. With respect to previous literature, this thesis presents an extension of SHR with theaddition of name mobility (as in π-calculus). This extension allows us to substantiallyincrease the expressive power of the approach for representing complex mobile and reconfigurablesystems, 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 introductionof 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 processalgebras 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 synchronizationsubsumes π-calculus. We define a translation where a transition in the π-Calculus isrepresented as a transition of the corresponding translated judgement (i.e. a rewritingstep). Since π-calculus is equipped with an interleaving semantics and only with two partnersynchronizations, we prove a complete correspondence between π-calculus anda 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 describingstyle reconfigurations (called transformations). The notions of reconfigurationand mobility imply changes to the architecture structure by changing components andconnections. These modifications that a system may suffer lead to the question of howwe 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 astyping proofs. Reconfigurations must preserve types: in type theory terminology, thisproperty is called subject reduction. Our approach is to define transformations on typingproofs rather than on graphs: as long as cutting and pasting typing proofs still yieldstyping proofs, subject reduction is guaranteed. The formalization is done by representingboth graphs and productions as terms of a typed λ-calculus,where a HR derivation stepcorresponds to application followed by β-reduction. Then, transformations are specifiedas (higher order) term rewritings: if all the term rewriting rules transform typing proofsinto 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-izethe design process with component and connector features which could be specifiedlater, still guaranteeing consistency. The main difference of the approach for reconfiguration using SHR with respectto the one using transformations, is that SHR is more dynamic in the sense that itapplies to running open-ended systems without global control except for synchronization,whereas the approach with transformations may be useful for working at the level ofblueprints, i.e. it rearranges the design steps of the system to produce a different butconsistent system. Thus, the latter method can be applied to specify very general kindsof reconfigurations and mobility (as it is shown in the thesis examples), but it requiresa global knowledge of system structure. The different topics introduced in the thesis are accompanied by specific examplesto clarify the various constructions and to show their expressive power, and by a casestudy of a remote medical care system that is used all along the thesis.
Citación:
---------- APA ----------
Hirsch, Dan Francisco. (2003). Modelos de transformación de Grafos para estilos de arquitectura de software. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n3569_Hirsch
---------- CHICAGO ----------
Hirsch, Dan Francisco. "Modelos de transformación de Grafos para estilos de arquitectura de software". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2003.https://hdl.handle.net/20.500.12110/tesis_n3569_Hirsch
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n3569_Hirsch.pdf