Communication et routage
IF306 |
(New November 28th, 2018) Instructions for the student seminar (which will take on December 14) and a list of topics are here.
Summary
This course focuses on algorithmic aspects underlying communication and information routing in distributed systems.
Content
The course offers each year two selected topics in the list below. For 2016/2017, the topics are Distributed data structures and routing (1.) and Power and limitations of shared memory systems (4.). The course concludes by a student seminar in which groups of students present a short lecture extending the material presented in class.
-
Distributed data structures and routing. Nicolas Hanusse/Cyril Gavoille.
-
Introduction to (fault-tolerant) distributed data structures
- Compact routing in trees
- Spanners
- Communication algorithms for wireless networks/Graph exploration. Ralf Klasing.
-
Data Gathering in Wireless Networks. This part of the course, we address the problem of gathering information in a specific node
of a radio network when interference constraints are present. We present complexity results and approximation algorithms for
several variants of the problem.
- Mobile Agent Computing.
A mobile agent is a program that circulates in a network, and that has the capability to execute
itself on different nodes. In this part of the course, we are interested in solving problems on
networks using mobile agents. Specific problems include Black Hole Search, Network exploration,
and Rendezvous/gathering.
- Data streaming algorithms. Olivier Beaumont.
Suppose that some statistics have to be computed on a large amount of data that does not fit in main memory. This situation may arise for example in databases or in a pre-computing phase of a parallel computation. Data streaming algorithms operated under limited time and memory resources and, as a result of theses constraints often give an approximate answer.
-
Introduction to data-streaming.
- Counting distinct elements.
- Power and limitations of shared memory systems. Corentin Travers.
This part of the course studies in a somewhat idealized model shared memory algorithms for some fundamental distributed tasks. Some impossiblity results are also presented.
-
Wait-free computing
- Computing with reads and writes
- Consensus numbers
- Asynchronous computability theorem
Planning
Courses take place on Friday morning, 9:30-12:20, room TBA, except the first one.
Consensus and blockchain slides
Course webpage
http://ctravers.vvv.enseirb-matmeca.fr/IF306/
Ce document a été traduit de LATEX par HEVEA