Solo-valency and the cost of coordination Academic Article uri icon


  • 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\sqrt n 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 …

publication date

  • June 1, 2008