Solo-valency and the cost of coordination |
| |
Authors: | Danny Hendler Nir Shavit |
| |
Affiliation: | (1) Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel;(2) Department of Computer Science, Tel-Aviv University, Tel-Aviv, Israel |
| |
Abstract: | This paper introduces solo-valency, a variation on the valency proof technique originated by Fischer, Lynch, and Paterson. The new technique focuses on critical
events that influence the responses of solo runs by individual operations, rather than on critical events that influence a
protocol’s single decision value. It allows us to derive lower bounds on the time to perform an operation for lock-free implementations of concurrent objects such as linearizable
queues, stacks, sets, hash tables, counters, approximate agreement, and more. Time is measured as the number of distinct base
objects accessed and the number of stalls caused by contention in accessing memory, incurred by a process as it performs a
single operation. We introduce the influence level metric that quantifies the extent to which the response of a solo execution of one process can be changed by other processes.
We then prove the existence of a relationship between the space complexity, latency, contention and influence level of all
lock-free object implementations. Our results are broad in that they hold for implementations that may use any collection of read-modify-write operations in addition to read and write, and in that they apply even if base objects have
unbounded size.
Part of this work was done while the first author was a graduate student in the Department of Computer Science, Tel-Aviv University.
This work was supported in part by a grant from Sun Microsystems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|