선거는 분산 컴퓨팅에서 기본적인 문제에 해당한다. f≤[(n-1)/2]일때 우리는 한 노드에 연결된 최대 f 링크를 가지는 네트워크에서 n 개의 노드를 고려한다. 보통 지도자를 선거로 뽑거나, 최대 인식자를 찾거나, 스패닝 츄리를 구성하는 것은 메시지 복잡도가 같은 차수를 가지기 때문에 동일 문제의 범주에 속한다. 본 논문은 스패팅 츄리를 이용하여 간헐 링크 고장이 있는 비동기 완전 네트워크에서 지도자 선거 알고리즘을 위한 메시지 복잡도의 낮은 경계가 O(n^3) 임을 증명한다.

Election is a fundamental problem in the distributed computing. We consider n nodes in the network with f maximum number of faulty links incident on each node, where f≤[(n-1)/2]. In general, electing a leader, finding the maximum identifier and constructing a spanning tree belong to the same class in the distributed computing because of the same order of the message complexity. Using a spanning tree, we prove that the lower bound of message complexity for a leader election algorithm in an asynchronous complete network with intermittent link faults is O(n^3).