Interview with Best Student Paper Winner Nikolas Antzoulatos
Slide presentation from Winner of Best paper Award
On 21 September 2015 FoCAS held its third Workshop on Fundamentals of Collective Adaptive Systems in conjunction with SCOPES (Spatial and COllective PErvasive Computing Systems) at Cambridge, Massachusettes, USA as part of SASO, the ninth IEEE international conference on Self-Adaptive and Self-Organising Systems which was hosted by MIT.
The workshop brought together three distinct, yet closely related areas of research expected to play a major role in producing the key technical results needed to develop large-scale adaptive distributed systems in future :
Spatial computing – systems of individual entities, typically situated in a physical environment, in which the “functional goals” of the system are generally defined in terms of the system’s spatial structure. Typically, such systems are developed following a self-organisation approach, making spatial patterns arise by emergence.
Pervasive computing – including the “Internet of Things” deal with current and emerging scenarios in which humans, sensors, mobile, and embedded devices engage in complex interactions in a shared environment.
Collective adaptive systems – systems of tightly entangled components, achieving an overall goal through widespread cooperation, typically relying on self-adaptation techniques and collective/social intelligence.
Nine workshop papers were presented and abstracts are included below. The audience numbered 55 participants including representatives from ASCENS, ALLOW ENSEMBLES, DIVERSIFY, ORGANIC COMPUTING, PRIME, QUANTICOL, SAPERE, SMART SOCIETY.
The best student paper was awarded to Nikolas Antzoulatos for the paper “Advanced Manufacturing as an Industrial Application for Collective Adaptive Systems “ co-authored with David Sanderson, Jack Chaplin, Dídac Busquets, Jeremy Pitt, Carl German, Alan Norbury, Emma Kelly and Svetan Ratchev.
The FoCAS Science Café was also incorporated into the workshop programme and presented a preview of the FoCAS Research Roadmap to an audience of approximately 45 persons to obtain feedback and comments from a range of views. Additional audience suggestions will be included in the final version of the FoCAS Research Agenda.
FoCAS also supported two PhD students attending the FAS doctoral forum at SASO:
Ognjen Scekic from the Distributed Systems Group, TU Wien, Austria,
Benedikt Eberhardinger from Augsburg University, Germany
More information at: http://focas.eu/saso-doctoral-mentoring-program/
Session 1 : Organisations
Rule Conflicts in Holonic Institutions
Jie Jiang, Jeremy Pitt and Ada Diaconescu
Large-scale self-organised systems, such as distributed community energy systems, have called for coordination approaches that are able to deal with issues such as heterogeneity, inter-dependence and dynamic variability. Holonic institutions have been proposed as an approach to converging the structuration required for multi-scale, multi-criteria optimisation in nested enterprises with the formal representation of institutionalised powers required for the minimal recognition of the rights to self-organise. A holonic institution is composed of interrelated sub-institutions, each of which may again be composed of interrelated sub-institutions, and may itself be nested in a supra-institution. With constituting components having possibly conflicting interests and values, a critical module of such holonic structures is conflict resolution, i.e., each institution must be able to detect and resolve conflicts (1) between its own rules and that of the supra-institution (external), and (2) between its own rules and that of the individual members (internal). For this purpose, this paper presents a detailed analysis of rule conflicts that may exist in holonic institutions. By means of Event Calculus, we provide a formalisation of such conflicts.
An Approach for Collective Adaptation in Socio-Technical Systems
Antonio Bucchiarone, Naranker Dulay, Anna Lavygina, Annapaola Marconi, Heorhi Raik and Alessandra Russo
Socio-technical systems are systems where autonomous humans and computational entities collectively collaborate with each other to satisfy their goals in a dynamic environment. To be resilient, such systems need to adapt to unexpected human behaviours and exogenous changes in the environment. In this paper, we describe a framework for the development of social-technical systems where adaptation is itself a collective process driven by the awareness of capabilities, goals, constraints and preferences of humans and entities, and knowledge of the environment. The adaptation is controlled by a multi-criteria decision making function combined with an analytic hierarchic process (AHP). We present the formal model of our approach, the collective adaptation algorithm, and its application to a smart mobility scenario.
Session 2 : Foundations
Toward Predicting Distributed Systems Dynamics
Amy Kumar, Jacob Beal, Soura Dasgupta, Raghu Mudumbai
Systems of “building block” algorithms can guarantee that self-organizing systems eventually converge to a predictable state, but what of their dynamical behavior in environments with ongoing changes? To begin to address this challenge, we analyze a commonly used distributed distance estimation algorithm from a stability theory perspective, identifying key properties of monotonicity and dynamical behavior envelope. This allows standard stability theory analysis to be applied to predict the behavior of feedback systems based on this algorithm, particularly their stability and perturbation robustness, which we demonstrate through both analysis and empirical validation in simulation.
Analyzing Resilience Properties of Different Topologies of Collective Adaptive Systems
Thomas Glazier, Javier Camara, Bradley Schmerl and David Garlan
Modern software systems are often compositions of entities that increasingly use self-adaptive capabilities to improve their behavior to achieve systematic quality goals. Self-adaptive managers for each component system attempt to provide locally optimal results, but if they cooperated and potentially coordinated their efforts it might be possible to obtain more globally optimal results. The emergent properties that result from such composition and cooperation of self-adaptive systems are not well understood, difficult to reason about, and present a key challenge in the evolution of modern software systems. For example, the effects of coordination patterns and protocols on emergent properties such as the resiliency of the collectives need to be understood when designing these systems. In this paper we propose that probabilistic model checking of stochastic multiplayer games (SMG) provides a promising approach to analyze, understand, and reason about emergent properties in collectives of adaptive systems (CAS). Probabilistic Model Checking of SMGs is a technique particularly suited to analyzing emergent properties in CAS, since SMG models capture: (i)~the uncertainty and variability intrinsic to the CAS and its execution environment in the form of probabilistic and nondeterministic choices, and (ii)~the competitive/cooperative aspects of the interplay among the constituent systems of the CAS. Analysis of SMGs allows us to reason about things like the worst case scenarios, which constitutes a new contribution to understanding emergent properties in CAS. We investigate the use of SMGs to show how they can be useful in analyzing the impact of communication topology for collections of fully cooperative systems defending against an external attack.
A logic language for run time assessment of spatial properties in self-organising system
Francesco Luca De Angelis and Giovanna Di Marzo Serugendo
The assessment of emergent global behaviors of self-organizing applications is an important task to accomplish before employing such systems in real scenarios, yet their intrinsic complexity make this activity still challenging. In this paper we present a logic language used to verify global properties of self-organizing systems at run-time. The logic language extends a chemical-based coordination model based on logic inference recently proposed. The logic formulae defined by using the language operators depict the intended global spatial properties arising from local interactions among components. Logic formulae are distributively evaluated by using an inference procedure which checks them against the current global state of the system, verifying whether the intended emergent global behavior actually appears in the system. As examples of spatial properties we consider color patterns: at first we show how to verify specified patterns of identified colors in sets of nodes directly connected, then we present a other formulae verifying the appearance of global patterns of colors without specifying the colors themselves. We conclude the examples with the computation of mathematical functions, like the verification of the existence of a maximum value in a specific node of the system.
Recoverable DTN Routing based on a Relay of Cyclic Message-Ferries on a MSQ Network
An interrelation between a topological design of network and efficient algorithm on it is important for communication or transportation systems. In this paper, we propose a design principle for a reliable routing in a store-carry-forward manner based on autonomously moving message-ferries on a special structure of fractal-like network, which consists of a self-similar tiling of equilateral triangles. As a collective adaptive mechanism, the routing is realized by a relay of cyclic message-ferries corresponded to a concatenation of the triangle faces and using some good properties of the network structure. It is recoverable for local accidents in the hierarchical network structure. Moreover, the design principle is theoretically supported with a calculation method for the optimal service rates of message-ferries derived from a tandem queue model for stochastic processes on a chain of edges in the network. These results obtained from a combination of complex network science and computer science will be useful for developing a resilient network system.
Session 3 : Applications
Advanced Manufacturing as an Industrial Application for Collective Adaptive Systems
David Sanderson, Nikolas Antzoulatos, Jack Chaplin, Dídac Busquets, Jeremy Pitt, Carl German, Alan Norbury, Emma Kelly and Svetan Ratchev
Driven by market trends towards highly-personalised products, the manufacturing industry is facing a variety of challenges that require systems to be adaptive, robust, resilient, and responsive. Collective adaptive systems have the potential to provide solutions to a wide variety of these problems. This paper has two main aims: to highlight shared problems between industry and the collective adaptive systems research area, where solutions would enable a transformative impact on the manufacturing domain; and to generate discussion around the application of collective adaptive systems approaches to facilitate further adoption of such techniques in industry. This paper therefore focusses on a real-world industrial manufacturing scenario that is to be used as a demonstration for the application of self-adaptation and self-organisation methodologies. As such, it will be used to investigate the application of collective adaptive systems to the manufacturing domain. A number of key issues derived from a requirements gathering process of research projects are discussed, along with a number of potential approaches, with the hopes of generating further discussion and feedback.
Exploring Spatio-temporal Properties of Bike-sharing Systems
Vincenzo Ciancia, Diego Latella, Mieke Massink and Rytis Paskauskas
In this paper we explore the combination of novel spatio-temporal model-checking techniques, and of a recently developed model-based approach to the study of bike sharing systems, in order to detect, visualize and investigate potential problems with bike sharing system configurations. Previous results in the same research line have shown the presence of surprisingly long cycling trips in the trip-duration statistics of real bike sharing systems of both small and large cities. These are likely to be related to the difficulties of users to find suitable parking places for their hired bikes. Even more surprising is the algebraic shape of the tail of the distribution of the trip duration that represent these long trips, showing independence of the size of the system. Model based analysis has shown that this phenomenon occurs also when only local behaviour of users is considered, thus excluding timings that can be related to maintenance operations and repositioning. The application of spatio-temporal model-checking may lead to the discovery of particular spatio-temporal patterns that may help to explain the phenomenon.
Computational Fields meet Augmented Reality: Perspectives and Challenge
Danilo Pianini, Angelo Croatti, Alessandro Ricci and Mirko Viroli
In recent times, two very different techniques emerged tailored to environments pervaded of devices.Aggregate programming, and especially computational fields-based programming is a promising abstraction for coordinating the activities of multiple situated devices. At the same time, augmented reality is emerging as new mean of interacting with both the software and the world.
We note that both computational fields and aggregate programming are tightly bound to the physical world, and that they both enrich it, with collective computation and augmented information respectively. This works presents an early analysis of possible future research directions that involve both techniques, discussing some possible ways of integrating them.
The workshop organisers were
Giacomo Cabri (Università di Modena e Reggio Emilia, Italy)
Nicola Capodieci (Università di Modena e Reggio Emilia, Italy)
Mirko Viroli (Università di Bologna, Italy)
Jacob Beal (Raytheon BBN Technologies, Cambridge, Massachusetts, USA)
Jane Hillston (University of Edinburgh, UK)