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

DOI10.1007/978-3-031-09993-9_14OpenAlexW4285182826MaRDI QIDQ2097352

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)

Related Items (1)

Brief Announcement: Improved, Partially-Tight Multiplicity Queue Lower Bounds

Cites Work

• Unnamed Item
• The computability of relaxed data structures: queues and stacks as examples
• Linearizable read/write objects
• Improved time bounds for linearizable implementations of abstract data types
• Anomalies and similarities among consensus numbers of variously-relaxed queues
• Quantitative relaxation of concurrent data structures
• An upper and lower bound for clock synchronization
• Laws of order

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