Simulating few by many: k-concurrency via k-set consensus
Event details
| Date | 17.06.2009 |
| Hour | 15:15 |
| Speaker | Prof. Eli Gafni, University of California, Los Angeles |
| Location | |
| Category | Conferences - Seminars |
Perfection is the enemy of the good. Most backoff schemes wait until a single contending candidate survives. But it is ``the last mile'' which is usually the most costly: backoff systems which wait on some fixed $k>1$ perform better that those that require perfection, i.e. $k=1$.
This paper asks what tasks are read-write solvable ``k-concurrently '' i.e. tasks where progress can be guaranteed when contention goes below $k+1$. That's it, what good is backoff to $k>1$? While backoff to $k=1$ is omnipotent what set of tasks can be solved with $k>1$?
We show that the set of these tasks is exactly the set of tasks that are solvable wait-free with the availability of $k$-set consensus.
It is now for the system designer to decide whether good is good enough.
Prof. Gafni's homepage
Practical information
- General public
- Free