Evolutionary methods for self-organizing cooperation in peer-to-peer networks

The Peer-to-Peer network paradigm is drawing the attention of both final users and researchers for its features. P2P networks shift from the classic client-server approach to a high level of decentralization where there is no central control and all the nodes should be able not only to require services, but to provide them to other peers as well. While on one hand such high level of decentralization might lead to interesting properties like scalability and fault tolerance, on the other hand it implies many new problems to deal with. A key feature of many P2P systems is openness, meaning that everybody is potentially able to join a network with no need for subscription or payment systems. The combination of openness and lack of central control makes it feasible for a user to free-ride, that is to increase its own benefit by using services without allocating resources to satisfy other peers’ requests. One of the main goals when designing a P2P system is therefore to achieve cooperation between users. Given the nature of P2P systems based on simple local interactions of many peers having partial knowledge of the whole system, an interesting way to achieve desired properties on a system scale might consist in obtaining them as emergent properties of the many interactions occurring at local node level. Two methods are typically used to face the problem of cooperation in P2P networks: 1) engineering emergent properties when designing the protocol; 2) study the system as a game and apply Game Theory techniques, especially to find Nash Equilibria in the game and to reach them making the system stable against possible deviant behaviors. In this work we present an evolutionary framework to enforce cooperative behaviour in P2P networks that is alternative to both the methods mentioned above. Our approach is based on an evolutionary algorithm inspired by computational sociology and evolutionary game theory, consisting in having each peer periodically trying to copy another peer which is performing better. The proposed algorithms, called SLAC and SLACER, draw inspiration from tag systems originated in computational sociology, the main idea behind the algorithm consists in having low performance nodes copying high performance ones. The algorithm is run locally by every node and leads to an evolution of the network both from the topology and from the nodes’ strategy point of view. Initial tests with a simple Prisoners’ Dilemma application show how SLAC is able to bring the network to a state of high cooperation independently from the initial network conditions. Interesting results are obtained when studying the effect of cheating nodes on SLAC algorithm. In fact in some cases selfish nodes rationally exploiting the system for their own benefit can actually improve system performance from the cooperation formation point of view. The final step is to apply our results to more realistic scenarios. We put our efforts in studying and improving the BitTorrent protocol. BitTorrent was chosen not only for its popularity but because it has many points in common with SLAC and SLACER algorithms, ranging from the game theoretical inspiration (tit-for-tat-like mechanism) to the swarms topology. We discovered fairness, meant as ratio between uploaded and downloaded data, to be a weakness of the original BitTorrent protocol and we drew inspiration from the knowledge of cooperation formation and maintenance mechanism derived from the development and analysis of SLAC and SLACER, to improve fairness and tackle freeriding and cheating in BitTorrent. We produced an extension of BitTorrent called BitFair that has been evaluated through simulation and has shown the abilities of enforcing fairness and tackling free-riding and cheating nodes.

Parapoxvirus: basi genomiche della patogenesi

Parapoxvirus (PPV) are member of a genus in the family poxviridae which currently encompasses four species: the prototype orf virus (OV), bovine papular stomatitis virus (BPSV), pseudocowpox virus (PCPV) and parapoxvirus of New Zealand red deer (PVNZ). PPVs cause widespread, but localized diseases of small and large ruminants and they can also be transmitted to man. Knowledge of the molecular biology of PPV is still limited as compared to orthopoxviruses, especially vaccinia virus (VACV). The PPV genome displays a high G+C content and relatively small size for poxvirus. Coventional electron microscopy displays PPV virions with ovoid shape and slightly smaller in size than the brickshaped orthopoxviruses. The most striking feature, which readily enables identification of PPV, is a tubule-like structure that surrounds the particle in a spiral fashion. PPV genome organization and content is very similar to that of other poxviruses, the central region contain 88 genes which are present in all poxviruse, in contrast the terminal regions are variable and contain a set of genes unique to the genus PPV. Genes in the near-terminal regions of the genome are frequently not essential for growth in cultured cells encoding factors with important roles in virushost interactions including modulating host immune responses and determining host range. Recently it was suggested that the open reading frames (ORFs) 109 and 110 of the OV genome have a major role in determining species specificity during natural infection in sheep and goats. This hypothesis is based on the analysis of a few number of sequences of different sheep and goats viral isolates. PPV replicate into the cytoplasm of infected cells and produce three structurally different infectious particles: the intracellular mature virions (IMV), intracellular enveloped virions (IEV) and the extracellular enveloped virions (EEV). The vaccinia A33R and A34R hotologue proteins encoded by the ORFS 109 and 110 are expressed in the envelope of the IEV and EEV. The F1L immunodominant protein of orf virus is the major component of the surface tubule structure of the IMV and can post-translationaly insert into membranes via Cterminal, hydrofobic anchor sequence like its orthologue VACV H3L protein. Moreover the F1L protein binds to glycosaminoglycans on the cell surface and has an important role in IMV adsorption to mammalian cells. In this study we investigated the morphogenesis of the PPV through the construction of a mutant virus deleted of the F1L protein. A study of the deleted virus life cycle was conducted in different type of cells and its morphology was observed with electron microscopy. It was demonstared that F1L protein have important role in morphogenesis and infectivity. Moreover it is essential to determine the spiral fashion of the tubule like structure of the virion surface. Some pathogenetic aspects of the PPV infection were studied, in particular the protein implicated in the host range were analysed in detail. An experimental infection with OV and PCPV was conducted in goats and sheep. After infection, the severity of the lesions were comparable in both the animal species. The OV did not result in severe disease neither in sheep nor in goats, suggesting that host factors, rather than virus strain characteristics, may play an important role in the pathogenesis of the Parapoxvirus infections. The PCPV failed to produce any lesion in both sheep and goats, ruling out the possibility of any recombination between PCPV and OV during natural infection in these animal species. The phylogenetic analysis of the ORFs 109 and 110 from several goats and sheep viral isolates showed a clustering based on the antigenic content of the protein that was independent from species and geographic origin.

A novel map-matching procedure for low-sampling GPS data with applications to traffic flow analysis

An extensive sample (2%) of private vehicles in Italy are equipped with a GPS device that periodically measures their position and dynamical state for insurance purposes. Having access to this type of data allows to develop theoretical and practical applications of great interest: the real-time reconstruction of traffic state in a certain region, the development of accurate models of vehicle dynamics, the study of the cognitive dynamics of drivers. In order for these applications to be possible, we first need to develop the ability to reconstruct the paths taken by vehicles on the road network from the raw GPS data. In fact, these data are affected by positioning errors and they are often very distanced from each other (~2 Km). For these reasons, the task of path identification is not straightforward. This thesis describes the approach we followed to reliably identify vehicle paths from this kind of low-sampling data. The problem of matching data with roads is solved with a bayesian approach of maximum likelihood. While the identification of the path taken between two consecutive GPS measures is performed with a specifically developed optimal routing algorithm, based on A* algorithm. The procedure was applied on an off-line urban data sample and proved to be robust and accurate. Future developments will extend the procedure to real-time execution and nation-wide coverage.

Heuristic algorithms for the Capacitated Location-Routing Problem and the Multi-Depot Vehicle Routing Problem

The Capacitated Location-Routing Problem (CLRP) is a NP-hard problem since it generalizes two well known NP-hard problems: the Capacitated Facility Location Problem (CFLP) and the Capacitated Vehicle Routing Problem (CVRP). The Multi-Depot Vehicle Routing Problem (MDVRP) is known to be a NP-hard since it is a generalization of the well known Vehicle Routing Problem (VRP), arising with one depot. This thesis addresses heuristics algorithms based on the well-know granular search idea introduced by Toth and Vigo (2003) to solve the CLRP and the MDVRP. Extensive computational experiments on benchmark instances for both problems have been performed to determine the effectiveness of the proposed algorithms. This work is organized as follows: Chapter 1 describes a detailed overview and a methodological review of the literature for the the Capacitated Location-Routing Problem (CLRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). Chapter 2 describes a two-phase hybrid heuristic algorithm to solve the CLRP. Chapter 3 shows a computational comparison of heuristic algorithms for the CLRP. Chapter 4 presents a hybrid granular tabu search approach for solving the MDVRP.

Reconstruction from image correspondences

A single picture provides a largely incomplete representation of the scene one is looking at. Usually it reproduces only a limited spatial portion of the scene according to the standpoint and the viewing angle, besides it contains only instantaneous information. Thus very little can be understood on the geometrical structure of the scene, the position and orientation of the observer with respect to it remaining also hard to guess. When multiple views, taken from different positions in space and time, observe the same scene, then a much deeper knowledge is potentially achievable. Understanding inter-views relations enables construction of a collective representation by fusing the information contained in every single image. Visual reconstruction methods confront with the formidable, and still unanswered, challenge of delivering a comprehensive representation of structure, motion and appearance of a scene from visual information. Multi-view visual reconstruction deals with the inference of relations among multiple views and the exploitation of revealed connections to attain the best possible representation. This thesis investigates novel methods and applications in the field of visual reconstruction from multiple views. Three main threads of research have been pursued: dense geometric reconstruction, camera pose reconstruction, sparse geometric reconstruction of deformable surfaces. Dense geometric reconstruction aims at delivering the appearance of a scene at every single point. The construction of a large panoramic image from a set of traditional pictures has been extensively studied in the context of image mosaicing techniques. An original algorithm for sequential registration suitable for real-time applications has been conceived. The integration of the algorithm into a visual surveillance system has lead to robust and efficient motion detection with Pan-Tilt-Zoom cameras. Moreover, an evaluation methodology for quantitatively assessing and comparing image mosaicing algorithms has been devised and made available to the community. Camera pose reconstruction deals with the recovery of the camera trajectory across an image sequence. A novel mosaic-based pose reconstruction algorithm has been conceived that exploit image-mosaics and traditional pose estimation algorithms to deliver more accurate estimates. An innovative markerless vision-based human-machine interface has also been proposed, so as to allow a user to interact with a gaming applications by moving a hand held consumer grade camera in unstructured environments. Finally, sparse geometric reconstruction refers to the computation of the coarse geometry of an object at few preset points. In this thesis, an innovative shape reconstruction algorithm for deformable objects has been designed. A cooperation with the Solar Impulse project allowed to deploy the algorithm in a very challenging real-world scenario, i.e. the accurate measurements of airplane wings deformations.

Evidence for a new boson in the search for the Standard Model Higgs particle decaying to four leptons at CMS

One of the main targets of the CMS experiment is to search for the Standard Model Higgs boson. The 4-lepton channel (from the Higgs decay h->ZZ->4l, l = e,mu) is one of the most promising. The analysis is based on the identification of two opposite-sign, same-flavor lepton pairs: leptons are required to be isolated and to come from the same primary vertex. The Higgs would be statistically revealed by the presence of a resonance peak in the 4-lepton invariant mass distribution. The 4-lepton analysis at CMS is presented, spanning on its most important aspects: lepton identification, variables of isolation, impact parameter, kinematics, event selection, background control and statistical analysis of results. The search leads to an evidence for a signal presence with a statistical significance of more than four standard deviations. The excess of data, with respect to the background-only predictions, indicates the presence of a new boson, with a mass of about 126 GeV/c2 , decaying to two Z bosons, whose characteristics are compatible with the SM Higgs ones.

Nonlinear Observers for Sensorless Control of Permanent Magnet Synchronous Motors

In this thesis, the industrial application of control a Permanent Magnet Synchronous Motor in a sensorless configuration has been faced, and in particular the task of estimating the unknown “parameters” necessary for the application of standard motor control algorithms. In literature several techniques have been proposed to cope with this task, among them the technique based on model-based nonlinear observer has been followed. The hypothesis of neglecting the mechanical dynamics from the motor model has been applied due to practical and physical considerations, therefore only the electromagnetic dynamics has been used for the observers design. First observer proposed is based on stator currents and Stator Flux dynamics described in a generic rotating reference frame. Stator flux dynamics are known apart their initial conditions which are estimated, with speed that is also unknown, through the use of the Adaptive Theory. The second observer proposed is based on stator currents and Rotor Flux dynamics described in a self-aligning reference frame. Rotor flux dynamics are described in the stationary reference frame exploiting polar coordinates instead of classical Cartesian coordinates, by means the estimation of amplitude and speed of the rotor flux. The stability proof is derived in a Singular Perturbation Framework, which allows for the use the current estimation errors as a measure of rotor flux estimation errors. The stability properties has been derived using a specific theory for systems with time scale separation, which guarantees a semi-global practical stability. For the two observer ideal simulations and real simulations have been performed to prove the effectiveness of the observers proposed, real simulations on which the effects of the Inverter nonlinearities have been introduced, showing the already known problems of the model-based observers for low speed applications.