Engineering Complex Computational Ecosystems

Self-organising pervasive ecosystems of devices are set to become a major vehicle for delivering infrastructure and end-user services. The inherent complexity of such systems poses new challenges to those who want to dominate it by applying the principles of engineering. The recent growth in number and distribution of devices with decent computational and communicational abilities, that suddenly accelerated with the massive diffusion of smartphones and tablets, is delivering a world with a much higher density of devices in space. Also, communication technologies seem to be focussing on short-range device-to-device (P2P) interactions, with technologies such as Bluetooth and Near-Field Communication gaining greater adoption. Locality and situatedness become key to providing the best possible experience to users, and the classic model of a centralised, enormously powerful server gathering and processing data becomes less and less efficient with device density. Accomplishing complex global tasks without a centralised controller responsible of aggregating data, however, is a challenging task. In particular, there is a local-to-global issue that makes the application of engineering principles challenging at least: designing device-local programs that, through interaction, guarantee a certain global service level. In this thesis, we first analyse the state of the art in coordination systems, then motivate the work by describing the main issues of pre-existing tools and practices and identifying the improvements that would benefit the design of such complex software ecosystems. The contribution can be divided in three main branches. First, we introduce a novel simulation toolchain for pervasive ecosystems, designed for allowing good expressiveness still retaining high performance. Second, we leverage existing coordination models and patterns in order to create new spatial structures. Third, we introduce a novel language, based on the existing ``Field Calculus'' and integrated with the aforementioned toolchain, designed to be usable for practical aggregate programming.

Efficient parallel proximity queries and an application to highly complex motion planning problems with many narrow passages

In vielen Bereichen der industriellen Fertigung, wie zum Beispiel in der Automobilindustrie, wer- den digitale Versuchsmodelle (sog. digital mock-ups) eingesetzt, um die Entwicklung komplexer Maschinen m ̈oglichst gut durch Computersysteme unterstu ̈tzen zu k ̈onnen. Hierbei spielen Be- wegungsplanungsalgorithmen eine wichtige Rolle, um zu gew ̈ahrleisten, dass diese digitalen Pro- totypen auch kollisionsfrei zusammengesetzt werden k ̈onnen. In den letzten Jahrzehnten haben sich hier sampling-basierte Verfahren besonders bew ̈ahrt. Diese erzeugen eine große Anzahl von zuf ̈alligen Lagen fu ̈r das ein-/auszubauende Objekt und verwenden einen Kollisionserken- nungsmechanismus, um die einzelnen Lagen auf Gu ̈ltigkeit zu u ̈berpru ̈fen. Daher spielt die Kollisionserkennung eine wesentliche Rolle beim Design effizienter Bewegungsplanungsalgorith- men. Eine Schwierigkeit fu ̈r diese Klasse von Planern stellen sogenannte “narrow passages” dar, schmale Passagen also, die immer dort auftreten, wo die Bewegungsfreiheit der zu planenden Objekte stark eingeschr ̈ankt ist. An solchen Stellen kann es schwierig sein, eine ausreichende Anzahl von kollisionsfreien Samples zu finden. Es ist dann m ̈oglicherweise n ̈otig, ausgeklu ̈geltere Techniken einzusetzen, um eine gute Performance der Algorithmen zu erreichen.rnDie vorliegende Arbeit gliedert sich in zwei Teile: Im ersten Teil untersuchen wir parallele Kollisionserkennungsalgorithmen. Da wir auf eine Anwendung bei sampling-basierten Bewe- gungsplanern abzielen, w ̈ahlen wir hier eine Problemstellung, bei der wir stets die selben zwei Objekte, aber in einer großen Anzahl von unterschiedlichen Lagen auf Kollision testen. Wir im- plementieren und vergleichen verschiedene Verfahren, die auf Hu ̈llk ̈operhierarchien (BVHs) und hierarchische Grids als Beschleunigungsstrukturen zuru ̈ckgreifen. Alle beschriebenen Verfahren wurden auf mehreren CPU-Kernen parallelisiert. Daru ̈ber hinaus vergleichen wir verschiedene CUDA Kernels zur Durchfu ̈hrung BVH-basierter Kollisionstests auf der GPU. Neben einer un- terschiedlichen Verteilung der Arbeit auf die parallelen GPU Threads untersuchen wir hier die Auswirkung verschiedener Speicherzugriffsmuster auf die Performance der resultierenden Algo- rithmen. Weiter stellen wir eine Reihe von approximativen Kollisionstests vor, die auf den beschriebenen Verfahren basieren. Wenn eine geringere Genauigkeit der Tests tolerierbar ist, kann so eine weitere Verbesserung der Performance erzielt werden.rnIm zweiten Teil der Arbeit beschreiben wir einen von uns entworfenen parallelen, sampling- basierten Bewegungsplaner zur Behandlung hochkomplexer Probleme mit mehreren “narrow passages”. Das Verfahren arbeitet in zwei Phasen. Die grundlegende Idee ist hierbei, in der er- sten Planungsphase konzeptionell kleinere Fehler zuzulassen, um die Planungseffizienz zu erh ̈ohen und den resultierenden Pfad dann in einer zweiten Phase zu reparieren. Der hierzu in Phase I eingesetzte Planer basiert auf sogenannten Expansive Space Trees. Zus ̈atzlich haben wir den Planer mit einer Freidru ̈ckoperation ausgestattet, die es erlaubt, kleinere Kollisionen aufzul ̈osen und so die Effizienz in Bereichen mit eingeschr ̈ankter Bewegungsfreiheit zu erh ̈ohen. Optional erlaubt unsere Implementierung den Einsatz von approximativen Kollisionstests. Dies setzt die Genauigkeit der ersten Planungsphase weiter herab, fu ̈hrt aber auch zu einer weiteren Perfor- mancesteigerung. Die aus Phase I resultierenden Bewegungspfade sind dann unter Umst ̈anden nicht komplett kollisionsfrei. Um diese Pfade zu reparieren, haben wir einen neuartigen Pla- nungsalgorithmus entworfen, der lokal beschr ̈ankt auf eine kleine Umgebung um den bestehenden Pfad einen neuen, kollisionsfreien Bewegungspfad plant.rnWir haben den beschriebenen Algorithmus mit einer Klasse von neuen, schwierigen Metall- Puzzlen getestet, die zum Teil mehrere “narrow passages” aufweisen. Unseres Wissens nach ist eine Sammlung vergleichbar komplexer Benchmarks nicht ̈offentlich zug ̈anglich und wir fan- den auch keine Beschreibung von vergleichbar komplexen Benchmarks in der Motion-Planning Literatur.

A Critical Review of Opinion Polls relating to Iranian Voting Intentions: Problems of Research Methodology as applied to Complex Societies

After the 10th Iranian Presidential election on June 12, 2009, several public opinion polls taken in Iran attracted the attention of policy-makers and journalists around the world because of the political crisis that followed. In this paper I first review critically the polls conducted by the WPO (WorldPublicOpinion.org), PIPA (Program on International Policy Attitudes) at the University of Maryland. I also review an essay by Steven Kull, which is based on the aforementioned poll results and which in my opinion leads to false conclusions concerning Iran’s political prospects. I also discuss “An Analysis of Multiple Polls of the Iranian Public,” published by WPO-PIPA on February 3 2010. The present paper arrives at the overall conclusion that it is impossible to obtain an accurate image of political opinions in societies as complicated as that of Iran by concentrating on only one technique of research and analysis, especially when the political and social situation in the society concerned is in a state of constant flux.

On Software Engineering Repositories and Their Open Problems

In the last decade, a large number of software repositories have been created for different purposes. In this paper we present a survey of the publicly available repositories and classify the most common ones as well as discussing the problems faced by researchers when applying machine learning or statistical techniques to them.

Configuration management and product lines to enhance the replication process in software engineering

This research is concerned with the experimental software engineering area, specifically experiment replication. Replication has traditionally been viewed as a complex task in software engineering. This is possibly due to the present immaturity of the experimental paradigm applied to software development. Researchers usually use replication packages to replicate an experiment. However, replication packages are not the solution to all the information management problems that crop up when successive replications of an experiment accumulate. This research borrows ideas from the software configuration management and software product line paradigms to support the replication process. We believe that configuration management can help to manage and administer information from one replication to another: hypotheses, designs, data analysis, etc. The software product line paradigm can help to organize and manage any changes introduced into the experiment by each replication. We expect the union of the two paradigms in replication to improve the planning, design and execution of further replications and their alignment with existing replications. Additionally, this research work will contribute a web support environment for archiving information related to different experiment replications. Additionally, it will provide flexible enough information management support for running replications with different numbers and types of changes. Finally, it will afford massive storage of data from different replications. Experimenters working collaboratively on the same experiment must all have access to the different experiments.

Consolidation problems

The analysis of deformation in soils is of paramount importance in geotechnical engineering. For a long time the complex behaviour of natural deposits defied the ingenuity of engineers. The time has come that, with the aid of computers, numerical methods will allow the solution of every problem if the material law can be specified with a certain accuracy. Boundary Techniques (B.E.) have recently exploded in a splendid flowering of methods and applications that compare advantegeously with other well-established procedures like the finite element method (F.E.). Its application to soil mechanics problems (Brebbia 1981) has started and will grow in the future. This paper tries to present a simple formulation to a classical problem. In fact, there is already a large amount of application of B.E. to diffusion problems (Rizzo et al, Shaw, Chang et al, Combescure et al, Wrobel et al, Roures et al, Onishi et al) and very recently the first specific application to consolidation problems has been published by Bnishi et al. Here we develop an alternative formulation to that presented in the last reference. Fundamentally the idea is to introduce a finite difference discretization in the time domain in order to use the fundamental solution of a Helmholtz type equation governing the neutral pressure distribution. Although this procedure seems to have been unappreciated in the previous technical literature it is nevertheless effective and straightforward to implement. Indeed for the special problem in study it is perfectly suited, because a step by step interaction between the elastic and flow problems is needed. It allows also the introduction of non-linear elastic properties and time dependent conditions very easily as will be shown and compares well with performances of other approaches.

Improved boundary elements in torsion problems

Since the epoch-making "memoir" of Saint-Venant in 1855 the torsion of prismatic and cilindrical bars has reduced to a mathematical problem: the calculation of an analytical function satisfying prescribed boundary values. For over one century, till the first applications of the F.E.M. to the problem, the only possibility of study in irregularly shaped domains was the beatiful, but limitated, theory of complex function analysis, several functional approaches and the finite difference method. Nevertheless in 1963 Jaswon published an interestingpaper which was nearly lost between the splendid F. E.M. boom. The method was extended by Rizzo to more complicated problems and definitively incorporated to the scientific community background through several lecture-notes of Cruse recently published, but widely circulated during past years. The work of several researches has shown the tremendous possibilities of the method which is today a recognized alternative to the well established F .E. procedure. In fact, the first comprehensive attempt to cover the method, has been recently published in textbook form. This paper is a contribution to the implementation of a difficulty which arises if the isoparametric elements concept is applicated to plane potential problems with sharp corners in the boundary domain. In previous works, these problems was avoided using two principal approximations: equating the fluxes round the corner or establishing a binode element (in fact, truncating the corner). The first approximation distortes heavily the solution in thecorner neighbourhood, and a great amount of element is neccesary to reduce its influence. The second is better suited but the price payed is increasing the size of the system of equations to be solved. In this paper an alternative formulation, consistent with the shape function chosen in the isoparametric representation, is presented. For ease of comprehension the formulation has been limited to the linear element. Nevertheless its extension to more refined elements is straight forward. Also a direct procedure for the assembling of the equations is presented in an attempt to reduce the in-core computer requirements.

Membrane Systems Working with the PFactor: Best Strategy to Solve Complex Problems.

A membrane system is a massive parallel system, which is inspired by the living cells when processing information. As a part of unconventional computing, membrane systems are proven to be effective in solving complex problems. A new factor is introduced. This factor can decide whether a technique is worthwhile being used or not. The use of this factor provides the best chances for selecting the strategy for the rules application phase. Referring to the “best” is in reference to the one that reduces execution time within the membrane system. A pre-analysis of the membrane system determines the P-factor, which in return advises the optimal strategy to use. In particular, this paper compares the use of two strategies based on the P-factor and provides results upon the application of them. The paper concludes that the P-factor is an effective indicator for choosing the right strategy to implement the rules application phase in membrane systems.

Stoichiometry in Context: Inquiry-Guided Problems of Chemistry for Encouraging Critical Thinking in Engineering Students

This paper focuses on examples of educational tools concerning the learning of chemistry for engineering students through different daily life cases. These tools were developed during the past few years for enhancing the active role of students. They refer to cases about mineral water, medicaments, dentifrices and informative panels about solar power, where an adequate quantitative treatment through stoichiometry calculations allows the interpretation of data and values announced by manufacturers. These cases were developed in the context of an inquiry-guided instruction model. By bringing tangible chemistry examples into the classroom we provide an opportunity for engineering students to apply this science to familiar products in hopes that they will appreciate chemistry more, will be motivated to study concepts in greater detail, and will connect the relevance of chemistry to everyday life.

Emotions and the Engineering of Adaptiveness in Complex Systems

A major challenge in the engineering of complex and critical systems is the management of change, both in the system and in its operational environment. Due to the growing of complexity in systems, new approaches on autonomy must be able to detect critical changes and avoid their progress towards undesirable states. We are searching for methods to build systems that can tune the adaptability protocols. New mechanisms that use system-wellness requirements to reduce the influence of the outer domain and transfer the control of uncertainly to the inner one. Under the view of cognitive systems, biological emotions suggests a strategy to configure value-based systems to use semantic self-representations of the state. A method inspired by emotion theories to causally connect to the inner domain of the system and its objectives of wellness, focusing on dynamically adapting the system to avoid the progress of critical states. This method shall endow the system with a transversal mechanism to monitor its inner processes, detecting critical states and managing its adaptivity in order to maintain the wellness goals. The paper describes the current vision produced by this work-in-progress.

Enhancing regression models for complex systems using evolutionary techniques for feature engineering

This work proposes an automatic methodology for modeling complex systems. Our methodology is based on the combination of Grammatical Evolution and classical regression to obtain an optimal set of features that take part of a linear and convex model. This technique provides both Feature Engineering and Symbolic Regression in order to infer accurate models with no effort or designer's expertise requirements. As advanced Cloud services are becoming mainstream, the contribution of data centers in the overall power consumption of modern cities is growing dramatically. These facilities consume from 10 to 100 times more power per square foot than typical office buildings. Modeling the power consumption for these infrastructures is crucial to anticipate the effects of aggressive optimization policies, but accurate and fast power modeling is a complex challenge for high-end servers not yet satisfied by analytical approaches. For this case study, our methodology minimizes error in power prediction. This work has been tested using real Cloud applications resulting on an average error in power estimation of 3.98%. Our work improves the possibilities of deriving Cloud energy efficient policies in Cloud data centers being applicable to other computing environments with similar characteristics.

Mathematical foundations for efficient structural controllability and observability analysis of complex systems

The relationship between structural controllability and observability of complex systems is studied. Algebraic and graph theoretic tools are combined to prove the extent of some controller/observer duality results. Two types of control design problems are addressed and some fundamental theoretical results are provided. In addition new algorithms are presented to compute optimal solutions for monitoring large scale real networks.