Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Towards Optimal Synchronous Counting
Speaker:Joel Rybicki
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Date, Time and Location
Date:Friday, 27 March 2015
Duration:45 Minutes
Building:E1 4
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.


Name(s):Joel Rybicki
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Joel Rybicki, 03/25/2015 01:57 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Joel Rybicki, 03/25/2015 02:00 PM
  • Joel Rybicki, 03/25/2015 01:57 PM -- Created document.