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
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
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
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. http://lip6.fr/Marc.Shapiro/papers/geodistr-FS-Systor-2015.pdf
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).
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.