Juhana Laurinharju · Jukka Suomela

# Brief announcement: Linial’s lower bound made easy

PODC 2014 · 33rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Paris, France, July 2014 ·

# Abstract

Linial’s seminal result shows that any deterministic distributed algorithm that finds a $3$-colouring of an $n$-cycle requires at least $\log^*(n)/2 - 1$ communication rounds. We give a new simpler proof of this theorem.

# Publication

Magnús Halldórsson and Shlomi Dolev (Eds.): PODC’14, Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, July 15–18, 2014, Paris, France, pages 377–378, ACM Press, New York, 2014

ISBN 978-1-4503-2944-6