Results 141 to 150 of about 1,172 (171)

Quasi-Linearizability is Undecidable

2015
Quasi-linearizability is a quantitative relaxation of linearizability. It preserves the intuition of the standard notion of linearizability and permits more flexibility. The decidability of quasi-linearizability has been remaining open in general for a bounded number of processes.
Chao Wang 0069, Yi Lv, Gaoang Liu, Peng Wu 0002   +3 more
openaire   +1 more source

Verifying linearizability with hindsight

Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, 2010
We present a proof of safety and linearizability of a highly-concurrent optimistic set algorithm. The key step in our proof is the Hindsight Lemma, which allows a thread to infer the existence of a global state in which its operation can be linearized based on limited local atomic observations about the shared state.
Peter W. O'Hearn, Noam Rinetzky, Martin T. Vechev, Eran Yahav, Greta Yorsh   +4 more
openaire   +1 more source

Asynchronous Resilient Linearizability

2013
We address the problem of implementing a distributed data-structure that can tolerate process crash failures in an asynchronous message passing system, while guaranteeing correctness linearizability with respect to a given sequential specification and resiliency the operations are guaranteed to terminate, as long as a majority of the processes do not ...
Sagar Chordia, Sriram K. Rajamani, Kaushik Rajan, Ganesan Ramalingam, Kapil Vaswani   +4 more
openaire   +1 more source

Sequential Consistency as Lazy Linearizability

Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '02, 2002
This revue shows that, from an implementation point of view, sequential consistency can be considered as a form of lazy linearizability. This claim is supported by a versatile protocol that can be tailored to implement any of them.
openaire   +2 more sources

Geometric Implications of Linearizability

Journal of Dynamics and Differential Equations, 2001
A linearization in a neighbourhood of a hyperbolic fixed point of a diffeomorphism or a flow is a local change of variable conjugating it to a linear system. It was known that hyperbolicity is enough to guarantee \(C^0\) linearizability, and there has been much work about the smooth linearizability question: How close can the smoothness of the ...
openaire   +2 more sources

Counting networks are practically linearizable

Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing - PODC '96, 1996
Counting Networks are Practically Linearizable” Nancy Lynch t Nir Shavit $ Alex Shvartsman~ Dan Touitou f Counting networks are a class of concurrent structures that allow the design of highly scalable concurrent data structures in a way that eliminates sequential bottlenecks and contention.
Nancy A. Lynch, Nir Shavit, Alexander A. Shvartsman, Dan Touitou   +3 more
openaire   +1 more source

Global Feedback Linearizability of Locally Linearizable Systems

1986
This paper is dedicated to Wilfred Kaplan and to Georges Reeb as a token of my admiration and friendship.
openaire   +1 more source

A Generic Logic for Proving Linearizability

2016
Linearizability is a commonly accepted notion of correctness for libraries of concurrent algorithms, and recent years have seen a number of proposals of program logics for proving it. Although these logics differ in technical details, they embody similar reasoning principles. To explicate these principles, we propose a logic for proving linearizability
Artem Khyzha, Alexey Gotsman, Matthew J. Parkinson   +2 more
openaire   +2 more sources

Complex integrability and linearizability of cubic -equivariant systems with two 1: resonant singular points

Journal of Differential Equations, 2021
Pei Yu, Jinliang Wang
exaly  

Set-linearizability

Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing - PODC '94, 1994
openaire   +1 more source