Christoph Lenzen: Efficient Construction of Global Time in SoCs despite Arbitrary Faults

Given a fully connected synchronous system in which rounds are labeled by integers modulo 2^lambda (i.e., nodes have small synchronized lambda-bit clocks), we would like to construct large (say 32- or 64-bit) synchronized clocks. The catch is that we require (i) Byzantine fault-tolerance, (ii) self-stabilization, and (iii) have channels of very few (ideally just 1 or 2) bits width. We present novel consensus-based techniques to achieve efficient solutions to this problem, both in terms of stabilization time and the minimal values of lambda.