Fast protocols for leader election and spanning tree construction in a distributed network |
| |
Authors: | M. N. Vyalyi I. M. Khuziev |
| |
Affiliation: | 1.Dorodnitsyn Computing Center of the Russian Academy of Sciences,Moscow,Russia;2.National Research University—Higher School of Economics,Moscow,Russia;3.Moscow Institute of Physics and Technology (State University),Moscow,Russia |
| |
Abstract: | We consider leader election and spanning tree construction problems in a synchronous network. Protocols are designed under the assumption that nodes in the network have identifiers but the size of an identifier is unlimited. We present fast protocols with runtime O(D log L+L), where L is the size of the minimal identifier and D is the network diameter. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|