---
_id: '16903'
abstract:
- lang: eng
  text: "We consider the clock synchronization problem in the (discrete) beeping model:
    Given a network of $n$ nodes with each node having a clock value $\\delta(v) \\in
    \\{0,\\ldots T-1\\}$, the goal is to synchronize the clock values of all nodes
    such that they have the same value in any round.\r\nAs is standard in clock synchronization,
    we assume \\emph{arbitrary activations} for all nodes, i.e., the nodes start their
    protocol at an arbitrary round (not limited to $\\{0,\\ldots,T-1\\}$).\r\nWe give
    an asymptotically optimal algorithm that runs in $4D + \\Bigl\\lfloor \\frac{D}{\\lfloor
    T/4 \\rfloor} \\Bigr \\rfloor \\cdot (T \\mod 4) = O(D)$ rounds, where $D$ is
    the diameter of the network.\r\nOnce all nodes are in sync, they beep at the same
    round every $T$ rounds.\r\nThe algorithm drastically improves on the $O(T D)$-bound
    of \\cite{firefly_sync} (where $T$ is required to be at least $4n$, so the bound
    is no better than $O(nD)$).\r\nOur algorithm is very simple as nodes only have
    to maintain $3$ bits in addition to the $\\lceil \\log T \\rceil$ bits needed
    to maintain the clock.\r\nFurthermore we investigate the complexity of \\emph{self-stabilizing}
    solutions for the clock synchronization problem: We first show lower bounds of
    $\\Omega(\\max\\{T,n\\})$ rounds on the runtime and $\\Omega(\\log(\\max\\{T,n\\}))$
    bits of memory required for any such protocol.\r\nAfterwards we present a protocol
    that runs in $O(\\max\\{T,n\\})$ rounds using at most $O(\\log(\\max\\{T,n\\}))$
    bits at each node, which is asymptotically optimal with regards to both, runtime
    and memory requirements."
author:
- first_name: Michael
  full_name: Feldmann, Michael
  id: '23538'
  last_name: Feldmann
- first_name: Ardalan
  full_name: Khazraei, Ardalan
  last_name: Khazraei
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Feldmann M, Khazraei A, Scheideler C. Time- and Space-Optimal Discrete Clock
    Synchronization in the Beeping Model. In: <i>Proceedings of the 32nd ACM Symposium
    on Parallelism in Algorithms and Architectures (SPAA)</i>. ACM; 2020. doi:<a href="https://doi.org/10.1145/3350755.3400246">10.1145/3350755.3400246</a>'
  apa: Feldmann, M., Khazraei, A., &#38; Scheideler, C. (2020). Time- and Space-Optimal
    Discrete Clock Synchronization in the Beeping Model. In <i>Proceedings of the
    32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>.
    ACM. <a href="https://doi.org/10.1145/3350755.3400246">https://doi.org/10.1145/3350755.3400246</a>
  bibtex: '@inproceedings{Feldmann_Khazraei_Scheideler_2020, title={Time- and Space-Optimal
    Discrete Clock Synchronization in the Beeping Model}, DOI={<a href="https://doi.org/10.1145/3350755.3400246">10.1145/3350755.3400246</a>},
    booktitle={Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms
    and Architectures (SPAA)}, publisher={ACM}, author={Feldmann, Michael and Khazraei,
    Ardalan and Scheideler, Christian}, year={2020} }'
  chicago: Feldmann, Michael, Ardalan Khazraei, and Christian Scheideler. “Time- and
    Space-Optimal Discrete Clock Synchronization in the Beeping Model.” In <i>Proceedings
    of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>.
    ACM, 2020. <a href="https://doi.org/10.1145/3350755.3400246">https://doi.org/10.1145/3350755.3400246</a>.
  ieee: M. Feldmann, A. Khazraei, and C. Scheideler, “Time- and Space-Optimal Discrete
    Clock Synchronization in the Beeping Model,” in <i>Proceedings of the 32nd ACM
    Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2020.
  mla: Feldmann, Michael, et al. “Time- and Space-Optimal Discrete Clock Synchronization
    in the Beeping Model.” <i>Proceedings of the 32nd ACM Symposium on Parallelism
    in Algorithms and Architectures (SPAA)</i>, ACM, 2020, doi:<a href="https://doi.org/10.1145/3350755.3400246">10.1145/3350755.3400246</a>.
  short: 'M. Feldmann, A. Khazraei, C. Scheideler, in: Proceedings of the 32nd ACM
    Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, 2020.'
date_created: 2020-04-29T07:16:35Z
date_updated: 2022-01-06T06:52:58Z
department:
- _id: '79'
doi: 10.1145/3350755.3400246
external_id:
  arxiv:
  - '2005.07388'
language:
- iso: eng
project:
- _id: '96'
  name: Algorithmen für programmierbare Materie in einem physiologischen Medium
publication: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
  Architectures (SPAA)
publisher: ACM
status: public
title: Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model
type: conference
user_id: '23538'
year: '2020'
...