TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Please select your role
to obtain appropriate quick-links.
As a LIPIcs/OASIcs author, you will be invited by e-mail to register at the Dagstuhl Submission Server. The server will guide you through the publication workflow. Preliminary information can be found here:
Quick Links

Dagstuhl Seminar 13081

Consistency In Distributed Systems

( Feb 17 – Feb 22, 2013 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/13081
Organizers
Coordinator
Contact
Publications
Impacts
Schedule
Motivation
Show Motivation

Distributed computing is everywhere, but remains hard: there is a fundamental tension between consistency versus availability and the ability to tolerate failures. Understanding and defining a consistency semantics that has scalability and correctness properties appropriate for a particular purpose is complex and error-prone. This has significant implications on the design of the entire distributed computing infrastructure, including communication primitives, storage, and development environments. Better understanding and tools are needed, to ensure that programs behave as expected, and to enable non-experts to build distributed applications.

This seminar brings together researchers and practitioners in complementary areas (algorithms, systems, programming languages, verification, hardware and databases), in order to achieve cross-fertilization, comparing different experiences and knowledge in building scalable and correct distributed systems. Specifically, we would like to compare lessons learnt and emerging design patterns, with the aim of distilling these into programming methodologies, programming tools, and languages to help make distributed computing easier and more accessible.

Goals: We propose to address the following topics and questions in the seminar:

  • Different concepts of consistency in a distributed system; for instance data-centric vs. computation-centric definitions; weak, strong, eventual consistency; transactional vs. causal consistency; etc.
  • Trade-offs between scalability, consistency, performance, fault tolerance, and programming expressiveness. What kinds of tools and methodologies can we provide to help understand and control these trade-offs?
  • Application requirements: What are common requirements of distributed applications? Can we formalize commonly desired (generic) correctness (or performance) properties? How do applications achieve the required properties, while ensuring adequate performance, in practice? What design patterns and idioms work well?
  • How can consistency violations be detected, measured and quantified? Can we build verification or testing tools to check that systems have these desired correctness properties?
  • To what degree can these properties be guaranteed by the platform (programming language, libraries, and runtime system)? What are the performance implications?
  • Weakly consistent systems are hard to design, test and debug. Do existing testing and debugging tools suffice for identifying and isolating bugs due to weak consistency?
Summary
Show Summary

In distributed systems, there exists a fundamental trade-off between data consistency, availability, and the ability to tolerate failures. This trade-off has significant implications on the design of the entire distributed computing infrastructure such as storage systems, compilers and runtimes, application development frameworks and programming languages. Unfortunately, it also has significant, and poorly understood, implications for the designers and developers of end applications. As distributed computing become mainstream, we need to enable programmers who are not experts to build and understand distributed applications.

A seminar on "Consistency in Distributed Systems" was held from 18th to 22nd, February, 2013 at Dagstuhl. This seminar brought together researchers and practitioners in the areas of distributed systems, programming languages, databases and concurrent programming, to make progress towards the above mentioned goal. Specifically, the aim was to understand lessons learnt in building scalable and correct distributed systems, the design patterns that have emerged, and explore opportunities for distilling these into programming methodologies, programming tools, and languages to help make distributed computing easier and more accessible.

We may classify current approaches to deal with the challenges of building distributed applications into the following three categories:

  • Strong Consistency and Transactions: Strong consistency means that shared state behaves like on a centralised system, and programs (and users) cannot observe any anomalies caused by concurrent execution, distribution, or failures. From a correctness perspective, this is a most desirable property. For instance, a database management system protects the integrity of shared state with transactions, which provide the so-called ACID guarantees: atomicity (all-or-nothing), consistency (no transaction in isolation violates database integrity), isolation (intermediate states of a transaction cannot be observed by another one), and durability (a transaction's effects are visible to all later ones).
  • Weak Consistency: Unfortunately strong consistency severely impacts performance and availability. As applications executing in the cloud serve larger workloads, providing the abstraction of a single shared state becomes increasingly difficult. Scaling requires idioms such as replication and partitioning, for which strongly-consistent protocols such as 2-Phase Commit are expensive and hard to scale. Thus, contemporary cloud-based storage systems, such as Amazon's Dynamo or Windows Azure Tables, provide only provide weak forms of consistency (such as eventual consistency) across replicas or partitions. Weakly consistent systems permit anomalous reads, which complicates reasoning about correctness. For example, application designers must now ascertain if the application can tolerate stale reads and/or delayed updates. More parallelism allows better performance at lower cost, but at the cost of high complexity for the application programmer.
  • Principled Approaches to Consistency: A number of approaches and tools have been developed for reasoning about concurrently-accessed shared mutable data. The concept of linearizability has become the central correctness notion for concurrent data structures and libraries. This has led to significant advances in verification, testing and debugging methodologies and tools. Transactional memory provides a higher-level, less error-prone programming paradigm.
  • Principles for weak consistency: More recently, a number of principles have emerged for dealing with weak consistency. For example, if all operations in a program are monotonic, strong correctness guarantees can be provided without the use of expensive global synchronization. Similarly, certain data structures such as sets and sequences can be replicated in a correct way without synchronisation.

These developments illustrate the benefits of cross-fertilization of ideas between these different communities, focused on the topic of concurrency. We believe that such principled approaches will become increasingly critical to the design of scalable and correct distributed applications. The time is ripe for the development of new ideas by cross-fertilisation between the different research communities.

Goals

It is crucial for researchers from different communities working in this same space to meet and share ideas about what they believe are the right approaches to address these issues. The questions posed for the seminar include:

  • Application writers are constantly having to make trade-offs between consistency and scalability. What kinds of tools and methodologies can we provide to help this decision? How does one understand the implications of a design choice?
  • Weakly consistent systems are hard to design, test and debug. Do existing testing and debugging tools suffice for identifying and isolating bugs due to weak consistency?
  • Can we formalize commonly desired (generic) correctness (or performance) properties?
  • Can we build verification or testing tools to check that systems have these desired correctness properties?
  • How do applications achieve the required properties, while ensuring adequate performance, in practice? What design patterns and idioms work well?
  • To what degree can these properties be guaranteed by the platform (programming language, libraries, and runtime system)? What are the performance tradeoffs (when one moves the responsibility for correctness between the platform and application)?

In order to ensure a common understanding between the different research communities that the workshop brings together, the seminar started with a few tutorials from the perspective of each community. Other presentations presented a specific piece of research or a research question. Participants brain-stormed on a specific issue during each of the two break-out sessions.

This report

This report is the compilation of notes taken by several note-takers, rotating at each session. The majority of the participants served as scribe for some session.

It will be helpful to refer to the abstracts and slides of the different presentations, which are available at http://www.dagstuhl.de/mat/index.en.phtml?13081.

References

  1. Daniel J. Abadi. Consistency tradeoffs in modern distributed database system design. Computer, 45(2):37–42, February 2012.
  2. Eric Brewer. CAP twelve years later: How the "rules" have changed. IEEE Computer, 45(2):23–29, February 2012.
  3. Maurice Herlihy and Jeannette Wing. Linearizability: a correcteness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463–492, July 1990.
  4. Maurice Herlihy and J. Eliot B. Moss. Transactional memory: Architectural support for lock-free data structures. In Int. Conf. on Comp. Arch. (ISCA), pages 289–300, San Diego CA, USA, May 1993.
Copyright Bettina Kemme and Ganesan Ramalingam and André Schiper and Marc Shapiro and Kapil Vaswani
Participants
Show Participants
  • Marcos K. Aguilera (Microsoft Corp. - Mountain View, US) [dblp]
  • Hagit Attiya (Technion - Haifa, IL) [dblp]
  • Carlos Baquero (University of Minho - Braga, PT) [dblp]
  • Annette Bieniusa (TU Kaiserslautern, DE) [dblp]
  • Alejandro P. Buchmann (TU Darmstadt, DE) [dblp]
  • Sebastian Burckhardt (Microsoft Corporation - Redmond, US) [dblp]
  • Bernadette Charron-Bost (Ecole Polytechnique - Palaiseau, FR) [dblp]
  • Allen Clement (MPI-SWS - Saarbrücken, DE) [dblp]
  • Mike Dodds (University of York, GB) [dblp]
  • Amr El Abbadi (University of California - Santa Barbara, US) [dblp]
  • Alan Fekete (The University of Sydney, AU) [dblp]
  • Pascal Felber (Université de Neuchâtel, CH) [dblp]
  • Carla Ferreira (Universidade Nova de Lisboa, PT) [dblp]
  • Alexey Gotsman (IMDEA Software - Madrid, ES) [dblp]
  • Maurice Herlihy (Brown University - Providence, US) [dblp]
  • Ricardo Jimenez-Peris (Technical University of Madrid, ES) [dblp]
  • Bettina Kemme (McGill University - Montreal, CA) [dblp]
  • Petr Kuznetsov (TU Berlin, DE) [dblp]
  • David B. Lomet (Microsoft Corporation - Redmond, US) [dblp]
  • Maged M. Michael (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
  • Achour Mostefaoui (University of Nantes, FR) [dblp]
  • Yiannis Nikolakopoulos (Chalmers UT - Göteborg, SE) [dblp]
  • Fernando Pedone (University of Lugano, CH) [dblp]
  • Nuno Preguica (Universidade Nova de Lisboa, PT) [dblp]
  • Vivien Quéma (INRIA - Grenoble, FR) [dblp]
  • Kaushik Rajan (Microsoft Research India - Bangalore, IN) [dblp]
  • Ganesan Ramalingam (Microsoft Research India - Bangalore, IN) [dblp]
  • Robert Rehner (TU Darmstadt, DE) [dblp]
  • Noam Rinetzky (Tel Aviv University, IL) [dblp]
  • Luis Rodrigues (Technical University of Lisboa, PT) [dblp]
  • Rodrigo Rodrigues (Universidade Nova de Lisboa, PT) [dblp]
  • Nicholas Rutherford (University of Louvain, BE)
  • Mooly Sagiv (Tel Aviv University, IL) [dblp]
  • André Schiper (EPFL - Lausanne, CH) [dblp]
  • Marc Shapiro (INRIA - Paris, FR) [dblp]
  • Liuba Shrira (Brandeis University - Waltham, US) [dblp]
  • Alexander A. Shvartsman (University of Connecticut - Storrs, US) [dblp]
  • Pierre Sutra (Université de Neuchâtel, CH) [dblp]
  • Douglas B. Terry (Microsoft Corp. - Mountain View, US) [dblp]
  • Peter Van Roy (University of Louvain, BE) [dblp]
  • Kapil Vaswani (Microsoft Research India - Bangalore, IN) [dblp]
  • Marko Vukolic (EURECOM - Biot, FR) [dblp]
  • Jennifer L. Welch (Texas A&M University - College Station, US) [dblp]
  • Pawel T. Wojciechowski (Poznan University of Technology, PL) [dblp]
Related Seminars
  • Dagstuhl Seminar 18091: Data Consistency in Distributed Systems: Algorithms, Programs, and Databases (2018-02-25 - 2018-03-02) (Details)
Classification
  • data bases / information retrieval
  • programming languages / compiler
  • semantics / formal methods
Keywords
  • Distributed Computing
  • Weak and Strong Consistency
  • Replication
  • Partitioning
  • Transactions
Seminar 13081
© 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
ImprintContactAccessibilityPrivacy