Lower bounds on message passing implementations of multiplicity-relaxed queues and stacks

DOI10.1007/978-3-031-09993-9_14MaRDI QIDQ2097352zbMATH OpenOpenAlexFDO

Authors Edward Talmage

Publication date 11 November 2022

Full work available at URL https://doi.org/10.1007/978-3-031-09993-9_14

zbMATH Keywords

lower boundsmessage passingdistributed data structuresrelaxed data types

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites work

• scientific article; zbMATH DE number 1351080 (Why is no real title available?)
• An upper and lower bound for clock synchronization
• Anomalies and similarities among consensus numbers of variously-relaxed queues
• Improved time bounds for linearizable implementations of abstract data types
• Laws of order, expensive synchronization in concurrent algorithms cannot be eliminated
• Linearizable read/write objects
• Quantitative relaxation of concurrent data structures
• The computability of relaxed data structures: queues and stacks as examples

Cited in

(2)

• Brief Announcement: Improved, Partially-Tight Multiplicity Queue Lower Bounds
• scientific article; zbMATH DE number 3947971 (Why is no real title available?)

This page was built for publication: Lower bounds on message passing implementations of multiplicity-relaxed queues and stacks

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