### Fault Tolerance in Distributed Systems (FTDS)

Prof. Paulo VeríssimoUniversidade 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 book Distributed Systems For System Architects, Paulo Verissimo and Luis Rodrigues, 2001, Kluwer Academic Publishers
- Slides: Part 1
- Slides: Part 2
- Slides: Part 3
- Slides: Part 4
- Slides: Part 5

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

Prof. Letizia TancaPolitecnico 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.

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

Handouts:

### Introduction to the Theory of Computational Complexity (TCC)

Prof. Pierluigi CrescenziUniversità 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 SaittaUniversità 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: