الگوریتم انحصار متقابل توزیع شده احتمالی با مرتب سازی دقیق غیر اریب
Abstract
1- Introduction
2- Related work
3- Probabilistic characterization of aggregate set
4- Resolving aggregate set
5- The algorithms
6- Analysis of correctness and topological properties
7- Experimental evaluation
8- Comparative analysis
9- Conclusion
References
Abstract
The applications of distributed computing systems are pervasive in nature involving multiple shared resources. The distributed mutual exclusion algorithms of various classes are employed to control concurrency of accessing shared resources maintaining data consistency. In general, the distributed mutual exclusion algorithms are designed based on fixed or dynamic graph structures formed by a set of processes, where the distributed mutual exclusion mechanisms are realized depending upon timestamp based ordering of events or by employing token circulation in the graph. On the contrary, in large scale heterogeneous distributed systems, an aggregate set of processes can be generated under special circumstances, where processes in a group are equally eligible to enter into critical section. In order to maintain safety and liveness properties of mutual exclusion in such cases, the probabilistic characterization as well as topological analysis of aggregate set in computing space is necessary. This paper proposes a probabilistic algorithm and its topological characterization for mutual exclusion in aggregate set of processes. The analysis of failure model of strictly ordered distributed inclusion–exclusion designs is constructed in the presence of aggregate set. The unbiased probabilistic algorithm is based on two-phased elastic randomization. The algorithm is evaluated through detailed simulation and, the related probabilistic characterization in topological subspace is evaluated. A detailed comparative analysis of the algorithm with respect to other distributed mutual exclusion algorithms is presented.
Introduction
The present day distributed computing systems have two distinct characteristics namely, multilevel heterogeneities and, large scale involving thousands of computing nodes. The multi-level heterogeneities include network level heterogeneity, hardware level heterogeneity and, system software level heterogeneity. Traditionally, the distributed computing systems are modeled as arbitrary graph structures, where nodes of a graph represent distributed processes and the edges of a graph represent network links. However, a distributed computing system can be modeled in view of topological spaces comprised of sets of distributed events generated by individual processes [23]. In any case, a distributed computing system maintains a set of shared resources concurrently accessed by a subset of distributed processes, which requires designing of mutual exclusion for Critical Sections (CS) [12]. The main aim of mutual exclusion is to maintain data consistency, liveness and fairness of computation involving shared resources [2, 6, 11]. The traditional distributed mutual exclusion (mutex) algorithms are designed employing two approaches namely, (1) logical clock based timestamps for ordering of requests in a group of processes, and (2) repeated circulation of a token between processes [7]. If a token is lost then the fault detection and regeneration of a new token may incorporate unpredictable delay in a system.