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, Nov. 1998
10.3745/KIPSTE.1998.5.11.2855,   PDF Download:

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
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


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.