Computing $k$-Atomicity in Polynomial Time

DOI10.1137/16M1056389zbMath1391.68012OpenAlexW2797588120MaRDI QIDQ4637504

Xiao-Zhou Li, Naomi Nishimura, Wojciech Golab, Alejandro López-Ortiz

Publication date: 24 April 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1056389

zbMATH Keywords

verificationconsistencyatomicitydistributed storage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Information storage and retrieval of data (68P20) Distributed systems (68M14)

Uses Software

• Cassandra
• Dynamo

Cites Work

• Unnamed Item
• Unnamed Item
• On interprocess communication. I: Basic formalism
• The NP-completeness of the bandwidth minimization problem
• Randomized registers and iterative algorithms
• Parametrized complexity theory.
• Computing Weak Consistency in Polynomial Time
• Timed consistency for shared distributed objects
• Analyzing consistency properties for fun and profit
• Computing the Bandwidth of Interval Graphs
• Axioms for memory access in asynchronous hardware systems
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• On the Complexity of Timetable and Multicommodity Flow Problems
• Complexity Results for Bandwidth Minimization
• Testing Shared Memories
• Probabilistic quorum systems
• Distributed Computing
• Parameterized Algorithms

This page was built for publication: Computing $k$-Atomicity in Polynomial Time