Linearizable counting networks

DOI10.1007/s004460050019zbMath1448.68226MaRDI QIDQ5137016

Nir Shavit, Orli Waarts, Maurice P. Herlihy

Publication date: 30 November 2020

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004460050019

zbMATH Keywords

data structures; linearizability; concurrency; contention; counting networks

Mathematics Subject Classification ID

68P05: Data structures

68M14: Distributed systems

68W15: Distributed algorithms

Related Items

Hundreds of impossibility results for distributed computing, Read-modify-write networks, Threshold counters with increments and decrements, An efficient counting network, The cost of concurrent, low-contention Read \& Modify \& Write, Public data structures: counters as a special case., Long-lived counters with polylogarithmic amortized step complexity

Cites Work

• Unnamed Item
• Unnamed Item
• A steady state analysis of diffracting trees
• Efficient synchronization of multiprocessors with shared memory
• The serializability of concurrent database updates
• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
• Counting networks
• Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors
• A new solution of Dijkstra's concurrent programming problem
• Contention in shared memory algorithms
• Coins, weights and contention in balancing networks
• A combinatorial treatment of balancing networks
• The mutual exclusion problem