self-stabilizing
| العنوان: | self-stabilizing |
|---|---|
| المؤلفون: | Joel Rybicki, Christoph Lenzen |
| المصدر: | Distributed Computing |
| سنة النشر: | 2019 |
| مصطلحات موضوعية: | FOS: Computer and information sciences, Computer Networks and Communications, Computer science, Deterministic algorithm, Modulo, Binary number, Response time, 0102 computer and information sciences, Topology, 01 natural sciences, Theoretical Computer Science, 03 medical and health sciences, Task (computing), 0302 clinical medicine, Asymptotically optimal algorithm, Computational Theory and Mathematics, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Hardware and Architecture, 030220 oncology & carcinogenesis, Node (circuits), Distributed, Parallel, and Cluster Computing (cs.DC), State (computer science) |
| الوصف: | 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 Comment: 1+30 pages, 6 figures, extended and revised version |
| وصف الملف: | application/pdf |
| اللغة: | English |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2ef39b4157ca1f50db9e9ae05a0ca0c8 https://hdl.handle.net/21.11116/0000-0004-7AD6-221.11116/0000-0004-7AD8-0 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi.dedup.....2ef39b4157ca1f50db9e9ae05a0ca0c8 |
| قاعدة البيانات: | OpenAIRE |
| الوصف غير متاح. |