MCSR (Minimal Causal and Set Representation) approach 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 approach begins receiving a database of Vector Clocks as input, from which the fully-causal HBR original graph is generated. Then, by using graph transformation rules, the IDR and the CAOS graphs are generated. Two sets of rules are proposed: the "HBR2IDR" for the generation of the IDR graph and the "IDR2CAOS" for the generation of the CAOS graph.

The gain of such graphs is shown by comparing them with the HBR graph in terms of their number of nodes and edges. 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 exist 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%.

The resultant causal graphs can be used for different purposes, such as for the design of more efficient algorithms, validaion, verification, and/or the debugging of the existing ones, among others.

Retrieved from http://homepages.laas.fr/khalil/GMTE/index.php?n=GMTE.MCSR

Page last modified on January 21, 2015, at 06:42 PM EST