

Title

Diffusione dell'informazione in grafi statici e dinamici

Teacher

Prof. Pierluigi Crescenzi

Syllabus

Rumor spreading is a wellknown gossipbased distributed algorithm for disseminating information in large networks. According to the synchronous push version of this algorithm, an arbitrary source node is initially informed, and, at each time step (a.k.a., round), an informed node u chooses one of its neighbors v uniformly at random, and this node becomes informed at the next time step. In the symmetric pull version of the algorithm, at each time step, a not informed node u randomly chooses one of its neighbors v; if v is informed, then u becomes informed at the next time step. Finally, the pushandpull version is a combination of the two previous versions, in which, at each time step, each informed node executes a "push operation", and each not informed node executes a "pull operation". Rumor spreading was first introduced in the context of replicated databases, as a solution to the problem of distributing updates and driving replicas towards consistency. Successively, it has been proposed in several other application areas, such as failure detection in distributed systems, peersampling, adaptive machine discovery, and distributed averaging in sensor networks. Apart from its applications, rumor spreading has also been deeply analyzed from a theoretical and mathematical point of view. In particular, the completion time of rumor spreading, that is, the number of steps required in order to have all nodes informed, has been investigated in the case of several different network topologies, such as complete graphs, hypercubes, random graphs, and preferential attachment graphs. Besides obtaining bounds on the completion time of rumor spreading, most of these works also derive deep connections between the completion time itself and some classic measures of graph spectral theory, such as, for example, the conductance of a graph. The techniques and the arguments adopted in these studies strongly rely on the fact that the underlying graph is "static" and does not change over time. It is then natural to ask ourselves what is the speed of rumor spreading in the case of "dynamic" networks, where nodes and edges can appear and disappear over time (several emerging networking technologies such as ad hoc wireless, sensor, mobile networks, and peertopeer networks are indeed inherently dynamic). In this dynamic environment, even in the case of the simplest communication protocol that implements the broadcast operation, that is, the flooding protocol (according to which a source node is initially informed, and, whenever an uninformed node has an informed neighbor, it becomes informed itself at the next time step), it has been shown that evolving graphs can exhibit communication properties which are much stronger than static networks. In this course, we will first review several results concerning the completion time of rumor spreading in the case of static networks. We will then present some results concerning the completion time of the flooding protocol, which have been obtained in the case of some interesting graph evolution models. Finally, we will present very recent results concerning the completion time of the push version of rumor spreading in the case of dynamic graphs.

Materials


Period


Calendar

Tutte le lezioni si terranno in Sala Seminari Ovest
PRIMA PARTE
Lunedi' 8 Luglio: 912
Lunedi' 8 Luglio: 1517
Martedi' 9 Luglio: 912
Martedi' 9 Luglio: 1517
SECONDA PARTE
Lunedi' 15 Luglio: 912
Lunedi' 15 Luglio: 1517
Martedi' 16 Luglio: 912
Martedi' 16 Luglio: 1517




Title

Iterative rounding

Teacher

Prof. Fabrizio Grandoni

Syllabus

PREREQUISITES:
Attendees are expected to be familiar with elementary notions of linear algebra, probability theory and, possibly, complexity theory and linear programming. However, all the needed definitions and lemmas will be recalled during the seminars.
ABSTRACT:
IIterative Rounding is a recent, and very powerful tool to design
approximation algorithms. The basic idea is as follows. One solves a
(carefully chosen) linear programming relaxation of the considered
NPhard problem. Then one rounds some variable in the fractional
solution (which corresponds to fixing part of the solution under
construction) according to proper rounding rules. The problem is then
simplified, and the process is iterated on the residual problem until
a solution to the original problem is obtained. Alternatively or in
combination to rounding, one can also relax (i.e. drop) one
constraint. This leads to "slightly" infeasible solutions. In these
seminars we will describe a representative sample of the most relevant
results obtained via iterative rounding in the literature.
The seminars will be tentatively organized as follows. In the first
week, we will introduce approximation algorithms, and present a few
foundamental results and techniques in the area. The second week will
be devoted to approximation algorithms based on linear programming. We
will first introduce linear programming, and then present some
LPbased techniques in approximation algorithms. The final part of the
week will be devoted to iterative rounding.
Sala Seminari W
April 812 and May 610
Mon: 16  18
Tue, Wed, Thu, Fri: 9  11

Materials


Period


Calendar





Title

Security at work

Teacher

Prof. Luca Viganò

Syllabus

In the Internet of Services (IoS), systems and applications are no longer the result of programming components in the traditional meaning but are built by composing services that are distributed over the network and reconfigured and consumed dynamically in a demanddriven, flexible way. However, composing services leads to new, subtle and dangerous, vulnerabilities due to interference between component services and policies, the shared communication layer, and application functionality.
I will present the AVANTSSAR Platform and the SPaCIoS Tool, two integrated toolsets for the formal specification and automated validation of trust and security of applications in the IoS at design time and run time, respectively. Both toolsets have been applied as a proof of concept on a set of security problem cases drawn from industrial and opensource IoS application scenarios, thereby paving the way to transferring project results successfully to industrial practice and to standardization bodies and opensource communities.
I will present also a number of particular results that have been obtained in the AVANTSSAR and SPaCIoS projects, such as previously unknown attacks, compositionality results, novel attacker models and techniques for efficient security verification and testing.
May 27  June 5
Sala Seminari Ovest 1113
(additional 4h t.b.a.)

Materials


Period


Calendar















Title

Reti mobili: reti ad hoc e di sensori

Teacher

Stefano Chessa

Syllabus

The course aims at providing knowledge on mobile ad hoc, mesh, and sensor
networks, by describing their organizations models and architectures, and by
presenting the main design and implementation issues. The course presents
the main issues at the MAC, network, transport, and application layers. In
particular it gives emphasis to the issues in routing, energy management,
topology control, and data management. It also presents some specific
applications for wireless sensor networks, such as localization and
tracking, and the problem of integration of wireless sensor networks in
context aware systems or in other networks. Finally the course presents some
standards, such as 802.11X, 802.15.x, Bluetooth and Zigbee, and gives some
examples of commercial platforms for wireless sensor networks.

Materials


Period


Calendar





Title

Processes inspired by the functioning of living cells: Natural Computing approach

Teacher

Prof. Dr. G. Rozenberg

Syllabus

Natural Computing is an interdisciplinary research field that investigates humandesigned computing inspired by nature as well as computation taking place in nature, i.e., it investigates models, computational techniques, and computational technologies inspired by nature as well as it investigates phenomena/processes taking place in nature in terms of information processing.
One of research areas from the second strand of research is a computational understanding of the functioning of the living cell. We view this functioning in terms of formal processes resulting from interactions between (a huge number of) individual reactions. These interactions are driven by two mechanisms, facilitation and inhibition: reactions may (through their products) facilitate or inhibit each other.
We present a formal framework for the investigation of these interactions. We motivate this framework by explicitly stating a number of assumptions that hold for processes resulting from these interactions, and we point out that these assumptions are very different from the ones underlying traditional models of computation. We discuss some basic properties of these processes, and demonstrate how
to capture and analyse, in our formal framework, some notions related to cell biology and biochemistry.
Research topics in this framework are motivated by biological considerations as well as by the need to understand the underlying computations. The models we discuss turned out to be novel and attractive from the theory of computation point of view. This is extensively discussed throughout the course.
The course is of a tutorial style and selfcontained. In particular, no prior knowledge of biochemistry or cell biology is required.
The course is suited for master and PhD students as well as researchers and faculty members. It is of interest to computer scientists and mathematicians interested in formal models of computation as well as to bioinformaticians, biochemists, and biologists interested in foundational/formal understanding of biological processes.
The presented framework was developed jointly with A.Ehrenfeucht from University of Colorado at Boulder.
May 20, 21, 22, 23  1013
Aula Magari, Pian dei Mantellini, 44, Siena.

Materials


Period


Calendar



 


