AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

MPI Audience

English

45 Minutes

Saarbrücken

Consider a complete communication network of n nodes, where the nodes receive a common clock pulse. We study the synchronous c-counting problem: given any starting state and up to f faulty nodes with arbitrary behaviour, the task is to eventually have all correct nodes counting modulo c in agreement. Thus, we are considering algorithms that are self-stabilizing despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have linear stabilisation time in f, (3) use a small number of states, and (4) achieve almost-optimal resilience. Prior algorithms either resort to randomisation, use a large number of states, or have poor resilience. In particular, we achieve an exponential improvement in the space complexity of deterministic algorithms, while still achieving linear stabilisation time and almost-linear resilience.

This is joint work with Christoph Lenzen and Jukka Suomela.

Manuscript: http://arxiv.org/abs/1503.06702

Joel Rybicki

--email hidden

passcode not visible

logged in users only