Linearizable counting networks

DOI10.1007/S004460050019MaRDI QIDQ5137016zbMATH OpenOpenAlexFDO

Authors Nir Shavit, Orli Waarts, Maurice 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

concurrencycontentioncounting networksdata structureslinearizability

Mathematics Subject Classification ID

Distributed systems (68M14) Data structures (68P05) Distributed algorithms (68W15)

Recommendations

• Timing conditions for linearizability in uniform counting networks
• Counting networks
• A Lower Bound on Wait-Free Counting
• Sequentially consistent versus linearizable counting networks
• Concurrent counting is harder than queuing

Cites work

• A combinatorial treatment of balancing networks
• A new solution of Dijkstra's concurrent programming problem
• A steady state analysis of diffracting trees
• Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors
• Coins, weights and contention in balancing networks
• Contention in shared memory algorithms
• Counting networks
• Efficient synchronization of multiprocessors with shared memory
• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 742955 (Why is no real title available?)
• The mutual exclusion problem
• The serializability of concurrent database updates

Cited in

(18)

• Timing conditions for linearizability in uniform counting networks
• Linearizable read/write objects
• The cost of concurrent, low-contention Read \& Modify \& Write
• Public data structures: counters as a special case.
• The counting pyramid: an adaptive distributed counting scheme
• Bounded-wait combining: constructing robust and high-throughput shared objects
• Long-lived counters with polylogarithmic amortized step complexity
• Constructing Shared Objects That Are Both Robust and High-Throughput
• Counting networks
• A Lower Bound on Wait-Free Counting
• scientific article; zbMATH DE number 2006662 (Why is no real title available?)
• Hundreds of impossibility results for distributed computing
• Read-modify-write networks
• Concurrent counting (extended abstract)
• Brief Announcement: Intermediate Value Linearizability: A Quantitative Correctness Criterion
• Sequentially consistent versus linearizable counting networks
• Threshold counters with increments and decrements
• An efficient counting network

This page was built for publication: Linearizable counting networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5137016)