An impossibility about failure detectors in the iterated immediate snapshot model

被引：9

作者：

Rajsbaum, Sergio ^{[2
]}

Raynal, Michel ^{[1
]}

Travers, Corentin ^{[1
]}

机构：

[1] IRISA, F-35042 Rennes, France

[2] Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City 04510, DF, Mexico

来源：

INFORMATION PROCESSING LETTERS | 2008年 / 108卷 / 03期

关键词：

Asynchronous shared memory system; Atomic read/write register; Distributed computing; Distributed computability; Failure detector; Iterated immediate snapshot model; Process crash; Snapshot operation;

D O I：

10.1016/j.ipl.2008.05.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Iterated Immediate Snapshot model (IIS) is ail asynchronous computation model where processes communicate through a sequence of one-shot Immediate Snapshot (IS) objects. It is known that this model is equivalent to the usual asynchronous read/write shared memory model, for wait-free task solvability. Its interest lies in the fact that its runs are more structured and easier to analyze than the runs in the shared memory model. As the IIS model and the shared memory model are equivalent for wait-free task solvability, a natural question is the following: Are they still equivalent for wait-free task solvability, when they are enriched with the same failure detector? The paper shows that the answer to this question is "no". (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：160 / 164

页数：5

共 23 条

[1] ATOMIC SNAPSHOTS OF SHARED-MEMORY [J].