کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
432119 | 688713 | 2009 | 8 صفحه PDF | دانلود رایگان |
This paper presents two new randomized distributed algorithms for the generation of acyclic orientations upon anonymous distributed systems of arbitrary topology. Both algorithms, called Alg-Neighbors and Alg-Edges , make use of biased and unbiased dice having f≥2f≥2 faces, and are analyzed in terms of correctness, expected time complexity and rate of convergence. First, the Alg-Neighbors algorithm is presented as a generalization of the Calabrese/França algorithm for dice (or coins) with 2 faces. It is proved that a convenient biasing function applied to all dice changes the expected time complexity from sub-exponential, i.e., O(f(ff−1)n−1) (for unbiased dice with ff faces), to O(n)O(n), where nn is the number of the system’s nodes. Next, it is shown that the Alg-Edges algorithm is able to produce acyclic orientations in O(logfm)O(logfm) steps with high probability, where mm denotes the total number of edges. Finally, a speed of convergence versus quality of acyclic orientation generation (associated number of colors) tradeoff is identified between Alg-Neighbors and Alg-Edges algorithms. Computational experiments were carried out in order to provide a more accurate description of the behavior of both algorithms.
Journal: Journal of Parallel and Distributed Computing - Volume 69, Issue 3, March 2009, Pages 239–246