Languages and algorithms for distributed Applications

Teacher(s)

Riviere Etienne;

Language

English
> French-friendly

Prerequisites

Main themes

• Study of the theoretical basis of distributed systems, distributed algorithms, and languages for distributed programming.
• Study of the specific issues related to distributed and mobile systems : geographic distribution, management of localized and distributed resources, fault tolerance, security, interoperability, and openness.
• Practical use of several representative and advanced systems and languages for programming collaborative, distributed, and mobile applications.

Learning outcomes

At the end of this learning unit, the student is able to :

Given the learning outcomes of the "Master in Computer Science and Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes: INFO1.1-3 INFO2.2-4 INFO5.4-5 INFO6.1, INFO6.5 Given the learning outcomes of the "Master [120] in Computer Science" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes: SINF1.M2 SINF2.2-4 SINF5.4-5 SINF6.1, SINF6.5 Students completing successfully this course will be able to: define distributed systems and distributed algorithms with concepts they contain and the properties they give to programs; design collaborative applications on distributed systems using rigorous models to deal with concurrency and partial failure; implement collaborative applications on distributed systems using appropiate technics; use some advanced tools for the development of distributed and mobile applications. Students will have developed skills and operational methodology. In particular, they have developed their ability to: think with abstractions (reason correctly about a system that consists of several layers of abstractions, and define new abstractions to simplify a problem's solution).

Content

The course is organized in two parts.
In the first part, we cover classical results and algorithms in message-passing distributed systems where nodes know and can communicate with all other nodes in a relatively small-scale setting. This part includes:

• Introduction to distributed systems
• Distributed programming using the Elixir actor-based language
• Formal models and specifications of distributed systems (safety and liveness)
• Distributed graph algorithms
• Time and the ordering of events
• Multicast algorithms
• Coordination: mutual exclusion, leader election
• Consensus algorithms and failure detectors
• State Machine Replication
• Byzantine fault tolerance

In the second part, we shift our focus to large-scale distributed systems operating at internet scale and under adversarial conditions. This second part covers:

• Gossip-based dissemination and coordination
• Structured overlay networks (e.g., distributed hash tables)
• Blockchain systems (e.g., Bitcoin, Ethereum, Hyperledger Fabric)
• Decentralized data stores (e.g., IPFS)
• Chosen topics based on recent advances in the area and in the professor’s research (non-exhaustive examples: publish/subscribe systems, layer-2 blockchain networks, ad-hoc mobile systems, local-first systems and CRDTs, …)

Teaching methods

• Weekly lecture with the instructor;
• Weekly exercise sessions with the assistants, including problem-solving on paper and programming exercises in Elixir (in part 1);
• Weekly guided sessions and tutorials linked with the programming project (in part 2).

Evaluation methods

The evaluation for the January session is as follows:

• Midterm exam: 0% or 25%, see below (around week 8, on the content of part 1 only)
• Project: 25%, based on a documented software deliverable and an oral defense
• Final exam: 50% if counting the midterm at 25% is beneficial to the student, and 75% otherwise (during the session, on the content of both parts 1 and 2)

The project is mandatory and is done during the quadrimester. It can be done only once, and it counts for the whole academic year. Students prepare and defend the project in pairs, but the grade is individual. The midterm exam is also mandatory and cannot be redone in the September session.
The evaluation for the September session is as follows:

• Midterm exam: 0% or 25%, see below (kept from January session)
• Project: 25% (kept from January session)
• Final exam: 50% if counting the midterm at 25% is beneficial to the student, and 75% otherwise (on the content of both parts 1 and 2)

All course material is provided in English. Students can answer exam questions and present their project in English or French.
The midterm and final exams may use all or a subset of the following evaluation modalities. The respective proportion of points for each part is announced at the beginning of the exam:

• open questions on the course content
• open problems requiring an application of skills and knowledge acquired during the course
• multiple-choice and multiple-answer questions under the principle of "standard-setting". An incorrect answer to one of the questions cannot lead to a negative grade, and the exam part as a whole cannot grant negative points. However, a minimum threshold (announced in the exam) of correct answers is necessary before effectively acquiring points for this exam part.

The professor may request that a student take an additional oral exam in addition to the midterm or final exam and/or the project in cases including, but not limited to, technical issues or suspicion of irregularities.
Rules regarding the use of artificial intelligence (AI) for the project
Responsible use of AI for implementing the project in the Elixir language is accepted under the following rules:

• Students must take full responsibility for their work and be able to explain orally all the code and deliverables (documentation, deployment scripts, etc.) submitted as part of the project.
• The use of AI must be precisely documented in the project documentation, in a dedicated section indicating which AIs were used and for which part. Submitting code or documentation generated partially or entirely by AI without documenting this use will be considered plagiarism. Students who did not use AI must also indicate this in the section. Failure to provide an AI statement with the project will lead to a penalty of -5/20 points.
• Use considered abusive of AI, undermining the acquisition of the knowledge targeted by the project, may be considered an irregularity under Section 7, Articles 107 and following of the General Regulations for Studies and Exams (RGEE), with all the consequences that entail, as provided in Articles 111 and following. In the event of suspected abusive use of AI in the submitted project or an incomplete or inaccurate report of AI use, the course instructor may summon the student concerned for an additional oral consultation and take the necessary measures in consultation with the EPL jury chair.

Other information

Knowledge of basic programming. Experience in concurrent programming and/or functional languages (as covered, for example, by LINFO1131) is a plus but not a strict requirement.
LINFO2345 is designed to be complementary to the following courses:

• LINFO2145 (Cloud computing) covers distributed applications for the cloud and associated data management and processing at a higher level and with a stronger emphasis on software engineering and operating systems aspects. Yet, it benefits from understanding the underlying algorithms and tradeoffs covered in LINFO2345.
• LINFO2355 (Multicore programming) covers concurrent programming in shared memory, and synchronization and scaling techniques on a single multi-core machine. LINFO2345 focuses on message-passing systems. The two topics are highly complementary but relate to different tools and techniques.

Online resources

Moodle page of the course (lookup for LINFO2345).

Bibliography

Mandatory course material on Moodle:

• Course slides
• Exercices 

Additional books and research papers may be suggested during the lectures but none are mandatory.

Faculty or entity

> INFO