کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331401 | 686688 | 2005 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An elementary proof that Herman's Ring is Î(N2)
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An elementary proof that Herman's Ring is Î(N2) An elementary proof that Herman's Ring is Î(N2)](/preview/png/10331401.png)
چکیده انگلیسی
Herman's Ring [Inform. Process. Lett. 35 (1990) 63; http://www.cs.uiowa.edu/ftp/selfstab/H90.ps.gz] is an algorithm for self-stabilization of N identical processors connected uni-directionally in a synchronous ring; in its original form it has been shown to achieve stabilization, with probability one, in expected steps O(N2logN). We give an elementary proof that the original algorithm is in fact O(N2); and for the special case of three tokens initially we give an exact (quadratic) solution of 4abc/N, where a,b,c are the tokens' initial separations. Thus the algorithm overall has worst-case expected running time of Î(N2). Although we use only simple matrix algebra in the proof, the approach was suggested by the general notions of abstraction, nondeterminism and probabilistic variants [A. McIver, C. Morgan, Refinement and Proof for Probabilistic Systems, Technical Monographs in Computer Science, Springer-Verlag, New York, 2004]. It is hoped they could also be useful for other, similar problems. We conclude with an open problem concerning the worst-case analysis.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 94, Issue 2, 30 April 2005, Pages 79-84
Journal: Information Processing Letters - Volume 94, Issue 2, 30 April 2005, Pages 79-84
نویسندگان
Annabelle McIver, Carroll Morgan,