HomeResearchPublications

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

back to overview

Reference

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).

Publication type

Paper in Conference Proceedings

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.

Persons

Organizational Units

  • Institute of Information Systems
  • Hilti Chair of Business Process Management