Abstract | ||
---|---|---|
We introduce a simple liveness property for shared object implementations that is gracefully degrading depending on the degree
of synchrony in each run. This property, called adaptive progress, provides a gradual bridge between obstruction-freedom and wait-freedom in partially-synchronous systems. We show that adaptive
progress can be achieved using very weak shared objects. More precisely, every object has an implementation that ensures adaptive
progress and uses only abortable registers (which are weaker than safe registers). As part of this work, we present a new
leader election abstraction that processes can use to dynamically compete for leadership such that if there is at least one
timely process among the current candidates for leadership, then a timely leader is eventually elected among the candidates.
We also show that this abstraction can be implemented using abortable registers. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/s00446-010-0106-4 | Distributed computing |
Keywords | DocType | Volume |
Correct Process,Failure Detector,Activity Monitor,Leader Election,Liveness Property | Journal | 22 |
Issue | ISSN | Citations |
5-6 | 0178-2770 | 1 |
PageRank | References | Authors |
0.36 | 14 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marcos Kawazoe Aguilera | 1 | 2519 | 153.60 |
Sam Toueg | 2 | 4557 | 541.76 |