We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Common2 extended to stacks and unbounded concurrency.
- Authors
Afek, Yehuda; Gafni, Eli; Morrison, Adam
- Abstract
This paper extends Common2, the family of objects that implement and are wait-free implementable from 2 consensus objects, in two ways: First, the object is shown to be in the family, refuting a conjecture to the contrary [6]. Second, Common2 is investigated in the unbounded concurrency model, whereas until now it was considered only in an n-process model. We show that the , and objects are in Common2 even with respect to this stronger notion of wait-free implementation. Our constructions rely on a wait-free implementation of immediate snapshots in the unbounded concurrency model, which was previously not known to be possible. The introduction of unbounded concurrency to the study of Common2 opens several directions of research: are there objects that have n-process implementations but are not unbounded concurrency implementable? We conjecture that swap is such an object. Additionally, the hope is that a impossibility proof, which eludes us in the n-process model, will be easier to establish in the unbounded concurrency model.
- Subjects
GEOMETRICAL constructions; MATHEMATICAL models; RESEARCH; GEOMETRY; MATHEMATICS
- Publication
Distributed Computing, 2007, Vol 20, Issue 4, p239
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-007-0023-3