Online Failure Diagnosis in Interdependent Networks

Davood Shiri () and Vahid Akbari ()
Additional contact information
Davood Shiri: Koç University
Vahid Akbari: University of Nottingham, Jubilee Campus

SN Operations Research Forum, 2021, vol. 2, issue 1, 1-14

Abstract: Abstract In interdependent networks, nodes are connected to each other with respect to their failure dependency relations. As a result of this dependency, a failure in one of the nodes of one of the networks within a system of several interdependent networks can cause the failure of the entire system. Diagnosing the initial source of the failure in a collapsed system of interdependent networks is an important problem to be addressed. We study an online failure diagnosis problem defined on a collapsed system of interdependent networks where the source of the failure is at an unknown node (v). In this problem, each node of the system has a positive inspection cost and the source of the failure is diagnosed when v is inspected. The objective is to provide an online algorithm which considers dependency relations between nodes and diagnoses v with minimum total inspection cost. We address this problem from worst-case competitive analysis perspective for the first time. In this approach, solutions which are provided under incomplete information are compared with the best solution that is provided in presence of complete information using the competitive ratio (CR) notion. We give a lower bound of the CR for deterministic online algorithms and prove its tightness by providing an optimal deterministic online algorithm. Furthermore, we provide a lower bound on the expected CR of randomized online algorithms and prove its tightness by presenting an optimal randomized online algorithm. We prove that randomized algorithms are able to obtain better CR compared to deterministic algorithms in the expected sense for this online problem.

Keywords: Interdependent networks; Failure diagnosis; Online algorithms; Competitive ratio (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-021-00055-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:2:y:2021:i:1:d:10.1007_s43069-021-00055-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-021-00055-2

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().