Name
Abstract | ||
|---|---|---|
In this paper, we define k-abortable objects, the first kind of abortable objects [2, 7] that guarantee some degree of progress even under high contention. The definition is simple and natural: intuitively, an operation on a k-abortable object can abort only if k operations from distinct processes succeed during the execution of the aborted operation. We first show that k-abortable objects can easily implement k -lock-free objects, i.e., objects where at least k processes make progress [5], but in contrast to k-lock-free objects, k-abortable objects always return control. We then give an efficient universal construction for wait-free k-abortable objects shared by n processes that takes only O(k) steps per operation. We also give a (varOmega (log k))-steps lower bound for universal constructions of k-abortable objects shared by (n ge k) processes. Since every wait-free k-abortable object can implement its k-lock-free counterpart, our universal construction also provides a universal construction for k-lock-free objects. |
Year | Venue | Field |
|---|---|---|
2016 | DISC | Abort,Shared memory,Asynchronous system,Computer science,Upper and lower bounds,Theoretical computer science,Distributed algorithm,If and only if,Distributed computing |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Naama Ben-David | 1 | 15 | 6.02 |
| David Yu Cheng Chan | 2 | 2 | 1.07 |
| Vassos Hadzilacos | 3 | 1204 | 199.70 |
| Sam Toueg | 4 | 4557 | 541.76 |