VCube: A Provably Scalable Distributed Diagnosis Algorithm

被引：13

作者：

Duarte, Elias P., Jr. ^{[1
]}

Bona, Luis C. E. ^{[1
]}

Ruoso, Vinicius K. ^{[1
]}

机构：

[1] Univ Fed Parana, Dept Informat, BR-81531990 Curitiba, Parana, Brazil

来源：

2014 5th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA) | 2014年

关键词：

SYSTEM-LEVEL DIAGNOSIS; FAULT-DIAGNOSIS; HYPERCUBE;

D O I：

10.1109/ScalA.2014.14

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

VCube is a distributed diagnosis algorithm for virtually interconnecting network nodes. VCube presents several logarithmic properties, and is a logical hypercube when all nodes are fault-free. VCube is dynamic in the sense that nodes can leave and rejoin the system as they become faulty and are repaired. The topology re-organizes itself and keeps its logarithmic properties even if an arbitrary number of nodes are faulty. Fault diagnosis is based on tests. All fault-free nodes of a system with N nodes detect an event with a latency of at most log(2)(2)N testing rounds. In this work we specify the algorithm and show that the worst number of tests executed is Nlog(2)N per log(2)N rounds. Besides the correctness proofs, experimental results are also given.

引用

页码：17 / 22

页数：6

共 28 条

[1] IMPLEMENTATION OF ONLINE DISTRIBUTED SYSTEM-LEVEL DIAGNOSIS THEORY [J].

BIANCHINI, RP ;

BUSKENS, RW .

IEEE TRANSACTIONS ON COMPUTERS, 1992, 41 (05) :616-626

[2] HyperBone: A scalable overlay network based on a virtual hypercube [J].

Bona, Luis C. E. ;

Duarte, Elias P., Jr. .

2008 IEEE NETWORK OPERATIONS AND MANAGEMENT SYMPOSIUM, VOLS 1 AND 2, 2008, :1025-+

[3]

Chandrapal P, 2005, LECT NOTES COMPUT SC, V3816, P192, DOI 10.1007/11604655_23

[4]

Dahbura A.T., 1989, CONCURRENT COMPUTATI

[5] A Survey of Comparison-Based System-Level Diagnosis [J].

Duarte, Elias P., Jr. ;

Ziwich, Roverli P. ;

Albini, Luiz C. P. .

ACM COMPUTING SURVEYS, 2011, 43 (03)

[6] A dependable SNMP-based tool for distributed network management [J].

Duarte, EP ;

De Bona, LCE .

INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS AND NETWORKS, PROCEEDINGS, 2002, :279-284

[7] A hierarchical adaptive distributed system-level diagnosis algorithm [J].

Duarte, EP ;

Nanya, T .

IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (01) :34-45

[8]

Duarte Jr E.P., 2009, 6 IEEE LAT AM NETW O, P1

[9]

Duarte Jr E.P., 2000, IEEE INT S CLUST COM, P299

[10] Comparison-Based System-Level Fault Diagnosis: A Neural Network Approach [J].

Elhadef, Mourad ;

Nayak, Amiya .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2012, 23 (06) :1047-1059

← 1 2 3 →