Skip to main content

RAZONAMIENTO FORMAL PARA TECNOLOGIAS FACILITADORAS Y EMERGENTES

RTI2018-094403-B-C31

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos I+D+i Retos de Investigación
Call year 2018
State Plan 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSIDAD COMPLUTENSE DE MADRID

Resultados relacionados

Resultados totales (Incluyendo duplicados): 1
Encontrada(s) 1 página(s)

Docta Complutense
Publication Contribución de congreso (ConferenceOutput)

Conditional dynamic partial order reduction and optimality results

  • Isabel Márquez, Miguel
Testing concurrent systems requires exploring all possible nondeterministic interleavings that the concurrent execution may have, as any of the interleavings may reveal an erroneous behaviour of the system. This introduces a combinatorial explosion on the number of states that must be considered, which leads often to a computationally intractable problem. In the present PhD thesis, this challenge will be addressed through the development of new Partial Order Reduction techniques (POR). The cornerstone of POR theory is the notion of independence, that is used to decided whether each pair of concurrent events p and t are in a race and thus both executions p · t and t · p must be explored. A fundamental goal of this thesis is to introduce notions of conditional independence –which ensure the commutativity of the considered events p and t under certain conditions that can be evaluated in the explored state– with a DPOR algorithm in order to alleviate the combinatorial explosion problem. The new techniques that we propose in the thesis have been implemented within the SYCO tool. We have carried out accompanying experimental evaluations to prove the effectiveness and applicability of the proposed techniques. Finally, we have successfully verified a range of properties for several case studies of Software-Defined Networks to illustrate the potential of the approach, scaling to larger networks than related techniques.