Average case behavior of election algorithms for unidirectional rings

摘要

The problem of election for asynchronous rings of processors is considered. Because of its many applications, this problem is important for both the practical and theoretical points of view. Thus, the availability of an algorithm that is good in both the average and the worst case has significant meaning. As an effort to achieve this goal, a new algorithm is designed and is simulated sequentially and analyzed by statistical methods. The statistical analysis demonstrates that the algorithm proposed is near optimal in the average case while its worst case message complexity is still O(n lg n). This is accomplished with the cost of one more bit in every message. This result is very interesting because it is contrary to the common belief that algorithms with good worst case complexity perform worse in the average case