• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

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

Problems of Information Transmission. 2017. Vol. 53. No. 2. P. 183-201.
M.N.Vyalyi, Khuziev I.

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(Dlog L+L), where L is the size of the minimal identifier and D is the network diameter.