Communication-Efficient Broadcasting in Complete Networks with Dynamic Faults | Theory of Computing Systems Skip to main content
Springer Nature Link
Log in

Communication-Efficient Broadcasting in Complete Networks with Dynamic Faults

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

We consider the problem of message (and bit) efficient broadcasting in complete networks with dynamic faults. Despite the simplicity of the setting, the problem turned out to be surprisingly interesting from the algorithmic point of view. In this paper we show an Ω(n + t f t/(t – 1)) lower bound on the number of messages sent by any t-step broadcasting algorithm, where f is the number of faults per step. The core of the paper contains a constructive O(n + t f (t + 1)/t) upper bound. The algorithms involved are of time complexity O(t), not strictly t. In addition, we present a bit-efficient algorithm of O(n log2 n) bit and O(log n) time complexities. We also show that it is possible to achieve the same message complexity even if the nodes do not know the id’s of their neighbours, but instead have only a Weak Sense of Direction.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

  1. School of Information Technology and Engineering, University of Ottawa, 800 King Edward Avenue, P.O. Box 450, Stn. A, Ottawa, Ontario, K1N 6N5, Canada

    Stefan Dobrev

Authors
  1. Stefan Dobrev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stefan Dobrev.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dobrev, S. Communication-Efficient Broadcasting in Complete Networks with Dynamic Faults. Theory Comput Systems 36, 695–709 (2003). https://doi.org/10.1007/s00224-003-1134-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-003-1134-2

Search

Navigation