Trading Bit, Message, and Time Complexity of Distributed Algorithms Algorithm for Growth-Bounded Graphs

zurück zur Übersicht

Referenz

Schneider, J., & Wattenhofer, R. (2011). Trading Bit, Message, and Time Complexity of Distributed Algorithms Algorithm for Growth-Bounded Graphs. Paper presented at the Symposium on Distributed Computing (DISC).

Publikationsart

Beitrag in Konferenztagungsband

Abstract

We present tradeoffs between time complexity t, bit complexity b, and message complexity m. This allows to derive lower bounds on the time complexity for distributed algorithms as we demonstrate for the MIS and the coloring problems. We reduce the bit-complexity of the state-of-the art O(Delta) coloring algorithm without changing its time and message complexity. We also give techniques for several problems that require a time increase of tc (for an arbitrary constant c) to cut both bit and message complexity by Omega(log t). This improves on the traditional time-coding technique which does not allow to cut message complexity.

Mitarbeiter

Einrichtungen

  • Institut für Wirtschaftsinformatik
  • Hilti Lehrstuhl für Business Process Management