Conflict Managers for Self-stabilization without Fairness Assumption
Conflict Managers for Self-stabilization without Fairness Assumption
复制标题
没有公平假设的自我稳定冲突管理者
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
M. Potop;S. Tixeuil
在本文中，我们指定了冲突管理器抽象。非正式地，冲突管理器保证处于冲突中的任何两个节点不能同时进入它们的关键区域（安全），并且至少有一个节点能够执行其关键区域（进度）。冲突管理器问题严格弱于经典的局部互斥问题，在经典的局部互斥问题中，任何请求进入其临界区的节点最终都会这样做（公平性）。我们认为，冲突管理器是一种有用的机制，可以将大量在本质上顺序模型中运行的自稳定算法转换为在完全异步分布式模型中运行的自稳定算法。我们提供了抽象的两种实现（一种是确定性的，另一种是概率性的），并提供了一种组合机制来获得通用的转换器。我们的变压器具有较低的开销：确定性变压器只需要一个内存位，并且保证了按网络度顺序的时间开销，概率变压器不需要额外的内存。虽然概率算法在匿名网络中执行，但它只提供了概率稳定性保证。相比之下，确定性变压器需要初始对称性破缺，但保留了原始算法的保证。
In this paper, we specify the conflict manager abstraction. Informally, a conflict manager guarantees that any two nodes that are in conflict cannot enter their critical section simultaneously (safety), and that at least one node is able to execute its critical section (progress). The conflict manager problem is strictly weaker than the classical local mutual exclusion problem, where any node that requests to enter its critical section eventually does so (fairness). We argue that conflict managers are a useful mechanism to transform a large class of self-stabilizing algorithms that operate in an essentially sequential model, into self-stabilizing algorithm that operate in a completely asynchronous distributed model. We provide two implementations (one deterministic and one probabilistic) of our abstraction, and provide a composition mechanism to obtain a generic transformer. Our transformers have low overhead: the deterministic transformer requires one memory bit, and guarantees time overhead in order of the network degree, the probabilistic transformer does not require extra memory. While the probabilistic algorithm performs in anonymous networks, it only provides probabilistic stabilization guarantees. In contrast, the deterministic transformer requires initial symmetry breaking but preserves the original algorithm guarantees.