Cyber space is a distributed information processing system that enables message-based interactions among CSs by means of direct and indirect cyber channels. For instance, the IP-based Internet is a prominent example of a planet-scale cyber space where in principle any two systems with a unique IP address can establish cyber channels and exchange Itoms. The concept of (physical) proximity and neighborhood of CSs does not necessarily play a significant role in cyber space. The physical distance between two CSs exchanging messages via cyber space might only affect the delay of the message, but has no other impact on the communication (e.g., does not change message contents in the absence of faults).

A direct cyber channel conveys messages from one sending CS to one or more receiving CS without any modifications.

An indirect cyber channel is established over the state of a shared memory which is located somewhere in cyber space. The sending CSs modify the shared memory by means of state messages. The shared memory is also possibly affected by cyber dynamics a form of environmental dynamics. Cyber dynamics are autonomous processes inherent within the cyber space and/or cyber interactions of other not explicitly modeled systems. Finally, receiving CSs obtain the (partial) state of the shared memory. For example, the publish-subscribe [13] communication paradigm is supported by indirect cyber channels where cyber-dynamics (that are in this example part of the system architecture) take care about queueing published messages and notifying subscribers. Many popular message-based middleware platforms support publish-subscribe, e.g., the Robot Operating System (ROS) [34], or Eclipse paho1 , based on MQTT [5].

#### Physical Environment

The physical environment consists of things and physical fields (energy) whose properties we model as a dynamic network of physical state variables. Such a network of state variables can be described in an environmental model (for example, see [21] about an ontology-based environmental model) which captures the interrelationships (e.g., transfer delays, functional dependencies, location) of the state variables. For example, the temperature and the pressure of air are physically related and if one is affected by an actuation, so is the other one. Our networked view on the relations of physical state variables allows for a simple composition of environmental models, the consideration of different levels of detail, and taking interfacing effects into account. Note that one can reduce this network to a single set of physical state variables where all relations among the variables need to be described explicitly.

In the physical environment the concept of proximity is essential, because many physical interactions depend on distance (e.g., force fields). In case the entourages of two or more CSs overlap during the IoD, a stigmergic information flow, i.e., a physical interaction, can take place. Overlapping entourages help to limit the size of the environmental model that needs to be considered for the interaction of CSs. Figure 1 shows the network of physical state variables which is under the influence of environmental dynamics, but also part of the entourage of multiple CSs. Environmental dynamics are the time-sensitive effects of autonomous processes occurring in the environment.

Fig. 1. Overlapping entourage of CPSs enabling physical interaction

1 https://eclipse.org/paho/.

An actuator is an interface device of a CS which allows the CS to apply changes to one or more state variables of the physical environment that is currently part of the CS's entourage. Besides this actuation also other environmental dynamics may act on the network of state variables. For example, a heating actuator might increase the state variable 'room temperature', while environmental dynamics (heat dissipation) additionally affect the state variable over time. Concerning our environmental model, actuators are connected to the environmental model such that their influences affect the state variables appropriately by considering their placement, actuation delays, and effect propagation through the environmental model.

Sensors within the interface of a CS can observe a state variable of the physical environment. Usually these observations are limited with respect to measurement resolution, temporal accuracy, and rate limits. Consequently, such an observation is only partial and noisy. Similar to actuators, also the sensors need to be appropriately connected with the environmental model in order to take their placement and their capability to make observations (measurement delay) into account.

#### 3.2 Interface Layers

Interface layers allow the discussion of system interface properties and their definition in interface specifications at different abstraction levels and modeling viewpoints. In the following, three interface layers are introduced: the cyber-physical, the informational, and the service layer. The informational layer is an abstraction over the cyber-physical one, while the service layer structures the behavior of a system in a set of capabilities.

#### Cyber-Physical Layer

At the cyber-physical layer information is represented by data items (e.g., a bit-pattern in cyber space, or properties of things/energy in the physical world) that are transferred among interacting systems during the Interval of Discourse (IoD). While in this layer there is a distinction between cyber- and physical channels, both share many properties, because cyber channels are implemented by physical channels. Consequently, any interaction over cyber-physical channels is ruled by the progression of time and fundamentally constrained by the speed of light and distance among communicating systems. Time is an elemental property of cyber- and physical interfaces and must be considered at all interaction abstractions. Important properties of the cyber-physical layer are: signals (i.e., prearranged representation of information), transmission medium, characteristics of connectors, frequencies, bit rates, energy levels.

Interface properties at the cyber-physical layer are defined in the Cyber-Physical Interface Specification (CP-Spec) which consists of the two disjoint specifications: Interface Physical Specification (P-Spec) and the Interface Message Specification (M-Spec).

#### Physical Interfaces

Physical interfaces of CSs are realized by energy transformers that are able to (1) take observations from the physical environment, and (2) set actions initiated from the computer system of the CS in the physical environment. An observation in time-aware CPSoSs is a time-stamped measurement of a physical state variable (a property of a thing). A sensor is an interface device that measures the physical environment and produces observations in the form of digital data (a bit pattern), whereas the sensor design determines which property of the physical environment is observed. Sensor-fusion and state estimation [22] are well researched techniques to improve the fidelity of sensor observations. An actuator is an interface device that accepts digital data and control information (e.g., an actuation deadline) from an interface component, and realizes the intended effect in the physical environment (influences physical state variables).

As physical interfaces enable the interaction with the time-sensitive physical environment, they are time-sensitive as well. Hence, sensor/actuator latency and jitter affect the temporal accuracy of an observation or the timely effect in the physical environment.

The design of sensors and actuators as well as their placement in the physical environment determines the semantics of the digital in-, and/or, output bit-pattern, i.e., effectively form a basic Itom that contains the observation or actuation. In regard to information theory, we often have that some property of a thing (e.g., voltage level) has additional meaning to its receivers (e.g., digital zero and one), while the actual property of the thing becomes irrelevant, after the measured value has been properly abstracted. This refinement process takes place according to a receiver/sender shared conceptual context. It removes intrinsic information and produced a higher level Itom that contains only the extrinsic information. In computer systems, such overlay-meaning needs to be added as meta data until an Itom is formed which the target CSs can interpret and access correctly. The refinement process also removes unnecessary data that is not needed to convey the intended information, i.e., transforms raw object data to refined object data.

Take for example a speed limit sign at the side of the road which should be interpreted as such by an autonomous car CS. First, a camera sensor of the CS produces a bitmap Itom where the road side including the speed limit is contained as a large array of pixels. Then, for instance machine learning-based methods take this bitmap Itom, segment the image, and finally extract an Itom describing the speed limit sign. At this point the bitmap Itom including its large object data becomes irrelevant and can be removed from the computer system memory. The new Itom is then further contextualized with surrounding/implicit information (e.g., which metric or non-metric system the country where the road is located uses). Finally, it is possible to construct the speed limit Itom consisting of object data that represents a numeric value and meta data which explains (e.g., decimal, km/h, speed limit) the object data to be usable by the CS.

The Interface Physical Specification (P-Spec) describes the properties of sensors and actuators (e.g., sample rates, value/time uncertainties, observation granularity) in order to exchange Itoms with the physical environment according to a specified purpose. On the input side the P-Spec specifies the formation of basic level Itoms from sensor observations. On the output side the P-Spec defines how basic level Itoms are implemented by actuators as influences on physical state variables. The P-Spec together with an environmental model allows for the description of stigmergic channels.

#### Cyber Interfaces

Cyber interfaces produce and/or consume messages, i.e., bit-patterns in cyber space (e.g., an email) according to the Interface Message Specification (M-Spec). The M-Spec consists of three parts [25]: (1) the transport specification, (2) the syntactic specification, and (3) the semantic specification. The transport specification describes all properties of a message that are needed by the communication system to correctly deliver the message from the sender to the receiver(s). A correctly transported message adheres to all temporal and dependability specifications. The cyber interface consists of ports (channel endpoints) where messages are placed for sending, or received messages are read from. A port has the following properties:

The named syntactic units of a message are called message variables [25] and are defined in the syntactic specification. Additionally, the semantic specification links the name of message variable to its explanation, i.e., syntactic and semantic specification define the Itom contained in a cyber message.

For cyber interfaces we can differentiate among several types of compatibility:

In case of context compatibility, syntactic compatibility suffices to realize full compatibility. In case of context incompatibility a gateway is required to translate the data representation of the sender to a data representation that is compatible with the context of the receiver.

#### Informational Layer

This interface layer concerns the timely exchange of Itoms by unidirectional channels across interfaces. It provides an abstraction over cyber-physical channels to context-independent [27], direct and indirect information flows among systems and their environment [28]. The abstraction over cyber-physical channels removes any lower-level details of the interactions that is not relevant for describing the information processing behavior of CSs. Itoms at this layer are maximally refined and explicitly specified, i.e., their meta data is available to the extent necessary for all CSs that are possibly involved with these Itoms. Their realization at the lower-level cyber-physical layer must adhere to the semantics specified at the informational layer, otherwise the abstraction is invalid and there is risk of property mismatch among interacting CSs. All for the CPSoS service relevant cyber-physical interactions must be taken into account at the informational layer. Otherwise there are hidden channels at the informational layer which might compromise security, safety, or may lead to unexpected behavioral detrimental emergence.

Further, the informational layer focuses on modeling the direct and indirect communication among CSs. There are cases where it is beneficial not to model every system involved in an interaction explicitly, but regard them as anonymous common environment of a smaller set of systems of interest which indirectly interact over this common environment. Indirect communication also allows for decentralized coordination of systems [36] and the description of cascading effects [16].

An Itom channel is characterized by what kind of Itoms the channel can transport, the sender, one or more recipients, temporal properties, and dependability properties. The Interface Itom Specification (I-Spec) describes the Itoms exchanged at the system interface, independently of how the information transfer is actually realized. For example: a system 'car' notifies cars behind about its sudden change of velocity to an immediate stop by 'emergency brake' Itoms. In the cyber-physical layer these Itoms might be implemented by: (1) a stigmergic channel between the braking car and the cars behind who observe that the car in front suddenly slows down, (2) a stigmergic channel realized by the brake light of the sender and the human operators of the cars behind, and (3) a wireless car2car cyber channel between the braking car and the cars behind.

#### Service Layer

At the service layer, the interface exposes the system behavior structured as capabilities. In contrast to the informational layer, Itom channels are not individually described at the service layer, but only the interdependencies between the exchanged Itoms are specified. If a system with a need is matched with a system that offers the needed capability, the interdependencies must be resolved in the information interface layer with concrete Itom channels. Hence, at the service interface layer there is an instantiable collection of Itom channels per offered capability where generic properties of the Itom channels and their interaction pattern are described.

Systems may provide many services through their interfaces provided that their internal structure can rely on required services. This concept is a fundamental principle in the Service-oriented Architecture (SoA) [12] where components in need of capabilities and components that offer capabilities are brought together by means of a service registry, service discovery, and service composition. A service provider is a component that provides a service, while a service consumer is a component that uses a service. The service registry is a repository of Interface Service Specifications (S-Specs) of capabilities that can be provided by a service provider. Service discovery is the process where service consumers match their service requirements against the available S-Specs in a service registry. Finally, service composition is the integration of multiple services into a new service. The benefits of this service-based view are twofold:

First, there is an immediate reduction of complexity, because one does not need to regard component relations on the basis of single Itom channels anymore. Service consumers can discover services they depend on, and a scheduler can instantiate the necessary unidirectional Itom channels automatically. Further service composition enables the formation of higher-level services based on low-level services. Take the example of a service that provides a humanoid robot the capability to open doors. Such a service would need to implement planning and re-planning of the complex movements realized by lower-level actuation services while constantly taking into account observations (e.g., position of arms, state of the door) from lower-level sensing services.

Second, the coupling of components (integrated in one system) is loose, because the actual constituents of composed services are unimportant background details in the service-based view. This freedom in service composition allows for self-organized system reconfiguration such that the system is able to perform optimally in case new services become available and previously active services become un-available. For example, a service consumer does not depend on a single component to provide the required service, but the service consumer can lookup multiple suitable services from the service registry and choose the optimal regarding computational, communicational, or other costs.

These benefits have been originally observed in the context of free market economy where trading among buyers and sellers led to efficiency in the production and distribution of products.

An S-Spec also includes a set of quality metrics that are available for an independent observer to determine the quality of a provided service. Based on these quality metrics, service providers can offer their service under a Service Level Agreement (SLA) which consists of Service Level Objectives (SLOs) together with the price of a service, and compensation actions in case an SLO of a committed service was not achieved. An SLO describes a quantifiable service objective based on measurable quality metrics that can be monitored independently of the service provider. Service providers can publish their SLA with a reference to the S-Spec of an offered service at the service registry, such that prospective service consumers can find and choose an appropriate service provider.

#### 3.3 Interfaces of a Constituent System

Interfaces within Constituent Systems (CSs) that are not exposed to other CSs or the CS's environment are called internal interfaces. A CS is embedded in its environment by its external interfaces. When applying the principle of separation of concerns, there are three subtypes of external interfaces: Time-Synchronization Interface (TSI), Relied Upon Interface (RUI), and utility interfaces. The TSI enables external time-synchronization to establish a global timebase for realizing time-aware CPSoS. Most important for the integration of a CS in a CPSoS is its RUI which is the interface the emergent and operational CPSoS service relies upon. The optional utility interface is an interface of a CS that does not need to be considered for the operational service of CPSoSs.

The purposes of the utility interfaces are to (1) configure and update the CS, (2) diagnose the CS, and (3) let the CS interact with its remaining local environment which is unrelated to the operative service of the CPSoS. These three purposes justify the introduction of the following utility interfaces: Configuration Interface (C-Interface), Diagnostic Interface (D-Interface), and Local I/O Interface (L-Interface). Figure 2 shows all external interfaces of a CS.

In time-aware CPSoSs, the CSs have access to a synchronized global time base with bounded precision. Such a global time base can be established by external clock synchronization over the TSI to, for example, a Global Navigation Satellite System (GNSS) like GPS. Time-awareness allows for temporally ordering observed events and temporally correctly executing timely available actions in a distributed setting. Naturally, in case the communication or computation subsystem or both fail to deliver or execute an action at its deadline, the execution cannot be guaranteed to be temporally correct. However, in a time-aware CPSoS the temporal order of observed events – no matter which CS observed them – can be always determined.

We briefly discuss the utility interfaces. The C-Interface is an interface of a CS that is used for the integration of the CS into a CPSoS and the reconfiguration of the CS's RUIs while integrated in a CPSoS. In time-aware CPSoSs the C-Interface allows to update the interface specification of RUIs to realize time-controlled evolution (see Sect. 5.3). A predefined validity instant which is part of the interface specification determines when all affected CSs need to use the updated RUI specification and abandon the old RUI specification. This validity instant should be chosen appropriately far in the future (e.g., in the order of the update or maintenance cycle of all impacted CSs). Service providers guarantee that the old interface specification remains active until the validity instant such that service consumers can rely on them up to the reconfiguration instant. The D-Interface is an interface that exposes the internals of a CS for the purpose of diagnosis. Finally, the L-Interface is an interface that allows a CS

Fig. 2. Interfaces of a Constituent System (CS)

to interact with its surrounding physical reality that is not accessible over any other external interface, for example to realize Human Machine Interfaces (HMIs), or provide other CS-local only services.

A connected interface is an interface that is connected to at least one other interface by a channel. Some external interfaces are always connected with respect to the currently active operational mode of a correct system. A disconnected external interface might be the cause of a fault [4] (e.g., a loose cable that was supposed to connect a joystick to a flight controller) which might even lead to a catastrophic failure.

CSs may connect their RUIs according to a RUI connecting strategy that searches for and connects to RUIs of other CSs. The RUI connecting strategy is a part of the interface specification of RUIs and searches for desired, with respect to connections available, and compatible RUIs of other CSs and connects them until they either become undesirable, unavailable, or incompatible. For instance, in the global Automated Teller Machine (ATM) network, a cardholder together with a smartcard based payment card form a CS that is most of the time disconnected from any other CSs. The RUI connecting strategy of the payment card CS is influenced by the cardholder's need for cash (desire), nearby located and operational ATM terminals (availability) and whether the ATM terminal accepts the payment card (compatibility).

#### 4 Relied Upon Interfaces

This section discusses the Relied Upon Interface (RUI) model at the previously introduced interface layers, also showing how interface layers are connected. Then the section proposes appropriate execution semantics of the RUI model at the informational layer and closes with a brief discussion of how CPSoS dynamicity is handled by the RUI specification.

#### 4.1 RUI Model Overview

The Relied Upon Interface (RUI) establishes a system boundary of a CS by separating it from its environment. The part of the CS behavior which the CPSoS service relies upon can be observed at the RUI of the CS. Consequently, the interface specification of a CS's RUI hides the possibly complex internal behavior of a CS from the overall CPSoS. However, even more importantly the complexity of the overall behavior of a possibly enormous CPSoS is also hidden from a CS at its RUI. Hence, the RUI specification can be regarded as a complexity firewall because it regulates all interactions taking place across the specified interface. Innate to RUIs, i.e., the points of interactions of CSs, is the transfer of information occurring over these interfaces. It follows an examination of RUIs for each of the three interface layers that we introduced in Sect. 3.2.

#### RUI Cyber-Physical Layer

Figure 3 gives an overview of cyber-physical interactions at the RUIs of two CSs that are externally time-synchronized and have access to a global timebase. The RUI consists of two sub-interfaces: the Relied Upon Message Interface (RUMI) a cyber interface, and the Relied Upon Physical Interface (RUPI).

The RUPI consists of sensors and actuators that take and time-stamp observations of and/or act at a defined deadline on some physical state (e.g., the temperature of a room) in the physical environment according to their design. Environmental dynamics (e.g., heat dissipation through walls) act additionally to other CSs on the physical state. CSs that interact with each other over a common physical environment establish a stigmergic channel [28], i.e., they communicate indirectly by influencing and measuring the physical state.

The RUMI allows (1) for the unidirectional transport of state and event messages [25] by means of conventional direct cyber channels, and (2) for the indirect coordination with other CSs by means of indirect cyber channels. A state message contains only state observations, i.e., the observed state (e.g., temperature of a room) at a specific instant.

#### RUI Informational Layer

The informational layer abstracts over informational context-sensitivity, and focuses on direct and indirect information flows among CSs. An indirect channel (cyber or stigmergic) is modelled by instantiating an additional Environmental CS (ECS).

This interface layer is useful during the design of CPSoSs (e.g., model-based design, design space exploration), as well as in the analysis of CPSoSs. For example, we believe that identifying causally related interactions among CSs is paramount for detecting and predicting emergence (see Chap. 3). Naturally, for finding such causal relationships the RUI specifications, the associated interface models, and the environmental models need to be accurate regarding reality, i.e., there should not be any hidden channels. A hidden channel is a latent information flow among CSs that has not been considered by the modeler. Hidden channels might close feedback loops that are believed to be liable for possibly undesired detrimental emergence [28]. In case some

Fig. 3. Relied Upon Interfaces (RUIs) at the cyber-physical layer

behavior is observed at the RUIs of CSs during CPSoS operation, but cannot be reproduced in a simulation at the informational layer, there are hidden channels present that should be identified.

#### RUI Service Layer

At the service interface layer, we introduce Relied Upon Services (RUSs) that are provided at the RUI of a CS. They are described in the Service Specification (S-Spec) of the RUI as a set of RUS-related operations. A service operation is a behavioral abstraction over one or more unidirectional Itom channels. It groups them together and defines their interaction pattern, i.e., the sequence of all operation-related Itoms over all channel endpoints from the perspective of the service provider. Examples of interaction patterns are: request-response, notify, or solicit. Actual Itom channels, or consequently cyber-physical channels are only instantiated (or their provisioning considered) if a RUS is committed to a service requester.

Besides defining the operations of a RUS, the S-Spec also includes a set of quality metrics that allow an independent observer (e.g., a monitoring CS) to determine the quality of a RUS provided at a CS. Based on this quality metrics, a RUS provider can publish its Service Level Agreement (SLA) at the service registry such that service requesters are able to find and request suitable services. RUS providers and consumers are CSs. The service registry – depending on dynamicity and business requirements of the particular CPSoS – can be either realized as another CS (operated by an SoS authority) to allow for a runtime RUS composition, or it is realized in an off-line manner.

At the service level we model the emergent CPSoS service as a set of dependencies on the required RUSs, such that any CS that wants to use or benefit from the emergent CPSoS service needs to provide these RUSs. However, a CS does not need to directly provide all or even any RUSs a given emergent CPSoS service depends on, as long as the CS is able to request and consume them from other RUS providers.

#### Example

This section shows in a small example how the interface layers of the RUI are connected. The example CPSoS consists of n interacting CSs. At the cyber-physical interface layer, it contains CSs that interact by using direct and indirect cyber-physical channels. In the informational layer these channels correspond to Itom channels and Itom processing subsystems that implement the behavior of indirect communication. Finally, at the service layer we are able to group channels that are associated with a service and express service dependency relationships.

#### Cyber-Physical Layer

Figure 4 shows cyber-physical interactions realized by some concrete technology (e.g., data exchanged in cyber space by a TCP/IP network stack, physical location of the CS on a street influenced by actuators). To relate the channels among the CSs and their environment across all interface layers, we draw all channels related to a distinguishable service with the same style. Cyber Channels (CCs) are drawn with a solid line style, while Physical Channels (PCs) are drawn with a dashed line style. Some of the CCs and some of the PCs are labeled for easier identification.

CC 1 and CC 2 are direct cyber channels of the same service (e.g., a database lookup service realized by a request and a response channel). CC 3 and CCs originating from CSs 3 to n-1 are writers of an indirect channel. For example, they publish information whether an alarm occurred. This indirect channel has only one reader (CC 4): CS n which could be an alarm monitor. Further, there is a stigmergic channel realized by PC 1 (actuator which is part of the CS 1 RUPI), physical state variables, and PC 2 (a sensor device of the CS 2 RUPI). Another stigmergic channel (realized in the figure via the overlapping entourages in the lower right of the physical environment) is shown where all CSs are able to influence physical state variables and also observe them, for example the position of CSs on a street.

#### Informational Layer

Figure 5 shows the example CPSoS at the informational layer. All direct CCs have a corresponding Itom Channel (IC), for example see IC 1 corresponds to CC 1. The indirect CC is realized by an additional Environmental CS (ECS) which implements the behaviour of the indirect CC described by an appropriate environmental model (shared memories with all acting cyber dynamics). Also for each stigmergic channel an additional ECS realizes the environmental model (environmental model with all acting environmental dynamics).

Fig. 4. Constituent Systems (CSs), Cyber Channels (CCs), and Physical Channels (PCs) at the cyber-physical interface layer

Fig. 5. Constituent Systems (CSs) and Itom Channel (ICs) at the informational interface layer

Service Layer

The service layer of the example CPSoS consists of four services in the dependency relation shown in Fig. 6. For example, service A depends on the environmental services C and D. Service A might be a database lookup service provided by CS 2. The incoming and outgoing arrows on the left of the service vertex symbolize the two Itom channel ports from the perspective of the service provider (one input port and one output port). The three environmental services B, C, and D are provided by ECSs (e.g., environmental service D is provided by ECS 3 in the informational layer). CSs that consume such services need to either act as an influence/writer, or as an observer/reader. The ports on the left side of an environmental service represents the influence/writer service consumer

Fig. 6. Service interface layer

(e.g., CS 1 is an influence/writer of ECS 2), and the ports on the right side of an environmental service stand for the observer/reader service consumer (for instance, CS 2 is an observer/reader of ECS 2).

#### 4.2 Execution Semantics of the Informational RUI Model

The interface model describes the part of the system behavior which is observable at that interface. In the previous section we presented an overview of the RUI model. In this section we want to enrich our interface design by suggesting a Frame-based Synchronous Dataflow Model (FSDM) as an execution semantic for the informational layer. Having such execution semantics, allows the detailed study of CPSoSs with respect to behavioral properties at the informational layer in the value domain and in the temporal domain.

#### Frame-Based Synchronous Dataflow Model

The FSDM is prominent in modeling dependable real-time systems that interact with physical systems or models of them. Further, there are many high-quality tools and languages to design, execute/simulate, and verify such synchronous models, e.g., GIOTTO [20], and Lustre [18].

In the FSDM the dense physical time is discretized into frames, i.e., periodic sequences of constant duration. Each of the frames consists of a synchronization phase and a processing phase. During the synchronization phase the input is received (in a sample and hold manner) from the system environment and the output is sent to the environment. In the processing phase the system's function calculates the next state and the output from the input and the current state. Only during the synchronization phase there is interaction between a CS and its otherwise free-running environment. Under the synchronous hypothesis [33] a frame duration is short enough such that the system appropriately reacts to changes in its environment. Hence, the frame duration is determined by the environmental dynamics. For instance, for a keyboard-based Human Machine Interface (HMI) a frame duration of 50 ms is appropriate for most applications, while for a crash detection system in a car a frame duration lower than 1 ms is more appropriate.

It follows a brief overview of the implementation of the CPSoS elements at the informational layer by means of the FSDM:

#### Implementation Considerations

In time-aware CPSoSs the CSs as well as the cyber channels might not be able to guarantee the reaction time constraints imposed by the FSDM. Still, if inputs (and outputs) adhere to the state semantics, there are sophisticated state estimation techniques [22] available to tolerate occasional violations of the synchronous hypothesis (even to the extent of incorporating state observations with significant delay and jitter, e.g., cf. [11], Fig. 2).

In time-aware CPSoSs the CSs can use the available global timebase to drive a periodic control subsystem of a CS as follows: Frame start instants are aligned with a tick event of the global time and frame durations are multiples of the granularity of the global time. Further, the periodic control subsystem is responsible in the processing phase to activate application tasks, and during the synchronization phase to conduct send and receive actions. There is implementation technology available that readily supports the FSDM. Examples are: TTEthernet [35], TTP/C, or the ACROSS Multi-Processor System-on-Chip [37].

#### 4.3 RUIs Under Dynamicity

Dynamicity describes the reaction or reconfiguration capabilities that have been already considered in the CPSoS design. Therefore, any supported dynamicity needs to be defined in the RUI specifications. We examine three prototypical dynamicity cases:

RUIs might be connected only for a finite duration within an Interval of Discourse (IoD). A disconnected RUI might be a normal, fault-free interface state and may result at most in CS service degradation, but not in CS failure. This key aspect of RUIs is responsible for the impossibility to establish a static system boundary of a CPSoS. CSs may disconnect and reconnect and they might even be part of multiple CPSoSs (e.g., a modern day NFC enabled smartphone can be part of the global telephone network, the Internet, and the global ATM network which are three large and independently operating CPSoSs).

The RUI connection strategy is part of the interface specification of RUIs that regulates how CSs establish connections. All RUI connecting strategies are local to their respective CS. Still, they influence the dynamic global network topology of a CPSoSs. Consequently, they are co-responsible for the occurrence and regulation of self-organization and emergent phenomena.

At the cyber-physical and informational layers of RUIs it is cognitively complex to describe the dynamic CS interaction that is necessary for accessing a service on the basis of individual channels, because the specific client CSs are unknown before runtime. For example, take a CS that offers a database service. This database service requires a request and a response Itom channel per client CS. For n client CSs one would need to specify 2n dedicated channels at the cyber-physical or informational interface layer. When considering the same situation at the service layer, only the database service together with the two required channels needs to be specified. The mechanisms of service discovery and service composition allow a scheduler to automatically instantiate the request and response channels for each client CS during runtime.

Finally, CSs might need to react to the changing environment and need to reconfigure the set of offered services in order to: (1) accomplish overall CPSoS goals (e.g., limit total energy budget, enter a safe state, …), or (2) tolerate faults (e.g., suddenly disconnected CSs or failing CSs). At the service interface layer, paradigms known from the Service-oriented Architecture (SoA) are readily available for use. For example, one such paradigm is to replace services with a degraded version, or to replace failed services altogether with services from other (redundant) CSs [21].

#### 5 Interfaces in Evolving Cyber-Physical Systems-of-Systems

Evolution of Cyber-Physical Systems-of-Systems (CPSoSs) concerns design modifications introduced into the interacting Constituent Systems (CSs) that are triggered by changes in the CPSoS environment. Changes of the CPSoS environment might include, for example, advances in technology, or are changes in societal or business needs. Often these needs originate from the desire to change a service towards increased efficiency or the wish to introduce new services altogether. Ultimately, evolutionary changes to the design and consequently operation of the CPSoS should counteract obsolescence in order to keep the CPSoS relevant, increase its business value for involved stake holders, while not deteriorating already provided and still needed services.

When discussing evolution in possibly large and complex systems like CPSoSs we distinguish between unmanaged and managed evolution [32]. In unmanaged evolution there is no guidance about how a CPSoS evolves. Owners of CSs are free to change services and cooperation with other CSs is motivated by each CS owner's own gain in perceived business value. Facebook, Wikipedia, Google services, and Twitter messaging are examples of CSs whose interfaces are controlled and evolved by the respective owning companies. The composition of such CSs is not driven by a specific central purpose and leads to virtual SoSs (e.g., Twitter/Facebook integration of fitness tracking and training applications, or a clever integration of Wikipedia and Facebook to realize file-sharing services). Consequently, unmanaged evolution is most suitable for virtual SoSs where there is no clear central purpose.

In this section we focus on the technical realization of managed evolution [32] which is most appropriate for collaborative SoSs (but also directed and acknowledged SoSs, see Chap. 1 for details about SoS classifications). Managed evolution has been originally suggested in the context of large, long-term operational software systems that also show many similarities with CPSoSs (complex functional, semantical, temporal, technical, and operational interdependencies of interacting systems with non-trivially replaceable legacy subsystems). In collaborative SoSs, managed evolution must be planned and supervised by an SoS authority, i.e., an organizational entity (for example established by a CPSoS consortium or enterprise), such that "the efficiency of developing and operating the system is preserved or even increased" [32]. The SoS authority has a specific CPSoS purpose in mind, maintains the specifications of Relied Upon Interfaces (RUIs), and has a set of capabilities in order to manage CPSoS evolution. The capabilities are:

In the following we discuss scope and challenges of managed evolution in time-aware CPSoSs and in particular investigate evolution at Relied Upon Interfaces (RUIs) of CSs. We attempt to confine risks associated with unexpected detrimental emergence and finally suggest a set of guidelines how to handle evolution in time-aware CPSoSs.

#### 5.1 Scope and Challenges

Managed evolution as described in [32] discusses and addresses challenges related to large, complex, and long-term operational software systems. The comprehensive findings of the authors apply to collaborative SoSs, because they share all characteristics of the systems discussed in [32]. For example, one important challenge the authors address is maintaining agility (i.e., the ability to efficiently implement evolutionary changes) while also carrying out necessary changes to increase the system's business value.

Further, the authors extensively examine organizational, governance, and even cultural or people aspects of evolving systems, while in this chapter we mostly concentrate on technical aspects. In the following, we identify challenges specifically occurring in the evolution of time-aware CPSoSs that we want to tackle:

CPSoS dynamicity need to evolve together with changes in the CPSoS service. For example, in case an evolutionary change allows more efficient use of crossroads and use of street lanes, different traffic situations might arise which require different reaction strategies in order to optimize traffic flow and minimize detrimental effects of faults.

Note that we do not claim that this list of challenges is complete. There might be more challenges related to evolution, especially, if one wants to discuss CPSoSs of specific application domains.

#### 5.2 Local and Global Evolution

We call changes within a CS that do not affect its interactions with other CSs local evolution. Local evolution does not modify any of the CS's RUI specifications and consequently remains invisible at the CPSoS level. Still, local evolution is important to optimize the operation of CSs, introduce new or change local-only CS services, or prepare CSs for a pending global evolutionary step.

Local evolution harbors the risk of introducing hidden channels (i.e., unconsidered interactions) among CSs which could lead to emergent effects. Hence, local evolution must carefully respect RUI specifications which forbid – in principle – any interaction of a CS with its environment that is not explicitly defined. However, in praxis this is difficult to achieve, especially in relation to stigmergic interactions over a common physical environment. For example, a processor may leak information via its power consumption. In case some local evolutionary change enables an attacker to measure the power consumption, CPSoS security might be compromised.

In contrast to local evolution, we call changes that affect the interactions of CSs and thus the service of the overall CPSoS global evolution. As such, global evolution concerns the change of RUI specifications and how these changes are coming into effect. In CPSoSs we have continuous evolution. Consequently, CPSoSs cannot be changed radically, but need to evolve gradually towards changed or new goals in evolutionary steps of limited scope preferably with predictable effects.

Inspired by biological evolution of life (cf. Darwin and natural selection) we regard CPSoS evolution as a tree-like search towards adaptation to environmental conditions. The search space consists of all possible changes that can be realized to address (changed) environmental conditions. Naturally this search space is too large to explore exhaustively; only some of the possible changes are actually realized and can be represented as a tree-like search space exploration. Figure 7 sketches how we view the process of global evolution in CPSoSs. Each of the vertices of the acyclic graph represents a specific evolutionary state or version of the CSs making up a CPSoS. The edges in the graph represent evolutionary steps. The vertical dashed line represents the instant now which separates the past (versions of CSs that exist and may or may not be in operation) from the future (versions of CSs that are planned and are not operational yet). We assume that some versions of CSs are compatible at the present. In the figure we have indicated two overlapping sets of versions of CSs that are compatible (upper and lower lassos containing a set of vertices each).

Fig. 7. Tree-like search towards adaptation

Three fundamentally different types of evolutionary steps have been identified:

Note that in some cases a version can be abandoned and not evolved further as we have illustrated in Fig. 7 by using the shaded version vertex which has no outgoing edge. CSs of such an abandoned version will turn into legacy CSs until they become obsolete.

In terms of managed evolution, forks create mostly business value, while merges increase agility. Basic steps either increase business value or agility. It is in the responsibility of the involved SoS authorities to appropriately control evolutionary steps such that the business value for all stakeholders stays viable while simultaneously agility is not reduced. Both, business value and agility are quality metrics that are composed of CPSoS application-specific quality metrics. For example, the business value of a CPSoS consisting of autonomous cars that should transport humans in a city while minimizing environmental pollution can be assessed by average transportation time per km and average pollution per km.

#### 5.3 Managing Global Evolution at Relied upon Interfaces

Integral to managing evolution in CPSoSs is the establishment of an SoS authority over RUI specifications. The SoS authority needs to carefully plan and execute evolutionary steps that – depending on their magnitude – may require considering the possibility of unexpected detrimental emergent effects, and modifying the management of CPSoS dynamicity.

#### SoS Authority and Management of RUI Specifications

We consider the SoS authority as a mandatory organizational entity in collaborative SoSs that has societal, legal, or business responsibilities in order to keep the CPSoS relevant to its stakeholders. For this purpose, the SoS authority has monitoring and amelioration powers within the CPSoS in order to steer it towards a desired target version. In particular the SoS authority manages RUI specifications and controls how changes of these specifications are rolled out. An SoS authority might be composed of representatives of key CPSoS stakeholders, like CS manufacturers or governments.

SoS authorities select and adopt a suitable set of standards developed by standardization organizations such as the Institute of Electrical and Electronics Engineers (IEEE), the Society of Automotive Engineers (SAE), or the Object Management Group (OMG). The role of standardization organizations in CPSoSs is to provide a stable and broadly accepted conceptual and technological basis for the realization of RUI specifications. For example, the SAE J1708 standard specifies the serial communication (physical layer) of Electronic Control Units (ECUs) in heavy duty vehicles.

In the following we outline a technical realization of RUI specification management on a Service-oriented-Architecture (SoA) approach. Authorized Relied Upon Service (RUS) specifications (S-Specs) are administrated at a service registry (see Sect. 3.2). Only the SoS authority can authorize and publish S-Specs at the service registry. For example, a CS owner2 participates in the CPSoS by being a RUS provider that offers the RUS in compliance to an authorized S-Spec. In support of multi-version evolution the service registry needs to feature version management for authorized S-Specs, i.e., the SoS authority can add new versions of S-Specs to the service registry that coexist with older S-Spec versions. Now owners of CSs that provide RUSs have the possibility to specify in their respective SLAs to which specific version of an authorized S-Spec they refer to. For each supported S-Spec version a different SLA needs to be offered by the CS owner.

Besides managing RUI specifications the SoS authority needs to assess and steer the overall evolutionary process of the CPSoS. The performance of the evolutionary process of a CPSoS is derived from measurable quality metrics describing business value and agility of the CPSoS. Consequently, the measurement of the evolutionary performance can be efficiently integrated in the monitoring and analyzing blocks of the AMADEOS solutions concerning the management of CPSoS dynamicity (see Chap. 7). One example of an important quality metric for the assessment of the

2 For the sake of brevity we assume here that the owner of a CS is also its manufacturer and user.

evolutionary performance in CPSoSs is the adoption rate of existing or newly introduced CSs to new or changed versions of S-Specs.

The adoption rate is controllable by the SoS authority who can give incentives in order to move the evolutionary process towards a desired target version. Incentives can be advantages or disadvantages where even monetary penalties apply in case a CS is not upgraded to a more recent version. For example, in the global Automated Teller Machine (ATM) network SoS the payment card industry shifted liability at a specified deadline from money institutes to the Point of Sale (PoS) operators (usually merchants), if they used old and insecure equipment to process payment cards. As the deadline of the liability shift approached and passed, PoS operators risked compensating monetary losses caused by fraud from their own pocket, if an insecure PoS terminal under their responsibility was involved. This strong incentive forced PoS operators to upgrade to more secure PoS terminals where they are not liable in the event of fraud.

#### Magnitude and Effects of Evolutionary Steps

We define the magnitude of an evolutionary step by considering which of the interface layers (see Sect. 3.2) of RUIs are affected by it:

Methods from Scenario-based Reasoning (SBR) [6] can be employed to pre-evaluate effects of evolutionary steps according to CPSoS-specific quality metrics under quantified uncertainty.

#### Handling Continuous Evolution

It remains to discuss the transition from one CPSoS version to an evolved version. Continuous evolution in CPSoSs is based on the principle of backward compatibility of its CSs. This backward compatibility needs to be established by upgrading or introducing new CSs that also support the interaction with non-upgraded CSs.

We have already described a multi-version service registry and that Relied Upon Service (RUS) providing CSs can support multiple versions of S-Specs. Now we want to emphasize that also CSs requesting RUS have the possibility to consume different versions of a RUS. In fact, the more versions of RUSs a CS is able to provide or consume, the 'smoother' a CPSoS is able to evolve. Naturally, newly introduced RUSs should not disrupt existing or legacy RUSs.

At some point conflicting or obsolete RUSs need to be retired and old, non-upgradable CSs that depend on them or provide them become incompatible with more recent CSs. In case these old and non-upgradable CSs are still essential for the operation of the CPSoS they become legacy CSs and their service needs to be appropriately wrapped. For example, a wrapping CS can be introduced in an evolutionary step. The wrapping CS is able to offer the service of the legacy CS encapsulated in a version of a RUS that is compatible with all non-legacy CSs.

In time-aware CPSoSs there is the benefit of a global time that allows temporally coordinating the execution of an evolutionary step. The SoS authority can define validity instants in new versions of RUI specifications such that they are switched on at a specific instant. For example, a desired emergent effect may only occur if a critical number of CSs adhere to the new RUS version simultaneously. Also, for some CPSoSs it might be useful to steer its CSs first to a safe, ground, or dormant state, then perform further (physical) upgrades, and finally awake them to interact in the evolved CPSoS (see car-recalls and repair procedures in the automotive domain).

#### 5.4 Avoiding Detrimental Emergence

The occurrence of unexpected detrimental emergence is a problematic case in engineering, operating and evolving CPSoSs. Against our expectations and current predictive capabilities something harmful and possibly catastrophic happened. Why can we not prevent unexpected emergence by design? While the engineering process is indeed responsible for the interaction abilities of the CSs, CPSoSs are also open systems that interact with their environment. This environment of a CPSoS may change over time and/or might be insufficiently understood, i.e., in general we cannot be certain that our models of the CPSoS environment are complete. Also the boundary of a CPSoS is dynamic and influences how the CPSoS environment affects the CPSoS itself. For example, consider a fault-tolerant CPSoS: If the number of its redundant CSs is small, an environment that causes intermittent faults in CSs at a constant rate (e.g., radiation) is much more hostile than compared to the same CPSoS where the number of redundant CSs is large.

An evolving CPSoS attempts to adapt to changes in its environment (real changes or a changed understanding of the environment). Consequently, there are two co-dependent causes that enable the occurrence of unexpected detrimental emergence in CPSoSs:

To the best of our knowledge there is currently no scalable theory to eliminate the first cause with certainty. The number of possible interactions in real-world CPSoSs (physical environment!) diminishes any hope to exhaustively test for all known emergent phenomena, and to evaluate them with respect to their possibly detrimental effects. Even if there was a theory solving this issue, one fundamental problem remains: Identifying unknown emergence, i.e., effects or properties that are conceptually novel at the macro-level (SoS level), but are not present in the non-relational phenomena of the parts at the micro-level (level of CSs).

Unfortunately, the situation is even worse concerning the second presumed cause that enables the occurrence of unexpected emergence. Changes in the CPSoS environment are outside the sphere of control of a CPSoS consortium. Some of these changes may lead to the occurrence of previously rare or unlikely interactions of CSs which may in return result in a (detrimental) unexpected emergent phenomenon.  They may close causal loops or enable cascading effects which again could trigger (detrimental) unexpected emergence.

In summary, it appears that in principle we cannot prevent all first occurrences of detrimental emergent phenomena with absolute certainty. Further, both an ill-conceived evolutionary step, and (unlucky) changes in the CPSoS environment may lead to undesired emergent phenomena. In the following subsections we discuss a mitigation strategy based on results described in Chap. 3.

#### Mitigation Strategy

In order to minimize occurrence and subsequent damage due to unexpected detrimental emergence we suggest a mitigation strategy consisting of the following procedures:

that ameliorates ongoing detrimental emergence and prevents its further occurrence. Amelioration can be implemented in the management of CPSoS dynamicity by deploying suitable reaction strategies (e.g., introduction of randomness to break unintended synchronization [31]). Prevention of detrimental emergence should be implemented by appropriately constraining the RUIs of CSs such that their interactions do not lead to the detrimental emergent effect anymore.

• Prediction of detrimental emergence: When planning an evolutionary step, we can predict/search for detrimental emergence by applying analytical methods (e.g., finding causal loops, cascading effects) as well as simulation of models of the CPSoS and its environment.

#### Detecting Unknown Emergence

Often emergent phenomena are associated with some kind of regularities or shift in densities, but looking for something unknown that does not appear to have any generic and unique characteristics limits our detection abilities. Mogul [31] suggests building a library of signatures of emergence that occur in distributed computer systems and gives interesting examples: trashing caused by 'unlucky' scheduling (not just overprovisioning), unintended synchronization, unintended oscillation or periodicity, detectable by spectral analysis, deadlock and livelock, phase change, chaotic behavior.

While building such a library still requires some decision procedure to classify anomalies as emergent, it would – together with monitoring – allow for efficient detection of already encountered emergence. A decision procedure to classify anomalies could be supported by unsupervised machine learning. Self-organizing Maps (SOMs) appear to be a particularly interesting technique where clusters of structure or density differences in data can be found (see Fig. 8, right).

The SOM [23] is an unsupervised machine learning approach that is based on an artificial neural network of a usually low-dimensional topology (e.g., two-dimensional as depicted in Fig. 8, left). During the training process possibly high-dimensional input data is (after appropriate pre-processing [19]) firstly vector quantized and secondly mapped to the SOM while attempting to preserve the original topology of the input data. Various visualizations for SOMs exist to both make the information contained in the SOM accessible for analysis, but also to allow for assessments concerning the quality of the vector quantization and the quality of the topology preservation. Consequently, visualizations are critical for the interpretation of SOMs. Visualizations often focus on a single or a few aspects of the SOM, i.e., for analyzing SOMs, it is often necessary to study multiple visualizations of them in combination. For example, visualizations can express structural information about input vector density relations, distance relations among mapped input vectors (also called topology), or class information. Further, SOMs can be used to both semantically relate different input samples among one another, and to predict the relation of new input samples to input samples used in training.

Fig. 8. Self-Organizing Maps (SOMs) reveal emergent regularities in high-dim input data

#### 5.5 Design Guidelines for Evolvable Systems-of-Systems

We conclude this section with a list of design guidelines for evolving CPSoSs that in particular apply to collaborative SoSs:

• Keep human domain experts in the design loop of evolutionary steps. The CPSoSs that we want to engineer and operate integrate humans, affect humans and should co-evolve with humans. Consequently, only humans are fully capable of judging how to best address a change in the environment of CPSoSs.

## 6 Conclusion

In this chapter we discussed interfaces in time-aware Cyber-Physical Systemsof-Systems (CPSoSs) for the purpose to investigate behavioral properties of CPSoSs. First, we characterized relevant architectural elements of CPSoSs and introduced three interface layers: the cyber-physical layer, the informational layer, and the service layer. Based on this conceptual groundwork, we identified (among other interfaces) the Relied Upon Interface (RUI) of a Constituent System (CS) as the fundamental interface responsible for the operational behavior of CPSoSs and managing CPSoS evolution.

The RUI is a CS interface on which the global, operational CPSoS service relies upon. We described the RUI model at each of the introduced interface layers, and outlined execution semantics for the informational layer to support the exploration of behavioral effects, like the occurrence of emergence.

In the second part of the chapter we focused on CPSoS evolution and how to manage it at the RUI of CSs. To this end we introduced an SoS authority that is in control of RUI specifications, plans evolutionary steps, and carries them out by changing RUI specifications. We discovered that both – changes in the CPSoS environment and evolutionary changes – harbors the risk of unpredicted detrimental emergence and suggested a mitigation strategy.

Acknowledgments. Warm regards to Sorin Iacob and Andrea Bondavalli for the insightful discussions about stigmergic channels. We thank the following experts for reviewing and helping to improve the chapter: Wilfried Elmenreich (Alpen-Adria-Universität Klagenfurt, AT), Sorin Iacob (Thales, NL), and Wilfried Steiner (TTTech, AT).

#### References

Open Access This chapter is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, duplication, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the work's Creative Commons license, unless indicated otherwise in the credit line; if such material is not included in the work's Creative Commons license and the respective action is not permitted by statutory regulation, users will need to obtain permission from the license holder to duplicate, adapt or reproduce the material.

# Emergence in Cyber-Physical Systems-of-Systems (CPSoSs)

Hermann Kopetz1 , Andrea Bondavalli2 , Francesco Brancati3 , Bernhard Frömel1(&) , Oliver Höftberger1 , and Sorin Iacob4

1 Institute of Computer Engineering, Vienna University of Technology, Vienna, Austria<EMAIL_ADDRESS><EMAIL_ADDRESS>2 Department of Mathematics and Informatics, University of Florence, Florence, Italy<EMAIL_ADDRESS>3 Resiltech SRL, Pisa, Italy<EMAIL_ADDRESS>4 Thales Netherlands B.V, Delft, The Netherlands<EMAIL_ADDRESS>
# 1 Introduction

The essence of the concept emergence is aptly communicated by the following quote, attributed to Aristotle, who lived more than 2000 years ago: The Whole is Greater than the Sum of its Parts. The interactions of Parts can generate a Whole with unprecedented properties that go beyond the properties of any of its constituent Parts. The immense varieties of inanimate and living entities that are found in our world are the result of emergent phenomena that have a small number of elementary particles at their base.

A System-of-Systems (SoS) consists of a set of autonomous technical systems, called constituent systems (CS) that are independent and provide a useful service to their environment [18]. The purpose of building a System-of-Systems out of CSs is to realize new services that go beyond the services provided by any of the isolated CSs. Emergence is thus at the core of SoS engineering.

A Cyber-Physical System (CPS) is a synthesis of processes in the physical environment and computer systems that contain sensors to observe the physical environment and actuators to influence the physical environment. In most cases, the computer systems are distributed and contain computational nodes connected through networks that realize the information exchange among the nodes. A Cyber-Physical System-of-Systems (CPSoS) is an integration of stand-alone CPSs that provides services that go beyond the services of any of its isolated CPSs.

It is the objective of this chapter to investigate the phenomenon of emergence in CPSoS. In the following section we look at some prior work on emergence in the

This work has been partially supported by the FP7-610535-AMADEOS project.

© The Author(s) 2016

A. Bondavalli et al. (Eds.): Cyber-Physical Systems of Systems, LNCS 10099, pp. 73–96, 2016. DOI: 10.1007/978-3-319-47590-5\_3

domains of philosophy and computer science. Since emergence is always referring to phenomena that occur at a given level of a hierarchic system model, Sect. 3 elaborates in detail on the concept of a multi-level hierarchy. Section 4 presents a definition of emergence in the SoS context and discusses some properties of emergent phenomena. Section 5 introduces a number of examples of emergent phenomena in computer systems. Section 6 discusses some design guidelines that help to detect the potential of emergent phenomena in a CPSoS and mitigate the effects of detrimental emergence. This Chapter terminates with a conclusion in Sect. 7.

#### 2 Related Work

In philosophy the questions of how the diversity of the world emerges out of simple physical building blocks has been a topic of inquiry since the time of the ancient Greeks, leading to abundant literature about emergence, e.g., the survey articles [20, 34] or the books by [4, 6, 16]. Computer scientists got interested in the topic of emergence when it was realized that some striking phenomena that are observed at the system level of complex systems could not be explained by looking at the system's components in isolation. A well-publicized example of such a striking phenomenon is the flash crash of the stock market on May 6, 2010 [2]. Emergence can be regarded as an intriguing part-whole relation that investigates how the properties and the interaction of the parts lead to novel phenomena of a whole.

Holland remarks in [16]: Despite its ubiquity and importance, emergence is an enigmatic and recondite topic, more wondered at than analyzed… It is unlikely that a topic as complicated as emergence will submit meekly to a concise definition and I have no such definition to offer. Fromm [9, 10] elaborates on different forms of emergence and investigates the emergence of complexity in large systems. In [26], Mogul describes emergent misbehavior in a number of computer systems, discusses how emergence can manifest itself, and proposes a research agenda for studying the phenomena of emergence in complex computer systems. In the European Research Project TAREA SoS the current state of the art in the field of SoS has been captured [14] and a roadmap for future SoS research has been proposed. In this roadmap the topics of theoretical foundations of SoSs and of emergence are in a prominent position. In [19], Keating argues for the development of a firm epistemological foundation of emergence in SoSs. In the proceedings of the yearly IEEE conference on Systems of Systems Engineering and the book [18] by Jamshidi relevant contributions to the topic of emergence in SoSs can be found. Parunak and VanderBrok [28] and Huberman and Hogg [17] observed that variable temporal delays play a key role in the generation of emergent misbehavior in an SoS. In [5] Boschetti and Gray elaborate on the limits of insights gained from computer simulations when modeling emergent phenomena in natural systems.

#### 3 Multi-level Hierarchy

The understanding and analysis of the immense variety of things and their behavior in the non-living and living world around us require appropriate modeling structures. Such a modeling structure must limit the overall complexity of a single model and support the step-wise integration of a multitude of different models. One such widely identified modeling structure is that of a multi-level hierarchy, where level-specific rules and laws govern the interdependence of entities at each level of the hierarchy. Since the phenomenon of emergence is always associated with levels of a multi-level hierarchy it is useful to start with a thorough discussion of multi-level hierarchies.

A multi-level hierarchy is a recursive structure where a system, the whole at the level of interest (the macro-level), can be taken apart into a set of sub-systems, the parts, that interact statically or dynamically at the level below (the micro-level). Each one of these sub-systems can be viewed as a system of its own when the focus of observation is shifted from the level above to the level below. This recursive decomposition ends when the internals of a sub-system is of no further interest. We call such a sub-system at the lowest level of interest (the base of the hierarchy) an elementary part or a component.

In his seminal paper The Architecture of Complexity Herbert Simon posits [32] (p. 219): If there are important systems in the world that are complex without being hierarchic, they may to a considerable degree escape our observation or understanding.

Our models of the world of things are organized along such a widely cited Multi– level Material Hierarchy, giving rise to the establishment of dedicated scientific disciplines for each level, e.g.:

#### 3.1 Whole versus Parts

Viewed from the macro-level, the whole is an established entity that encapsulates and hides its parts that interact at the lower level. If the parts at the micro-level that form the whole at the macro level are all identical we talk about a homogeneous structure, otherwise we talk about a heterogeneous structure.

At a given macro-level, we consider the whole as an entity that is surrounded by a surface. Interfaces located at the surface of the whole control the exchange of matter, energy or information among the wholes at the same level.

Koestler [21] (p. 341) has introduced the term holon to refer to the two-faced character of an entity in a multi-level hierarchy. The word holon is a combination of the Greek "holos", meaning all, and the suffix "on" which means part. The point of view of the observer determines which view of a given holon is appropriate in a particular scenario.

Fig. 1. Two-faced character of a holon

Figure 1 gives a graphical representation of the holon. Viewed from the outside at the macro level, a holon is a stable whole that can interact with other holons of that level by an interface across its surface. Viewed from below, the micro-level, a holon is characterized by a set of interacting parts that are confined by the boundaries of the holon. This rigorous enclosure of the parts of a holon at the micro-level is absolutely essential to maintain the integrity of the abstraction of a holon as a whole at the macro level.

Koester states in [21] (p. 343): Every holon has the dual tendency to preserve and assert its individuality as a quasi-autonomous whole; and to function as an integrated part of an (existing or evolving) larger whole. This polarity between Self-Assertive (S-A) and Integrative (INT) tendencies is inherent in the concept of hierarchic order and a universal characteristic of life.

There are two relations characterizing two adjacent levels of a hierarchy: (i) the level relation between the whole at the macro-level and the parts of the micro-level and (ii) the interaction relation among the parts of the micro-level.

#### 3.2 Level Relations

The type of the level relation determines the character of a multi-level hierarchy. In this section we focus on three types of level relations, a nested (or structure) hierarchy, a description hierarchy and a control hierarchy. For the emergence of novel behavior in a CPSoS the control hierarchy is the most important.

Structure Hierarchy. We call a hierarchy a structure (or nested) hierarchy if the whole comprises the parts or, in different wording, the parts are contained in the whole, i.e., consists of (from the top to the bottom) or forms (from the bottom to the top) stand for the level relation of containment.

Structure hierarchies are formed by the identification and classification of the observation of physical structures that are existent in the world of things, irrespective of the subjective view of the observer. These physical structures are often formed by physical force-fields (see also Sect. 3.3, Physical Interactions).

The Multi-level Material Hierarchy referred to in the beginning of Sect. 3 above is an example for a structure hierarchy.

Description Hierarchy. A multi-level hierarchy that describes a set of related entities at different levels of abstraction is called a multi-level description hierarchy. A description hierarchy can be much simpler than the related structure hierarchy provided the structure hierarchy is highly redundant. If a complex structure is completely un-redundant, then it is its own simplest description [32] (p. 221).

We distinguish two types of descriptions, state descriptions and process descriptions. State descriptions describe the state of the world at the instant of observation. Process descriptions explain how a new state of the world unfolds as time progresses that is how the state transitions happen. A description of behavior is a process description.

The classification of entities in a description hierarchy is usually based on cognitive models of the observer and thus may be dependent on the subjective view of the observer. Moreover, depending on the purpose, different levels of description of the same physical structure can be introduced by the observer.

For example, the thermodynamic description of the behavior of a gas is at a higher level of description than the statistical description of the same physical material and the choice among them may depend on the purpose of the description.

If the redundancy of a structure is removed from its description hierarchy, then a significant simplification of the description can be realized (e.g., [32] p. 220).

In case the elements of a hierarchy are constructs, i.e. non-material entities that are the product of the human mind, the assignment of the constructs to hierarchical levels always results in a description hierarchy, the organization of which is determined by the purpose of the observer.

In many, but not in all cases, the description hierarchy of a structure follows the structure hierarchy.

Control Hierarchy. In a control hierarchy the macro-level provides some constraints on the structure or behavior of the parts at the micro-level thus establishing a causal link from the macro level to the micro-level. Constraints restrict the behavior of things beyond the natural laws, which the things must always obey.

In many, but not all cases, the control hierarchy follows the structure hierarchy. Ahl [1] (p. 107) provides the following example: The concept army denotes a structure hierarchy that consists of the soldiers of all ranks and contains them all. In contrast, a general at the top of an army (a military hierarchy) controls the soldiers, but does not contain them.

In some cases, as the example of the military hierarchy above shows, the control constraints originate from outside, i.e. above the macro-level. In other cases, the control constraints have their origin in the whole, i.e. the collective behavior of the parts of the micro-level. It is this latter case that is relevant for the analysis of emergence. Many equivalent examples can be found in Distributed Computing when we have centralized or decentralized control and management. Since behavior (function plus time) is a concept that depends on the progression of time, there is a temporal dimension in control hierarchies that deal with behavior.

#### Since the behavior of the parts forms the behavior of the whole, but the whole can constrain the behavior of the parts we have an example of a causal loop in such a control hierarchy.

We can observe such a causal loop in many scenarios that are classified as emergent in every-day language: the behavior of birds in flocks, the synchronized oscillations of fireflies or the build-up of a traffic jam at a congested highway.

Pattee [30] discusses control hierarchies extensively in The Physical Basis and the Origins of Hierarchical Control. In order to support the simplification at the macro-level and establish a hierarchical control level, a control hierarchy must on one side abstract from some degrees of freedom of the behavior of the parts at the micro-level but on the other side must constrain some other degrees of freedom of the behavior of the parts, i.e., a control hierarchy must provide constraints from above, while, in a multi-level material hierarchy the natural laws provide constraints from below.

The delicate borderline between the constraints from above on the behavior of the micro-parts and the freedom of behavior of the micro-parts is decisive for the proper functioning of any control hierarchy.

There are two extremes of control which lead to a collapse of the control hierarchy: (i) full control from above which defeats the principle of abstraction of control and leads to a full deterministic behavior and (ii) no constraints from above which can lead to unconstrained chaotic behavior (see Fig. 2).

For example, a good conductor of an orchestra will control the tempo of the performance without taking away the freedom from the musicians to express their individual interpretation of the music.

Fig. 2. Self assertiveness of a holon

#### 3.3 Interaction Relations

Formal Hierarchy. Simon [32] (p. 195) calls a hierarchy a formal hierarchy if the interaction relation is empty, i.e., the parts are only related to the whole of the higher adjacent level. If, in the above example, the soldiers relate at a given level only to their boss, but not to each other, then we have an example of a formal hierarchy. Models that have the structure of a formal hierarchy are rare.

Physical Interactions. The physical interactions at any considered level of a material hierarchy can be classified in the following three dimensions: (i) distance among the parts, (ii) force fields among the parts and (iii) frequency of interactions among the parts. In general, as we move up the levels of a material hierarchy the distance increases, the force-field magnitude decreases and the frequency of interactions decreases [32].

Simon argues that the laws that govern the behavior at each level are nearly independent of the level above and below, giving rise to the principle of near decomposability [32] (p. 209) of levels.

This principle of near decomposability states that an approximate model suffices in most cases to model the behavior at any given level of a multi-level hierarchy.

This approximate model considers only the physical interactions at the considered level and abstracts from the behavior of the high-frequency parts at the level below and considers the dynamic parameters of the low frequency parts at the level above that provide the constraints as constants.

Informational Interactions. Informational interactions exchange information among the communicating partners. When the information exchanged consists of data and an explanation of the data we observe the exchange of Itoms.

Itom: An Itom is an atomic unit of object data and meta data. The object data represents some semantic content, and the meta data provides an explanation of the object data, i.e., how the semantic content represented by object data can be accessed. The semantic content of (or the information contained in) an Itom reports about a timed proposition relating to some entities in the world [23].

In a Cyber-Physical System-of-Systems (CPSoS) we distinguish between two types of informational interactions: (i) message-based information interactions in cyber space and (ii) stigmergic information interactions in the physical world.

Interactions in the cyber space allow in principle the exchange of explicitly defined Itoms which travel unmodified (invariant semantic content) from a sender to a set of receivers. Stigmergic interactions are indirect and involve influencing the state of the common environment of senders and receivers. Such environment may also be under the possible influence of environmental dynamics. Environmental dynamics are autonomous processes in the environment (physical world or cyber space) that also act on the state of the environment. Consequently, in stigmergic interactions it is – in many cases – not possible to send the same Itom from sender to receivers. Instead very often receivers will only be able to observe object data which is (more or less closely) related to the original data sent and needs to be correctly interpreted to avoid property mismatch. A model of the environmental dynamics able to represent the processing and modifications performed on data would be paramount in the understanding and mastering of stigmergic information exchange.

In cyber space data is represented by a bit-pattern that can be generated by the processing of stored Itoms or by some data acquisition process, e.g., by a sensor. For data acquisition, the design of the sensor determines how the acquired bit pattern has to be interpreted, i.e., provides for the explanation of the object data.

Since an Itom is a higher-level concept than the sole object data in an Itom, we propose to use Itoms in the specification of Relied-Upon Interfaces (RUIs) among the Constituent Systems (CSs) of a CPSoS (see Chap. 2). According to [23] the full specification of an Itom has to provide answers to the following questions:

Message-based Information Flows: A message-based information flow is present if one CS sends a message to another CS. In many legacy distributed systems only object data is contained in a message while the explanation of the data is derived from the context.

In a CPSoS the involved CSs can be operating in differing contexts, e.g., in the US and Europe. For example, in the US temperature is represented by degrees Fahrenheit, while in Europe temperature is represented by degrees Celsius. As a consequence, the same data (bit-patterns) can convey a different meaning if the contexts of the sender differs from the context of the receiver of the message, causing a property mismatch. Such property mismatches have been the cause of severe accidents.

Stigmergic Information Flows: A stigmergic information flow is present if one sending CS acts on the physical environment and changes the state of the environment and later on another receiving CS observes the changed state in the environment with a sensor that captures the sensor specific aspect of the environment [24]. Consider, for example, the coordination of cars on a busy highway to realize a smooth flow of traffic. In addition to the direct communication by explicit signals among the drivers of the cars (e.g., the blinker or horn), the stigmergic information flow based on the observation of the movement of the vehicles on the road (caused by the actions of other drivers) is a primary source of information for the assessment of a traffic scenario. An important characteristic of stigmergic information flows is the consideration of up to date environmental dynamics.

Hidden Channels. There exist many indirect information flows, in particular stigmergic ones, which remain both (i) unknown to the sender which is not aware of the flow, and (ii) are not captured by systems designers or modelers. We call such existing interaction relations hidden channels.

Hidden channels are problematic, because they can contribute to the generation of causal loops (and therefore take active part in the rise of emergent phenomena). In addition, these causal links may lead to a modification of the understood holarchy abstraction, i.e., parts of one level interact directly with parts of another level which may establish hidden level relations (e.g., a control hierarchy). Effects of such modification of the holarchy abstraction may cause both unintended information leakage (violations of security properties) and unexpected negative emergence.

Usually it is difficult to protect the state of the physical environment regarding observations of receivers. Additionally, in many cases a sender may be even unaware of leaking information to its environment. For example, consider security attacks based on observing the electromagnetic emissions of a processor on smart cards [11].

Still, hidden channels should be avoided by properly identifying them (see Sect. 6.1) or insulating against them (e.g., firewalls, physical insulation).

#### 4 Emergence

It is quite common, as we move up a multi-level hierarchy, that novel phenomena can be observed at a given level that are not present at the level below. We call these new phenomena emergent phenomena. We use the term phenomenon as an umbrella term that can refer to structure, behavior or property.

In many cases the laws that explain the genesis of these emergent phenomena are formulated post facto because it would require a very knowledgeable mind to predict a priori all possible phenomena that can come into existence out of the interactions of many given parts. The first appearance of an emergent phenomenon is often a surprise to a human observer.

#### 4.1 Definition of Emergence

In order to achieve a level of objectivity we aim for a definition of emergence that is based on a property of the scenario and not on a relation between the scenario and the observer.

Let us analyze the relationship between two adjacent levels of a multi-level hierarchy, the micro-level (the level of the parts) and the macro-level (the level of the whole) where emergent phenomena are observed, assuming that the level relation is given. We restrict our analysis to these two levels and disregard the case where some properties of the parts are themselves emergent with respect to their lower-level parts. Our definition of emergence in a Cyber-Physical Systems-of-Systems is the result of many interdisciplinary discussions during the AMADEOS Workshop on Emergence in Cyber-Physical Systems-of-Systems [15].

#### A phenomenon of a whole at the macro-level is emergent if and only if it is of a new kind with respect to the non-relational phenomena of any of its proper parts at the micro level.

A phenomenon is of a new kind if the concepts required to explain this phenomenon cannot be found in the world of the isolated parts. Conceptual Novelty is thus the landmark of our definition of emergence.

Note that, according to the above definition, the emergent phenomena must only be of a new kind with respect to the non-relational phenomena of the parts, not with respect to the knowledge of the observer. If a phenomenon of a whole at the macro-level is not of a new kind with respect to the non-relational phenomena of any of its proper parts at the micro level then we call this phenomenon resultant.

The essence for the occurrence of emergent phenomena at the macro-level (the SoS level) lies in the interactions of the parts at the micro-level, i.e., in the spatial arrangement of the parts caused by physical force-fields and/or the designed temporal informational interactions among the parts at the micro-level.

In CPSoS, the phenomenon we are interested in is behavior. In a CPSoS the observable behavior of a system is the temporal sequence of observable states of the system in the Interval of Discourse. We are thus interested in diachronic emergence, where initial interactions of the parts at the micro-level precede the appearance of the emergent phenomenon at the macro level.

We assume that the temporal distance between two observation instants of an observer is a multiple of a smallest duration. This smallest temporal distance expresses the grain of observation of this particular observer. If the duration of a state is shorter than the grain of observation then this short-lived state may evade the observations of this observer. The duration of the grain of observation should be selected on the basis of the purpose of the observer, the dynamics of the observed system and the minimal response time of the entities at the chosen level of observation.

Some scientists posit that emergent behavior is connected with a surprise of the observer [31]. According to this view, emergence occurs, if the causal link between the interactions of the parts and the behavior of the whole is non obvious to the observer (and therefore a surprise to the observer). According to this definition, the state of knowledge of the observer is the decisive criterion for the classification of a phenomenon as emergent. As a consequence, different observers with different states of knowledge will judge the same phenomenon differently. It follows that emergence is considered a relation between the whole and the observer and not a property of the whole.

#### 4.2 Explained vs Unexplained Emergence

At first we pose the question whether emergent properties are reducible to the properties of the parts considered in isolation.

The following quote about Scientific Reduction is taken from the Stanford Encyclopedia on Philosophy:

The term 'reduction' as used in philosophy expresses the idea that if an entity x reduces to an entity y then y is in a sense prior to x, is more basic than x, is such that x fully depends upon it or is constituted by it. Saying that x reduces to y typically implies that x is nothing more than y or nothing over and above y.

In an artifact, such as a CPSoS, emergent properties appear at the macro-level if the parts at the micro-level interact according to a design provided by a human designer this is more than the parts considered in isolation. It follows that emergent properties in a CPSoS are not reducible to the parts considered in isolation.

According to our definition of emergence in Sect. 4.1, a novel phenomenon is considered emergent, irrespective of whether it can be explained how the new phenomenon at the macro level has developed out of the parts at the micro-level. Given the present state of knowledge, some of these emergent phenomena can be explained by existing theories while there are other emergent phenomena where at present no full explanation can be given as to how they developed. Examples for (as of today) unexplained emergence are the generation of life or the generation of the mind on top of the neurons in the brain.

But what constitutes a proper scientific explanation? Hempel and Oppenheim [13] (p. 138) outlined a general schema for a scientific explanation of a phenomenon as follows:

#### **Given**  *Statements of antecedent conditions*  **and** *General Laws*  **then a logical deduction of the**  *Description of the empirical phenomenon to be explained*  **is entailed***.*

The antecedent conditions can be initial conditions or boundary conditions that are unconstrained by the general laws.

The general laws can be either universally valid natural laws that reign over the behavior of things or logical laws describing a valid judgment in the domain of constructs. Natural laws do not change in time or have a memory of the past. A natural law, such as a physical law, must hold everywhere, no matter what level of a multi-level hierarchy is the focus of the investigations.

A weaker form of explanation is provided if the general laws in the above schema are replaced by established rules. There are fundamental differences between general laws and established rules. General laws are inexorable and universally valid while established rules are structure dependent and local. Rules about the behavior of things are based on more or less meticulous experimental observations. A special case is the introduction of imposed rules, e.g., the rules of an artificial game, such as chess. The degree of accuracy and rigor of various established rules differ substantially.

It thus follows that between the two extremes of scientifically explained and not explained at all there is a continuum of explanations that are more or less acceptable and are relative with respect to the general state of knowledge and the opinion of the observer at a given point in time.

#### 4.3 Conceptualization at the Macro-level

According to our definition of emergence, novel concepts should be formed and new laws may have to be introduced to be able to express the emerging phenomena at the macro level appropriately. Note that the emergent phenomena and laws must be new w. r.t. the phenomena of the isolated parts, but not necessarily new with respect to the knowledge of the observer, i.e., such phenomena are emergent irrespective of the state of knowledge of the observer.

In the history of science, many novel laws that employ new concepts have been introduced to capture the newly observed regularities of phenomena at a macro-level. We call such a new law that deals with the emerging phenomena at a macro level an intra-ordinal law [27]. At a later time, some of these laws have been reduced to well-understood effects of the parts at the adjacent micro-level, e.g., the thermodynamic theory of a gas can be explained by the statistical theory of gas [3].

Since the concepts at the macro level are new with respect to the existing concepts that describe the properties of the parts, the established laws that determine the behavior of the parts at the micro-level will probably not embrace the new concepts of the macro-level. Therefore, it is often necessary to formulate inter-ordinal laws (also called bridge laws) to relate the established concepts at the micro-level with the new concepts of the macro-level.

The proper conceptualization of the new phenomena at the macro level is at the core of the simplifying power of a multi-level hierarchy with emergent phenomena.

Let us look at the example of a transistor. The transistor effect is an emergent effect caused by the proper arrangement of dopant atoms in a semiconducting crystal. The exact arrangement of the dopant atoms is of no significance as long as the provided behavioral specifications of a transistor are met. In a VLSI chip that contains millions of transistor, the detailed microstructure of every single transistor is probably unique, but the external behavior of the transistors (the holons) is considered the same if the behavioral parameters are within the given specifications. It is a tremendous simplification for the designer of an electronic circuit that she/he does not have to consider the unique microstructure of every single transistor.

#### 4.4 Downward Causation

In classical physics, the concept of causation links an effect to an earlier cause. If in the domain of Newtonian mechanics precisely defined initial conditions (the cause) are given, an object will move along a trajectory (the effect) that is fully determined by the differential equations that express the laws of macro-mechanics. However, in the domain of micro-mechanics, where quantum-physical laws reign, it is not possible to observe the initial conditions of an object without influencing the object of observation. This is one of the reasons, why the concept of unidirectional causation is highly debated in the modern sciences. Another reason pertains to the multitude of parameters, captured in the notion of a causal field that characterizes the causes of real-life phenomena. It is often up to subjective judgment to determine which one of these many causes is considered the most prominent cause.

On the other side, the unidirectional cause-effect relation plays a prominent role in our subjective models of the world in order to realize intended effects or to avoid the causes of undesired effects. To quote Pattee [29] (p. 64 onwards): I believe the common everyday meaning of the concept of causation is entirely pragmatic. In other words, we use the word cause for events that might be controllable… the value of the concept of causation lies in its identification of where our power and control can be effective. … when we seek the cause of an accident, we are looking for those particular focal events over which we might have had some control. We are not interested in all those parallel subsidiary conditions that were also necessary for the accident to occur, but that we could not control... .

Along this line of reasoning the term downward causation denotes the concept that the whole at the macro-level can constrain or even control the behavior of the parts at the micro-level (the level below).

Downward causation is a difficult concept to define precisely, because it describes the collective, concurrent, distributed behavior at the system level. … Downward causation is ubiquitous and occurs continuously at all levels, but it is usually ignored simply because it is not under our control. … The motion of one body in an n-body model might be seen as a case of downward causation [29] (p. 64).

Downward causation establishes a causal loop between the micro-level and the adjacent macro level. The interaction of the parts at the micro-level causes the whole at the macro-level while the whole at the macro-level constrains the behavior of the parts at the micro-level (see also Sect. 5.2). We conjecture that in a multi-level hierarchy emergent phenomena are likely to appear at the macro-level when there is a causal-loop formed between the micro-level that forms the whole and the whole (i.e., the ensemble of parts) that constrains the behavior of the parts at the micro-level.

In a system that exhibits downward causation the degrees of freedom of the parts that can be exploited at the micro-level, e.g., by mechanisms of self-organization are limited by:

Note that in a concrete system, some of these categories can be empty. For example, in a hierarchy of constructs there is no upward causation, i.e. constraints on the parts from below caused by natural laws.

In our opinion the exclusion argument by Kim [20] —that in a system with downward causation macro causal powers compete with micro causal powers and, if this is the case, micro causal powers will always win, needs to be reconsidered since the macro causal powers and the micro causal powers restrict different degrees of freedom of the parts and are thus not in conflict.

Another different way in which emergence is observed in practice in the real world also is the one caused by a Cascade effect [8]. A cascade effect exists, if in a system with a multitude of parts at the micro level a state change of a part at the micro-level causes successive state changes of many other parts at the micro level. The cumulative effect of the totality of these state changes results in a novel phenomenon, such as an avalanche or a nuclear explosion. An epidemic is also a good example for a cascade effect. Cascade effects are diachronic, since they develop over time.

There may be other mechanisms that lead to emergent phenomena that we have not yet identified.

#### 4.5 Supervenience

The principle of Supervenience [25] establishes an important dependence relation between the emerging phenomena at the macro-level and the interactions and arrangement of the parts at the micro-level. Supervenience states that

Sup\_1: a given emerging phenomenon at the macro level can emerge out of many different arrangements or interactions of the parts at the micro-level while

Sup\_2: a difference in the emerging phenomena at the macro level requires a difference in the arrangements or the interactions of the parts at the micro level.

Because of Sup\_1 one can abstract from the many different arrangements or interactions of the parts at the micro level that lead to the same emerging phenomena at the macro level—see the example of the transistor above. Sup\_1 entails a significant simplification of the higher-level models of a multi-level hierarchy.

Because of Sup\_2 any difference in the emerging phenomena at the macro level can be traced to some significant difference at the micro level. Sup\_2 is important from the point of view of failure diagnosis.

#### 4.6 Classification of Emergence

Figure 3 depicts a schema for the classification of emergent phenomena.

In a CPSoS the CSs interact, i.e., via message-based channels in cyber space in which they exchange Itoms, and interact also via stigmergic channels information flows in the

Fig. 3. Classification of emergent phenomena

physical world. These interactions can give rise to emergent behavior at the level of CPSoS. Although this behavior is explainable in principle, we may not be able to explain or predict this behavior in practice due to our ignorance about the full scope of the CPSoS, the precise temporal interactions among the CS (see e.g. the deadlock example in Sect. 3.5) and hidden communication channels behind the interfaces of a CS.

#### 5 Examples of Emergence in Computer Systems

In this Section we discuss a number of examples of emergent behavior in computer systems. The first four examples can be explained, while the fifth example, the Flash Crash of the stock market on May 6, 2010 [2], although explainable in principle has not been explained in practice up to today.

#### 5.1 Deadlock in Computer Systems

In some publications, the occurrence of a deadlock in a computer system is called an emergent phenomenon [12]. With the advent of multi-programming computer systems, the following event has been occasionally observed: when executing a number of processes concurrently, the system comes to a permanent halt, although each process, executed in isolation executes flawlessly. At first, this phenomenon could not be explained and was considered a surprise. Later on (around the year 1970) a full explanation of this phenomenon, called deadlock, was given [7]. The following simple example of Fig. 4 explains the essence of the phenomenon deadlock.

Let us consider the execution of a seat reservation system (cf. Fig. 4) in an ideal world, where no failures of the computer hardware will ever occur. As long as only a

finite number of reservation processes of Type A are executed concurrently, the system will operate flawlessly forever. The same will happen if only a finite number of reservation processes of Type B execute concurrently. However, if a finite number of processes of Type A and processes of Type B operate concurrently, the system will sometimes stop forever (deadlock). Stopping forever is the novel phenomenon that is not happening if processes of Type A or processes of Type B operate in isolation.

In the program sketch of Fig. 4 there are two semaphore variables, Smoney and Sseat initialized with the value 1. Whenever a process executes a Wait operation on a semaphore variable, the process is only allowed to enter the following Critical Section if the value of the semaphore variable is positive at the start of execution of the atomic operation Wait. The atomic operation Wait tests the value of the designated semaphore variable. In case the test gives a positive value, it decreases the value of the semaphore variable by 1 and enters the Critical Section. Otherwise it waits until the value of the semaphore variable gets positive. The semaphore operation Signal, executed at the end of a Critical Section, increases the value of the designated semaphore variable by 1 and thus enables another waiting process to enter the Critical Section.

In Fig. 4, the semaphore Smoney ensures that in the following Critical Section, dealing with the money only a single process is allowed to execute at an instant. Likewise, the semaphore variable Sseat ensures that in the following Critical Section dealing with the seat allocation only a single process is allowed to execute at a time. As long as processes of type A execute concurrently, the execution of Wait(Smoney) is always followed by Wait(SSeat).

However, if the executions of processes of Type A and Type B are interleaved, then it can happen that a process of Type A enters the Critical Section protected by Smoney and, before the process of Type A executes the operation Wait(SSeat) a process of Type B enters its critical Section protected by Sseat. From now on, a deadlock is unavoidable if the money and the seat are available, since both processes have to wait forever on the release of the respective following Critical Section.

The observed phenomenon of deadlock fulfills the requirement of an emergent phenomenon:

It is important to note that although this phenomenon is fully explainable it is not predictable, even in theory. If two processes try to execute the same semaphore operation exactly simultaneously, the underlying hardware enters into a state of metastability [33] (p. 77). It is not predictable, even in theory, which one of the two simultaneous processes will win this race.

It is also revealing to look at the problem of deadlock from the point of view of determinism. Although each one of the individual processes, the parts, behaves deterministically the behavior of the overall system, the whole, is non-deterministic.

#### 5.2 Distributed Fault-Tolerant Clock Synchronization

In a time-triggered distributed computer system computational and communication processes are triggered by the progression of a global notion of physical time. This global notion of physical time must be fault-tolerant in order to mitigate the effects of a failing physical clock.

A distributed fault-tolerant synchronization algorithm constructs the fault-tolerant global time. Such an algorithm comprises the following three phases [22] (p. 69):

According to the theory of clock synchronization the number N of clocks in a system must be larger than 3 k, where k is the number of faulty clocks i.e., N ≥ (3k + 1).

A physical clock is a device that contains a physical oscillator (e.g., a crystal) and a counter that counts the number of ticks of the oscillator and thus contains the state of the clock. The frequency of the physical oscillator is determined by the laws of physics and depends on the size of the crystal and environmental conditions, such as temperature or pressure—a case of upward causation. The speed of the oscillator cannot be modified by downward causation. However, the state of the clock is modified by downward causation in step iii of the algorithm.

The phenomenon fault-tolerant clock synchronization fulfills the requirement of an emergent phenomenon:

This example of emergence is interesting from the point of view of how upward causation (the frequency of a physical clock) and downward causation (the periodic correction of the state of a clock caused by the time value calculated by the ensemble of clocks at the macro level) interact and form a causal loop.

#### 5.3 Alarm Processing

In an industrial plant an alarm is triggered when the value of a significant state variable exceeds a preset threshold limit. There may be thousands of significant state variables that are monitored in a large industrial plant. Since a single serious fault may cause a correlated alarm shower an alarm processing system must reduce the alarm rate at the operator interface to a manageable level in order to avoid an operator overload. The alarm processing system establishes the causal dependencies of alarms and decides which alarms can be hidden from the operator.

An alarm processing system consists of distributed sensors that can detect alarms and send alarm messages, a communication system that transports the alarm messages to an alarm processing center and the alarm analysis software that decides which alarm to hide.

Alarms are events that happen infrequently in normal operation. Many communication protocols for the transport of the alarm messages are of the PAR (Positive Acknowledgment of Retransmission) type for the transmission of event messages. The PAR protocol contains a retransmission mechanism to resend a message in case the previously sent message is not acknowledged in due time. Under heavy load, this mechanism can lead to a cascade effect

In the case of a correlated alarm shower that arises from a single serious fault, the event-triggered communication system slows down because the increased load on a finite capacity channel causes a delay of some messages. This slow-down induces the retransmission mechanism to kick in and to increase the load on the communication system even further. This can lead to a collapse called thrashing—an emergent phenomenon.

#### 5.4 Conway's Game of Life

Conway's Game of Life is a simple cellular automaton. It is played on a set of cells organized in a square array. Since there are no things involved, there is no upward causation from natural laws.

The simple rules of Conway's game of life are shown in Fig. 5. A player can select the initial conditions, i.e. the initial marking of the cells on the square array, as he/she pleases. After a round of updating all cells according to the transition rules, a new marking on the square array comes into sight. This marking forms the initial conditions for the following round, etc. Given defined initial condition, the series of states that develop is deterministic.

Let us choose the pattern for the initial conditions as shown in the left upper corner of Fig. 5. If all other cells of the square array are empty, then a phenomenon called glider appears.

If we select a grain of observation that observes the evolving patterns on the square array only after every four rounds then we clearly see the glider moving down diagonally along the square array. Holland calls this an emergent phenomenon [16].

#### 5.5 Stock Market Crash on May 6, 2010

In today's electronic financial markets, an electronic trader can execute more than 1000 trades in a single second. The actions of a multitude of human traders and automated trading systems at the micro-level cause the valuation of the assets at the macro level which in turn influences the actions of the human traders and the algorithms of the automated trading systems, thus forming causal loops and cascade effects that can result in emergent misbehavior.

Aldrich et al. [2] reports about such a misbehavior of the stock market, called the Flash Crash on May 6, 2010: "… in the span of a mere four and half minutes, the Dow Jones Industrial Average lost approximately 1,000 points."

"As computerized high-frequency traders exited the stock market, the resulting lack of liquidity causes shares of some prominent companies to trade down as low as a penny or as high as \$100.000" (N.Y Times, October 1, 2010)

About half an hour after the start of the Flash Crash, the stock market stabilized at a level that was significantly below the pre-crash valuation, destroying billions of dollars of equity.

The Flash Crash raises difficult, policy-relevant questions of causation. As is the case with most market events, the circumstances of the Flash Crash cannot be reconstructed because a detailed record of the precise temporal order of all relevant events is not available. This "Flash Crash" occurred in the absence of fundamental news that could explain the observed price pattern and is generally viewed as the result of endogenous factors related to the complexity of modern equity market trading Aldrich et al. [2].

Analysts lack access to the specifications of the automated trading algorithms that were active in the markets prior to and during the crash, and cannot replicate the strategies implemented by human traders active during the relevant period. Intense investigations and congressional hearings followed, but conclusive evidence is still missing six years after the crash. Although the sequence of events that caused the Flash Crash is explainable in theory it cannot be reconstructed in practice due to the concurrency and ignorance about the immense multitude of interacting transactions.

# 6 Consequences for CPSos Design

In CPSoS design not all the combinations allowed by Fig. 3 are of interest, in fact we are particularly interested in the behavior domain, i.e., behavioral emergence. Figure 6 classifies the emergent behavior of a CPSoS from the point of view of the consequences of this behavior on the overall mission of a CPSoS and from the prediction or awareness we may have on the appearance of emergent behavior.

Expected and beneficial emergent behavior is the normal case (quadrant 1) that results from a conscious design effort. Unexpected and beneficial emergent behavior is a positive surprise (quadrant 3). Expected detrimental emergent behavior can be avoided by adhering to proper design rules (quadrant 2). The problematic case is quadrant 4, unexpected detrimental emergent behavior.

In safety-critical CPSoSs, an unexpected detrimental emergent behavior can be the cause of a catastrophic accident. But how can we detect and avoid an unknown and therefore unexpected emergent phenomenon?

Fig. 6. Contribution of emergent behavior

Clearly a conscious and aware design discipline aims to move, as knowledge progresses, more and more emergent phenomena from quadrant 4 to quadrant 2, in which provisions can be taken to mitigate, eliminate or prevent detrimental emergence. To exemplify just observe that while at its first manifestation deadlock was a problematic issue in distributed systems, today every computer student is though many of the different ways we have developed to properly address it.

Still our knowledge regarding CPSoS may remain limited and our ignorance about them can hardly be sufficiently reduced especially when we consider COTS components and legacy constituent systems. In fact, most CPSoS are built incorporating such LEGACY and COTS on which very little is known and where the information flow is often quite hidden.

In the remainder of this section we will focus on quadrant 4, the problematic case of detrimental unexpected emergent with special regards to undiscovered emergent phenomena never seen before.

#### 6.1 Exposure of the Direct and Indirect Information Flow

In a CPSoS emergent behavior is the result of direct or indirect flow of information among the constituent systems.

At design time, the planned message-based, stigmergic and sometimes human information flow patterns should be analyzed in order to find potential causal loops and cascade effects. However, this analysis has limits where part of the information flow is hidden behind the interface of a CS whose interface model is incomplete because it abstracts from the details of the world behind the interface.

At run time, the actual information flow should be observed without the probe effect and documented with precise timestamps such that the temporal order of events can be reconstructed in a post hoc analysis of a scenario to establish the precise sequence that led to detrimental emergent behavior. This POST MORTEM analysis would be particularly useful to discover and explain new (just encountered) emergent phenomena. Actually such analysis, coupled with disclosure of the internal algorithms used for automatic trading would have allowed to explain the Stock Market Crash (Sect. 5.5).

#### 6.2 Safety-Critical Systems

The behavior of a safety-critical system should conform to the design model that is the basis of the safety argument. The design model does not and cannot take into account unknown emergent effects that can cause a deviation of the actual behavior from the intended behavior.

Since in safety-critical CPSoS even a very small probability for a detrimental emergent phenomenon cannot be tolerated, it is proposed that the evolving state of a safety-critical CPSoS is meticulously monitored by an independent monitor component in order to detect the onset of an unexpected deviation of the actual state from the intended state. This deviation can be an indication for the start of an unknown (and therefore unexpected) detrimental emergent behavior. The system internal information flow to the monitoring system must operate in real-time in order that the monitor can act promptly. Since emergent behavior is diachronic, (i.e. it develops over time) an independent meta (monitoring) system that continually observes the evolving state of the object system can detect the early onset of a deviation and thus provide an immediate warning of a forthcoming disruption due to an emergent phenomenon. Based on this immediate warning, mitigating actions can be activated that bring the object system back to normal operation or at least to a safe state.

It is important to note that the monitoring system should be state-based, and not process-based. A state-based monitoring system acts on a higher-level of abstraction than a process-based system since it is concerned with the properties of the states of a system only and not with the much more involved processes that generate the state changes. A state-based monitoring system is thus much simpler than a process-based monitoring system. This fundamental difference between a state based and a process-based system is also important from the point of view of design diversity to detect hidden software errors.

Taking again the example of the Stock Market Crash (Sect. 5.5), if an independent monitoring system (without knowledge of the trading algorithms) had continually observed significant parameters that are relevant indicators of the market state and it had acted in the sub-millisecond range to stop the trading activities (safe state) the flash-crash that disrupted the market and wiped out billions of dollars of equity could have been avoided.

# 7 Conclusions

The purpose of building a Cyber-Physical System-of-Systems out of Constituent Systems (CSs) is to realize new services that go beyond the services provided by any of the CSs in isolation. Emergence is thus at the core of CPSoS engineering. In this Chapter we have surveyed some of the abundant past literature on emergence from the fields of philosophy and computer science, looked at the characteristics of multi-level hierarchies, developed a CPSoS definition of emergence and analyzed some examples of emergent behavior in computer systems.

We identified the basic mechanism that can lead to emergent phenomena: causal loops between the macro-level and the micro-level of a multi-level hierarchy (with the variant of cascade effects) that result in conceptually novel phenomena. We came to the conclusion that due to the ignorance about the scope of CPSoS even a thorough design analysis cannot uncover all potential mechanisms that can result in unexpected emergent phenomena at run-time. Unexpected emergent phenomena manifest themselves in a CPSoS by a diachronic deviation of the actual behavior from the intended (design) behavior.

Since unknown emergent effects can be the cause of a deviation of the actual behavior from the intended behavior, the meticulous observation of the behavior of a safety-critical CPSoS by an independent monitoring system can detect the onset of diachronic emergence and initiate mitigating actions before the detrimental emergent phenomenon has fully developed.

#### References

Open Access This chapter is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, duplication, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the work's Creative Commons license, unless indicated otherwise in the credit line; if such material is not included in the work's Creative Commons license and the respective action is not permitted by statutory regulation, users will need to obtain permission from the license holder to duplicate, adapt or reproduce the material.

# AMADEOS SysML Profile for SoS Conceptual Modeling

Paolo Lollini1(&) , Marco Mori1 , Arun Babu2 , and Sara Bouchenak3

> 1 Department of Mathematics and Informatics, University of Florence, Firenze, Italy<EMAIL_ADDRESS>2 Resiltech SRL, Pisa, Italy<EMAIL_ADDRESS>3 Université Grenoble Alpes, Grenoble, France<EMAIL_ADDRESS>
# 1 Introduction

In the European Union FP7-610535-AMADEOS project, a conceptual model for Systems of Systems (SoSs) has been conceived to find a common language allowing experts to collaborate on modelling, engineering, and analyzing SoSs (see public deliverable D2.3 "AMADEOS conceptual model - Revised" [1]).

Analogously to the conceptual model for the architecture of software intensive systems, we separated the description of basics SoS concepts into different perspectives. These perspectives are called viewpoints, each of which is focused on different concerns of the SoS: structure, evolution, dynamicity, dependability, security, time, multi-criticality and emergence.

© The Author(s) 2016

This work has been partially supported by the FP7-610535-AMADEOS project.

A. Bondavalli et al. (Eds.): Cyber-Physical Systems of Systems, LNCS 10099, pp. 97–127, 2016. DOI: 10.1007/978-3-319-47590-5\_4

In this chapter we will focus on the basic SoS concepts belonging to the different viewpoints and on their semantic relationships, and we will present a SysML profile to represent the conceptual model.

The rest of this chapter is structured as follows: Sect. 2 presents the different concepts defined in a SysML profile to model an SoS. Section 3 describes the structural properties of an SoS in term of architecture, communication and interface. Section 4 defines the concept of evolution related to all changes of an SoS. Section 5 presents the concept of dynamicity that represents the variation to the operation of an SoS considered at design time. Section 6 describes the concepts related dependability, security and multi-criticality aspects. Section 7 describes the global notion of time exploited in an SoS, while Sect. 8 defines the concept of emergence of novel phenomena at the SoS level. Then, Sect. 9 introduces a concrete case study to illustrate the application of basic SoS concepts. Lastly, Sect. 10 provides a brief overview of related works before the conclusion in Sect. 11.

# 2 Conceptual Modeling Support: The AMADEOS SysML Profile

This section focuses on the definition of a SysML profile as a modeling support for representing the basic concepts for SoS and their relationships. Following the viewpoint-driven approach previously introduced, the concepts and their relationships have been modeled using a SysML semi-formal representation, organized in a profile1 composed by viewpoint-related packages. To this end, we have defined specific constructs and we have exploited already implemented stereotypes available in other related profiles to support specific viewpoints. Our proposed profile is meant to be used by designers in describing the static SoS structure and its dynamic behavior according to the introduced viewpoints. Such an SoS description can be adopted to be kept consistent across viewpoints by tools and for machine-assisted cross-viewpoint analyses (e.g., finding detrimental emergent SoS behavior).

The SoS profile will be used as an abstract model to represent the topology and the state evolution of an operational SoS. The profile diagrams contain the SoS basic concepts distributed in sub-packages as follows:

1 https://github.com/AMADEOSConceptualModel/SysMLProfileAndApplication.git - GitHub public link to the AMADEOS SysML profile and the Smart Grid application.

It is worth noticing that most of the above packages come from a direct mapping to the views previously defined except for SoS Architecture, SoS Communication and SoS Interface that all together implement the Structure view, and for SoS Dynamicity and SoS Scenario-based reasoning that map into the Dynamicity view.

We have implemented the whole profile by exploiting the Eclipse integrated development environment, jointly with Papyrus. Eclipse is an open source environment and offers all the related advantages in terms of cost, customizability, flexibility and interoperability. Papyrus is an Eclipse plugin, which offers a very advanced support to define UML profiles.

In the following sections, we will discuss the key elements of the conceptual model for each identified viewpoint. All the new introduced stereotypes extend the "Block" stereotype of SysML, if not differently specified. For the sake of readability, we will not represent such relations in the SysML diagrams describing the different packages.

#### 3 Structure Viewpoint

The viewpoint of structure represents architectural concerns of an SoS. In particular, it defines the manner in which CSs are composed [17] and how do they exchange semantically well-defined messages [10] through their interfaces [22].

The static structure of an SoS is based on the concept of a Constituent System (CS), which is 'An autonomous subsystem of an SoS, consisting of computer systems and possibly of a controlled objects and/or human role players that interact to provide a given service'. A CS exchanges information that is either represented by things/energy or data with its environment by means of interfaces. The environment of a CS includes all entities that are able to interact with the CS, including other CSs. In our context, information is a proposition about the state of or an action in the world, which is either an attribute of a physical thing (e.g., temperature of a room) or an attribute of an abstract construct (e.g., execution time of a program).

The interfaces among which the CSs interact one another are the Relied Upon Interfaces (RUIs). As such, the CS service – which is its intended behavior – is provided at this interface. RUI is further structured in the Relied Upon Message Interface (RUMI) and the Relied Upon Physical Interface (RUPI). RUMI allows for message-based communication of CSs over cyberspace (e.g., the Internet) while RUPI enables the indirect physical exchange of things or energy among CSs over their common environment. It consists of sensors and actuators that take and time-stamp observations of and/or act at a defined deadline on some physical state (e.g., the temperature of a room) in the physical environment according to their design. Environmental dynamics (e.g., heat dissipation through walls) act additionally to other CSs on the physical state. CSs that interact with each other over a common physical environment establish a stigmergic channel, i.e., they communicate indirectly over influencing and measuring the physical state. For more details on the interface topic, please refer to [11], and Chapter 2 of this book.

The profile supports the description of the static and dynamic structure of an SoS representing: the basic architectural elements and their semantic relationships; the sequence of messages exchanged among CSs in an SoS; the points of integration, i.e., interfaces, allowing the exchange of information/energy among connected entities.

The structural properties of an SoS are described using three different packages "SoS Architecture" (Sect. 3.1), "SoS Communication" (Sect. 3.2), and "SoS Interface" (Sect. 3.3). The first defines Stereotypes useful to describe the topology of an SoS; the second provides Stereotypes to describe the communication aspects between the Constituent Systems of an SoS; finally, "SoS Interface" semi-formalizes internal and external points of interaction of an SoS.

#### 3.1 SoS Architecture Package