PaPEC 2014

Principles and Practices of Eventual Consistency Workshop co-located with EuroSys 2014.

Proceedings available at: http://dl.acm.org/citation.cfm?id=2596631

Strong consistency is easy to understand, but it requires synchronisation, which has a high cost and does not tolerate partial system failure or network partitions well. Hence, the past decade has seen renewed interest in an alternative - Eventual Consistency (EC) - where data is accessed and modified without coordination. Many production systems guarantee only EC, including NoSQL databases, key-value stores and cloud storage systems. EC improves responsiveness and availability, updates propagate more quickly, and enables less coordination-intensive and often less complex protocols.

EC is crucial for scalability but represents an unfamiliar design space. Conflicts and divergence are possible, making them hard to program against, while metadata growth and maintaining system-wide invariants can also become problematic. As more developers interact with and program against distributed storage systems, understanding and managing these trade-offs becomes increasingly important.

Although EC remains poorly understood, there has recently been considerable momentum in the research and development community: the past several years have seen the (re)introduction of useful concepts, such as replicated data types, monotonic programming, causal consistency, red-blue consistency, novel proof systems, etc., designed to allow improve efficiency, programmability, and overall operation of weakly consistent stores.

This workshop aims to investigate the principles and practice of Eventual Consistency. It will bring together theoreticians and practitioners from different horizons: system development, distributed algorithms, concurrency, fault tolerance, databases, language and verification, including both academia and industry. In order to make EC computing easier and more accessible, and to address the limitations of EC and explore the design space spectrum between EC and strong consistency, we will share experience with practical systems and from theoretical study, to investigate algorithms, design patterns, correctness conditions, complexity results, and programming methodologies and tools.

Relevant discussion topics include:

• Design principles, correctness conditions, and programming patterns for EC.
• Techniques for eventual consistency: session guarantees, causal consistency, operational transformation, conflict-free replicated data types, monotonic programming, state merge, commutativity, etc.
• Consistency vs. performance and scalability trade-offs: guiding developers, controlling the system.
• Analysis and verification of EC programs.
• Strengthening guarantees: transactions, fault tolerance, security, ensuring invariants, bounding metadata memory, and controlling divergence, without losing the benefits of EC.
• Platform guarantees vs. application involvement: guiding developers, controlling the system.