Complexity in Computer Systems: Concept, Causes and Controls
John A McDermid, University of York, UK


Abstract: Complexity in computer systems arises from many sources - both within and outwith the system. Internal sources include the design of modern computer hardware, e.g. super-scalar processors, and distributed systems. The success of computer systems breeds complexity - through increasingly demanding requirements, and through ever greater dependence of society on the continued and trustworthy operation of the systems. Complexity is thus inescapable - unless we wish to reduce our dependence on computers, and to forgo the benefits that they bring us. This then raises the question of how we control, or at least cope with, ever-increasing complexity.

The paper will consider various facets of what is meant by complexity, and investigate the causes, or sources, of complexity in modern computer systems. It will focus on embedded systems, with stringent dependability requirements as these pose some of the most significant challenges. It will suggest a number of strategies, for coping with the different sources of complexity. This will including the notion of product families and the use of a risk as a unifying concept in management of complexity.


Overcoming Software Complexity by Constructing Abstraction Hierarchies - The Principles and Applications
Tosiyasu Laurence Kunii, Hosei University, Japan


Abstract: Ever increasing software complexity requires serious consideration to make software as a whole into sustainable social infrastructure. Abstraction hierarchies realized as incrementally modular hierarchies of software are shown to be the strong candidates to reduce software complexity. Some research results in computer graphics and database systems are shown to demonstrate the effectiveness of constructing abstraction hierarchies to this end. Homotopical and cellular models are as used as convenient intermediary levels of abstraction. Class inheritance hierarchies of object-oriented languages such as Python for rapid prototyping and Java for platform-free software development are considered for implementation.


Dynamically Detecting Relevant Program Invariants
David Notkin, University of Washinton, USA


Abstract: Explicitly stated program invariants can help programmers by characterizing certain aspects of program execution and identifying program properties that must be preserved when modifying code. In practice, these invariants are usually absent from code. An alternative to expecting programmers to annotate code with invariants is to automatically infer invariants from the program itself.

This talk describes dynamic techniques for discovering invariants from execution traces; the essential idea is to look for patterns in and relationships among variable values over a set of executions. An implementation has indicated that the approach is both effective -- successfully rediscovering formal specifications -- and useful -- discovering invariants that assisted a software evolution task.

The talk will also discuss, both in terms of invariant detection and also in more general terms, issues related to the potential synergy between static and dynamic analysis techniques.

This is joint work with Michael Ernst, Bill Griswold, Yoshio Kataoka, Jake Cockrell, and Adam Czeisler.


Principles and Mechanisms for Evolving Software Systems: A Report from a Project on Software Evolution Principles
Takuya Katayama, Japan Advanced Institute of Science and Technology, Japan


Abstract: Software evolution generally means that software can change its structure and functions to tolerate changes of its specification and its operating environment. Though it is widely recognized that software can evolve is one of the most important requirements of the software which can live long, current software is not made to allow evolution in a reasonable cost. Besides, it is shared by many software researchers and practitioners that very complex software could only be built by evolving it starting from its simple version.

The significant amount of work has been done so far on software evolution, however, it is still a difficult problem. This comes from the lack of understanding of principles for evolving software. A project has been formed to investigate the principles for building software with evolutionary mechanisms, which has been supported by Ministry of Education and involved major software researcher from Japanese universities. In the project, we have studied software evolution problem for three year from the following five standpoints: (1) the theories for evolutionary software, (2) fundamental mechanisms for software evolution, (3) methodologies for constructing evolutionary software, (4) systems for software evolution and (5) evolution of exiting software. In this paper we introduce what we have learned from the project.