Publications related to Linearizability

Related publications (29)

Secure Interface Design Leveraging Hardware/Software Support

Computer systems rely heavily on abstraction to manage the exponential growth of complexity across hardware and software. Due to practical considerations of compatibility between components of these complex systems across generations, developers have favou ...

EPFL2024

WarpAttack: Bypassing CFI through Compiler-Introduced Double-Fetches

Mathias Josef Payer, Flavio Toffalini, Luca Di Bartolomeo

Code-reuse attacks are dangerous threats that attracted the attention of the security community for years. These attacks aim at corrupting important control-flow transfers for taking control of a process without injecting code. Nowadays, the combinations o ...

IEEE COMPUTER SOC2023

Efficient Multi-Word Compare and Swap

Rachid Guerraoui, Mihail Igor Zablotchi

Atomic lock-free multi-word compare-and-swap (MCAS) is a powerful tool for designing concurrent algorithms. Yet, its widespread usage has been limited because lock-free implementations of MCAS make heavy use of expensive compare-and-swap (CAS) instructions ...

Schloss Dagstuhl, Leibniz-Zentrum2020

Efficient Protocols for Enforcing Causal Consistency in Geo-Replicated Key-Value Data Stores

Kristina Spirovska

Modern large-scale data platforms manage colossal amount of data, generated by the ever-increasing number of concurrent users. Geo-replicated and sharded key-value data stores play a central role when building such platforms. As the strongest consistency m ...

EPFL2020

Distributed Computing with Modern Shared Memory

Mihail Igor Zablotchi

In this thesis, we revisit classic problems in shared-memory distributed computing through the lenses of (1) emerging hardware technologies and (2) changing requirements. Our contributions consist, on the one hand, in providing a better understanding of th ...

EPFL2020

PaRiS: Causally Consistent Transactions with Non-blocking Reads and Partial Replication

Willy Zwaenepoel, Diego Didona, Kristina Spirovska

Geo-replicated data platforms are at the backbone of several large-scale online services. Transactional Causal Consistency (TCC) is an attractive consistency level for building such platforms. TCC avoids many anomalies of eventual consistency, eschews the ...

2019

PaRiS: Causally Consistent Transactions with Non-blocking Reads and Partial Replication

Willy Zwaenepoel, Diego Didona, Kristina Spirovska

Geo-replicated data platforms are the backbone of several large-scale online services. Transactional Causal Consistency (TCC) is an attractive consistency level for building such platforms. TCC avoids many anomalies of eventual consistency, eschews the syn ...

IEEE COMPUTER SOC2019

The PCL Theorem: Transactions cannot be Parallel, Consistent, and Live

Rachid Guerraoui, Victor Bushkov, Panagiota Fatourou

We establish a theorem called the PCL theorem, which states that it is impossible to design a transactional memory algorithm that ensures (1) parallelism, i.e., transactions do not need to synchronize unless they access the same application objects, (2) ve ...

ASSOC COMPUTING MACHINERY2019

Rethinking General-Purpose Decentralized Computing

Bryan Alexander Ford, Eleftherios Kokoris Kogias, Georgia Fragkouli, Enis Ceyhun Alp

While showing great promise, smart contracts are difficult to program correctly, as they need a deep understanding of cryptography and distributed algorithms, and offer limited functionality, as they have to be deterministic and cannot operate on secret da ...

Association for Computing Machinery2019

Brief Announcement: Persistent Multi-Word Compare-and-Swap

Matej Pavlovic

This brief announcement presents a fundamental concurrent primitive for persistent memory - a persistent atomic multi-word compare-and-swap (PMCAS). We present a novel algorithm carefully crafted to ensure that atomic updates to a multitude of words modifi ...

ASSOC COMPUTING MACHINERY2018

Reliability Mechanisms for Controllers in Real-Time Cyber-Physical Systems

Maaz Mashood Mohiuddin

Cyber-physical systems (CPSs) are real-world processes that are controlled by computer algorithms. We consider CPSs where a centralized, software-based controller maintains the process in a desired state by exchanging measurements and setpoints with proces ...

EPFL2018

Atomic object reads for in-memory rack-scale computing

Babak Falsafi, Boris Robert Grot, Alexandros Daglis

A distributed memory system including a plurality of chips, a plurality of nodes that are distributed across the plurality of chips such that each node is comprised within a chip, each node includes a dedicated local memory and a processor core, and each l ...

2018

Wren: Nonblocking Reads in a Partitioned Transactional Causally Consistent Data Store

Willy Zwaenepoel, Diego Didona, Kristina Spirovska

Transactional Causal Consistency (TCC) extends causal consistency, the strongest consistency model compatible with availability, with interactive read-write transactions, and is therefore particularly appealing for geo-replicated platforms. This paper pres ...

2018

The Inherent Cost of Remembering Consistently

Rachid Guerraoui, Mihail Igor Zablotchi, Nachshon Cohen

Non-volatile memory (NVM) promises fast, byte-addressable and durable storage, with raw access latencies in the same order of magnitude as DRAM. But in order to take advantage of the durability of NVM, programmers need to design persistent objects which ma ...

2018

The Inherent Cost of Remembering Consistently

Rachid Guerraoui, Mihail Igor Zablotchi, Nachshon Cohen

Non-volatile memory (NVM) promises fast, byte-addressable and durable storage, with raw access latencies in the same order of magnitude as DRAM. But in order to take advantage of the durability of NVM, programmers need to design persistent objects which ma ...

2018

Execution Trace Graph of Dataflow Process Networks

Marco Mattavelli, Simone Casale Brunet

The paper introduces and specifies a formalism that provides complete representations of dataflow process network (DPN) program executions, by means of directed acyclic graphs. Such graphs, also known as execution trace graphs (ETG), are composed of nodes ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2018

Efficient Logging in Non-Volatile Memory by Exploiting Coherency Protocols

James Richard Larus, Nachshon Cohen

Non-volatile memory (NVM) technologies such as PCM, ReRAM and STT-RAM allow processors to directly write values to persistent storage at speeds that are significantly faster than previous durable media such as hard drives or SSDs. Many applications of NVM ...

ACM2017

The Disclosure Power of Shared Objects

Rachid Guerraoui, Mihail Igor Zablotchi, Julien Michel Stainer, Peva François Blanchard

Shared objects are the means by which processes gather and exchange information about the state of a distributed system. Objects that disclose more information about the system are therefore more desirable. In this paper, we propose the schedule reconstruc ...

2017

Incremental Consistency Guarantees for Replicated Objects

Rachid Guerraoui, Matej Pavlovic, Dragos-Adrian Seredinschi

Programming with replicated objects is difficult. Developers must face the fundamental trade-off between consistency and performance head on, while struggling with the complexity of distributed storage stacks. We introduce Correctables, a novel abstraction ...

2016

Optimistic Concurrency with OPTIK

Rachid Guerraoui, Vasileios Trigonakis

We introduce OPTIK, a new practical design pattern for designing and implementing fast and scalable concurrent data structures. OPTIK relies on the commonly-used technique of version numbers for detecting conflicting concurrent operations. We show how to i ...

ACM Press2016