Fast protocols for leader election and spanning tree construction in a distributed network


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access 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

Supplementary Files
Action
1. JATS XML

Copyright (c) 2017 Pleiades Publishing, Inc.