Objectives:
The future of the computing technology relies on fast access, transformation, and exchange of data between multiple CPUs which may live on the same circuit or across large-scale networks such as the Internet. The design of software systems, data structures, that support high-frequency parallel accesses to high-quantity data is a fundamental challenge. This lecture will be decomposed in three parts that we outline below.
The first part will describe the design of data structures that can be used in multi-threaded programming, i.e., when multiple threads of computation communicate by writing or reading into a shared memory. Multi-threaded programming has become mainstream and it typically relies on optimized implementations of common abstract data types like stacks, queues, sets, and maps, whose operations execute in parallel across processor cores to maximize efficiency. Synchronization between operations must be minimized to reduce response time and increase throughput which leads to non-trivial and tricky algorithms. We will present a representative sample of such algorithms and discuss their correctness.
The second and third part will focus on data structures, e.g., key-value stores or distributed ledgers aka blockchains, that are deployed over a network such as the Internet. The second part will address the issue of maintaining availability of data in an adversarial environment where computers can crash or network links can be interrupted. To deal with such an environment data is replicated at multiple sites in the network which may however lead to consistency issues that need to be addressed by the application. We will discuss the most prevalent design principles and consistency criteria that support modern key-value stores used in state of the art cloud environments.
The third part will focus on adversarial environments where computers can also behave maliciously sending counterfeit messages, the so-called Byzantine failures. A famous example of data structures that run in such an environment are blockchains which implement a ledger to record decentralised finance transactions, e.g., smart contract transactions. We will present recent designs of Proof-of-Stake and Proof-of-Work blockchains focusing on the algorithmic details.
Some advanced cryptographic techniques, like zero-knowledge, will be reviewed, for privacy and scaling blockchains.
Lectures will be accompanied by a mix of theoretical (TD) and practical (TP) tutorials.
Language: The course material is in English. Lectures can be taught either in French or in English, at the students' convenience.
Evaluation: 20% Graded homeworks + 80% Final written exam.
Prerequisites: A fair knowledge of Java is desirable as well as some knowledge of sequential algorithms.
