May 10

Paper on Antidote and Cure accepted for ICDCS

Our paper titled “Cure: Strong semantics meets high availability and low latency” will appear in the forthcoming ICDCS conference. A preprint is available here.

Apr 16

Three papers at PaPoC 2016

In the PaPoC 2016 programme:

Mahsa Najafzadeh, Alexey Gotsman, Hongseok Yang, Carla Ferreira and Marc Shapiro. The CISE Tool: Proving Weakly-Consistent Applications Correct

Alejandro Z. Tomsic, Tyler Crain and Marc Shapiro. PhysiCS: efficient consistent snapshots for scalable snapshot isolation

Marek Zawirski, Carlos Baquero, Annette Bieniusa, Nuno Preguiça and Marc Shapiro. Eventually Consistent Register Revisited

Feb 10

Marc Shapiro Invited talk at Grenoble, 3 March 2016

Consistency —ensuring that data items distributed over remote computers agree with each other— is a fundamental issue of distributed computing. No single consistency model is appropriate for all uses: strong consistency requires lots of synchronisation, which has availability and performance issues; weak consistency performs and scales better but is error-prone. Indeed, the famous “CAP” impossibility result shows there is an inherent trade-off between fault tolerance, performance, and programmability. The first part of the talk will provide some general background on the consistency trade-off.

This has led to a split between databases designed for strong consistency and those designed for performance and availability; application designers must make an early decision of which consistency model to go with. Instead, we propose to fine-tune the database to provide the highest possible performance and availability that is appropriate for a given application. Our Just-Right Consistency approach leverages a novel static analysis (called CISE), which can prove whether a given distributed application maintains a given correctness invariant. In the second part of the talk, we will explain the intuition behind CISE, and how we use it to co-design the application and its consistency model, thereby minimising synchronisation to what is strictly necessary to ensure correctness

Jan 11

Paper @PODC 2015 “The Weakest Failure Detector for Eventual Consistency”

Nov 18

Consistent asynchronous distributed programs: POPL’16 paper, demo

Asynchronous replication is available and fast, but what about consistency? We propose a logic for showing that such a program maintains its invariants. We implemented the rule in a static analysis tool and ran a few interesting examples. See the video of the tool and the paper to appear at POPL 2016:

‘Cause I’m Strong Enough: Reasoning about Consistency Choices in Distributed Systems.
A. Gotsman, H. Yang, C. Ferreira, M. Najafzadeh, M. Shapiro.
Symp. on Principles of Programming Languages, Jan. 2016. St. Petersburg, Florida, USA

Aug 03

Paper @Middleware 2015 “Write Fast, Read in the Past: Causal Consistency for Client-side Applications”

Our paper “Write Fast, Read in the Past: Causal Consistency for Client-side Applications” has been accepted for publication at Middleware 2015. A preliminary version is available as Inria Research Report RR-8729.

Apr 28

New paper at Systor: Merging Semantics for Conflict Updates in Geo-Distributed File Systems

Read our new paper, to appear in Systor in May 2015 (Haifa, Israel): “Merging Semantics for Conflict Updates in Geo-Distributed File Systems” by Vinh Tao, Marc Shapiro, and Vianney Rancurel.

Feb 27

ASPLOS 2015 / NumaGiC: a Garbage Collector for Big Data on Big NUMA Machines

Paper accepted for presentation at ASPLOS 2015. DOI: 10.1145/2694344.2694361. Bibtex.

Lokesh Gidra, Gaël Thomas, Julien Sopena, Marc Shapiro, Nhan Nguyen

On contemporary cache-coherent Non-Uniform Memory Access (ccNUMA) architectures, applications with a large memory footprint suffer from the cost of the garbage collector (GC), because, as the GC scans the reference graph, it makes many remote memory accesses, saturating the interconnect between memory nodes. We address this problem with NumaGiC, a GC with a mostly-distributed design. In order to maximise memory access locality during collection, a GC thread avoids accessing a different memory node, instead notifying a remote GC thread with a message; nonetheless, NumaGiC avoids the drawbacks of a pure distributed design, which tends to decrease parallelism. We compare NumaGiC with Parallel Scavenge and NAPS on two different ccNUMA architectures running on the Hotspot Java Virtual Machine of OpenJDK 7. On Spark and Neo4j, two industry-strength analytics applications, with heap sizes ranging from 160 GB to 350 GB, and on SPECjbb2013 and SPECjbb2005, NumaGiC improves overall performance by up to 45% over NAPS (up to 94% over Parallel Scavenge), and increases the perfor- mance of the collector itself by up to 3.6× over NAPS (up to 5.4× over Parallel Scavenge).

Feb 27

EuroSys 2015: Putting Consistency Back into Eventual Consistency

Paper accepted for publication at EuroSys 2015

Valter Balegas, Mahsa Najafzadeh, Sérgio Duarte, Carla Ferreira, Marc Shapiro, Rodrigo Rodrigues, Nuno Preguiça

Geo-replicated storage systems are at the core of current Internet services. The designers of the replication protocols for these systems have to choose between either support- ing low latency, eventually consistent operations, or supporting strong consistency for ensuring application correctness. We propose an alternative consistency model, explicit consistency, that strengthens eventual consistency with a guarantee to preserve specific invariants defined by the applications. Given these application-specific invariants, a system that supports explicit consistency must identify which operations are unsafe under concurrent execution, and help pro- grammers to select either violation-avoidance or invariant-repair techniques. We show how to achieve the former while allowing most of operations to complete locally, by relying on a reservation system that moves replica coordination off the critical path of operation execution. The latter, in turn, allow operations to execute without restriction, and restore in- variants by applying a repair operation to the database state. We present the design and evaluation of Indigo, a middle- ware that provides Explicit Consistency on top of a causally- consistent data store. Indigo guarantees strong application invariants while providing latency similar to an eventually consistent system.

Jul 06

“On the Scalability of Snapshot Isolation” @Euro-Par 2013

“On the Scalability of Snapshot Isolation”, by Masoud Saeida Ardekani, Pierre Sutra, Marc Shapiro and Nuno Preguiça, is accepted for publication at Euro-Par 2013, Aachen, Germany, August 2013.  See pre-print here.