Name
Abstract | ||
|---|---|---|
ABSTRACTDouble Compare-And-Swap (DCAS) is a tremendously useful synchronization primitive, which is also notoriously difficult to implement efficiently from objects that are provided by hardware. We present a randomized implementation of DCAS with O(logn) expected amortized step complexity against the oblivious adversary, where n is the number of processes in the system. This is the only algorithm to-date that achieves sub-linear step complexity. We achieve that by first implementing two novel algorithms as building blocks. One is a mechanism that allows processes to repeatedly agree on a random value among multiple proposed ones, and the other one is a restricted bipartite version of DCAS. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3406325.3451133 | ACM Symposium on Theory of Computing |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| George Giakkoupis | 1 | 248 | 20.48 |
| Mehrdad Jafari Giv | 2 | 0 | 0.34 |
| Philipp Woelfel | 3 | 432 | 38.40 |