Election on faulty rings with incomplete size information

摘要

This paper considers the election problem on asynchronous ring networks in which one link may undetectably fail. It is assumed that the size of the ring in inexact form is known to the processes, i.e., a lower and/or upper bound. For the case of u/2l/spl les/u, where l is a lower bound and u is an upper bound on ring size, an optimal algorithm of worst case message complexity O(nlog n) is given. For the case l/spl les/u/2 it is shown that election is unsolvable. By assuming that each process in addition knows the identifiers of its two neighbors, the latter case becomes solvable. An algorithm of complexity O(nlog n+(n-l)n) is given that is proven optimal.