The Iterated Restricted Immediate Snapshot Model
In the Iterated Immediate Snapshot model (IIS) the memory consists of a sequence of one-shot Immediate Snapshot (IS) objects. Processes access the sequence of IS objects, one-by-one, asynchronously, in a waitfree manner; any number of processes can crash. Its interest lies in the elegant recursive structure of its runs, hence of the ease to analyze it round by round. In a very interesting way, Borowsky and Gafni have shown that the IIS model and the read/write model are equivalent for the wait-free solvability of decision tasks. This paper extends the benefits of the IIS model to partially synchronous systems. Given a shared memory model enriched with a failure detector, what is an equivalent IIS model? The paper shows that an elegant way of capturing the power of a failure detector and other partially synchronous systems in the IIS model is by restricting appropriately its set of runs, giving rise to the Iterated Restricted Immediate Snapshot model (IRIS).
Sergio Rajsbaum Michel Raynal Corentin Travers
Instituto de Matematicas, UNAM, D.F. 04510, Mexico IRISA, Campus de Beaulieu, 35042 Rennes Cedex, France Facultad de Informatica, UPM, Madrid, Spain
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
487-497
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）