Self-adaptive systems (SAS) need to reflect on the current environment conditions, their past and current behaviour to support decision making. Decisions may have diferent efects depending on the context. On the one hand, some adaptations may have run into dificulties. On the other hand, users or operators may want to know why the system evolved in a certain direction. Users may just want to know why the system is showing a given behaviour or has made a decision as the behaviour may be surprising or not expected. We argue that answering emerging questions related to situations like these requires storing execution trace models in a way that allows for travelling back and forth in time, qualifying the decision making against available evidence. In this paper, we propose temporal graph databases as a useful representation for trace models to support self-explanation, interactive diagnosis or forensic analysis. We define a generic meta-model for structuring execution traces of SAS, and show how a sequence of traces can be turned into a temporal graph model. We present a first version of a query language for these temporal graphs through a case study, and outline the potential applications for forensic analysis (after the system has finished in a potentially abnormal way), self-explanation, and interactive diagnosis at runtime.
• Software and its engineering → Software system models;
In [
In this paper we ofer the first contributions towards allowing the system to support explanations to operators and end users based on a generic meta-model. Specifically, we define a generic meta-model for structuring execution traces of SAS, and show how a sequence of traces can be turned into a temporal graph model. We present a ifrst version of a query language for these temporal graphs based on specific cases related to a case study. Our solution relies on temporal model-based graphs that abstracts decisions, evidence collected and their corresponding estimated impacts on quality properties of the system. We foresee two potential applications of our approach: forensic analysis of SAS once the system has finished, and selfexplanation supported by the self-adaptive system at runtime.
The paper is organised as follows. Section 2 presents the basic concepts in self-explanation and temporal graphs needed to understand the rest of the text. Section 3 describes our proposed approach for creating frameworks for reusable self-explanation, and outlines our proof of concept implementations of the key components. Section 4 presents a case study on an existing self-adaptive system, together with a number of time-aware queries targeted at users and developers. Section 5 relates this work to others in the fields of self-explanation and model versioning. Section 6 concludes the paper with some general remarks and our lines of future work. 2
This section will present some of the basic concepts that underlie our proposal: the need for self-explanation in self-adaptive system, and our specific choice among the various definitions available in the literature for temporal graphs. 2.1
Our increasing reliance on software systems has made self-adaptation
a expected capability. However, self-adaptation actions may run
into problems or unexpected behaviour due to uncertainty in the
environment [
Early work has been done by Roth-Berghofer et al [
owns ti
Video
key:
node: 1
time: i
value:
name: Eve
friend: [
Bob
Video
key:
node: 3
time: i
value:
name: Bob
owns: [
watched owns
watched owns
ti+2
Video
key:
node: 1
time: i+1
value:
name: Eve
friend: [
time temporal graph state chunks should cover why specific services were recommended and how the system infers that the end user will agree, and therefore maintain the end user satisfied by the recommendations. In their work explanation generation was an aim.
More recently, the need of self-explanation in self-adaptive
systems was argued in [
A graph is a well-understood concept in computer science: in its most basic form, it is a collection of nodes with edges connecting them, which may be directed or undirected. There is a number of ways to extend the concept of a graph with the time dimension: in this section we will present three, one of which is the base for our proposal.
Kostakos [
This representation lends itself well to variants of traditional graph metrics, such as temporal distance between two people, or the temporal availability of a path from one person to another (i.e. whether there is a chain of emails from one person to another while considering time ordering). It uses discrete time, where timepoints act as timeslices and events are assumed to be instantaneous.
In a later survey of temporal networks by Holme and
Sarämaki [
Regardless, these two previous works consider temporal graphs
to be rearrangements of a sequence of events between persistent
entities, which may or may not be instantaneous. In contrast,
Hartmann et al. consider temporal graphs as attributed labelled graphs1
whose state evolves over time [
Hartmann et al. proposed a more eficient data model and storage mechanism for these temporal graphs, and made it available as the 1Attributed graphs have key-value pairs in their nodes and edges, and labelled graphs classify nodes and edges into equivalence sets, e.g. “person” nodes and “emailed” edges. Neo4j is a well-known implementation of this data structure. Greycat open source project2. In this data model (shown in Figure 2), the graph is stored as a collection of nodes, which are conceptual identifiers that are mapped to specific state chunks depending on the world and timepoint chosen to visit it. Nodes have a lifespan between two specific timepoints, and within that lifespan they may take on a sequence of state chunks. Each state chunk appears at a specific timepoint and overrides any previous state chunk.
In the example in Figure 2, during timepoint i + 1 a “watched” edge is created from “Eve” to “Video”, and in i + 2 “Alice” enters the graph and posts a “friendReq” to “Bob”. Instead of storing the three full graphs outright, we only create new state chunks for “Eve” and “Alice” as needed, using a copy-on-write style. State chunks are keyed by node, time and (in Greycat) by world. This third coordinate makes it possible to “fork” the graph into multiple branching paths, which enables what-if analyses.
The approach presented in this paper adopts the data model by Hartmann et al. of an evolving labelled attributed graph. If we can turn the models that the system operates upon into this type of temporal graphs, we could allow the system to reflect on what it has been doing in the long and the short term, and provide clear explanations about its history to the user. 3
Our end goal is to develop a generic and reusable framework to allow self-adaptive systems using the models@run.time approach to reflect upon their past execution and to improve the explanations provided to the users about their behaviour. In this section we will describe the various components that we see as necessary to achieve this goal. The next section will present an initial case study for a SAS which must choose between multiple configurations. 3.1
Self-adaptive systems are generally built as feedback loops (e.g.
those following the MAPE-K architecture [
As an example of a potential execution trace metamodel for self-adaptive systems that need to switch between multiple conifgurations, consider the metamodel shown in Figure 3. At the top level, the Log for a time slice records the requested non-functional requirements as NFR objects (which have specific satisficement thresholds between 0 and 1), together with the Metrics to be measured to check their satisficement, and the alternative Actions that can be taken. These are used in the various Decisions that must be taken by the system. The system is pre-configured with a RewardTable linking the satisfaction of certain NFR with certain Actions to a reward value. These rewards may evolve over time. 2https://github.com/datathings/greycat
Each Decision is based on an Observation of the environment, which produces a set of Measurements of the Metrics. In this version of the language we do not include specific values, but rather between which of the various Thresholds the value was. For instance, if we had three thresholds x and y with values 10 and 20, position 0 would be for x < 10, position 1 would be 10 ≤ x < 20, and position 2 would be x ≥ 20. Using these measurements, the system would derive a set of beliefs about the satisficement of the NFR and the value of the diferent Actions, and finally pick a specific Action from the Decision. 3.2
The next part of the approach is to store the models themselves
in a temporal graph to facilitate querying. In the literature, there
are essentially two approaches to integrate graph databases with
modelling technologies: changing the storage layer of the system
directly (as implemented by NeoEMF [
Either option is valid, but we chose Hawk as it had a number of
advantages over NeoEMF for this problem. First, using Hawk does
not require modifying existing systems: Hawk has a
componentbased architecture, making it possible to change the database
technology, graph updating algorithms and supported model storage
locations to fit the situation. In addition, Hawk has been specifically
designed to detect the parts of a model that have changed, and only
changes the subgraph that is impacted by these changes [
In our implementation, we have extended Hawk with the ability to use Greycat as a backend. We have also extended Hawk with a time-aware version of the incremental graph update algorithm, which tells time-aware backends (i.e. Greycat) to “travel in time” to the timepoint when the change has been introduced before applying the detected changes. This allows for the preservation of the original graph at the previous timepoint, making it possible to travel back and forth in time to answer queries about the history of the trace execution model. 3.3
Having a convenient way to write queries over the history of the graph is another important ingredient for reusable self-explanation. To simplify adoption, the most direct approach is to start from an existing model querying language (e.g. OCL), and then add the ability to traverse the history of a model element or a type through their lifespans. Our definitions for the history of a model element and a type are as follows: • The history of a model element starts from the moment it is created, and ends when it is destroyed. Model elements are assumed to have a unique identity, which could be a natural or artificial identifier or its location within the model. There will be a new version of a model element every time its state changes, whether by changing the value of an attribute or the target of one of its references to other model elements. • Model element types are considered “immortal”, in the sense that they are created at the first timepoint in the graph and last to the virtual “end of time” of the graph. We will have a [0..*] requirements
NFR
For model elements and model element types, we consider these to be the basic time-aware operations that must be supported by the temporal graph backend (e.g. Greycat): i) retrieving all versions, ii) all versions within a range, iii) versions from/up to a certain timepoint (included), iv) earliest/previous/next/latest version, and v) retrieving the timepoint for that version.
Our approach is heavily inspired by the “history” fields proposed
by Rose and Segev during their work on temporal object-oriented
data models in the 90s [
For our proof-of-concept implementation, Hawk already had
most of the elements, as it came with a number of backend-specific
and backend-agnostic query engine components. The most mature
query language at the time of writing is a dialect of the Epsilon
Object Language (EOL) [
The last piece in the puzzle would be to have a reusable set of visualizations for a certain class of self-adaptive system. These could be dashboards with the key instants in the self-adaptive Operation Syntax All versions, from x.versions newest to oldest Versions within a range x.getVersionsBetween(from, to) Versions from a time- x.getVersionsFrom(from) point (included) Versions up to a time- x.getVersionsUpTo(from) point (included) Earliest / latest version x.earliest, x.latest Next / previous version x.next, x.prev/x.previous Version timepoint x.time system, to allow users to jump to the main changes in behaviour that were introduced automatically, or a predefined sequence of “why”-form questions for common queries: why was it doing this at that time, why did it stop doing the previous action, why did it reason that was beneficial, why was the reasoning process in such a state, and why was the user configuration like that.
Adding these visualizations to a system should require less effort once we have achieved the definition of a standardized trace metamodel, and have reusable temporal storage and querying capabilities that we can always start from. The visualizations would be backed by time-aware queries, and could be packaged together with the configuration of the self-adaptive system for a specific problem domain.
Beyond getting the data, another challenge is finding an accessible way to present it, which steps into the realm of human-computer interaction and is outside the scope of this paper. Regardless, at this stage the reusable visualizations remain as a future line of work. 4
As an example to demonstrate the feasibility of the ideas proposed,
let us consider the case of the Remote Data Mirroring (RDM)
selfadaptive system (SAS). RDM is a technique to protect data against
inaccessibility to therefore provide further resistance to data loss
[
Fig. 4 presents the R-POMDP (Relational Partially Observable
Markov Decision Process [
The RDM described above has been designed to be configured
by using two diferent topologies: minimum spanning tree (MST)
and redundant topology (RT). These two possible configurations
allow the RDM selectively activate and deactivate network links to
change its overall topology at runtime [
The RDM SAS self-adapts reconfiguring itself at runtime according to the changes in its environment, which may include either delayed or dropped messages and network link failures. Each network link in the RDM brings upon an operational cost and has a measurable throughput, latency, and loss rate. The performance and reliability of the RDM are determined by these metrics according to the following trade-of: while RT is more reliable than MST, RT can be prohibitively more expensive than MST in some contexts. Each configuration provides its own levels of reliability and energy costs which are taken into account while estimating the levels of Listing 1: Excerpt of the original JSON trace execution logs from the Remote Data Mirroring self-adaptive system satisficement of the NFRs observed, the Maximization of Reliability (MR) and the Minimization of Energy Consumption (MEC). As such, and RDM makes decisions about the topologies to use. The operators may find themselves asking the reasons why the RDM SAS has used one topology instead of the other.
The states of these NFRs are not directly observable.
Observations about their states are obtained by using monitoring variables
(called MON variables). Two MON variables REC=“Ranges of
Energy Consumption" and NCC=“Number of Concurrent
Connections" has been specified. In [
In its current implementation, the RDM SAS produces execution traces in JSON format for each time slice, mentioning the observations made, the currently estimated levels of satisficement of the NFRs, and the preferences currently being applied in the decision process. The JSON log is made available for forensic purposes to debug the system after the fact. Listing 1 shows an excerpt of the log for the first time slice.
Due to time constraints, for this first feasibility study it was decided to collect a large number of JSON logs and transform them into a temporal graph, answering queries away from the system (in an “of-line” fashion). It is planned to revise the RDM SAS in future studies to have it maintain the temporal graph while it is running, so queries can be answered “on-line” for reflection and
3https://git.aston.ac.uk/garcia-a/hawk-mrt2018 4https://github.com/mondo-project/mondo-hawk 5https://subversion.apache.org/ 6A previous version with second-level rather than millisecond-level timestamps required 2.6MB instead. We intend to investigate this further in future studies. other times they will want to identify points in time where the self-adaptive system misbehaved.
Listing 2 shows a first example of what can be done for the developers. It allows the RDM SAS developer to check if the internal reward values in the decision algorithm have evolved over time or if they have remained the same. It operates as follows: (1) RewardTableRow.latest returns the latest version of the RewardTableRow type node in the temporal graph. There are only two versions for this node: the one at the beginning of time with no instances, and the second one with all the instances. RewardTableRows are not created or deleted, they are simply modified with diferent reward values. (2) .all returns all instances of that type at that point in time. (3) .collect(x | expression) visits each instance, computing an expression and collecting the results into a new list. (4) r_row.versions.size returns the number of versions for that instance. This would be the number of times that the reward values have changed. (5) .max() computes the maximum value over the list with all the numbers of versions of the various RewardTableRows.
Essentially, if the query returns 1 we know that the reward values have remained the same, whereas if it returns 2 or higher we will know that it has changed at some point, and depending on the value we will know how often it happened. For this experiment, the query returned 442 - there was a reward table row that had changed that many times in value.
Developers can easily expand upon the queries to produce more nuanced results. Listing 3 shows a more advanced example that computes some basic descriptive statistics of the reward table rows 13 14 } 15 } 16 operation Sequence average() { return self.sum() / self.size(); } 4.2
We argue that self-explanation needs to be tailored to the reader. SAS developers and integrators will be interested on a diferent type of explanations about the system. Particularly, they will often need to verify that certain desirable properties are being met, while
thrashing within the SAS Listing 5: EOL query to find cases when observations clash against the understanding of satisficement within the SAS var decVersions = Decision.latest.all.first.versions; var dvBeforeLast = decVersions.subList(1, decVersions.size); var dvWithObs = dvBeforeLast.collect(dv | Sequence { dv.time, dv.actionTaken.name, dv.supportingObservations() over time. This query makes use of EOL context operations to define the “reward shifts” of a specific version of a RewardTableRow. If we have only one version, it is the empty sequence. If it has more than one version, then it is the sequence of diferences between the values of each version and the one immediately before it. For values (0.1, 0.12, 0.11) we would have shifts of (0.02, −0.01). This can give us an idea of whether the reward recalculation is keeping shifts bounded, or if the values are wildly shifting from one timepoint to the next. In the case of the current log, the SAS kept shifts bounded to a symmetric range within ±0.034, with an average of −5.31 × 10−9.
Continuing with the theme of checking if the SAS is behaving appropriately, it may be important to notice situations in which the system may be “thrashing” between two actions, which suggest that the decision process may benefit from a “tolerance interval” where it will not react just yet to an observed situation. Listing 4 shows a query designed to find the longest sequence of actions that are only backed by a single observation, i.e. intervals in which the (1) Lines 1–5 go from the earliest to the second last versions of the only Decision in the RDM SAS. For each of them, they compute a triplet with the timepoint, the name of the action taken, and the number of supporting observations. (2) The number of supported operations is defined by the context operation in lines 24–33, which counts the number of observations that existed before the next version of that decision. (3) Lines 8–21 find the longest sequence of triplets with 1 supporting observation. For our trace, the query finds a sequence of 8 timepoints when the SAS is switching back and forth between RT and MST after each observation.
Queries can also be used to find less intuitive scenarios. Being probabilistic, R-POMDP may infer that a certain NFR is not being met even though the current observation may say otherwise: this simulates sensor failures and noise. Listing 5 shows a query which found 18 time slices when the Minimization of Energy Consumption NFR satisfaction did not match the Rate of Energy Consumption measurement. Either the NFR was met even though we were in the high ranges of REC, or the NFR was not met even though we were in the low ranges of REC. As a minor detail, for each version of the measurement we check the belief level at the same timepoint by using travelInTime on the belief node. 4.3
Other queries may be more generally useful to the wider community around the SAS, and could be fed into dashboards. They would Listing 6: EOL query to compute statistics about NFR satisifcement above their thresholds return NFRBelief.latest.all.collect(nfrb | nfrb.stats()); operation NFRBelief stats() { var versions = self.versions; var nAbove = versions.select(v |
v.estimatedProbability >= v.nfr.threshold).size; var nBelow = versions.size − nAbove; return Map { 'name' = self.nfr.name,
'above' = nAbove, 'below' = nBelow }; 1 2 3 4 5 6 7 8 9 10 } essentially start of from the NFRs and give increasingly more detailed explanations of to what degree they were met, what was 15 done to correct situations when they were not met, and why those 16 corrective actions were chosen. 17
Listing 6 shows a query which indicates how often the various 18 NFRs were met. The query takes all the NFRBelief instances, and 19 visits all their versions, counting how many are above and below 20 their thresholds7. We compute a simple triplet with the name of 21 the NFR and the number of times we believed it to be above/below 22 } the threshold. Regarding MEC, out of the 888 unique belief levels 23 } stated by the SAS, 670 passed the threshold and 218 did not. 665 24 return results; belief levels passed MR, and 223 did not. 25
Deeper self-explanation requires looking at how the satisfice- 26 ment of the MRs evolved over time, and how the system reacted 27 to it. Listing 7 shows a query that will produce a timeline of how 28 the NFRs changed between being met and not met, as shown in 29 Listing 8. 30
Looking at line 1 of the output, we see that the system started 31 with both MR and MEC unmet, that it stayed like that for 1 obser- 32 vation, and that since it observed that REC was low and NCC was 33 high, it decided to go with RT as an action. Line 2 shows that the 34 system started meeting MR and MEC, but then observed energy 35 } usage (REC) to be in the high ranges, so it went into MST. Interestingly, MEC started to fail later on, even though the observed energy usage was not that high: again, this may be due to the probabilistic nature of R-POMDP observed in Listing 5.
In general, the main advantage of the presented approach is that it allows for rapid development and iteration of new queries on the history of the model, making it possible to create the explanations for a category of SAS as required, and then later package them as premade, reusable visualizations. } return result; 5
This paper is based on a combination of various results from the areas of self-explanation for decision making systems, and model versioning. In this section we will relate the work to several key contributions in these fields. 7Interestingly, this query could easily accommodate dynamic NFR thresholds without any changes, since we visit the NFR through the version of the belief. var currentStates = computeStates(vNfrMecB.first.time); var newStates : Map; var results : Sequence; var length = 0; for (v in vNfrMecB) { newStates = computeStates(v.time); if (newStates.equals(currentStates)) {
length += 1; } else { var lastDecision = Decision.latest.all.first.travelInTime(v.time); results.add(Sequence { currentStates, length, v.time, // time of last decision taken in this interval lastDecision.observation.description, lastDecision.actionTaken.name // name of action }); currentStates = newStates; length = 1; operation computeStates(instant: Integer): Map { var nfrbs = NFRBelief.latest.all
.collect(nfrb | nfrb.travelInTime(instant)); var result : Map; for (nfrb in nfrbs) { result.put(nfrb.nfr.name,
nfrb.estimatedProbability >= nfrb.nfr.threshold);
4 ...] 5.1
The area of research about self-explanation and interactive is still
in its infancy. The need for it is exacerbated due to the use of
artificial intelligence and machine learning. However, few research
initiatives exist. The authors in [
In [
As a complex artifact developed within teams, keeping track of
the various revisions that a model goes through is very important.
According to the survey by Brosch et al. [
In terms of tools, many practitioners use simple and mature
text-based version control systems (VCS) to keep track of their
models (e.g. Git), and they use standalone state-based model
comparison and merging tools (e.g. EMF Compare8). Others accept the
additional complexity for the sake of additional functionality and
use dedicated model repositories, which handle model revisions in
terms of model elements and their references. Some well-known
examples are Eclipse Connected Data Objects9, which stores model
revisions inside a relational database (usually combined with a
relational database), or EMFStore [
In the last few years, there has been increasing interest in having
time-awareness as a native capability of the modelling framework
itself. In 2012, Holmes et al. implemented a copy-on-write
versioning scheme for models at an element level using UUIDs [
Another recent work in the area of temporal graph stores for
models is ChronoSphere, developed by Haeusler et al. [
One last idea that Borsch et al. identified in their survey as an open research area was intention-aware model versioning, where merges could be simplified by encoding what the modelers wanted to accomplish with their changes. We have not found many research initiatives in the area since then, but we find that the idea of encoding the intentions of a change in the model could certainly be relevant and useful for self-explanation. For future work, we are considering model versioning approaches where the self-adaptive model-based system would encode their intentions upon the various changes. These intentions could also be indexed by Hawk into the temporal graph, and could be accessed from EOL queries. 6
In this work, we have described the key requirements for a reusable framework for self-explanation in self-adaptive systems: a generic and extensible execution trace metamodel, a temporal graph to store these traces, a time-aware query language that allows to reason about the history of the models, and a set of reusable visualizations the main types of self-adaptive systems in the wild. We have provided proof-of-concept implementations for the first three. We have also demonstrated diferent queries aimed at explaining the self-adaptive nature of the systems to developers and end users.
The present work can be considered as a first step towards that reusable framework, suggesting several lines of future work. First, it would be useful to have a taxonomy of the various types of queries that diferent audiences may ask of a self-adaptive system, and the diferent levels of detail that we could use for our answers. Some of those queries may cross over multiple types of SAS, while others may be specific to a class of SAS. Once we determine which queries are the most valuable and reusable, we would develop visualizations based on them.
The trace execution metamodel shown in the paper captured most concepts used by the RDM SAS, but it may require further refinement to cover other SAS. We need to apply the approach to a wider range of SAS and to allow the extension of the trace execution metamodel with “profiles” for other types of self-adaptation approaches. This is a similar approach to UML and the use of proifles for specific domains.
The query language is based on a set of basic primitives around versions, but it lacks the richness of a more formal model such as linear temporal logic, with richer predicates such as “always”, “never” or “eventually”.
We also envision a diferent application of temporal graphs to produce better simulation models for the development of selfadaptive systems. If we kept track of the actions and their impacts in a self-adaptive system “deployed in the wild”, we could produce a better probability matrix between NFR satisficement levels, actions and observations. Further, we envision that the temporal graph models will act as runtime models to support self-explanation, interactive diagnosis and even decision-making. The language will provide a way how to access and change the runtime model during execution.