Deterministic computations whose history is independent of the order of asynchronous updating
Deterministic computations whose history is independent of the order of asynchronous updating
复制标题
其历史记录与异步更新顺序无关的确定性计算
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
P. Gács
中科院分区：
文献类型：
--
作者：
P. Gács
考虑一个处理器（站点）网络，其中每个站点x有一个有限的N(x)个邻居。有一个过渡函数f，对每个位置x计算下一个状态\xi (x)从N(x)中的状态。但是这些转换（更新）的应用顺序是任意的，一次一个或多个。如果站点x在时刻t的状态为\eta (x,t)，那么我们定义序列\zeta (x,0), \zeta (x,1)，…取顺序\eta (x,0), \eta (x,1)，…，并删除重复的内容。如果序列\zeta (x,i)（如果它是有限的，则它持续存在）仅取决于初始配置，而不取决于更新的顺序，则函数f具有不变的历史。
本文证明了虽然不变历史性质通常是不可判定的，但有一个有用的简单充分条件，称为交换性：对于任意构形，对于任意对相邻的x，y，如果更新会同时改变\xi (x)和\xi (y)，则先更新x后更新y的结果与反向更新x后更新y的结果相同。
Consider a network of processors (sites) in which each site x has a finite set N(x) of neighbors. There is a transition function f that for each site x computes the next state \xi(x) from the states in N(x). But these transitions (updates) are applied in arbitrary order, one or many at a time. If the state of site x at time t is \eta(x,t) then let us define the sequence \zeta(x,0), \zeta(x,1), ... by taking the sequence \eta(x,0), \eta(x,1), ..., and deleting repetitions. The function f is said to have invariant histories if the sequence \zeta(x,i), (while it lasts, in case it is finite) depends only on the initial configuration, not on the order of updates.
This paper shows that though the invariant history property is typically undecidable, there is a useful simple sufficient condition, called commutativity: For any configuration, for any pair x,y of neighbors, if the updating would change both \xi(x) and \xi(y) then the result of updating first x and then y is the same as the result of doing this in the reverse order.