ACCORDS

Este relatório em português

CNPq/NSF - ACCORDS Project - Report No. 2

1.1 Identification

Project Acronym: ACCORDS

Project title: Automatic Configuration and Monitoring of Component-Based Distributed Systems

Project Homepage: http://www.ime.usp.br/~song/accords

Main area: Computer Science

Coordinator in Brazil: Siang Wun Song

Institution: Universidade de São Paulo

Period of project: July 1, 1999 to June 30, 2002

Period of report: July 1, 2000 to August 30, 2001

1.2. Content

Project summary

The motivation for this research came from the fact that software flexibility is a major issue in the development of high performance and real-time applications, reliable systems, distributed systems, and in exploratory computing. Software systems have to deal with an increasing rate of change in technology and user requirements. Moreover, it is imperative that the scientific community and the industry develop techniques to support seamless integration of highly heterogeneous environments. Component technology has appeared as a solution for these problems. However, there is still little support for managing the interactions between the components. Existing component architectures also lack a good understanding of the nature and magnitude of the interactions between components and a notion of individual performance of components in a component-based system. This research project seeks to modify the way computer systems support component-based software to accommodate dynamic changes in rapidly evolving environments. By maintaining an explicit representation of the interactions between system and application components, the infrastructure can recognize the need for reconfiguration. In addition, it can know how to carry out this reconfiguration without compromising system stability, performance, and reliability.

Keywords

Meta-object protocol, distributed programming, checkpointing, consistent global states, monitoring and reconfiguration, aspect-oriented programming, dynamic programming, dynamic adaptation policies, mobile computing, adaptive software.

1.3. Introduction

The objective of this project is to find new forms to support software development based on components, considering that future computing environments will be distributed and highly dynamic.

The expected results are:

• A framework to represent explicitly and manage the interactions among system and application components.

• An infrastructure for recognizing the need for reconfiguration and carrying out the reconfiguration steps without compromising performance and stability.

• Evaluate the impact of the use of ``reflective ORBS'' in the tasks of monitoring and reconfiguration.

• Support for intra and inter-component dynamic configuration and evaluation of its use in the task of domain decomposition for parallel and distributed systems.

• An object-oriented framework to structure adaptive and reliable systems.

1.4. Main results

Publication of the participants

As shown by the complete list that follows, a large number of journal and conference papers has been produced.

Participation in conferences

Project members participated in international and national conferences. A complete list is shown in this report.

Research results

In the field of Adaptivity, our research led to the design of a middleware architecture to support the development of adaptive distributed applications. This architecture was described in a technical report produced by Francisco Jose da Silva e Silva, doctoral student, during his visit to our American partner: "Modeling Dynamic Adaptation of Distributed Systems" Francisco José da Silva e Silva, Markus Endler, Fábio Kon, Roy H. Campbell, M. Dennis Mikunas. University of Illinois at Urbana-Champaign. Report UIUCDCS-R-2000-2196, December,2000. More recently, Francisco described the applications of this architecture to Mobile Computing in a paper published at the Third Brazilian Workshop on Wireless Communication, Recife, August 2001. The architecture is already partially implemented in a Java/CORBA environment and it will be completed around July/2002.

With regard to inter-component dependence management, the research is advanced. Our American partners developed an object-oriented framework to manage dependencies in component systems and carried out experiments with different implementations of this framework for CORBA, Java, and C++. These results were enhanced by the work of the Brazilian researchers, who extended the framework to manage alternatives for each component. This extension was implemented using Java RMI technology and it was applied to a complex distributed application: a Distributed Traffic Information System for Mobile Computing developed at the IME-USP. This work is described in the paper "Adaptive Directory Services for Highly Dynamic Environments" to appear at the ACM/IFIP Middleware'2001 Conference as a Work in Progress paper in November. Two new masters students (Ricardo Koji Ushizaki e Marcelo Vinagreiro) are currently working on extension of the Traffic Information System to interface with distributed databases and to increase the facilities for dynamic reconfiguration.

Knowledge acquired:

Through interaction between researchers, it was possible to disseminate knowledge among project participants, with respect to the following problems:

• experience in the use of reflection to deal with exceptions;
• inter-relationship between dynamic adaptation and system reliability;
• techniques for configuration with message interposition through reflection;
• configuration on the middleware level;
• gains from dynamic configuration for fault tolerance.

Applicability

The results we obtained indicate a strong applicability of the framework for the development of distributed systems where faulty components can be dynamically substituted by alternatives that offer the same service.

Generation of products and processes

Library and prototypes that explore dynamic configuration are under development, in advanced stage. Source code is available at the web at the participants' pages.

Human resources formation

One participant on the American side, Fabio Kon, finished his Ph.D. program at the University of Illinois. He was then hired for a faculty position at the Department of Computer Science, Institute of Mathematics and Statistics, USP.

Interaction with the American partners

During the second year of the project, the Ph.D. student (advisor Professor Markus Endler) Francisco José da Silva e Silva visited the University of Illinois partner at Urbana-Chamgagne for one month, during August 2000. The activities included the presentation to the American partners of the modeling working being carried out in Brazil. He also participated in courses and seminars in areas related to the project.

Professor Luiz Eduardo Buzato visited the Systems Reseach Group of the University of Illinois during April 2001. He presented and discussed the recent results on efficient protocols for the computation of progressive visions and the application of these protocols to the 2K system of the University of Illinois and the Guraná/MOLDS system of the Institute of Computing of Unicamp.

Interaction in Brazil (inter and intra-institutional)

The interaction in Brazil happened in an informal way with many visits between the two Brazilian Universities. Besides a number of seminars, a Workshop ACCORDS was held on January 5, 2000, in the Institute of Computing of UNICAMP. Participated in this meeting members from USP and UNICAMP and one member from U. Illinois. The workshop program can be found in http://choices.cs.uiuc.edu/2k/Events/ACCORDSWorkshop2000.html and include several talks and progress reports followed by discussion.

1.5. Team

• Siang Wun Song (coordinator)
• Cecília Mary Fischer Rubira
• Dilma Menezes da Silva
• Fabio Kon
• Hernán Astudillo
• Luiz Eduardo Buzato
• Markus Endler

Graduate students:

• Alessandro FabrÌcio Garcia
• Alexandre Oliva
• Delano Medeiros Beder
• Francisco J. da Silva e Silva
• Gerson Mizuta Weiss
• Gisele Rodrigues Ferreira
• Gustavo M. D. Vieira
• Islene Calciolari Garcia
• Jorge Euler Vieira
• Marco Aurélio de Moura
• Paulo Astério de Castro Guerra
• Uirá Kulesza

Participation in conferences

• Name of Participant: Siang Wun Song
  Conference: Proceedings 13th International Conference on Parallel and Distributed Computing and Systems. Anaheim, California, USA, August 21 - 24, 2001.
• Name of Participant: Markus Endler
  Conference: 3rd. IEEE International Conference in Mobile and Wireless Communication Networks (MWCN2001), Recife, Agosto 2001.
• Name of Participant: Markus Endler
  Conference: 3o. Workshop de Comunicacao sem Fio e Computacao Movel (WCSF2001), Recife, Agosto 2001.
• Name of Participant: Fabio Kon
  Conference: XXI Congresso da Sociedade Brasileira da Computação, VIII Simpósio de Computação Musical, Fortaleza, julho de 2001.
• Name of Participant: Siang Wun Song
  Conference: XXI Congresso da Sociedade Brasileira da Computação, Jornada de Atualização em Informática, Fortaleza, julho de 2001.
• Name of Participant: Siang Wun Song
  Conference: The 2001 International Conference on Computational Science, San Francisco, May 28-30, 2001.
• Name of Participant: Fabio Kon
  Conference: ACM OOPSLA Conference, Minneapolis, EUA, outubro de 2000.
• Nome da Participante: Fabio Kon
  Conference: 9th IEEE International Symposium on High Performance Distributed Computing, Pittsburgh, EUA, agosto de 2000.
• Name of Participant: Siang Wun Song
  Conference: IFIP World Computer Congress 2000 - International Conference on Software: Theory and Practice. Beijing, China, August 21 - 25, 2000.

Publications by team members

Second year

• Dehne, F., Ferreira, A., Cáceres, E., Song, S. W., and Roncato, A. Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP. Algorithmica. To appear.
• A. Garcia, C. M. F. Rubira, A. Romanovsky & J. Xu. A Comparative Study of Exception Handling Mechanisms for Building Dependable Object-Oriented Software. Journal of Systems and Software, Elsevier, North-Holland, April 2002, ISSN 0164-1212. To appear.
• A. Garcia, D. Beder & C. M. F. Rubira. A Unified Meta-Level Software Architecture for Sequential and Concurrent Exception Handling. Computer Journal, Vol. 44, Issue 4, Oxford University Press, September 2001, ISSN 0010-4620. To appear.
• A. Garcia & C. M. F. Rubira. An Architectural-based Reflective Approach to Incorporating Exception Handling into Dependable Software. chapter 4, p. 189-206, In the book Advances in Exception Handling Techniques. 289 p. Editors: A. Romanovsky, C. Dony, J. L. Knudsen, A. Tripathi. Springer-Verlag, LNCS-2022, April 2001. (ISSN 0302-9743. ISBN 3-540-41952-7).
• Song, S. W. Editorial: Design of Efficient and Scalable Parallel Algorithms. Parallel and Distributed Computing Practices, Vol. 3, 2001. To appear.
• Song, S. W. Parallel Graph Algorithms for Coarse-Grained Multicomputers. Models for Parallel and Distributed Computation: Theory, Algorithmic Techniques and Applications. Applied Optimization Book Series. Kluwer. To appear.
• Dilma Menezes da Silva and Fabio Kon, Adaptive Directory Services for Highly Dynamic Environments. ACM/IFIP Middleware'2001 WIP Heidelberg, Germany, November, 2001.
• G. R. M. Ferreira, C. M. F. Rubira & R. de Lemos. Explicit Representation of Exception Handling in the Development of Dependable Component-Based Systems. In Proceedings of the 6th IEEE International Symposium on High Assurance Systems Engineering (HASE'01), October 24-26 , 2001, Boca Raton, Florida, USA, IEEE Computer Society Press.
• Mongelli, H. and Song, S. W. Efficient Two-Dimensional Parallel Pattern Matching with Scaling. Proceedings 13th International Conference on Parallel and Distributed Computing and Systems. August 21 - 24, 2001, pp. 360-364.
• Rocha, R. C. A. and Endler, M. MobiCS: An environment for prototyping and simulating distributed protocols for mobile networks , Proc. 3rd. IEEE International Conference in Mobile and Wireless Communication Networks (MWCN2001), Recife, 44-51, Brazil, August 2001.
• Nagamuta, V. e Endler. M. Simulando um Protocolo para Notificação Confiável baseado em Proxies Móveis. Proc. of the 3rd. Brazilian Workshop on Wireless Communication and Mobile Computing (WCSF2001), 18-26, Recife, Agosto 2001.
• Silva, F. S. e Endler, M. Desenvolvendo Software Adaptável para Computacao Movel. Proc. of the 3rd. Brazilian Workshop on Wireless Communication and Mobile Computing (WCSF2001), 93-101, Recife, Agosto 2001.
• Ribeiro, M. F. e Endler, M. Um protocolo indireto para Multicast Atomico em Computacao Móvel. Proc. of the 3rd. Brazilian Workshop on Wireless Communication and Mobile Computing (WCSF2001), 84-91, Recife, Agosto 2001.
• Manuel Román and Fabio Kon and Roy Campbell. Reflective Middleware: From Your Desk to Your Hand. IEEE Distributed Systems Online, Vol. 2, No. 5, July, 2001.
• Cáceres, E. N. and Mongelli, H. and Song, S.W. Algoritmos Paralelos usando CGM/PVM: Uma Introdução, texto preparado para o XXI Congresso da Sociedade Brasileira da Computação, Jornada de Atualização em Informática, Fortaleza, julho de 2001, pp. 219-278.
• Mongelli, H. and Song, S.W. Parallel String Matching with Scaling. Proc. 2001 International Conference on Parallel and Distributed Processing Techniques and Applications, Vol. 2, June 25-28, 2001, pp. 605-609.
• Cáceres, E.N. and Song, S. W. and Szwarcfiter, J. L. A Parallel Unrestricted Depth Search Algorithm. Proc. 2001 International Conference on Parallel and Distributed Processing Techniques and Applications, Vol. 1, June 25-28, 2001, pp. 521-526.
• D. M. Beder, B. Randell, A. Romanovsky, & C. M. F. Rubira. On Applying Coordinated Atomic Actions and Dependable Software Architectures for Developing Complex Systems. In Proceedings of the 4th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'2001), Magdeburg, Germany, May 2-4, 2001, pp. 103-112, IEEE Computer Society Press.
• Caceres, E.N., Song, S. W. and Szwarcfiter, J. L. A Coarse-Grained Parallel Algorithm for Maximal Cliques in Circle Graphs. The 2001 International Conference on Computational Science. Lecture Notes in Computer Science, Vol. 2074, V. Alexandrov, J. Dongarra, K. Tan (eds), Springer-Verlag. San Francisco, May 28-30, 2001, pp. 638-647.
• Nagamuta, V. e Endler, M. Coordinating Mobile Agents through the Broadcast Channel, Anais do Simposio Brasileiro de Redes de Computadores (SBRC-2001), CD-ROM, Florianopolis, May 2001.
• Islene C. Garcia, Gustavo M. D. Vieira e Luiz E. Buzato. RDT-Partner: An Efficient Checkpointing Protocol that Enforces Rollback-Dependency Trackability, Anais do Simposio Brasileiro de Redes de Computadores (SBRC-2001), CD-ROM, Florianopolis, May 2001.
• Islene Calciolari Garcia e Luiz Eduardo Buzato. On the Minimal Characterization of Rollback-Dependency Trackability Property, Proceedings of the 21th IEEE Int. Conf. on Distributed Computing Systems, Phoenix, Arizona, EUA, April, 2001.

• Gustavo Maciel Dias Veira, Islene Calciolari Garcia e Luiz Eduardo Buzato. Systematic Analysis of Index-Based Checkpointing Algorithms using Simulation, IX Simpósio de Computação Tolerante a Falhas, Florianópolis, Santa Catarina, March 2001.

• Mongelli, H. and Song, S. W. Parallel Pattern Matching with Scaling. Parallel Processing Letters. Vol. 11, pp. 125-138, March 2001.
• Fabio Kon, Tomonori Yamane, Christopher Hess, Roy Campbell and M. Dennis Mickunas. Dynamic Resource Management and Automatic Configuration of Distributed Component Systems. Proceedings of the 6th USENIX Conference on Object-Oriented Technologies and Systems (COOTS'2001), San Antonio, Texas, February, 2001.
• Fabio Kon, Roy H. Campbell and Klara Nahrstedt. Using Dynamic Configuration to Manage a Scalable Multimedia Distribution System. Computer Communications Journal (Special Issue on QoS-Sensitive Distributed Systems and Applications), Vol. 24, Elsevier Science Publisher, January, 2001, pp. 105-123.
• Francisco José da Silva e Silva, Markus Endler, Fabio Kon, Roy H. Campbell, and M. Dennis Mikunas. Modeling Dynamic Adaptation of Distributed Systems. University of Illinois at Urbana-Champaign. Report UIUCDCS-R-2000-2196, December, 2000.
• A. Garcia, D. M. Beder & C. M. F. Rubira. An Exception Handling Software Architecture for Developing Fault-Tolerant Software. In Proceedings of the 5th IEEE International Symposium on High Assurance Systems Engineering (HASE'00), November 15-17, 2000, Albuquerque, New Mexico, USA, pp. 311-320, IEEE Computer Society Press.
• Fabio Kon, Jalal Al-Muhtadi, Roy H. Campbell and M. Dennis Mickunas. My Dream of Jini. OOPSLA'2000 Workshop on the Jini Pattern Language, Minneapolis, October, 2000.
• Fabio Kon, Christopher Hess, Manuel Roman, Roy H. Campbell and M. Dennis Mickunas. A Flexible, Interoperable Framework for Active Spaces. OOPSLA'2000 Workshop on Pervasive Computing, Minneapolis, October, 2000.
• Dilma M. Silva, Fabio Kon and Roy Campbell. Dynamic Configuration of a Directory Service Using the ComponentConfigurator Framework. Proceedings of the Project SIDAM Workshop, Sao Paulo, September, 2000.
• Okuda, K. and Song, S. W. Revisiting Hamiltonian Decomposition of the Hypercube. SBCCI2000 - XIII Symposium on Integrated Circuits and System Design. Manaus, Brazil, September 18-24, 2000, pp. 55-60.
• Saukas, E. L. G. and Song, S. W. Parallel Programming Techniques for Distributed Memory Computers. IFIP World Computer Congress 2000 - International Conference on Software: Theory and Practice. Beijing, China, August 21 - 25, 2000, pp. 760-763.
• Islene Calciolari Garcia e Luiz Eduardo Buzato. Using Common Knowledge to Improve Fixed-Dependency-After-Send, Workshop de Testes e Tolerância a Falhas, Curitiba, July, 2000.

• Ferreira, A., Goldman, A. and Song, S. W. Broadcasting in bus interconnected networks. Journal of Interconnection Networks, Vol. 1, No. 2, June 2000, pp. 73-94.
• Mongelli, H. and Song, S. W. Parallel Range Minima on Coarse Grained Multicomputers. International Journal of Foundations of Computer Science. Vol. 10, No. 4, December 1999, pp. 375 - 389.

1.6. Conclusion

Analysis of results with respect to the initial proposal

The partial results indicate that the incorporation of mechanisms for dynamic adaptation increases system flexibility significantly. The investigation carried out to this moment presents reasonable cost (performance degradation), compatible to the technologies of popular distributed objects systems. The initial proposal emphasizes the use of computational reflection in deriving more generic mechanisms for automatic configuration. Our work with computational reflection focused on fault-tolerance and on the construction of dynamically configurable middleware systems. The work carried out by the doctoral student Francisco Silva and his advisors, Markus Endler and Fabio Kon, will demonstrate an integrated architecture for adaptive systems based on reflection principles.

Relevant contribution

The development of dynamically configurable components is essential to the construction of systems that execute in environments as Internet of large corporative networks, with the expected performance and reliability.

Difficulties encountered

The prior experience of all the research team with complementary aspects of the development of distributed and adaptable systems made the work very productive.

An inherent problem of such a project was the difficulty in integrating the software artifacts developed by various programmers in different research groups. Unfortunately, we were not able to standardize the environments and technologies employed. It is our short-term objective to concentrate on the integration of our results and implementations.

1.7. Bibliographical references

• Brent Agnew, Christine Hofmeister, and James Purtilo. ``Planning for change: A reconfiguration language for distributed systems'' Proc. of the Second International Workshop in Configurable Distributed Systems, pages 15--22. IEEE Computer Society Press, May 1994.
• L.E. Buzato, C.M.F. Rubira, and M.L.B. Lisboa. A reflective object-oriented architecture for developing fault-tolerant software. Journal of Brazilian Computer Society, 4(2):39--48, november 1997.
• Roy~Campbell et al. ``2K: A component-based network-centric operating system for the next millennium'' http://choices.cs.uiuc.edu/2k/, 1998.
• Michael J. Fischer, Nancy D. Griffeth, and Nancy A. Lynch. `` Global States of a Distributed System'' IEEE Transactions on Software Engineering, SE-8(3):198--202, may 1982.
• P. G. S. Florissi and Y. Yemini. `` Management of application quality of service'' Proc. of the 5th IEEE International Workshop on Distributed Systems: Operations and Management, 1994.
• M. Jones. `` Interposition agents: Transparently interposing user code at the system interface'' Operating System Review, 27(5):69--79, December 1993. Proc. 14th ACM Symp. on Operating Systems Principles.
• L.L.Ferreira and C.M.F.Rubira. `` Reflective design patterns to implement fault tolerance'' Proc. OOPSLA'98 Workshop on Reflective programming in C++ and Java, pages 39--48, Vancouver,Canada, October 1998. IEEE Computer Society.
• N.H. Minsky. ``Governing Distributed Systems: from Protocols to Laws'', In B.D. Shriver, editor, Proc. of the 24th Hawaii International Conference on System Sciences, pages 418--427. IEEE Computer Society Press, January 1991.
• Alexandre Oliva and Luiz Eduardo Buzato. `` Composition of meta-objects in Guaran·'' Workshop on Reflective Programming in C++ and Java, OOPSLA'98, Vancouver, Canada, October 1998.
• Beth Schroeder, "On-line monitoring: A tutorial", IEEE Computer, Vol. 29, No. 6, pg 72-78, 1995.
• Fabio Ko n and Roy H. Campbell, ``Dependence Management in Component-Based Distributed Systems'', IEEE Concurrency, Vol.8, No. 1, pg 26-36