An Ordered Binary Decision Diagram (OBDD) is a data structure that is used in an increasing number of fields of Computer Science (e.g., logic synthe- sis, program verification, data mining, bioinformatics, and data protection) for representing and manipulating discrete structures and Boolean functions. The purpose of this paper is to study the error resilience of OBDDs and to design a resilient version of this data structure, i.e., a self-repairing OBDD. In particular, we describe some strategies that make reduced ordered OBDDs resilient to errors in the indices, that are associated to the input variables, or in the pointers (i.e., OBDD edges) of the nodes. These strategies exploit the inherent redundancy of the data structure, as well as the redundancy introduced by its efficient implementations. The solutions we propose allow the exact restoring of the original OBDD and are suitable to be applied to classical software packages for the manipulation of OBDDs currently in use. Another result of the paper is the definition of a new canonical OBDD model, called Index-Resilient Reduced OBDD, which guarantees that a node with a faulty index has a reconstruction cost O(r), where r is the number of nodes with corrupted index. Experimental results on a classical benchmark suite validate the proposed approaches.

On the error resilience of ordered binary decision diagrams

BERNASCONI, ANNA;
2015-01-01

Abstract

An Ordered Binary Decision Diagram (OBDD) is a data structure that is used in an increasing number of fields of Computer Science (e.g., logic synthe- sis, program verification, data mining, bioinformatics, and data protection) for representing and manipulating discrete structures and Boolean functions. The purpose of this paper is to study the error resilience of OBDDs and to design a resilient version of this data structure, i.e., a self-repairing OBDD. In particular, we describe some strategies that make reduced ordered OBDDs resilient to errors in the indices, that are associated to the input variables, or in the pointers (i.e., OBDD edges) of the nodes. These strategies exploit the inherent redundancy of the data structure, as well as the redundancy introduced by its efficient implementations. The solutions we propose allow the exact restoring of the original OBDD and are suitable to be applied to classical software packages for the manipulation of OBDDs currently in use. Another result of the paper is the definition of a new canonical OBDD model, called Index-Resilient Reduced OBDD, which guarantees that a node with a faulty index has a reconstruction cost O(r), where r is the number of nodes with corrupted index. Experimental results on a classical benchmark suite validate the proposed approaches.
2015
Bernasconi, Anna; Ciriani, Valentina; Lago, Lorenzo
File in questo prodotto:
File Dimensione Formato  
BDDResilient.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 511.6 kB
Formato Adobe PDF
511.6 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/750039
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact