[Todos CMAT] Invitación: Defensa de Tesis de Doctorado de PEDECIBA Informática de la MSc. Ing. Graciela Ferreira.

[frobledo]

Estimados investigadores, estudiantes y docentes:

Nos complace invitarles a asistir a la defensa de la Tesis de  
Doctorado de PEDECIBA Informática de la MSc. Ing. Graciela Ferreira  
Leites Mundell.

Título de la Tesis: "Analysis and Optimization of Highly Reliable Systems".

Directores de Tesis: Dr. Pablo Romero, Dr. Sergio Nesmachnow.
Director Académico: Dr. Franco Robledo.

Día: jueves 25 de octubre de 2018.

Hora: 9:00hs.

Lugar: Salón de Posgrados 726, Piso 7 Cuerpo Central, Facultad de  
Ingeniería, UdelaR.

Tribunal:
- Dr. Bruno Tuffín (Directeur de Recherche, INRIA de Rennes, Francia)  
- REVISOR
- Dr. Guillermo Durán (Director del Instituto de Cálculo, Facultad de  
Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina)  
- REVISOR.
- Dr. Eduardo Fernández (Céntro de Cálculo, Instituto de Computación,  
PEDECIBA Informática, FING-UDELAR) - Presidente de Mesa.
- Dr. Alvaro Pardo (Facultad de Ingeniería, Universidad Católica del Uruguay).
- Dr. Eduardo Moreno (Universidad Adolfo Ibañez, Santiago de Chile, Chile).


----------------------------------------------------------------------------------------------------------------------------

Abstract:

In the field of network design, the survivability property enables the  
network to maintain a certain level of network connectivity and  
quality of service under failure conditions.

In this thesis, survivability aspects of communication systems are  
studied. Aspects of reliability and vulnerability of network design  
are also addressed. The contributions are three-fold.

First, a Hop Constrained node Survivable Network Design Problem  
(HCSNDP) with optional (Steiner) nodes is modelled. This kind of  
problems are NP-Hard. An exact integer linear model is built, focused  
on networks represented by graphs without rooted demands, considering  
costs in arcs and in Steiner nodes. In addition to the exact model,  
the calculation of lower and upper bounds to the optimal solution is  
included.  Models were tested over several graphs and instances, in  
order to validate it in cases with known solution. An Approximation  
Algorithm is also developed in order to address a particular case of  
SNDP: the Two Node Survivable Star Problem (2NCSP) with optional  
nodes. This problem belongs to the class of NP-Hard computational  
problems too.

Second, the research is focused on cascading failures and  
target/random attacks. The Graph Fragmentation Problem (GFP) is the  
result of a worst case analysis of a random attack. A fixed number of  
individuals for protection can be chosen, and a non-protected target  
node immediately destroys all reachable nodes. The goal is to minimize  
the expected number of destroyed nodes in the network. This problem  
belongs to the NP-Hard class. A mathematical programming formulation  
is introduced and exact  resolution for small instances as well as  
lower and upper bounds to the optimal solution. In addition to exact  
methods, we address the GFP by several approaches: metaheuristics,  
approximation algorithms, polytime methods for specific instances and  
exact methods in exponential time.

Finally, the concept of separability in Stochastic Binary Systems is  
here introduced. Stochastic Binary Systems (SBS) represent a   
mathematical model of a multi-component on-off system subject to  
independent failures. The reliability evaluation of an SBS belongs to  
the NP-Hard class. Therefore, we fully characterize separable systems  
using Han-Banach separation theorem for convex sets. Using this new  
concept of separable systems and Markov inequality, reliability bounds  
are provided for arbitrary SBS.

Keywords: Computation Complexity, Survivability, Graph Fragmentation  
Problem, Stochastic Binary Systems.