---
_id: '76'
abstract:
- lang: eng
  text: 'Consider a fully-connected synchronous distributed system consisting of n
    nodes, where up to f nodes may be faulty and every node starts in an arbitrary
    initial state. In the synchronous C-counting problem, all nodes need to eventually
    agree on a counter that is increased by one modulo C in each round for given C>1.
    In the self-stabilising firing squad problem, the task is to eventually guarantee
    that all non-faulty nodes have simultaneous responses to external inputs: if a
    subset of the correct nodes receive an external “go” signal as input, then all
    correct nodes should agree on a round (in the not-too-distant future) in which
    to jointly output a “fire” signal. Moreover, no node should generate a “fire”
    signal without some correct node having previously received a “go” signal as input.
    We present a framework reducing both tasks to binary consensus at very small cost.
    For example, we obtain a deterministic algorithm for self-stabilising Byzantine
    firing squads with optimal resilience f<n/3, asymptotically optimal stabilisation
    and response time O(f), and message size O(log f). As our framework does not restrict
    the type of consensus routines used, we also obtain efficient randomised solutions.'
article_processing_charge: Yes (via OA deal)
author:
- first_name: Christoph
  full_name: Lenzen, Christoph
  last_name: Lenzen
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
citation:
  ama: Lenzen C, Rybicki J. Near-optimal self-stabilising counting and firing squads.
    <i>Distributed Computing</i>. 2018. doi:<a href="https://doi.org/10.1007/s00446-018-0342-6">10.1007/s00446-018-0342-6</a>
  apa: Lenzen, C., &#38; Rybicki, J. (2018). Near-optimal self-stabilising counting
    and firing squads. <i>Distributed Computing</i>. Springer. <a href="https://doi.org/10.1007/s00446-018-0342-6">https://doi.org/10.1007/s00446-018-0342-6</a>
  chicago: Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting
    and Firing Squads.” <i>Distributed Computing</i>. Springer, 2018. <a href="https://doi.org/10.1007/s00446-018-0342-6">https://doi.org/10.1007/s00446-018-0342-6</a>.
  ieee: C. Lenzen and J. Rybicki, “Near-optimal self-stabilising counting and firing
    squads,” <i>Distributed Computing</i>. Springer, 2018.
  ista: Lenzen C, Rybicki J. 2018. Near-optimal self-stabilising counting and firing
    squads. Distributed Computing.
  mla: Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting
    and Firing Squads.” <i>Distributed Computing</i>, Springer, 2018, doi:<a href="https://doi.org/10.1007/s00446-018-0342-6">10.1007/s00446-018-0342-6</a>.
  short: C. Lenzen, J. Rybicki, Distributed Computing (2018).
corr_author: '1'
date_created: 2018-12-11T11:44:30Z
date_published: 2018-09-12T00:00:00Z
date_updated: 2025-04-15T06:53:15Z
day: '12'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/s00446-018-0342-6
external_id:
  isi:
  - '000475627800005'
file:
- access_level: open_access
  checksum: 872db70bba9b401500abe3c6ae2f1a61
  content_type: application/pdf
  creator: dernst
  date_created: 2018-12-17T14:21:22Z
  date_updated: 2020-07-14T12:48:01Z
  file_id: '5711'
  file_name: 2018_DistributedComputing_Lenzen.pdf
  file_size: 799337
  relation: main_file
file_date_updated: 2020-07-14T12:48:01Z
fulldoi: https://doi.org/10.1007/s00446-018-0342-6
has_accepted_license: '1'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
publication: Distributed Computing
publication_status: published
publisher: Springer
publist_id: '7978'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Near-optimal self-stabilising counting and firing squads
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...