Fault Tolerance in Distributed Systems (FTDS)

Prof. Paulo Veríssimo
Universidade de Lisboa (Portugal)

Summary:
The course intends to address the dependability of distributed systems. In short, how to ensure that they keep running correctly, in spite of mishaps such as faults, which if ignored, may lead to failure, but if treated instead, may keep the system working correctly. It contains the fundamental notions concerning dependability, such as the triad fault-error-failure and provides a comprehensive treatment of distributed fault tolerance. The course starts with a review of distributed systems: foundations, main paradigms (e.g., message passing; remote operations; group communication; time, clocks and synchrony; ordering and consistency; concurrency and atomicity) and main models (e.g., asynchronous vs. synchronous; client-server, group-oriented and event-based; distributed shared memory and message buses). Then fault-tolerant systems are then addressed in a structured manner. Fundamental concepts are introduced, from the generic notion of dependability and its associated concepts, to the introduction of distributed fault tolerance. Paradigms for distributed fault tolerance are addressed next and the student is exposed to issues such as: failure detection and membership; consensus and uniformity; fault-tolerant communication; replication management; resilience, voting, and recovery. The student is now ready to try and make sense of how complete solutions should look like, through the main strategies and models of distributed fault tolerance: F/T remote operations; F/T event services; transactions. A few examples of realistic systems consolidate these aspects. A case study turns the students into system architects designing their own fault-tolerant system. The VP'63 (Vintageport' 63) Large-Scale Information System belongs to an imaginary Portuguese wine company, with facilities spread through the country, and a traditional, centralized information system that must adapt to the modern times. The challenge consists in making VP'63 distributed and dependable. Finally, the student is exposed to advanced research directions concerning distribution, fault tolerance, and security. Intrusion tolerance is a new approach whereby, instead of trying to prevent every single intrusion, the latter are allowed, but tolerated. The system has the means to trigger automatic mechanisms that react, counteract, recover, mask, etc., in an automatic way, the effect of intrusions on the system state, preventing the intrusion from generating a system failure.

The course will be supported on the following material:

Context-Aware Databases: Design, Integration and Applications (CAD)

Prof. Letizia Tanca
Politecnico di Milano (Italy)

Summary:
Many interpretations of the notion of context have emerged in various fields of research like psychology, philosophy, or computer science. Context-aware systems are pervading everyday life, therefore context modelling is becoming a relevant issue and an expanding research field. In Information Management, context-aware systems are mainly devoted to determining which information is relevant with respect to the ambient conditions. Indeed, nowadays the amount of available data and data sources requires not only to integrate them (still a hard problem), but also to filter (tailor) their information in order to:

  • provide the user with the appropriately tailored set of data,
  • match devices' physical constraints,
  • operate on a manageable amount of data (for improving query processing efficiency),
  • provide the user with time- and location-relevant data (mobile applications).

The aims of this course are:

  • to give a definition of the notion of context in the database field, and provide a survey and comparison of the most interesting approaches to context modelling and usage available in the literature,
  • to introduce a comprehensive evaluation framework, allowing application designers to compare context models with respect to a given target application,
  • to analyze more deeply those features and those models which are relevant for the problem of context-aware data management, where the aim is to provide a systematic support to the designer of data management applications in determining the portions of information which are related to each given context.
The course will be accompanied by exercise sessions in which the students will design a context-aware database.

Prerequisites: database models, data design methodologies, database languages.

Handouts:

Introduction to the Theory of Computational Complexity (TCC)

Prof. Pierluigi Crescenzi
Università di Firenze (Italy)

Summary:
The theory of computational complexity deals with efficient algorithms: even though, during the last century, mathematicians, logicians, and computer scientists have been able to almost fully understand the power of algorithms, the power of "efficient" algorithms is still unclear. Indeed, the theory of computational complexity still contains more questions (and relationships among them) than answers. However, several fascinating results (and even answers) have been obtained in this research sector, that developed quite fast in the last three decades. The aim of the course will be to introduce the basic notions of the theory of computational complexity, without ignoring some of the most recent results. The course will be a broad introduction to the research field. At the beginning, classical topics of the theory of computational complexity will be presented, such as P, NP, EXP, diagonalization, space complexity classes, and the polynomial hierarchy. Successively, few more advanced topics will be introduced, such as randomized algorithms, interactive proofs, and applications to cryptography. The course will mainly follow the first part of the draft of the text book Complexity Theory: A Modern Approach, written by Sanjeev Arora and Boaz Barak.

Prerequisites: Classical notions of computability theory and of algorithms and data structures, such as Turing machine, reducibility and algorithm analysis.

Machine Learning (ML)

Prof. Lorenza Saitta
Università di Torino (Italy)

Summary:
The course aims at providing students with a comprehensive overview of the various approaches and techniques that have alternatively characterized Machine Learning during its 30-year life. They will include, not exhaustively, logical, connectionist, and evolutionary approaches, as well as reinforcement, case-based, and PAC-learning. Both supervised and unsupervised learning will be discussed. The topics will be presented following a historical perspective, in such a way that the complex internal dynamics of the field shall emerge, together with the contributions from (and links with) related disciplines, such as Statistics, Pattern Recognition, and Artificial Intelligence. In particular, the influence of Machine Learning and its current role inside the new field of Data Mining and Knowledge Discovery will be illustrated. Both theoretical and practical aspects of Machine Learning will be tackled, with special attention to the issues of computational complexity and validation methods. Finally, some open problems and hot topics at the frontier of today research will be discussed. Some exercises using open source packages available on the Web will be suggested. The exam will consists of a project, to be completed after the end of the course.

Handouts: