Paper Info
Title
A Mechanism for the Causal Ordered Set Representation in Large-Scale Distributed Systems
Abstract
Distributed systems have undergone a very fast evolution in the last years. Large-scale distributed systems have become an integral part of everyday life with the development of new large-scale applications, consisting of thousands of computers and supporting millions of users. Examples include global Internet services, cloud computing systems, \"big data\" analytic platforms, peer-to-peer systems, wireless sensor networks and so on. The recent research addresses questions related to the way of how to design, build, operate and maintain large-scale distributed systems. Another question associated to it is how to represent and ensure causal dependencies in such systems in a optimal way. Causal dependencies have been established according to the Happened-Before Relation (HBR), which was introduced by Lamport. The HBR establishes a strict partial order among the events in a system, and therefore, one main problem linked to it is the combinatorial state explosion. To attack this problem the Causal Order Set Abstraction (CAOS) theory arises. CAOS attains the optimal representation at the set level of the causal dependencies of events in a distributed system. In this paper, we propose a mechanism based on the HBR and the Immediate Dependency Relation to automatically model any large-scale distributed system execution into the CAOS form. The resultant CAOS model, expressed in the form of a graph, drastically reduce the state-space of a system. In general, the resultant CAOS graph 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 illustrate how the CAOS graph can be used for validation purposes. The mechanism is implemented in C++. The results of its execution shows the viability to support large-scale systems.
Year
DOI
Venue
2015
10.1109/WETICE.2015.20
WETICE Workshops
Keywords
Field
DocType
Distributed system, Happened Before Relation, Immediate Dependency Relation, Causal Ordered Set Abstraction
Dependency relation,Ordered set,Graph,Abstraction,Computer science,Theoretical computer science,Wireless sensor network,Big data,Distributed computing,The Internet,Debugging
Conference
ISSN
Citations 
PageRank 
1524-4547
0
0.34
References 
Authors
7
4
Name
Order
Citations
PageRank
Houda Khlif131.44
Hatem Hadj Kacem24714.43
Saúl E. Pomares Hernández320.73
Ahmed Hadj Kacem429564.22