EFFICIENT COUNTING WITH OPTIMAL RESILIENCE

Show full item record



Permalink

http://hdl.handle.net/10138/224608

Citation

Lenzen , C , Rybicki , J & Suomela , J 2017 , ' EFFICIENT COUNTING WITH OPTIMAL RESILIENCE ' , SIAM Journal on Computing , vol. 46 , no. 4 , pp. 1473-1500 . https://doi.org/10.1137/16M107877X

Title: EFFICIENT COUNTING WITH OPTIMAL RESILIENCE
Author: Lenzen, Christoph; Rybicki, Joel; Suomela, Jukka
Contributor: University of Helsinki, Biosciences
Date: 2017
Language: eng
Number of pages: 28
Belongs to series: SIAM Journal on Computing
ISSN: 0097-5397
URI: http://hdl.handle.net/10138/224608
Abstract: 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 behavior, the task is to eventually have all correct nodes labeling the pulses with increasing values 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 optimal resilience, (3) have a linear stabilization time in f (asymptotically optimal), (4) use a small number of states, and, consequently, (5) communicate a small number of bits per round. Prior algorithms either resort to randomization, use a large number of states and need high communication bandwidth, or have suboptimal resilience. In particular, we achieve an exponential improvement in both state complexity and message size for deterministic algorithms. Moreover, we present two complementary approaches for reducing the number of bits communicated during and after stabilization.
Subject: self-stabilization
Byzantine fault-tolerance
CLOCK SYNCHRONIZATION
ASYNCHRONOUS UNISON
AGREEMENT
FAULTS
TIME
111 Mathematics
113 Computer and information sciences
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
16M107877X.pdf 349.9Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record