论文标题
部分可观测时空混沌系统的无模型预测
Fault Tolerant Coloring of the Asynchronous Cycle
论文作者
论文摘要
我们提出了一种无需等待算法，以正确着色异步周期$ c_n $的n个节点，每个易碎节点以其（唯一）标识符为输入开始。该算法独立于$ n \ geq 3 $，并以$ \ mathrm {o}（\ log^* n）$ rounds在$ c_n $中运行。由于已知的匹配下限，该圆形复杂性是最佳的，它甚至适用于同步执行（无故障）执行。我们的算法所使用的颜色范围，即$ \ {0，...，4 \} $，这也是最佳的，这要归功于已知的下界已知的下限，即每当$ n $中，在共享内存系统中可以不解决的最低名称的名称数量是无用的。实际上，每当$ n = 3 $时，我们的模型与共享内存模型相吻合，并且在3个过程共享内存系统中可以重命名的最小名称数量为5。
We present a wait-free algorithm for proper coloring the n nodes of the asynchronous cycle $C_n$, where each crash-prone node starts with its (unique) identifier as input. The algorithm is independent of $n \geq 3$, and runs in $\mathrm{O}(\log^* n)$ rounds in $C_n$. This round-complexity is optimal thanks to a known matching lower bound, which applies even to synchronous (failure-free) executions. The range of colors used by our algorithm, namely $\{0, ..., 4\}$, is optimal too, thanks to a known lower bound on the minimum number of names for which renaming is solvable wait-free in shared-memory systems, whenever $n$ is a power of a prime. Indeed, our model coincides with the shared-memory model whenever $n = 3$, and the minimum number of names for which renaming is possible in 3-process shared-memory systems is 5.
