-Runtime models play a critical role in modern self-adaptive systems. Hence, runtime architectural models are needed when making adaptation decisions in architecture-based self-adaptive systems. However, when these systems are distributed and highly dynamic, there is an added need to discover the systems software architecture model at runtime. Current methods of runtime architecture discovery take a centralized approach, in which the process is carried out from a single location. These methods are inadequate for large distributed systems because they do not scale up well and have a single point of failure. Also, systems of such size consist of nodes that are typically highly dynamic in nature. Existing approaches to architecture discovery are not capable of addressing these concerns. This paper describes DeSARM (Decentralized Software Architecture discoveRy Mechanism), a completely decentralized and automated approach for runtime discovery of software architecture models of distributed systems based on gossiping and message tracing. DeSARM is able to identify at runtime important architectural characteristics such as components and connectors, in addition to synchronous and asynchronous communication patterns. Furthermore, through its use of gossiping, it exhibits the properties of scalability, global consistency among participating nodes, and resiliency to failures. The paper discusses DeSARM's architecture and detailed design, and demonstrates its properties through experimentation.
Software architecture—the high level structure of a software
system including a collection of components, connectors and
constraints—plays an increasingly critical role in the design
and development of any large complex software system. These
artifacts (i.e., components, connectors, and constraints) are
needed to reason about the system and act as a bridge
between requirements and implementation as well as provide
a blueprint for system construction and composition. The
architecture helps in the understanding of complex systems,
supports reuse at both the component and architectural level,
indicates the major components to be developed together with
their relationships and constraints, exposes changeability of
the system, and allows for verification and validation of the
target system at a high level [
Software architectures have been very influential in
self-adaptive systems, i.e., systems that are capable of
self-configuration, self-optimization, self-healing and
selfprotection, and are also called self-* or autonomic
systems [
Current methods of runtime architecture discovery take a centralized approach to constructing architectures dynamically. These methods are inadequate for large distributed systems because they do not scale up well and have a single point of failure. Also, systems of such size are often dynamic in nature due to changes in the runtime environment, where nodes join and leave the system unpredictably, and are subject to failures. Existing approaches do not address the aforementioned concerns.
We describe a method for runtime software architecture
discovery in a completely decentralized manner. This is
accomplished by keeping message logs at each node and
disseminating among the nodes identified component interaction
patterns (i.e., synchronous, asynchronous, single or multiple
destination) derived from the logs through selective gossip
exchanges. With selective gossiping, information
dissemination takes place only between nodes that are part of the
same application. This results in the containment of network
traffic, which in effect reduces communication overhead. All
references to DeSARM’s gossiping method heretofore refer
to selective gossiping. Through its use of gossiping, our
mechanism addresses the limitations of the current approaches
and exhibits the following properties: (1) resiliency to failures,
where the gossiping protocol always converges irrespective
of node failures, (2) global consistency among participating
nodes, where all nodes converge to the same architectural
view, and (3) scalability, where the gossiping protocol can
accomodate systems of increasing size [
Thus, the main contribution of this paper is DeSARM:
Decentralized Software Architecture discoveRy Mechanism,
a completely decentralized and automated method and
system for runtime discovery of software architecture models
of distributed systems using gossiping [
The rest of this paper is organized as follows. Section II discusses related work. Section III provides some basic assumptions. Section IV describes the architecture of DeSARM. Section V presents the results of our experiments with DeSARM. Section VI provides a discussion on important issues related to the architecture discovery mechanism. Finally, Section VII presents some concluding remarks and discusses possible future work.
In this paper we use architecture discovery instead of
recovery as is often found in the literature. Architecture recovery
refers to cases where the architecture was known but may have
been lost due to erosion or improper documentation [
Software architecture discovery approaches can be
classified into dynamic, static, and hybrid, i.e., combining both
dynamic and static analysis. Some examples of static analysis
approaches include [
Israr et al. [
Also related to our work is architecture-based software
dynamic adaptation, which addresses the dynamic software
reconfiguration of the architecture model and corresponding
implementation for the purpose of runtime adaptation and
evolution (see e.g., [
This paper makes the following assumptions: 1) If a component fails, it is restarted on the same node if the node is still running. This is common in modern component-based systems whereby components can be restarted when they are detected to have failed. 2) If a node fails, all the components running on that node fail. This assumption is obvious and does not require further comments. 3) If a node cannot be restarted after a failure, its components can be moved to other node(s) using an existing component recovery mechanism not within the scope of this work. This assumption is based on existing work on a runtime application recovery mechanism with which DeSARM is being integrated. See Section VII. 4) Software components can communicate either through a connection-less transport protocol such as UDP or a connection-oriented protocol such as TCP. Both types of communication are common in distributed systems and DeSARM supports either. 5) The software architecture is not known because it may dynamically change due to churn and failures. As explained in the introduction, this is the focus of this work. 6) The software deployment on physical nodes is not known. The set of nodes on which the software system is deployed is not assumed to be known and is discovered by DeSARM.
IV. SOFTWARE ARCHITECTURE DISCOVERY METHOD This section discusses DeSARM’s architecture. We first describe the structure of a node running DeSARM. Then, we give an overview of how gossiping and message tracing are incorporated into the discovery process. We then delve into the details of the architecture model discovery method.
A node in a distributed system consists of three layers according to Fig. 1: application layer, DeSARM layer, and communication middleware. The application layer consists of the distributed application components that communicate over the network via messaging events. Each component has two logs: message sent log (MSL) and message received log (MRL) as shown in Fig. 2. The DeSARM layer forms a wrapper around the communication middleware and provides the same interface to the application layer components as the communication middleware. DeSARM consists of a number of modules each providing different functionality (see Fig.2): Message logging: All incoming messages are logged before being passed to the application layer components and all outgoing messages are logged before being passed to the communication middleware. All messages are logged to stable storage.
Message log aggregation: The MSLs and MRLs of all components are aggregated to form an aggregate message log (AML) at each node. The AML contains the interactions between all components and their respective destination components. This is further merged with the AMLs from incoming gossip messages received from other nodes (see below).
Gossip-based dissemination: This forms the core of our architecture discovery method and enables the distribution of AMLs from each node throughout the system. Peer node selection: This is achieved through the maintenance of a component/node database which is derived by identifying component IDs and their related node IDs from incoming and outgoing messages. This ensures that only nodes running components that are part of the same application are selected for dissemination.
Control: The DeSARM controller manages the execution of the gossip process by maintaining the timing between consecutive rounds.
Architecture discovery: This is used to derive the architectural model of the system based on the message traces. Finally, the communication middleware provides network access allowing the sending and receiving of component-level and gossiping messages between nodes.
Gossip is an epidemic protocol, which due to its simplicity,
robustness and flexibility makes it ideal for reliable
dissemination of data in large-scale distributed systems. In
gossipbased dissemination, data spreads exponentially fast and takes
O (logN) rounds to reach all N nodes [
The main elements of the gossip-based dissemination
framework are: (1) peer selection, where a peer (node) selects
another peer uniformly at random from the set of available
peers, (2) data exchanged, which involves the exchange of
data between peers and is specific to the use of the gossip
mechanism, and (3) data processing, which details how each
peer handles the information received from other peers and
is also specific to the use of the gossip mechanism [
Peer selection: A peer P periodically chooses another peer Q uniformly at random from the set of peers that participate in the same application, i.e., DeSARM uses selective gossiping.
Data exchanged: The AML is sent from one peer to another.
Data processing: The received AML is merged with the local AML at each node to produce an updated AML.
Once a node detects that there are no further updates to the gossiped AMLs, it assumes that convergence was reached and a complete software architecture can be derived.
Each log entry in the MSL or MRL has the following fields: Timestamp Destination Type: single destination (SD) or multiple destination (MD) Message Type (mt): request reply (RQ), no-reply requested (NR), a reply to previous request (RP) Transaction ID Message Unique ID (mid) Return ID: equals 0 if mt 6= RP, otherwise equals “mid” of original request message Source Component: component sending the message Destination Component: component receiving the message Source Node ID: ID of sending node
Destination Node ID: ID of receiving node
The MRL and MSL for each component are scanned and the interaction patterns for these messages are identified. The following types of messages are considered: Reply requests (RQ), No-reply requests (NR), and Replies (RP).
These message types allows us to identify synchronous
vs asynchronous interactions. In the former case, since reply
messages are guaranteed to have a request, then the original
request reply message and its associated reply message are
treated as a single synchronous interaction (SY). If the original
message was sent as a unicast (SD) then the tuple (source,
destination, SY, SD) is added to the AML. Otherwise, if the
original message was sent as a multicast (MD), then the tuple
(source, destination, SY, MD) is added to the AML. No-reply
requested messages on the other hand are treated as
asynchronous interactions (AS) and added to the AML as (source,
destination, AS, SD) if the message was sent as a unicast, or
(source, destination, AS, MD) if the message was multicasted.
The AML is treated as a set so only unique tuple entries are
allowed for each component interaction, irrespective of the
frequency of such interactions in the message logs because
a software architecture does not consider how many times
a certain type of interaction occurred between components.
Further details on the algorithms implemented by DeSARM
can be found in [
After each round of gossiping, the updated AML is used to
incrementally discover the architecture, which is represented
as a labeled directed graph. The vertices of this graph
correspond to unique component ids and the edges correspond
to unique component interactions. Edges are labeled with the
interaction patterns (SY or AS) and destination types (SD or
MD). Further details on this process can also be found in [
To depict how DeSARM works, we use an example architecture of a distributed emergency monitoring system (see Fig. 4). The architecture consists of five types of components with three instances each of the Monitoring Sensor and RemoteSystem Proxy components, and a single instance of the other components. This example assumes that each component is assigned to a single node. When referring to components we mean component instances unless otherwise mentioned. The communication patterns within the system are:
Operator Presentation sends synchronous messages with reply to Alarm Service and Monitoring Data Service. !"#$%"&$#'(
)*#+"&( ,"-."#*#%( 6);():( Alarm Service and Monitoring Data Service send asynchronous multicast messages to Operator Presentation. Monitoring Sensor and Remote System Proxy send asynchronous unicast messages to Alarm Service and Monitoring Data Service.
The discovered architecture model corresponding to Fig. 4 is the graph shown in Fig.5. This shows the five component types of the system and their respective communication patterns as edge labels, which would have been derived by the architecture discovery process.
DeSARM was implemented in Java, and was developed by
extending an open source implementation of gossip [
Our experiments demonstrate the operation of DeSARM and assess its convergence and the number of messages exchanged by the DeSARM middleware. Two sets of experiments were completed. In the first experiment, two types of tests were conducted. In the first test, there were no component/node failures. In the second test, we added random failures with subsequent recovery for each of the components. This second test reveals the impact of failures on the convergence of DeSARM to the final architecture. In the second experiment, the scalability of the mechanism is examined.
We use the application described in Fig. 4, whose
architecture is known, and show that DeSARM converges exactly
to that known architecture. Table I shows the mapping
between nodes, components, and physical machines for this
architecture. As discussed above, the known and discovered
architectures are represented as graphs; we compare the
similarity between the two (the known and current version of the
discovered architecture) over time. For that, we use the graph
comparison algorithms proposed in [
Figure 6 shows how the architecture converges over time to the known architecture at each of the nodes shown in Table I under a no-failure case. Different nodes converge at different rates but at time 80 sec all nodes have converged to the correct software architecture. Nodes 6 and 9 are the first to converge and node 7 is the last. Note that in our implementation of gossiping, each time a node i sends a gossip message to node j, node j replies with a gossip message. This way, two nodes will exchange AMLs more often, leading to faster convergence. Because of the random nature of peer selection in the gossip protocol, some nodes may gossip more often with others, leading to different convergence rates among nodes. Additionally, the convergence rate is affected by the communication pattern among components.
Figure 7 shows the evolution of the architecture similarity when components fail. As the figure shows, failures start to occur after the first 80 sec, before convergence was achieved. In fact, the value of the similarity metric was equal to 0.9375 (i.e., < 1) at all nodes at t = 80 sec. The failure probability of each component, while processing, is set at 20% (a relatively high value) and the average component down time is set at 180 seconds. Thus, at approximately t = 260 sec, the failed components will start to recover from the failure and resume sending messages. DeSARM automatically resumes its message collection and gossiping of newly updated AMLs when components start to recover. When that happens, convergence Fig. 6. Architecture similarity at the 9 nodes as a function of time with no failures.
!# (!# $!!# $(!# %(!# &!!# &(!#
'!!# %!!# 4%+')/2'#3) -./0#&# -./0#+# -./0#$# -./0#)# -./0#%# -./0#*# -./0#'# -./0#(# -./0#,# is achieved as illustrated in Table II, which shows the times at which nodes 1-9 converge after failure recovery. As shown in Table II, node convergence times are spread between t = 340 sec and t = 400 sec.
Figures 6 and 7 are representative of similar results we obtained in other experiments.
Table III shows the number of gossip messages sent and received per node until convergence is achieved in the case when failures do not occur and in the case when failures occur. As the table shows, the average number of sent and received gossip messages when no failures occur is almost 1/3 of the corresponding number when there are failures.
For illustration and debugging purposes, each node collected an event log (not part of DeSARM) during the experiments. Entries in these logs are timestamped in nanoseconds and correspond to events such as sending application-level messages, sending/receiving DeSARM gossip messages, and computing architecture similarity metrics. At the end of the experiment, the event logs of all nodes were sort-merged offline to produce a single log. Figure 8 shows a few excerpts of this log. The first two entries of this log show application-level messages sent by component MSC at Node 1 to components ArmS (at Node 6) and MDS (at Node 8). The next two entries correspond to similar messages sent by MSC2 at Node 2, to components ArmS and MDS. Later in time, DeSARM at Node 1 sends a gossip message to Node 8 with Node 1’s current view of the AML, namely [(MSC,ArmS,AS,SD), (MSC,MDS,AS,SD)]. This view only reflects the messages that component MSC at Node 1 sent to nodes 6 and 8. Later in time, DeSARM at Node 8 receives the following gossip message from Node 4: [(RSP,ArmS,AS,SD), (RSP, MDS,AS, SD), (MDS, OP, AS, MD), (MSC3,MDS,AS,SD), (MSC2,MDS,AS,SD), (ArmS,OP,AS,MD), (MSC3, ArmS, AS, SD), (OP, ArmS, SY, SD), (MSC2, ArmS, AS, SD)]. As a result, Node 8’s similarity metric becomes 0.6875. Later in time, Node 8 receives a gossip message from Node 9 with an AML that reflects Node 9’s current view of the architecture. This AML is aggregated with Node 8’s AML resulting in an AML that reflects the entire software architecture. When the similarity metric for Node 8 is next computed, it shows a value of 1, indicating convergence at Node 8.
To test the scalability of the approach we tested DeSARM
on Argo [
Each component communicates with only two other components so that the initial AML at each node is a very small fraction of the complete AML. Therefore, the value of the similarity metric is very small to begin with. It starts at zero in some cases, when components on a node send a synchronous message to another component and have to wait for the reply. This way the DeSARM instance at each node would require more information to derive the complete architectural model than in the previous experiment.
The convergence time at the 30 nodes varied significantly due to the randomness in message exchange. The node that took the longest time to converge converged in 260 sec (i.e., 4.3 minutes) as shown in Table IV. This table shows the progression of the similarity metric over time. The table also shows that the rate of convergence, roughly defined as the increase in convergence over time is slower at the beginning and faster at the end. For example, after 58% of the time, the similarity metric has only achieved the value of 0.27. At 85% of the time, the similarity metrics achieved 0.73. While the slowest node to converge took over four minutes, the fastest took 30 seconds.
We discuss here some additional issues of interest, some of which are being addressed in ongoing work.
The first issue we address is whether DeSARM’s
selective gossiping mechanism always converges, i.e., if there
is the possibility of different nodes converging to different
discovered architectural models. To address this issue and to
ensure convergence, we employed anti-entropy based gossip
in DeSARM. In anti-entropy gossip, the gossiping protocol
runs indefinitely albeit at specified regular intervals [
The second issue is the relationship between gossip convergence speed and the gossip rate . A higher value of implies faster convergence at the cost of higher message overhead.
Other factors such as system size, component communication patterns, and gossip mode (see below) also affect convergence speed. For example, convergence speed is generally affected by the communication pattern among components, including how often they communicate and the number of components they communicate with. Two modes of gossiping can be used:
Time (sec) Similarity Metric push gossip (where a peer sends a message but does not to failures. These properties were demonstrated through varireceive one in return) vs. push-pull gossip (where a peer sends ous experiments, with and without component failures. These a message and receives one in return). Our implementation experiments assessed the rate of convergence of the DeSARM of DeSARM uses push-pull gossip, which accelerates conver- nodes towards the software architecture being discovered. gence. These experiments showed that DeSARM is resilient and
The third issue is the implication of dynamic architectural is able to discover the architecture even in the presence of changes during gossiping and how it affects convergence. We failures, albeit at a lower pace than the one when no failures are currenty addressing this issue through the integration of occur. DeSARM was implemented in Java using a multiDeSARM with an application recovery layer that runs above threaded architecture.
DeSARM and provides DeSARM with updates to events that In future work we plan to examine DeSARM’s capability
cause architectural changes. Examples of such events include of discovering architectures that change over time as in the
component failures as well as component removal due to adap- case of dynamic software adaptation [
The fourth issue is the overhead of the gossip mechanism and how it operates equally well with two or thirty physical
in relation to both network traffic as well as latency in the machines. In the future, we will run experiments in which a
vasending and receiving of component messages. DeSARM has riety of software architectures are generated following certain
very little network overhead for two reasons: the size of the distributions for parameters such as number of components
AMLs and its use of selective gossiping. As the AMLs contain and communication pattern types.
only unique tuple entries of component interactions, the size As mentioned previously, DeSARM is being integrated
of the AMLs are kept small. This in effect reduces the overall with an existing application recovery mechanism (ARM) that
bandwidth needed for gossip exchanges. Also, as mentioned allows for the runtime recovery of component(s) due to node
earlier, selective gossiping allows for the containment of failure [
This paper described DeSARM, a completely decentralized and automated approach for software architecture discovery of distributed systems based on gossiping and message tracing. Through message tracing, DeSARM is able to identify important architectural characteristics such as components and connectors in addition to synchronous and asynchronous communication patterns. Furthermore, through the use of gossiping, DeSARM exhibits the properties of scalability, global consistency among participating nodes, and resiliency