[{"user_id":"23538","_id":"16903","uri_base":"https://ris.uni-paderborn.de","project":[{"name":"Algorithmen für programmierbare Materie in einem physiologischen Medium","_id":"96"}],"status":"public","dini_type":"doc-type:conferenceObject","dc":{"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"title":["Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model"],"language":["eng"],"source":["Feldmann M, Khazraei A, Scheideler C. Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model. In: *Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)*. ACM; 2020. doi:10.1145/3350755.3400246"],"rights":["info:eu-repo/semantics/closedAccess"],"date":["2020"],"description":["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."],"publisher":["ACM"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1145/3350755.3400246","info:eu-repo/semantics/altIdentifier/arxiv/2005.07388"],"creator":["Feldmann, Michael","Khazraei, Ardalan","Scheideler, Christian"],"identifier":["https://ris.uni-paderborn.de/record/16903"]},"date_updated":"2022-01-06T06:52:58Z","external_id":{"arxiv":[]},"creator":{"id":"23538","login":"mfeldma2"},"author":[{"first_name":"Michael","last_name":"Feldmann","id":"23538"},{"last_name":"Khazraei","first_name":"Ardalan"},{"id":"20792","last_name":"Scheideler","first_name":"Christian"}],"department":[{"_id":"79","tree":[{"_id":"7"},{"_id":"34"},{"_id":"44"},{"_id":"43"}]}],"publication":"Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","type":"conference","citation":{"chicago":"Feldmann, Michael, Ardalan Khazraei, and Christian Scheideler. “Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model.” In *Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)*. ACM, 2020. https://doi.org/10.1145/3350755.3400246.","ieee":"M. Feldmann, A. Khazraei, and C. Scheideler, “Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model,” in *Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)*, 2020.","short":"M. Feldmann, A. Khazraei, C. Scheideler, in: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, 2020.","bibtex":"@inproceedings{Feldmann_Khazraei_Scheideler_2020, title={Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model}, DOI={10.1145/3350755.3400246}, 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} }","apa":"Feldmann, M., Khazraei, A., & Scheideler, C. (2020). Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model. In *Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)*. ACM. https://doi.org/10.1145/3350755.3400246","mla":"Feldmann, Michael, et al. “Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model.” *Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)*, ACM, 2020, doi:10.1145/3350755.3400246."},"language":[{}],"date_created":"2020-04-29T07:16:35Z","abstract":[{"lang":"eng"}]}]