Christoph Lenzen & Ulrich Schmid

Date: 17:00, Thursday, September 19, 2013
Speaker: Christoph Lenzen & Ulrich Schmid
Venue: IST Austria

We study the problem of triggering synchronous actions in
a distributed system. In sharp contrast to clock trees, which are
typically used for this purpose (e.g., in VLSI circuits or computer
networks), we are aiming at approaches that are both
self-stabilizing and Byzantine fault-tolerant. Moreover, we allow
for distributing trigger signals from multiple synchronized clock
sources. Interestingly, during Millions of years, evolution developed
solutions with similar properties for critical biological subsystems
such as the heart.

We argue that grid topologies, in particular a simple hexagonal
grid (termed HEX), provide a viable and scalable alternative to
traditional clock distribution approaches. HEX tolerates a limited
number of arbitrarily failing nodes and, on top of that, can
recover from an unbounded number of arbitrary transient faults.
I will conclude the talk with (i) a brief discussion of some lessons
learned, in particular the need for formal verification to overcome
the exploding proof complexity, and (ii) some relations to biological
systems. The presentation is tailored to a general audience, without
assuming previous knowledge

Posted in RiSE Seminar