| Item type |
デフォルトアイテムタイプ_（フル）(1) |
| 公開日 |
2025-01-27 |
| タイトル |
|
|
タイトル |
Neighborhood mutual remainder: self-stabilizing distributed implementation and applications |
|
言語 |
en |
| 作成者 |
Dolev, Shlomi
Kamei, Sayaka
Katayama, Yoshiaki
Ooshita, Fukuhito
Wada , Koichi
|
| アクセス権 |
|
|
アクセス権 |
open access |
|
アクセス権URI |
http://purl.org/coar/access_right/c_abf2 |
| 権利情報 |
|
|
言語 |
en |
|
権利情報 |
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s00236-023-00450-8 |
| 権利情報 |
|
|
言語 |
en |
|
権利情報 |
This is not the published version. Please cite only the published version. |
| 権利情報 |
|
|
言語 |
ja |
|
権利情報 |
この論文は出版社版ではありません。引用の際には出版社版をご確認、ご利用ください。 |
| 内容記述 |
|
|
内容記述 |
Motivated by the need to convert move-atomic assumption in LOOK-COMPUTE-MOVE (LCM) robot algorithms to be implemented in existing distributed systems, we define a new distributed fundamental task, the Neighborhood Mutual Remainder (NMR). Consider a situation where each process has a set of operations Op and executes each opera-tion in Op infinitely often in distributed systems. Then, let Oe ⊂ Op be a subset of operations, which a process cannot execute while its closed neighborhood executes operations in Op n Oe. The NMR is defined for such a situation. A distributed algorithm that satisfies the NMR requirement should satisfy the following two properties: (1) Liveness is satisfied if a process executes each operation in Op infinitely often, and (2) safety is satisfied if, when each process executes operations in Oe, no process in its closed neighborhood executes operations in Op n Oe. We formalize the concept of NMR and give a simple self-stabilizing algorithm using the pigeon-hole principle to demonstrate the design paradigm to achieve NMR. A self-stabilizing algorithm tolerates tran-sient faults (e.g., message loss, memory corruption, etc.) by its ability to converge from an arbitrary configuration to the legitimate one. In addition, we present an application of NMR to an LCM robot sys-tem for implementing a move-atomic property, where robots possess an independent clock that is advanced at the same speed. It is the first self-stabilizing implementation of the LCM synchronization for environments where each robot can have limited visibility and lights. |
|
言語 |
en |
| 出版者 |
|
|
出版者 |
Springer |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 関連情報 |
|
|
関連タイプ |
isVersionOf |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1007/s00236-023-00450-8 |
| 開始ページ |
|
|
開始ページ |
83 |
| 書誌情報 |
en : Acta Informatica
巻 61,
p. 83-100,
発行日 2023-12-18
|
| 旧ID |
56161 |
ActaInformatica_61_83.pdf (2.6 MB)
