Email this article Fast protocols for leader election and spanning tree construction in a distributed network
- Authors: Vyalyi M.N.1,2,3, Khuziev I.M.3
-
Affiliations:
- Dorodnitsyn Computing Center of the Russian Academy of Sciences
- National Research University—Higher School of Economics
- Moscow Institute of Physics and Technology (State University)
- Issue: Vol 53, No 2 (2017)
- Pages: 183-201
- Section: Communication Network Theory
- URL: https://journal-vniispk.ru/0032-9460/article/view/166388
- DOI: https://doi.org/10.1134/S0032946017020065
- ID: 166388
Cite item
Open Access
Access granted
Subscription Access
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.
About the authors
M. N. Vyalyi
Dorodnitsyn Computing Center of the Russian Academy of Sciences; National Research University—Higher School of Economics; Moscow Institute of Physics and Technology (State University)
Author for correspondence.
Email: vyalyi@gmail.com
Russian Federation, Moscow; Moscow; Moscow
I. M. Khuziev
Moscow Institute of Physics and Technology (State University)
Email: vyalyi@gmail.com
Russian Federation, Moscow
Supplementary files
