Distrbuted Processing and Lower Bound of Message Complexity for Election Alogorithm in a Complete Network with Intermittent Faults 


Vol. 5,  No. 11, pp. 2855-2861, Nov.  1998
10.3745/KIPSTE.1998.5.11.2855


PDF
  Abstract

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).

  Statistics


  Cite this article

[IEEE Style]

K. S. Dong, "Distrbuted Processing and Lower Bound of Message Complexity for Election Alogorithm in a Complete Network with Intermittent Faults," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 5, no. 11, pp. 2855-2861, 1998. DOI: 10.3745/KIPSTE.1998.5.11.2855.

[ACM Style]

Kim Seong Dong. 1998. Distrbuted Processing and Lower Bound of Message Complexity for Election Alogorithm in a Complete Network with Intermittent Faults. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 5, 11, (1998), 2855-2861. DOI: 10.3745/KIPSTE.1998.5.11.2855.