28/01/2015 – Workshop on mobile agents and robots


January, 28th 9.30-12.30, Room 1, Bulding Z, Campus Scientifico


9.30-9.35 Workshop presentation.

9.35-10.20 Prof. Evangelos Kranakis Carleton University, Ottawa, Canada: “Evacuating Robots from an Unknown Exit in a Disk”.

Consider k mobile robots inside a circular disk of unit radius. The robots are required to evacuate the disk through an unknown exit point situated on its boundary. We assume all robots having the same (unit) maximal speed and starting at the centre of the disk. The robots may communicate in order to inform themselves about the presence (and its position) or the absence of an exit. The goal is for all the robots to evacuate through the exit in minimum time.

We consider two models of communication between the robots: in non-wireless (or localcommunication model robots exchange information only when simultaneously located at the same point, and wireless communication in which robots can communicate one another at any time. We study the following question for different values of k: what is the optimal evacuation time for k robots? We provide algorithms and show lower bounds in both communication models for k=2 and k=3 thus indicating a difference in evacuation time between the two models. We also obtain almost-tight bounds on the asymptotic relation between evacuation time and team size, for large k. We show that in the local communication model, a team of k robots can always evacuate in time 3 + (2Π)/k, whereas at least 3 + (2Π)/k – O(k^{-2}) time is sometimes required. In the wireless communication model, time 3 + Π/k + O(k^{-4/3}) always suffices to complete evacuation, and at least 3+ Π/k is sometimes required. This shows a clear separation between the local and the wireless communication models.


10.25-11.10 Prof. Danny Krizanc Wesleyan University, Middletown, CT, U.S.A.: “The Dynamic Map Visitation Problem: Foremost Coverage of Time-varying Graphs.”

We consider the Dynamic Map Visitation Problem (DMVP), in which a team of agents must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during the agents’ navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP, shedding new light on the computational hierarchy R ⊃ B ⊃ P of TVG classes by analyzing them in the context of graph navigation. We provide hardness results for all three classes, and for several restricted topologies, we show a separation between the classes by showing severe inapproximability in R, limited approximability in B, and tractability in P. We also give topologies in which DMVP in R is fixed parameter tractable, which may serve as a first step toward fully characterizing the features that make DMVP difficult.

11.10-11.40 coffee break (registration is required).

11.40-12.10 PhD students demos with LEGO MINDSTORMS Robots.

23/10/2014 – Talk by Laurent Vuillon (Université de Savoie)

Title: From tilings to fibers: bio-mathematical aspects of fold plasticity
Time: 14:00
Location: Meeting room
Type: Research Result
Speaker: Laurent Vuillon (Université de Savoie)
Protein oligomers are made by the association of protein chains via intermolecular amino acid interactions (interaction between subunits) forming so called protein interfaces. This talk proposes mathematical concepts to investigate the shape constraints on the protein interfaces in order to promote oligomerization. First, we focus on tiling the plane (2 dimensions) by translation with abstract shapes. Using the fundamental Theorem of Beauquier-Nivat, we show that the shapes of the tiles must be either like a square or like a hexagon to tile the whole plane. Second, we look in more details at the tiling of a cylinder and discuss its relevancy in constructing protein fibers. The universality of such “building” properties are investigated through biological examples.

18/09/2014 – Talk by Soumya Sen

Title: Integrating XML with Data Warehouse
Time: 14:00
Location: Meeting room
Type: Research Result
Speaker: Soumya Sen
XML is the most widely used language in web environment. Many of the organizations maintain their semi-structured data in XML format for e-commerce and internet based applications. These XML data which are used to manage OLTP data can be processed further for analytical processing. Integration of XML and data warehouse for the innovation of business logic and to enhance decision making has therefore emerged as a demanding area of research interest. 
XML is semi-structured model where as majority of the OLAP are maintained through relational model. Thus the conversion is preferably aimed at Relational OLAP (ROLAP). The majority of the research work in this field is based on conversion of single XML schema to star or snowflake schema. A significant improvement is to consider multiple XML schemas and possibly identifying fact constellation.
However a major problem in existing research is the use of other intermediate tool, data structure or middleware to convert XML into data warehouse. The use of this extra entity slows down the process. Eliminating the presence of this entity is a good research challenge. XQuery, the query language on XML could be efficiently used to meet the challenge. A state of the art framework is presented to formalize a standard syntactical structure to construct lattice of cuboids from XML data as well performing the common OLAP operations using only XQuery.    

16/09/2014 – Talk by Lucia Gallina

Title: Formal Models for the Analyisis of Cloud Computing
Time: 12:00
Location: Meeting room
Type: Research Result
Speaker: Lucia Gallina
Cloud Computing is a smart solution aiming at effectively sharing massive computational resources on-line between multiple users. The key benefits of Cloud computing is virtualisation, provisioning and elasticity: clients see an infinite amount of virtual machines which they can lease on demand, responding to short-term application load, thus eliminating significant purchase and maintenance costs of private high-end computational infrastructure which would remain underutilised during off peak periods. This new paradigm creates a profitable market for cloud vendors who can simultaneously run client virtual machines on the same data centers, taking advantage of clever scheduling and resource provisioning. In the last few years, cloud computing had a great impact, and today companies such as Google, Amazon and Microsoft implement cloud solutions. However, there are still many open issues that have to be taken in consideration.
One of the main challenges is to invent precise resource provisioning technology, which is crucial in guaranteeing high performance and low-cost services. Indeed, resource allocation is organized with a pay as you go model, and it is fundamental to add or remove resources at a fine grain, ensuring the final users the services they are asking for, without delays, but at the same time without falling into over-provisioning, i.e., the under utilisation of the resources, which is a critical factor influencing the costs.

23/07/2014 – Talk by Wilayat Khan

Title: Client Side Web Session Integrity as a Non-Interference Property
Time: 11:00
Location: Meeting room
Type: Research Result
Speaker: Wilayat Khan

Because of the stateless nature of the HTTP protocol, web applications
that need to maintain state over multiple interactions with a client have
to implement some form of session management: the server needs to know to
what ongoing session (if any) incoming HTTP requests belong. Sessions are
usually implemented by means of session cookies, which are unpredictable
random identifier generated by the server at the start of a session.

Sessions can be attacked at network (e.g. sniffing), implementation (e.g.
script injection) and application layers. The attacks at the first two
layers are well-understood problems with well-understood solutions,
however, the problem of application-level session integrity is not yet
well-understood. An attack at application layer happens when a page in the
browser send malicious requests to any of the servers that the browser
currently has a session with, and that request will automatically get the
session cookie attached and hence will be considered as part of a
(possibly authenticated) session by the server, leading to CSRF attacks.
Moreover, malicious requests can also be sent by scripts included in or
injected by an attacker into a page from the same origin.

In this work, we refined our previous ideas to the classical
noninterference property as known from information flow security and
designed an information flow control technique that can enforce session
integrity in a more permissive and fine-grained way than access control

11/06/2014 – Talk by Ivan Stojic

Title: Optimisation of servers with different quality of services
Time: 14:00
Location: Meeting room
Type: Research Result
Speaker: Ivan Stojic

In many applications involving client/server or equivalent architecture, it is possible to vary the quality of services provided by the servers. Dynamic control of the quality of services is an effective mechanism for control of the performance of the system in conditions of varying system load. One of the basic problems involved in applying this mechanism is optimisation of the controlling policy that determines the level of quality of services based on the state of the system. In this seminar, after a brief introduction to Markov chains and basic queueing models, a Markov chain based model of a multiserver queue with processor-sharing discipline and different quality of services is presented. Calculation of the performance indices from the model and the prohibitive complexity of the exact solution are discussed next, motivating the introduction of a simpler model that heuristically approximates the original model and allows for more efficient model solution and optimisation of the controlling policy.

23/04/2014 – Talk by V-T. Hoang and M. Hussain

Title: Performance evaluation of TCP congestion control mechanisms ECN/RED and SAP-LAW in presence of UDP traffic
Time: 13:00
Location: Meeting room
Type: Research Result
Speaker: V-T. Hoang and M. Hussain

Internetworking often requires a large amount of users to share a common gateway to obtain the connectivity to the Internet. Congestion avoidance mechanisms are used to prevent the saturation of the gateway which represents a bottleneck of the system. The most popular congestion avoidance mechanisms are the Explicit Congestion Notification (ECN) and the Random Early Detection (ECN). Recently, a new method for the congestion avoidance has been proposed: the Smart Access Point with Limited Advertised Window (SAPLAW). The main idea is to hijack at the gateway the acknowledge packets in the TCP connections in order to artificially reduce the advertised destination window according to some bandwidth allocation policy. Therefore, the flux control mechanism is artificially exploited to control the congestion at the bottleneck. The advantage of this approach is that it does not drop any packet and does not require any modification in the TCP implementations at the clients. In this paper we propose stochastic models for the ECN/RED and SAP-LAW mechanisms in order to compare their performances under different scenarios. The models are studied in mean field regime, i.e., under a great number of TCP connections and UDP based transmissions while considering TCP greedy and temporary connection. in this paper we consider the presence of UDP traffic with bursts, and the case of not greedy TCP connections. The models for SAP-LAW are totally new. The comparison is performed in terms of different performance indices including average queue length, system throughput, expected waiting time.



16/04/2014 – Talk by Silvia Signorato

Title:  Le indagini informatiche nel procedimento penale: analisi, valutazioni, prospettive.
Time: 13:00
Location: Meeting room
Type: Research Result
Speaker: Silvia Signorato

Nell’attuale società globalizzata l’informatica permea ormai quasi ogni ambito del reale. Pressoché inevitabile, quindi, che pure la criminalità si avvalga dell’informatica per la commissione di reati. Al riguardo, si pensi solo a phishing, pedopornografia on line, diffamazioni commesse su social network, cyberstalking, adescamento di minori in Internet, violazione di diritto d’autore, istigazione on line al suicidio, in un crescendo di reati che non può non destare allarme sociale. 

A fronte della commissione di simili reati, anche le indagini penali divengono informatiche e sempre più spesso gli elementi di prova sono rappresentati da digital evidence.
Il seminario intende offrire un quadro introduttivo al tema delle indagini informatiche nel procedimento penale.
In tale ottica, anzitutto verranno tracciate le coordinate della disciplina vigente in materia; in secondo luogo, saranno esaminate le più rilevanti questioni giuridiche che derivano dall’impiego dell’informatica nell’ambito delle indagini penali; infine, verranno evidenziate le inedite prospettive delle investigazioni informatiche.

20/03/2014 – Talk by Paul-Andre Mellies

Title:  The free dialogue category with sums: an algebraic approach to game semantics
Time: 13:00
Location: Meeting room
Type: Research Result
Speaker: Paul-Andre Mellies (CNRS, Paris Diderot))
In this talk, I will give a direct combinatorial description of the free dialogue category with sums
as a category with dialogue games as objects and with innocent strategies as morphisms.
I will then explain how to apply this result in order to construct a functor from the category
of dialogue games and innocent strategies to the category of coherence spaces and cliques.
One obtains in this way another proof of the positionality theorem of innocent strategies,
which establishes moreover that the halting positions of an innocent strategy form a clique.

19/03/2014 – Talk by Andriana E. Gkaniatsou

Title:  Towards the automated analysis of low-level cryptographic protocols
Time: 13:00
Location: Meeting room
Type: Research Result
Speaker: Andriana E. Gkaniatsou (U. of Edinburgh)
In this talk we discuss the problem of the automated analysis of reversed engineered low-level cryptographic protocols. Such analysis is difficult, as most of such protocol implementations are proprietary and confidential.
Our proposal is to consider the analysis as an inference problem and use knowledge repair techniques to fix possible mismatches. We discuss our thoughts towards this problem, and some working examples based on real card implementations.