Descriptif

Objectifs:

L'avenir des technologies informatiques repose sur l'accès, la transformation et l'échange rapides de données entre plusieurs processeurs, qu'ils soient connectés au même circuit ou à des réseaux à grande échelle comme Internet. La conception de systèmes logiciels et de structures de données prenant en charge des accès parallèles haute fréquence à de grandes quantités de données constitue un défi fondamental. Ce cours sera divisé en trois parties, présentées ci-dessous.

La première partie décrira la conception de structures de données utilisables en programmation multithread, c'est-à-dire lorsque plusieurs threads de calcul communiquent en écrivant ou en lisant dans une mémoire partagée. La programmation multithread est devenue courante et repose généralement sur des implémentations optimisées de types de données abstraits courants tels que les piles, les files d'attente, les ensembles et les tables clé-valeur, dont les opérations s'exécutent en parallèle sur plusieurs cœurs de processeur afin de maximiser l'efficacité. La synchronisation entre les opérations doit être minimisée pour réduire les temps de réponse et augmenter le débit, ce qui conduit à des algorithmes complexes. Nous présenterons un échantillon représentatif de ces algorithmes et discuterons de leur correction.

Les deuxième et troisième parties se concentreront sur les structures de données, telles que les bases de données clé-valeur ou les registres distribués (blockchains), déployées sur un réseau tel qu'Internet. La deuxième partie abordera la question du maintien de la disponibilité des données dans un environnement concurrents où les ordinateurs peuvent tomber en panne ou les liaisons réseau être interrompues. Pour gérer un tel environnement, les données sont répliquées sur plusieurs sites du réseau, ce qui peut toutefois entraîner des problèmes de cohérence que l'application doit résoudre. Nous aborderons les principes de conception et les critères de cohérence les plus courants utilisés dans les bases de données clé-valeur modernes.

La troisième partie se concentrera sur les environnements concurrents où les ordinateurs peuvent également se comporter de manière malveillante en envoyant des messages contrefaits, appelés « fautes byzantines ». Un exemple célèbre de structures de données fonctionnant dans un tel environnement est celui des blockchains qui implémentent un registre pour enregistrer des transactions financières décentralisées, par exemple les transactions de smart contracts. Nous présenterons des conceptions récentes de blockchains de preuve d'enjeu et de preuve de travail, en nous concentrant sur les détails algorithmiques.

Certaines techniques cryptographiques avancées, comme le zero-knowledge, seront examinées pour la confidentialité et la mise à l'échelle des blockchains.

Les cours seront accompagnés d'un mélange de tutoriels théoriques (TD) et pratiques (TP).

Langue: Le materiel du cours est en anglais. Les cours magistraux peuvent être donnés en français ou en anglais, à la convenance des étudiants.

Évaluation: 20% Devoirs notés + 80% Examen final écrit.

Prérequis: Des connaissances raisonables de Java sont souhaitables, ainsi que des notions d'algorithmes séquentiels.