Adaptive progress: a gracefully-degrading liveness property

作者：Aguilera Marcos K^*; Toueg Sam

来源：Distributed Computing, 2010, 22(5-6): 303-334.

DOI：10.1007/s00446-010-0106-4

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.

• 出版日期2010-8
• 单位Microsoft