Computing weak consistency in polynomial time (extended abstract)

DOI10.1145/2767386.2767407MaRDI QIDQ2796276zbMATH OpenOpenAlexWikidataFDO

Authors Wojciech Golab, Xiaozhou (Steve) Li, N. Nishimura, Alejandro Lopez-Ortiz

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2767386.2767407

zbMATH Keywords

atomicityconsistencydistributed storageverification

Mathematics Subject Classification ID

Distributed systems (68M14) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Distributed algorithms (68W15)

Recommendations

• The complexity of weak consistency
• Weak consistency notions for all the CSPs of bounded width
• On the feasibility of consistent computations
• Decidability and complexity for quiescent consistency and its variations
• Solving CSPs using weak local consistency
• Round optimal concurrent non-malleability from polynomial hardness
• Completeness and weak completeness under polynomial-size circuits
• Completeness and weak completeness under polynomial-size circuits

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(9)

• Probabilistic weak simulation is decidable in polynomial time
• Analyzing linearizability violations in the presence of read-modify-write operations
• Decidability and complexity for quiescent consistency and its variations
• Efficient algorithms for checking the atomicity of a run of read and write operations
• Analyzing consistency properties for fun and profit
• A quasi-lower bound on the consistency strength of PFA
• Computing k-atomicity in polynomial time
• A much better polynomial time approximation of consistency in the LR calculus
• Languages and Compilers for Parallel Computing

This page was built for publication: Computing weak consistency in polynomial time (extended abstract)

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