Cybersecurity

GIUSEPPE ANTONIO DI LUNA

Obiettivi formativi

Il corso riguarda i sistemi distribuiti, con particolare attenzione alla tolleranza ai guasti. Gli studenti impareranno a comprendere le difficoltà introdotte dalla coesistenza inevitabile di conoscenza locale, asincronia e guasti. Comprenderanno come e quando, nonostante tali difficoltà, sia possibile costruire algoritmi distribuiti potenti. Al termine del corso, lo studente dovrà essere in grado di progettare algoritmi distribuiti tolleranti ai guasti e di fornire argomentazioni formali e convincenti sulla loro correttezza.

Conoscenza e capacità di comprensione

Lo studente conosce e comprende i concetti e i principi fondamentali dei sistemi distribuiti, quali processi, comunicazione, guasti, tempo, sincronizzazione, consistenza, consenso, broadcast, replicazione e tolleranza ai guasti.

Capacità di applicare conoscenza e comprensione

Lo studente è in grado di applicare le conoscenze sui sistemi distribuiti per progettare e implementare algoritmi distribuiti che risolvano problemi in diversi contesti e scenari, quali leader election, memoria condivisa, total order broadcast, replicated state machines, consenso e replicazione tollerante ai guasti.

Autonomia di giudizio

Lo studente è in grado di analizzare criticamente e confrontare diversi algoritmi distribuiti in termini di correttezza, efficienza, scalabilità, robustezza e complessità. Lo studente è inoltre in grado di identificare le assunzioni e i limiti di ciascun algoritmo e di valutarne l’adeguatezza rispetto a diverse applicazioni e requisiti.

Abilità comunicative

Lo studente è in grado di comunicare efficacemente i principali concetti e risultati relativi ai sistemi distribuiti utilizzando terminologia e notazione appropriate. Lo studente è inoltre in grado di presentare e discutere algoritmi distribuiti mediante diagrammi, pseudocodice, presentazioni orali e relazioni scritte.

Capacità di apprendimento

Lo studente sviluppa la capacità di approfondire autonomamente argomenti avanzati nell’ambito dei sistemi distribuiti e di mantenersi aggiornato sugli sviluppi del settore.

Course Abstract: The course is about distributed systems, with a specific focus on fault-tolerance. Students will learn to appreciate the difficulties introduced by the uncertainty given by the unavoidable coexistence of local knowledge, asynchrony, and failures.

They will understand how and when, in spite of these difficulties, it is possible to build powerful distributed algorithms. Such algorithms are essential to construct distributed systems in which geographical distant entities cooperate to solve disparate tasks.

The term ``failure" has to be intended in its more general meaning: it indicates any deviation from normal behavior. Therefore, it subsumes the concept of malignant intrusion. Algorithms will be presented in a formal, abstract, and modular way. At the end of the course, the student is expected to be able to design fault-tolerant distributed algorithms, and to provide formal and convincing arguments on their correctness.

At the end of the entire course the acquired skills should be:
Knowledge and understanding:: The student knows and understands the fundamental concepts and principles of distributed systems, such as processes, communication, failures, time, synchronization, consistency, consensus, broadcast, replication, and fault tolerance.
Applying knowledge and understanding: The student can apply the knowledge and understanding of distributed systems to design and implement distributed algorithms that can solve various problems in different settings and scenarios, such as leader election, shared memory, total order broadcast, replicated state machine, etc.
Making judgements: The student can critically analyze and compare different distributed algorithms in terms of correctness, efficiency, scalability, robustness, and complexity. The student can also identify the assumptions and limitations of each algorithm and evaluate their suitability for different applications and requirements.
Communication skills: The student can communicate effectively the main concepts and results of distributed systems using appropriate terminology and notation. The student can also present and discuss distributed algorithms using oral presentations and written reports.
Learning skills: The student can independently learn new distributed systems concepts and methods by reading scientific literature and following online courses. The student can also update their knowledge and skills by following the latest developments in the field.

Detailed Learning Objectives: (the objectives are given for each module of the program – see program section below).

For M1: Models, Abstractions, and Basic Concepts
Knowledge and understanding: Students will be able to explain basic concepts such as processes, communication, traces and execution, I/O automata, failures, event-based programming, links.
Applying knowledge and understanding: Students will be able to use models and abstractions to model distributed systems that can cope with different types of failures and communication channels.
Making judgements: Students will be able to evaluate the advantages and disadvantages of different models and abstractions for distributed systems.
Communication skills: Students will be able to present their designs for distributed models using appropriate notation and terminology.
Learning skills: Students will be able to learn new models from relevant sources for further autonomous study on distributed systems.

For M2: Time in Distributed Systems
Knowledge and understanding: Students will be able to explain the concepts of synchronous, asynchronous, and eventually synchronous systems; clock synchronization algorithms; logical clocks and vector clocks; happened-before relationship; failure detectors.
Applying knowledge and understanding: Students will be able to implement clock synchronization algorithms using message passing; use logical clocks and vector clocks to order events in distributed systems; use failure detectors to handle failures and elect leaders.
Making judgments: Students will be able to compare different clock synchronization algorithms in terms of accuracy, efficiency, and scalability; analyze the limits of ordering with timestamps; choose appropriate failure detectors for different system models.
Communication skills: Students will be able to use diagrams and pseudocode to illustrate clock synchronization algorithms, logical clocks and vector clocks, failure detectors.
Learning skills: Students will be able to use the acquired notion to autonomously study new clock synchronization algorithms and new abstractions of time in distributed systems.

For M3: Basic Broadcast Primitives
Knowledge and understanding: The student knows and understands the basic concepts and properties of different types of broadcast primitives in distributed systems, such as best effort, reliable, uniform reliable, and causal broadcast.
Applying knowledge and understanding: The student can apply the knowledge and understanding of broadcast primitives to design and implement distributed algorithms that use them as building blocks, such as consensus or total order broadcast.
Making judgements: The student can critically evaluate the advantages and disadvantages of different broadcast primitives in terms of correctness, efficiency, scalability, and fault-tolerance.
Communication skills: The student can communicate effectively with peers and instructors about the concepts and algorithms related to broadcast primitives using appropriate terminology and notation.
Learning skills: The student can independently learn new topics related to broadcast primitives by reading scientific papers or textbooks.

For M4: Shared Memories
Knowledge and understanding: The student knows and understands the basic concepts and properties of shared memory in distributed systems, such as consistency models, registers, and non-composability.
Applying knowledge and understanding: The student can apply the knowledge and understanding of shared memory to design and implement distributed algorithms that use it as an abstraction layer, such as atomic broadcast or mutual exclusion.
Making judgements: The student can critically compare and contrast different consistency models and register implementations in terms of correctness, efficiency, scalability, and fault-tolerance.
Communication skills: The student can communicate effectively with peers and instructors about the concepts and algorithms related to shared memory using appropriate terminology and notation.
Learning skills: The student can independently learn new topics related to shared memory by reading scientific papers or textbooks.

For M5: Consensus
Knowledge and understanding: The student knows and understands the basic concepts and properties of consensus in distributed systems, such as the consensus specification, the impossibility results (FLP), and the main algorithms (hierarchical consensus, Paxos, Raft).
Applying knowledge and understanding: The student can apply the knowledge and understanding of consensus to design and implement distributed algorithms that use it as a fundamental problem, such as state machine replication or atomic commit.
Making judgements: The student can critically analyze and compare different consensus algorithms in terms of correctness, efficiency, scalability, fault-tolerance, and complexity.
Communication skills: The student can communicate effectively with peers and instructors about the concepts and algorithms related to consensus using appropriate terminology and notation.
Learning skills: The student can independently learn new topics related to consensus by reading scientific papers or textbooks.

For M6: Replicated State Machines
Knowledge and understanding: The student knows the principles and techniques of total order broadcast and replicated state machine in distributed systems. The student understands how these concepts can be used to implement fault-tolerant services.
Applying knowledge and understanding: The student can design and implement total order broadcast algorithms using different communication primitives. The student can use replicated state machine to build consistent applications that tolerate failures.
Making judgements: The student can evaluate the trade-offs between different total order broadcast algorithms in terms of complexity, performance, and reliability. The student can compare active replication and primary backup approaches for replicated state machine.
Communication skills: The student can explain the concepts of total order broadcast and replicated state machine using appropriate terminology. The student can present their design choices and implementation details clearly and concisely.
Learning skills: The student can independently study advanced topics related to total order broadcast and replicated state machine. The student can apply their knowledge to new scenarios or problems in distributed systems.
For M7: BFT
Knowledge and understanding: The student knows and understands the main concepts and challenges of Byzantine fault tolerance (BFT) in distributed systems, such as authenticated channels, Byzantine broadcast, consensus, and replication.
Applying knowledge and understanding: The student can apply BFT techniques to design and implement distributed algorithms that can tolerate Byzantine failures, such as King algorithm and Raft protocol.
Making judgements: The student can critically evaluate the trade-offs and limitations of BFT solutions in terms of performance, security, scalability, and complexity.
Communication skills: The student can communicate effectively the main ideas and results of BFT research papers using oral presentations and written reports.
Learning skills: The student can independently learn new BFT concepts and methods by reading scientific literature and following online courses.

Prerequisiti
Basic knowledge of algorithms and complexity: concept of algorithm, complexity measures.
Basic knowledge of computer science and networks: communication protocols, client/server systems.
Basic knowledge of logic: induction, implications, proofs by contradiction.

Basic knowledge of algorithms and complexity: concept of algorithm, complexity measures.
Basic knowledge of computer science and networks: communication protocols, client/server systems.
Basic knowledge of logic: induction, implications, proofs by contradiction.

Distributed systems are a fundamental concept in modern computing, enabling the creation of large-scale, fault-tolerant systems that can provide robust, reliable services to users. This university-level course is designed to provide an in-depth understanding of distributed systems, starting with a brief history and overview of the challenges and motivations that led to their development.

Program:

The course is divided into seven modules, each of which covers a different aspect of distributed systems:

M1: Models, Abstractions, and Basic Concepts
In this module, students will learn about the core models and abstractions used in distributed systems, including processes, communication, traces and execution, and I/O Automata. Students will also study different types of failures, such as crash-stop and Byzantine failures, and learn about event-based programming and its abstraction, specification, and implementation. Finally, students will explore different types of links, including fair-lossy, stubborn, and point-to-point links.

M2: Time in Distributed Systems
This module focuses on time in distributed systems, covering synchronous, asynchronous, and eventually synchronous systems. Students will learn about different clock synchronization techniques, including Christian, Berkeley, and NTP, and study tree-based versus fully distributed algorithms. The module also covers logical clocks and vector clocks and the happened-before relationship. Students will also learn about encapsulating time in failure detectors, leader election, eventual leader election, and distributed system models, such as fail-stop, fail-noisy, and fail-silent systems.

M3: Basic Broadcast Primitives
In this module, students will explore different types of broadcast primitives, including best-effort broadcast, reliable broadcast, uniform reliable broadcast, and causal broadcast.

M4: Shared Memories
This module focuses on shared memories and explores different types of consistency, including regular, sequential consistency, and linearizability. Students will also learn about different types of registers, such as (1, N) register and atomic (1, 1), (1, N), and (N, N) registers. The module also covers the non-composability of sequential consistency and the relationship between consistency properties.

M5: Consensus
This module covers consensus and its specification. Students will explore hierarchical consensus, including uniform and non-uniform consensus. The module also covers FLP, including the proof that is not required, only the statement, and Paxos.

M6: Total Ordering and Replicated State Machine
In this module, students will learn about total order broadcast and replicated state machines, including Raft. The module also covers active replication versus primary backup.

M7: Byzantine Fault Tolerance (BFT)
This module covers the basics of BFT, including Byzantine failures and authenticated channels and crypto assumptions. Students will learn about Byzantine broadcast, including its consistency and reliability. The module also covers synchronous systems, including an impossibility result and the necessity of 3f+1 and King Algorithm.

Tentative course calendar:
The course is designed to be taught over 12 weeks, with five hours of teaching each week. The tentative course calendar is as follows:


Week 1:
Introduction to Distributed Systems
-Brief history;
-Challenges;
-Motivations.

Models, Abstractions, and Basic Concepts (M1)
-Processes, communication, traces and execution, I/O Automata;
-Failures: crash-stop, and Byzantine;
-Event-based programming: abstraction, specification, and implementations;
-Links: fair-lossy, stubborn, point-to-point.

Week 2/3:
Time in Distributed Systems (M2)
-Synchronous, asynchronous, and eventually synchronous systems;
-Clock Synchronization: Christian, Berkley, NTP;
-Clock sync. Tree-based vs Fully-Distributed Algorithms, Local Skew vs Global Skew, The limits of ordering with timestamps
-Logical clocks and Vector Clock, Happened-before relationship.

Week 3/4:
Time in Distributed Systems (M2) continued
-Encapsulating time in failure detectors: P, $\Diamond$-P;
-Leader election and Eventual Leader Election
-Distributed system models: fail-stop, fail-noisy, fail-silent."

Week 3/4:
Basic Broadcast Primitives (M3)
-Best effort broadcast;
-Reliable broadcast;
-Uniform reliable broadcast;
-Causal broadcast.

Week 5:
Shared Memories (M4)
-Consistency: regular, sequential consistency, and linearizability;
-Regular (1,N) register: Message Passing and (1,1)-Regular implementation
-Atomic (1,1), (1,N), and (N,N) registers;
-Non-composability of sequential consistency;
-Relationship between consistency properties;"

Week 7:
Consensus (M5)
-Consensus specification;
-Hierarchical consensus: uniform and non-uniform;
-FLP: proof not required only the statement
-Paxos.

Week 8:
Total Ordering and Replicated State Machine (M6)
-Total Order broadcast
-Replicated State Machine and Raft.
-Active Replication vs Primary Backup

Week 9:
BFT (M7)
-Intro: Byzantine failures.
-Authenticated Channel and crypto assumptions.
-Byzantine Broadcast, consistent and reliable.

Week 10:
BFT (M7) continued
-Consensus: synchronous systems, an impossibility result: the necessity of 3f+1.
-Consensus: synchronous systems: King Algorithm

Week 11:
Recap and Exercises

Introduction to Reliable and Secure Distributed Programming - C. Chacin, R. Guerraoui, and L. Rodrigues. 2011
Bibliografia di riferimento
Distributed Algorithms - N. Lynch. 1998. Distributed Computing - H. Attiya, J.L. Welch. 2004
Distributed Systems 3rd edition - M. Van Steen and A.S. Tanenbaum. The authors give away free copies: https://www.distributed-systems.net/index.php/books/distributed-systems-3rd-edition-2017/
Design and Analysis of Distributed Algorithms- N. Santoro, 2008.

Distributed Algorithms - N. Lynch. 1998.

Distributed Computing - H. Attiya, J.L. Welch. 2004

Distributed Systems 3rd edition - M. Van Steen and A.S. Tanenbaum. The authors give away free copies: https://www.distributed-systems.net/index.php/books/distributed-systems-3rd-edition-2017/

Design and Analysis of Distributed Algorithms- N. Santoro, 2008.

Tradizionale

Facoltativa

The evaluation is a written exam that tests the student’s knowledge and understanding of the fundamental concepts and principles of distributed systems, as well as their ability to apply them to solve simple problems. The exam consists of multiple-choice questions, short-answer questions, and problem-solving exercises.
The sufficient mark is 18/30 the highest possible mark is 30/30, the laude is awarded in special cases (complete mastery of the discipline).
The marks (18-21) are given to students that show a sufficient knowledge and understanding of fundamentals concepts and principle, but that have difficulties to apply these concepts in a novel way in problem solving exercises.
The marks (22-24) are given to students that show a good knowledge and understanding of fundamentals concepts and principle, but that can sufficiently apply these concepts in a novel way in problem solving exercises.
The marks (25-27) are given to students that show a good or complete knowledge and understanding of fundamentals concepts and principle, but that can apply these concepts in a novel way in problem solving exercises with minimal mistakes.
The marks (27-29) are given to students that show a complete knowledge and understanding of fundamentals concepts and principle, but that can apply these concepts in a novel way in problem solving exercises without mistakes.
The marks (30-30 Laude) are given to students that show a complete knowledge and understanding of fundamentals concepts and principle, but that can apply these concepts in a novel way in problem solving exercises without mistakes and with an elegant and efficient methodology. The Laude is awarded only to students that show a complete and total mastery of the discipline during an additional oral examination reserved to students that reach the mark of 30 in the written exam.

The exam is composed of a first part with multiple choices questions and open questions.

The second part is composed by one ore more exercises

The third part requires the design of a distributed algorithm. An example of exam is below:

https://drive.google.com/file/d/103KY5K6i0eOJqex2f3kBBl9MMCMVQ_gC/view?usp=sharing