=Paper= {{Paper |id=Vol-3642/paper7 |storemode=property |title=MCSR: A graph transformation based approach for Minimal and Compact Set Representation of Causal Dependencies in Distributed Systems |pdfUrl=https://ceur-ws.org/Vol-3642/paper7.pdf |volume=Vol-3642 |authors=Houda Khlif,Hatem Hadj Kacem,Saul Pomares Hernandez |dblpUrl=https://dblp.org/rec/conf/tacc/KhlifKH23 }} ==MCSR: A graph transformation based approach for Minimal and Compact Set Representation of Causal Dependencies in Distributed Systems == https://ceur-ws.org/Vol-3642/paper7.pdf

MCSR: A graph transformation based approach for
Minimal and Compact Set Representation of Causal
Dependencies in Distributed Systems⋆
Houda Khlif1,* , Hatem Hadj Kacem1 and Saul Pomares Hernandez2,3
1
ReDCAD Laboratory, ENIS, University of Sfax, Tunisia
2
INAOE, Tonantzintla, Mexico
3
CNRS, LAAS, F-31400 Toulouse, France

Abstract
Causal ordering is an important property in distributed systems. Several algorithms have been developed
over this principle. For example, there are solutions for roll-back recovery, multimedia synchronization,
model checking, and many others. All these algorithms establish causal dependencies according to the
Happened-Before Relation (HBR), which was introduced by Lamport, and they identify and ensure causal
dependencies based on the Vector Clocks’ algorithm introduced by Mattern and Fidge. The HBR is a
strict partial order, and therefore, one main problem linked to it is the combinatorial state explosion.
In this paper we present a graph transformation based approach called MCSR which constructs, for
a distributed computation, the minimal causal graph (IDR graph) at a single event level and a causal
consistent compact graph (CAOS graph) at an event set level. For this, we use the Immediate Dependency
Relation (IDR) and the Causal Order Set Abstraction (CAOS), respectively. Both resultant causal graphs
drastically reduce the state-space of a system. The MCSR receives a database of vector clocks as input,
from which it automatically generates the fully-causal HBR original graph, the IDR graph, and the
CAOS graph by using graph transformation rules. The resultant causal graphs can be used for different
purposes, such as for the design of more efficient algorithms, validation, verification of the existing ones,
among others. Finally, we compare the IDR graph and the CAOS graph with the HBR graph in terms of
their number of nodes and edges.

Keywords
Distributed system, Causal Ordered Set Abstraction, Happened Before Relation, Immediate Dependency
Relation, graph transformation.

1. Introduction
Causal ordering is an important property in distributed systems. The use of causal ordering
provides built-in message synchronization, reduces the non-determinism in a distributed compu-
tation, and provides an equivalent of the FIFO property at a party communication level. Causal
ordering guarantees that actions, such as requests or questions, are received (viewed) before
their corresponding reactions, results, or responses. Several algorithms have been developed
over the causal ordering principle. For example, there are solutions for checkpointing [1, 2],
TACC 2023: Tunisian-Algerian Joint Conference on Applied Computing, November 6 - 8, Sousse, Tunisia
*
Corresponding author.
$ houda.khlif@redcad.org (H. Khlif); hatem.hadjkacem@redcad.org (H. Hadj Kacem); spomares@inaoep.mx
(S. P. Hernandez)
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)

CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
roll-back recovery [3], predicate detection [4], group communication [5], multimedia data
synchronization [6, 7], model checking [8], and many others. All these algorithms establish
causal precedence dependencies according to the Happened-Before Relation (HBR), which
was introduced by [9], and they identify and ensure causal dependencies based on the Vector
Clocks (VCs) algorithm introduced by Mattern [10] and Fidge [11]. The HBR and VCs principles
avoid the use of any kind of global references and synchronization mechanisms. The HBR is a
strict partial order (transitive, irreflexive and antisymmetric) and therefore, one main problem
linked to it is the combinatorial state explosion [12]. This characteristic of the HBR renders the
analysis, verification and modeling of the existing solutions difficult, as well as the design of
new more efficient algorithms. In this paper we present an approach called MCSR (Minimal
and Compact Set Representation) which identifies, for a distributed computation, the minimal
causal graph (IDR graph) at a single event level and a causal compact causal set graph (CAOS
graph) at an event set level. In a previous work[13], we have used the algorithmic approach for
the generation of HBR, IDR and CAOS. In this contribution, we adopt the graph transformation
approach which offer an intuitive way to express and execute graph reductions, especially
for complex relationships or patterns within the graph. In Section 4.2 a comparative is given
between algorithmic solutions versus graph transformation. Our work use the Immediate
Dependency Relation (IDR) [14] and the Causal Order Set Abstraction (CAOS) [15]. We start
with a database of Vector Clocks as input, from which we generate the fully-causal HBR original
graph. Then, by using graph transformation rules, we generate the IDR and the CAOS graphs.
The efficiency of generating such graphs is shown by comparing them with the HBR graph
in terms of their number of nodes and edges. As we will show, both resultant causal graphs
drastically reduce the state-space of a system. The results show that the IDR and CAOS graphs
use significantly fewer graphs components in order to represent the causality of the system.
The resultant causal graphs can be used for different purposes, such as for the design of more
efficient algorithms, validation, verification, and/or the debugging of the existing ones, among
others. In this paper, we show how causal graphs can be used for validation purposes.
The rest of the paper is structured as follows: Section 2 presents the system model and associated
definitions. Our approach is detailed in Section 3, while some results are given in Section 4.
Finally, Section 5 concludes with a few remarks.

2. Background and Definitions
2.1. System Model
The system under consideration is composed of a set of processes 𝑃 = {𝑝1 , 𝑝2 , · · · , 𝑝𝑛 }. The
processes present an asynchronous execution and communicate only by message passing. 𝑀
is a finite set of messages, where each message 𝑚 ∈ 𝑀 is sent considering an asynchronous
reliable network which is characterized by no transmission time boundaries, no order delivery,
and no loss of messages. The set of destinations of a message 𝑚 is identified by 𝐷𝑒𝑠𝑡(𝑚).
Two types of events are considered here: internal and external events. An internal event is a
unique action which occurs at a process 𝑝 in a local manner and which changes only the local
process state. We denote the finite set of internal events as 𝐼. An external event is also a unique
action which occurs at a process, it is seen by other processes, and thus, affects the global state
of the system. The external events considered in this paper are the send and delivery events.
Let 𝑚 ∈ 𝑀 be a message. We denote by 𝑠𝑒𝑛𝑑(𝑚) the emission event and by 𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑦(𝑝, 𝑚)
the delivery event of 𝑚 to participant 𝑝 ∈ 𝑃 . The set of events associated to 𝑀 is the set:
𝐸(𝑀 ) = 𝑠𝑒𝑛𝑑(𝑚) ∪ 𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑦(𝑝, 𝑚). The whole set of events in the system is the finite set
𝐸 = 𝐼 ∪ 𝐸(𝑀 ). Each event 𝑒 ∈ 𝐸 is identified by a tuple 𝑖𝑑(𝑒) = (𝑝, 𝑥), where 𝑝 ∈ 𝑃 is the
producer of 𝑒, and 𝑥 is the local logical clock for events of 𝑝, when 𝑒 is carried out. When we
need to refer to a specific event we use the notation 𝑒𝑝,𝑥 .

2.2. Happened-Before Relation (HBR)
The Happened Before Relation for single events was defined by Lamport [9]. This relation
establishes causal precedence dependencies over a set of events. The HBR is a strict partial
order (transitive, irreflexive and antisymmetric). It is defined as follows:

Definition 1. The causal relation “→” is the smallest relation on a set of events 𝐸 satisfying the
following conditions:

• If 𝑎 and 𝑏 are events belonging to the same process, and 𝑎 was originated before 𝑏, then
𝑎 → 𝑏.
• If 𝑎 is the sending of a message by one process, and 𝑏 is the receipt of the same message in
another process, then 𝑎 → 𝑏.
• If 𝑎 → 𝑏 and 𝑏 → 𝑐, then 𝑎 → 𝑐.

By using Definition 1, Lamport defines that a pair of events is concurrently related “𝑎||𝑏” if it
satisfies the following condition:

𝑎||𝑏 if ¬(𝑎 → 𝑏 ∨ 𝑏 → 𝑎)

2.3. Vector Clocks
The Vector Clocks’ algorithm was simultaneously developed by Fidge [11] and Mattern [10]. It
was created to detect the causal relations among events in a distributed system. A Vector Clock
is an array of logical clocks of size 𝑛, where 𝑛 is the number of processes in a system. A Vector
Clock captures the causal state of the system. For each event e generated, a Vector Clock is
associated, and it is denoted by 𝑉 𝐶(𝑒). In general, the Vector Clocks’ algorithm is defined as
follows:

∙ Each process 𝑝𝑖 is equipped with a Vector Clock 𝑉 𝐶𝑖 . A process 𝑝𝑖 increments its own
Vector Clock for each event 𝑒 (internal or external) in the form:

𝑉 𝐶𝑖 [𝑖] := 𝑉 𝐶𝑖 [𝑖] + 1

∙ In each message 𝑚 sent by a process 𝑝𝑖 , the current Vector Clock 𝑉 𝐶𝑖 is piggybacked in
𝑚. At the reception of a message 𝑚 by a process 𝑝𝑗 , the process 𝑝𝑗 updates its clock as
follows:

𝑉 𝐶𝑗 := 𝑚𝑎𝑥(𝑉 𝐶𝑗 , 𝑉 𝐶𝑖 )
Where 𝑚𝑎𝑥 gets the maximum values of each pair of elements in the Vector Clocks.

Based on the Vector Clocks’ algorithm, the causal dependencies between a pair of events in a
system can be established as follows:

Definition 2. For a pair of events 𝑎, 𝑏 ∈ 𝐸, the event 𝑎 causally precedes the event 𝑏 if the
following condition is satisfied:

𝑎 → 𝑏 if 𝑉 𝐶𝑖 (𝑎) < 𝑉 𝐶𝑗 (𝑏)

2.4. Immediate Dependency Relation (IDR)
The IDR is the transitive reduction of the HBR ([14]). It is denoted by “↓”, and it is defined as
follows:
Definition 3. Two events 𝑎, 𝑏 ∈ 𝐸 have an immediate dependency relation “↓” if the following
restriction is satisfied:
𝑎 ↓ 𝑏 if 𝑎 → 𝑏 and ∀𝑐 ∈ 𝐸, ¬(𝑎 → 𝑐 → 𝑏)
Thus, an event 𝑎 causal immediately precedes an event 𝑏, if and only if no other event 𝑐 belonging
to 𝐸 exists, such that 𝑐 belongs to the causal future of 𝑎 and to the causal past of 𝑏.

Property 1. For all pair of events 𝑎, 𝑏 ∈ 𝐸, 𝑎 ̸= 𝑏:
if ∃𝑐 ∈ E such that (𝑎 ↓ 𝑐 and 𝑏 ↓ 𝑐) or (𝑐 ↓ 𝑎 and 𝑐 ↓ 𝑏), then 𝑎 || 𝑏

2.5. Causal Ordered Set Abstraction (CAOS)
Assuming the poset 𝐸 = (Ê,→) as the model adopted for a distributed computation, the objective
of CAOS is to establish over this poset the rules and conditions of association of events and the
conditions of ordering between the resulting sets ([15]).
Ordered sets of events. We consider a finite collection 𝑆 of ordered sets of events, where each
set 𝑊 ∈ 𝑆 is a set of events 𝑊 ⊆ 𝐸. The elements of a set are ordered according to the IDR.
Such elements compose a causal path (linearization) from an event 𝑒1 to an event 𝑒𝑘 such that
𝑊 = {𝑒1 ↓ 𝑒2 ↓ · · · ↓ 𝑒𝑘 }. We denote by 𝑤− and 𝑤+ the endpoint events of 𝑊 (𝑤− = 𝑒1 and
𝑤+ = 𝑒𝑘 ).
The definition of CAOS is made up of three parts:
Part I-Creation of sets. The rules 𝑅1 , 𝑅2 and 𝑅3 establish the creation of sets (Table 1, Lines
2–4). An event which satisfies one of these rules creates a new set, and it is by default associated
to such set as its left endpoint. The rule 𝑅1 creates a new set 𝑊 (𝑒) when an event 𝑒 does not
have causal history. The rule 𝑅2 creates a new set 𝑊 (𝑒) when it is detected that 𝑒 is concurrent
with respect to another event 𝑒𝑏 . The rule 𝑅2 ensures that when the pattern 𝑒𝑎 ↓ (𝑒||𝑒𝑏 ) occurs,
the event 𝑒 will be associated to a different set 𝑊 than the sets for 𝑒𝑎 and 𝑒𝑏 . Finally, the rule
𝑅3 creates a new set 𝑊 (𝑒) when it is detected that two concurrent events 𝑒𝑎 ||𝑒𝑏 converge to a
same event 𝑒. 𝑅3 ensures that when the pattern (𝑒𝑎 ||𝑒𝑏 ) ↓ 𝑒 occurs, the event 𝑒 will be associated
to a different set 𝑊 than the sets for 𝑒𝑎 and 𝑒𝑏 .
1. A new set 𝑊 (𝑒) is created in 𝑆 when:
C1. ∃𝑒 ∈ 𝐸, ¬(∃𝑍 ∈ 𝑁 : 𝑒 ∈ 𝑍) 1
𝑅1 = {𝑒 : ∅ ↓ 𝑒} or 2
𝑊 (𝑒) ← 𝑅2 = {𝑒 : ∃(𝑒𝑎 , 𝑒𝑏 ) ∈ 𝐸; 𝑒𝑎 ↓ 𝑒 ∧ 𝑒𝑎 ↓ 𝑒𝑏 } or 3
𝑅3 = {𝑒 : ∃(𝑒𝑎 , 𝑒𝑏 ) ∈ 𝐸; 𝑒𝑎 ↓ 𝑒 ∧ 𝑒𝑏 ↓ 𝑒} 4
2. The rest of the events 𝑒′ ∈ 𝐸 are assigned to a set 𝑊 (𝑒) ∈ 𝑁 as follows:
C2. ∃𝑊 (𝑒) ∈ 𝑁 , ∃𝑒′ ∈ 𝐸, ¬(∃𝑍 ∈ 𝑁 : 𝑒′ ∈ 𝑍) 5
𝑊 (𝑒) ← 𝑅4 . 𝑊 (𝑒) ∪ {𝑒′ : ∃𝑒𝑎 ∈ 𝑊 (𝑒), ∃𝑒𝑏 ∈ 𝐸; 𝑒𝑎 ↓ 𝑒′ ∧ ¬(𝑒𝑎 ↓ 𝑒𝑏 )} 6
Table 1
CAOS specification

Part II-Association of events. An event does not accomplish any of the rules of Part I, then it
will be associated to an existing set 𝑊 according to the rule 𝑅4 (Table 1, Line 6). The rule 𝑅4
associates events to sets by respecting the specification of the ordered set of events previously
presented where the elements of a set compose a linearization based on the IDR. Each new
event associated to a set 𝑊 becomes its right endpoint.
Part III-Arrangement of sets. The resulting sets 𝑊 ∈ 𝑆 are arranged. We say that a pair of
sets 𝑋, 𝑌 ∈ 𝑆 are IDR-related “𝑋 ↓ 𝑌 ” if the following condition is satisfied:

𝑋 ↓ 𝑌 if 𝑥+ ↓ 𝑦 −

2.6. Graph Transformation
Graph Transformation is a rule-based approach targeted towards the modification on a graph
([16, 17]). A Graph Transformation Rule is described by a pair of graphs 𝑟 = (𝐿, 𝑅), where 𝐿
is called the left-hand side graph and 𝑅 is called the right-hand side graph. Applying the rule
𝑟 = (𝐿, 𝑅) means finding a match of 𝐿 in the source graph and replacing 𝐿 with 𝑅.

2.6.1. The Single PushOut Approach (SPO)
A rule of type SPO is a production in the form of (𝐿, 𝑅). Its application to a graph 𝐺 is related to
the existence of an occurrence of 𝐿 in 𝐺. The application of the SPO rule to a graph 𝐺 involves
removing the graph corresponding to 𝐷𝑒𝑙 = (𝐿∖(𝐿 ∩ 𝑅)) and adding the graph corresponding
to 𝐴𝑑𝑑 = (𝑅∖(𝐿 ∩ 𝑅)). According to the SPO approach, all the dangling edges are deleted.

2.6.2. The Double PushOut Approach (DPO)
A rule of type DPO is a production in the form of (𝐿, 𝐾, 𝑅) where 𝐾 is used to clearly specify the
part to preserve after applying the rule. The difference between the SPO and DPO approaches is
that the application of this rule is attached to the “Dangling Condition”. This condition specifies
that the rule can not be applied if its application will lead to suspended edges. If both conditions
of existence of the occurrence of 𝐿 and absence of suspended edges are satisfied, then the
application of the rule involves the removal of the graph corresponding to the occurrence of
𝐷𝑒𝑙 = (𝐿∖𝐾) and the addition of a copy of the graph 𝐴𝑑𝑑 = (𝑅∖𝐾).
2.6.3. Negative Application Condition (NACs)
In some cases, it is necessary to express additional conditions to specify conditions related to
the absence of an occurrence in the graph. This type of condition is called Negative Application
Conditions or 𝑁 𝐴𝐶s. An SPO rule has the structure (𝐿, 𝑅, 𝑁 𝐴𝐶) and is applicable to a graph
𝐺 if there is an occurrence of 𝐿 in 𝐺 and if there is no case of 𝑁 𝐴𝐶 in 𝐺.

2.6.4. Neighborhood Controlled Embedding Approach (NCE)
The Neighborhood Controlled Embedding (NCE) mechanism ([17]) is based on the specification
of the so-called connection instructions to allow the gluing of the added nodes to the neighbors
of the removed nodes. These instructions are based on the labels of nodes to define new edges
that will be introduced. Connection instructions are described by a pair (𝑛, 𝛿). The execution of
this connection instruction involves the introduction of an edge between the added node 𝑛 and
all the neighbors nodes of the removed node whose label is 𝛿.
dNCE (𝑑 for edge label), eNCE (𝑒 for edge label), and edNCE are extensions of the NCE approach.
The edNCE approach is the combination of eNCE and dNCE approaches. The edNCE connection
instructions are in the form of (𝑛; 𝑝/𝑞; 𝛿; 𝑑; 𝑑′ ). Its execution implies the introduction of an edge
in the direction indicated by 𝑑′ between the node 𝑛 and all nodes 𝑛′ which are 𝑝-neighbours
and 𝑑-neighbours (in-neighbours if 𝑑=in and out-neighbours otherwise) of the removed node.

3. Graph transformation based approach
The genaration of the IDR and CAOS graphs can be done with using graph transformation
approaches. To do this, we have designed two sets of rules: the HBR2IDR for the generation of
the IDR graph and the IDR2CAOS for the generation of the CAOS graph (Figure 1).

« VCs2HBR »
VCs HBR IDR CAOS
Graph GMTE GMTE
comparator Graph Graph

« HBR2IDR »
VCs « IDR2CAOS »
Database Rule file
Rule file

Figure 1: General architecture for GT based approach

Our solution is based on two main approaches which are SPO and edNCE. The SPO approach
offers a flexible way of dealing with dangling edges. The edNCE approach is for the addition and
the removal of nodes. We have used GMTE1 (the Graph Matching and Transformation Engine)
to implement our approach.

1
GMTE and our MCSR approach are available at http://homepages.laas.fr/khalil/GMTE/
3.1. HBR to IDR
We have designed the HBR2IDR rules: 𝑟1 and 𝑟2 (presented in Figure 2a), which are sequentially
executed. Rule 𝑟1 verifies if it exists, in the HBR graph, local (c-labeled) edges which do not satify
the IDR condition. Then, it deletes the existing ones. Rule 𝑟2 deletes all transitive (t-labeled)
edges from the HBR graph as they are not immediate.
Firstly, rule 𝑟1 = (𝐿1 , 𝑅1 ) is applied to the HBR graph. Its application implies finding all
matches of 𝐿1 in 𝐺1 and replacing them with 𝑅1 . As a result, all 𝑐-labeled edges which are
𝑐
not immediate are removed. In fact, the c-labeled edge (𝑛1 −→ 𝑛3 ) in the pattern 𝐿1 is not
immediate because it exists a node 𝑛3 such that 𝑛1 → 𝑛3 → 𝑛2 . An illustrative example is
given in Figure 2a. In this example, it exists four matches of 𝐿1 . Therefore, the local edges
𝑐 𝑐 𝑐 𝑐
𝑒11 −→ 𝑒12 , 𝑒13 −→ 𝑒14 , 𝑒21 −→ 𝑒22 and 𝑒31 −→ 𝑒32 are removed and we obtain the graph
𝐺2 .

n1 c n2 n1 n2
t
r1 = L1 = , R1 =
r2 = L2 = n1 n2 , R2 = n1 n2

n3 n3

Graph G2 c-labeled edge
Graph G3 = IDR Graph
c-labeled edge d-labeled edge
Graph G1 = HBR Graph Graph G2
d-labeled edge t-labeled edge
t-labeled edge

e11 e12 e13 e14 e11 e12 e13 e14
e11 e12 e13 e14 e11 e12 e13 e14
Applying r2
e21 e022 e21 e022
Applying r1
e21 e022 e21 e022

e31 e32 e31 e32 e31 e32 e31 e32

(a) Applying rule 𝑟1 (b) Applying rule 𝑟2

Figure 2: HBR to IDR rules

Then, rule 𝑟2 = (𝐿2 , 𝑅2 ), presented in the top of Figure 2b, is applied to 𝐺2 . Its application
implies finding all maches of 𝐿2 in 𝐺2 and replacing them with 𝑅2 . That means finding all
𝑡-labeled edges and removing them. At this level, it is not necessary to verify if a transitive edge
is immediate. It is clear in its definition (If 𝑎 → 𝑏 and 𝑏 → 𝑐, then 𝑎 → 𝑐) that the transitive
edge does not satisfy the IDR condition. The result of 𝑟2 application is shown in Figure 2b. The
obtained graph 𝐺3 is the IDR graph of the system.

3.2. IDR to CAOS
In order to arrange the events of the IDR graph into ordered sets, based on CAOS abstraction,
we have designed the IDR2CAOS rules: 𝑟3 , 𝑟4 , 𝑟5 for sets creation and 𝑟6 for events association.
These rules are also sequentially executed.
Initially, 𝑟3 = (𝐿3 , 𝑅3 , 𝑁 𝐴𝐶3 ), presented in Figure 3a, is applied to the IDR graph. It verifies
the first rule of the CAOS rules (Table 1, Line 2). It means that, a node 𝑛1 creates a new set if
it does not exist a node 𝑛2 belonging to the causal past of 𝑛1 . This condition is satisfied with
using the negative application condition 𝑁 𝐴𝐶3 : 𝐿3 is replaced with 𝑅3 if 𝑁 𝐴𝐶3 does not
n3 n1 n2 n1 n2
set
r3 = L3 = n 1 , R3 = n 1 ,NAC3 = r4 = L4 = , R4 = set
n1 n3 n3

c-labeled edge
c-labeled edge Graph G4 d-labeled edge Graph G5
Graph G3 = IDR Graph d-labeled edge Graph G4
set set set
set
e11 e12 e13 e14 e11 e12 e13 e14
e11 e12 e13 e14 e11 e12 e13 e14
set
Applying r3 Applying r4
e21 e022 e21 e022 e21 e022 e21 e022

e31 e32 e31 e32 e31 e32 e31 e32

(a) Applying rule 𝑟3 (b) Applying rule 𝑟4

Figure 3: IDR to CAOS rules (Part I)

set
set set
n1 n2 n1 n2 n1 n2 n3
r5 = L5 = , R5 = r6 = L6 = , R6 =
n3 n3 Connection Instructions :
Ci1 = ( n = n1 , p/q = ‘set’ , n’ = n3 , d = in , d’ = in
c-labeled edge Ci2 = ( n = n2 , p/q = ‘set’ , n’ = n3 , d = out , d’ = out
Graph G4 d-labeled edge Graph G5
c-labeled edge
set set set set set Graph G6 Graph G7
d-labeled edge
e11 e12 e13 e14 e11 e12 e13 e14 set set set set set
e11 e12 e13 e14 e12 e13
set set
Applying r5
e21 e022 e21 e022 set
Applying r6
set
e21 e022 e21

set
e31 e32 e31 e32 e31 e32 e11

(a) Applying rule 𝑟5 (b) Applying rule 𝑟6

Figure 4: IDR to CAOS rules (Part II)

exist. A node that satisfies such a condition is denoted by the label “𝑠𝑒𝑡”. In the given example,
only the node 𝑒11 satisfies 𝑁 𝐴𝐶3 (there is no node which precedes 𝑒11 ). 𝑒11 creates a new set.
It is denoted by a label “𝑠𝑒𝑡”. The rule 𝑟4 = (𝐿4 , 𝑅4 ), presented in Figure 3b is nextly applied
to 𝐺4 . It models the second rule of the CAOS rules (Table 1, Line 3). Its application implies, if
the pattern 𝐿4 exists, it will replaced by 𝑅4 . That means, the node 𝑛2 creates a new set denoted
by the label “𝑠𝑒𝑡”. In the used example (Figure 3b), two matches exit (𝑒31 → 𝑒12 , 𝑒31 → 𝑒21 )
and (𝑒31 → 𝑒21 , 𝑒31 → 𝑒12 ). Consequently, in the output graph 𝐺5 , the nodes 𝑒12 and 𝑒21 are
denoted by a label “𝑠𝑒𝑡”.
The rule 𝑟5 = (𝐿5 , 𝑅5 ) is applied to graph 𝐺5 (see Figure 4a). This rule corresponds to the third
rule of the CAOS rules (Table 1, Line 4). Its application implies, if the pattern 𝐿5 exists in 𝐺5 , it
will replaced by 𝑅5 . Consenquently, the node 𝑛2 creates a new set that we denote also by a
label “𝑠𝑒𝑡”. Figure 4a shows the result of 𝑟5 application. In this example, only one match exists
(𝑒12 → 𝑒13 , 𝑒21 → 𝑒13 ) means that 𝑒13 creates a new set, therefore, it is denoted by a label “𝑠𝑒𝑡”.
Finally, 𝑟6 = (𝐿6 , 𝑅6 ) is to associate the rest of events to those which have created a new set
(𝑠𝑒𝑡-labeled nodes). This rule is based on the edNCE approach (see section 2.6.4). Rule 𝑟6 is
IDR edge
Number of rounds
transitive edge

...

Maximum Number
of processes p
...

...

...
...

Figure 5: Maximum number of edges in an HBR graph

also of type SPO. its application implies deleting each occurence of 𝐿6 in 𝐺6 and replacing it
with 𝑅6 . Consequently, 𝑟6 removes two consecutive nodes 𝑛1 , 𝑛2 ∈ 𝐺6 , adds a new node 𝑛3
(𝑠𝑒𝑡-labeled node) and finally, adds new edges to connect the added node to the neighbours of
deleted nodes. The addition of edges is made according to the connection instructions 𝐶𝑖1 and
𝐶𝑖2 , shown in the middle of Figure 4b. Ci1 adds a new edge connection from the added node 𝑛3
to a neighbour of the deleted node 𝑛1 . Ci2 adds a new edge connection from each neighbour of
the deleted node 𝑛2 to the added node 𝑛3 . Rule 𝑟6 is presented and illustrated with an example
in Figure 4b. A first match regroupes 𝑒11 and 𝑒31 in one set. Three others matches exist 𝑒13 and
𝑒32 , the added node regrouping 𝑒13 and 𝑒32 (𝑠𝑒𝑡-labeled node) and 𝑒22 , the new added node and
𝑒14 , respectively. 𝐺7 is the CAOS graph of the system.

4. Evaluation Results
The objective of this section is to illustrate the viability of the IDR graph and CAOS graph
construction and their efficiency in the causal dependency representation.

4.1. Why the IDR and the CAOS graphs are efficient?
Let 𝑝 and 𝑛 be two integers (𝑝 = number of processes in the system, 𝑛 = number of events). The
maximum number of edges in the HBR graph and the IDR graph is when we have the maximum
number of concurrent messages in each round (see Figure 5). Therefore, the number of nodes is
𝑛 = number of rounds × 𝑝.
The maximum number of edges (HBR edges = IDR edges + transitive edges) is:

𝑒 = 𝑝(𝑛-𝑝) + (𝑛−𝑝)(𝑛−2𝑝)
2

The maximum number of edges in the IDR graph is only:

𝑒′ = 𝑝(𝑛-𝑝)

The maximum number of edges in the CAOS graph is equal to the maximum number of edges
in the IDR graph. In fact, in the worst case the number of edges in the CAOS graph generated
from the IDR graph remains the same. Therefore, there is an important reduction of edges from
the HBR graph to the IDR/CAOS graph. Actually, there is also a reduction of nodes and edges
from the IDR graph to the CAOS graph. To show this, we have generated by simulation, the
Vector Clocks of three different system executions with 8, 21 and 50 events (nodes) and with 3, 8
and 15 processes, respectively. The events were triggered assuming a uniform distribution. For
each execution, we have constructed the HBR graph, the IDR graph and the CAOS graph, and
we compared the resulting graphs in terms of their number of nodes and edges. The obtained
results are presented in Figure 6.
100%
600

500

400

HBR
300
IDR
CAOS

200
100%

100
100% 100% 10%
100% 74% 8%
100% 100% 14%
100% 100% 30%15% 57% 9%
50%
0
Nodes Edges Nodes Edges Nodes Edges
Execution
System 1 1 Execution
System 22 Execution
System 33

Figure 6: HBR, IDR and CAOS comparison

The results show that the number of edges is greatly reduced from the HBR graph to the IDR
graph, and that the number of edges and nodes is even more reduced from the HBR graph to
the CAOS graph. Likewise, there is an important reduction of edges and nodes from the IDR
graph to the CAOS graph. The average reduction in the number of edges from the HBR graph
to IDR graph and to the CAOS graph is about 82% and 89%, respectively. The average reduction
in the number of nodes from the HBR graph and the IDR graph to the CAOS graph is about
41%, Finally, the average reduction in the number of edges from the IDR graph to the CAOS
graph is about 36%. We conclude this analysis with the following remark. It is interesting to see
that the reduction performance in the average number of edges in the IDR graph and the CAOS
graph increases as the number of nodes in the HBR graph increases.

4.2. Advantages of using the graph transformation approach
Graph transformation approaches are widely used in various research fields to model and analyze
complex systems that can be represented as graphs [18, 19]. They are used for tasks like modeling
software systems, studying social networks, optimizing control systems, planning transportation
networks, managing business processes and designing robotic behaviors. These approaches
offer a versatile way to model, analyze, and understand complex systems in various disciplines.
Graph transformation techniques can significantly reduce the time required to modify or analyze
graphs. they provide a powerful and intuitive framework for modeling, analyzing, and managing
the complexities of large-scale systems across various research domains. Their flexibility, formal
analysis capabilities, and compatibility with modern software engineering principles make them
well-suited for addressing the challenges posed by such systems. By defining transformation
rules, complex modifications can be applied systematically and automatically to large graphs.
This eliminates the need for time-consuming modifications and allows for efficient updates or
transformations. Graph transformation techniques can handle large-scale graphs efficiently. By
leveraging rule-based transformations, the complexity of graph modifications or analyses can be
managed effectively, allowing for scalability. This scalability ensures that the time cost remains
manageable even for complex graph structures and large datasets. representing distributed
systems as large graphs offers a powerful means to understand, analyze, and model the system’s
architecture, behavior, and interactions. In our case, we need to generate IDR and CAOS graphs
from the HBR graph which is very large graph. Graph transformation approaches have several
advantages when it comes to reducing a graph compared to using algorithmic solutions:

• They offer an intuitive way to express and execute graph reductions, especially for
complex relationships or patterns within the graph.
• Graph transformation excels in pattern matching, making it efficient for identifying and
reducing specific structures in the graph.
• Rule-based reductions simplify the reduction process and ensure transparency and main-
tainability.
• Graph transformation can leverage parallelism for large graphs.

When appropriately applied, graph transformation can provide powerful insights and solu-
tions in a wide range of domains. These advantages stem from the inherent ability of graph
transformation to represent complex structures in a flexible and intuitive way.

5. Conclusion
In this paper, we have presented a graph transformation based approach that constructs, for a
distributed computation, the causal graph (HBR graph), the minimal causal graph (IDR graph) at
a single event level and a causal consistent compact graph (CAOS graph) at an ordered event set
level. we have also illustrated the viability of the IDR graph and the CAOS graph construction
and their efficiency in the causal representation. The results show that both resultant causal
graphs drastically reduce the state-space of a system execution. On average the number of
edges from the HBR graph to IDR graph and the CAOS graph was reduced by 82% and 89%,
respectively, and the number of nodes from the HBR graph to CAOS graph was reduced by 41%.
It is interesting to see that the performance reduction in the average number of edges in the
IDR graph and CAOS graph increases as the number of nodes in the HBR graph increases.

References
[1] J. Helary, R. Netzer, M. Raynal, Consistency issues in distributed checkpoints, IEEE
Transactions on Software Engineering 25 (1999) 274–281.
[2] A. C. Simon, S. E. Pomares-Hernandez, J. R. P. Cruz, A delayed checkpoint approach for
communication-induced checkpointing in autonomic computing, in: 22th IEEE Interna-
tional WETICE Conference, 2013, pp. 56–61.
[3] R. Baldoni, J. Helary, A. Mostefaoui, M. Raynal, A communication-induced checkpointing
protocol that ensures rollback-dependency trackability, in: Symposium on Fault-Tolerant
Computing, 1997, pp. 68–77.
[4] P. Chandra, A. Kshemkalyani, Data-stream-based global event monitoring using pairwise
interactions, Journal of Parallel and Distributed Computing 68 (2008) 729–751.
[5] A. Nakamura, T. Tachikawa, M. Takizawa, Causally ordering group communication
protocol, in: Proceedings of the International Conference on Parallel and Distributed
Systems, 1994, pp. 48–55.
[6] K. Shimamura, K. Tanaka, M. Takizawa, Group communication protocol for multimedia
applications, in: Proceedings of the IEEE International Conference on Computer Networks
and Mobile Computing, ICCNMC, 2001, pp. 303–308.
[7] S. E. Pomares-Hernandez, J. E. Ramirez, L. M. Rosales, G. R. Gomez, An intermedia
synchronisation mechanism for multimedia distributed systems, International Journal of
Internet Protocol Technology 4 (2009) 207–2018.
[8] M. Wehrle, M. Helmert, The causal graph revisited for directed model checking, in:
International Static Analysis Symposium, volume 5673 of LNCS, Springer, 2009, pp. 86–101.
[9] L. Lamport, Time, clocks and the ordering of events in a distributed system, Communica-
tions of the ACM 21 (1978) 558–565.
[10] F. Mattern, Virtual time and global states of distributed systems, in: Proceedings of the
International Workshop on Parallel and Distributed Algorithms, 1988, pp. 215–226.
[11] C. J. Fidge, Timestamps in message-passing systems that preserve the partial ordering,
Proceedings of the 11th Australian Computer Science Conference. K. Raymond (Ed.) 10
(1988) 56–66.
[12] E. Clarke, O. Grumberg, M. Minea, D. Peled, State space reduction using partial order
techniques, International Journal on Software Tools for Technology Transfer 2 (1999)
279–287.
[13] H. Khlif, H. Hadj-Kacem, S. P. Hernandez, A. Hadj-Kacem, A mechanism for the causal
ordered set representation in large-scale distributed systems, in: Proceedings of the 24nd
International WETICE Conference, IEEE Computer Society, 2015, pp. 86–101.
[14] S. E. Pomares-Hernandez, J. Fanchon, K. Drira, The Immediate Dependency Relation: An
Optimal Way to Ensure Causal Group Communication, volume 6, Singapore University
Press and World Scientific Publications, 2004, pp. 61–79.
[15] S. E. Pomares-Hernandez, J. R. P. Cruz, M.Raynal, From the happened-before relation to
the causal ordered set abstraction, Journal of Parallel and Distributed Computing 72 (2012)
791–795.
[16] J. Engelfriet, G. Rozenberg, Handbook of Graph Grammars and Computing by Graph
Transformation, World Scientific Publishing, 1997, pp. 1–94.
[17] G. Rozenberg, Handbook of graph grammars and computing by graph transformation,
World Scientific Publishing (1997).
[18] G. Fayçal, A. Chaoui, A graph transformation based approach for multi-agent systems
reorganization, Multiagent Grid Syst. 15 (2019) 375–394.
[19] H.-J. Kreowski, S. Kuske, A. Lye, A. Windhorst, A graph-transformational approach for
proving the correctness of reductions between NP-problems, Electronic Proceedings in
Theoretical Computer Science 374 (2022) 76–93.