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 diferent purposes, such as for the design of more eficient 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.
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
computation, 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 [
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, afects 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 ,.
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 ¬( → ∨ → )
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: ∙ 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:
[] := [] + 1 := ( , )
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 () < ()
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 ||
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 diferent 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 diferent set than the sets for and .
1. A new set () is created in when: C1. ∃ ∈ , ¬(∃ ∈ : ∈ )
1 = { : ∅ ↓ } or () ← 2 = { : ∃(, ) ∈ ; ↓ ∧ ↓ } or
3 = { : ∃(, ) ∈ ; ↓ ∧ ↓ } 2. The rest of the events ′ ∈ are assigned to a set () ∈ as follows: C2. ∃ () ∈ , ∃′ ∈ , ¬(∃ ∈ : ′ ∈ ) () ← 4. () ∪ {′ : ∃ ∈ (), ∃ ∈ ; ↓ ′ ∧ ¬( ↓ )} 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 + ↓ −
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 .
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.
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 diference 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 = (∖).
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 .
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.
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).
VCs Database « VCs2HBR »
VCs comparator
HBR
Graph « HBR2IDR »
Rule file
GMTE « IDR2CAOS »
Rule file
IDR Graph
GMTE
CAOS Graph Our solution is based on two main approaches which are SPO and edNCE. The SPO approach ofers 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. 1GMTE 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.
r1 =
L1 = Graph G1 = HBR Graph n1 c n2 n3
, R1 = c-labeled edge d-labeled edge t-labeled edge n1
n2 n3
Graph G2 e21 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.
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
Graph G4 e11 e12 e13 e14 e12 e13
e14 e21 e022 Applying r3 e21
e022 set e11 e31 set e11 e31 r4=
L4 = n3 c-labeled edge d-labeled edge set e11 n1 n2 set n3 Graph G5 set e12
e13 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 Number of rounds
IDR edge transitive edge ...
...
...
. . . 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.
The objective of this section is to illustrate the viability of the IDR graph and CAOS graph construction and their eficiency in the causal dependency representation.
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: The maximum number of edges in the IDR graph is only: = (-) + (− )(− 2)
2 ′ = (-) 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 diferent 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.
600 500 400 300 200 100 0
100% 100% 100%50% 100%30%15% 100% 100%57% 14%9% 100% 100%74%
NodesESxeycsutetmion11Edges NodesExSecyusteiomn2 Edges
NodesExSecyusteiomn3 Edges 100% 10%8% 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.
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 ofer 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 eficient updates or transformations. Graph transformation techniques can handle large-scale graphs eficiently. By leveraging rule-based transformations, the complexity of graph modifications or analyses can be managed efectively, 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 ofers 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 ofer 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 eficient for identifying and reducing specific structures in the graph. • Rule-based reductions simplify the reduction process and ensure transparency and maintainability.
• Graph transformation can leverage parallelism for large graphs.
When appropriately applied, graph transformation can provide powerful insights and solutions 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.
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 eficiency 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. [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, Communications 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.