Description
Date depot: 11 avril 2022
Titre: Consistency trade-offs in edge computing
Directeur de thèse:
Pierre SENS (LIP6)
Directeur de thèse:
Marc SHAPIRO (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Systèmes et réseaux
Resumé: Decentralised systems are becoming crucial across many areas of computing. Current trends are pushing applications towards the edge, close to clients and to the source of information. This edge-first approach places data at the network edge; shared data is replicated, possibly in many locations. This improves response time and availability, tolerates high network latency, and enables disconnected operation, while potentially decreasing resource consumption by off-loading data centres.
Strong consistency of the distributed data is desirable, as it is familiar and supports arbitrary application logic. However, it conflicts with availability and response time, because every update requires coordination across the whole system. In contrast, weak consistency models are error-prone for applications and provide lesser guarantees.
A good trade-off is provided by transactional causal consistency (TCC), which supports high concurrency and performance, but ensures that updates are atomic and there are no ordering anomalies (i.e., if update depends on , all users will observe before ). TCC requires attaching ordering metadata to each update, in order to detect whether an event received might depend on one not yet received. It has been proved that the size of the metadata, in the worst case, is proportional to the number of processes, an
unacceptable burden in large-scale edge systems. Another problem is that metadata tends to accumulate over time and is difficult to garbage-collect safely.
Accordingly, modern systems make trade-offs, using hybrid consistency models that mix (for instance) TCC overall with strong consistency in specific sub-networks, or leverage specific communication topologies. This hybrid approach aims both to mitigate the growth of metadata, and to provide stronger guarantees to the application when or where necessary. So far, these trade-offs were made in an ad-hoc manner. In contrast, the aim of this thesis will be to study them in a systematic manner. The research has both a fundamental and an applied aspect and aims for practical results.
There are different metadata mechanisms, such as explicit dependency (graph), vector clocks (message numbering), or hash chaining. Metadata serves a number of distinct purposes, such as: to order events (causality), to compare events (concurrency), to detect and resolve conflicts, to optimise network traffic (anti-entropy), for detecting distributed stability, etc. Trade-offs have different effects on each of these aspects, which can be measured or evaluated qualitatively.
Based on a literature search and on a study of existing systems, the PhD student will study the different facets of causal and stronger consistency, in order to isolate, classify, and formalise the trade-offs. In addition, the student will perform an experimental study (most likely in simulation) of some interesting points in the design space, along metrics such as response time, availability, propagation delay, network cost, loss of parallelism, memory and computation resources, etc.
Ultimately, the goal of the research is to design, implement and evaluate an efficient hybrid consistency model for edge-first systems.
Requirements and application.