Reliable Broadcast in Dynamic Networks with Locally Bounded Byzantine Failures

被引：8

作者：

Bonomi, Silvia ^{[1
]}

Farina, Giovanni ^{[1
,2
]}

Tixeuil, Sebastien ^{[2
]}

机构：

[1] Sapienza Univ Roma, Dipartimento Ingn Informat Automat & Gest Antonio, Rome, Italy

[2] Sorbonne Univ, Lab Informat Paris 6, LIP6, CNRS, F-75005 Paris, France

来源：

STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2018 | 2018年 / 11201卷

关键词：

Byzantine reliable broadcast; Locally bounded failures; Dynamic networks; ALGORITHM;

D O I：

10.1007/978-3-030-03232-6_12

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Ensuring reliable communication despite possibly malicious participants is a primary objective in any distributed system or network. In this paper, we investigate the possibility of reliable broadcast in a dynamic network whose topology may evolve while the broadcast is in progress. In particular, we adapt the Certified Propagation Algorithm (CPA) to make it work on dynamic networks and we present conditions (on the underlying dynamic graph) to enable safety and liveness properties of the reliable broadcast. We furthermore explore the complexity of assessing these conditions for various classes of dynamic networks.

引用

页码：170 / 185

页数：16

共 18 条

[1]

Augustine J., 2013, PODC, DOI DOI 10.1145/2484239.2484275

[2] Reliable Broadcast in Radio Networks with Locally Bounded Failures [J].

Bhandari, Vartika ;

Vaidya, Nitin H. .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2010, 21 (06) :801-811

[3]

Casteigts A, 2012, INT J PARALLEL EMERG, V27, P387, DOI [10.1080/17445760.2012.668546, 10.1007/978-3-642-22450-8_27]

[4] Practical byzantine fault tolerance and proactive recovery [J].

Castro, M ;

Liskov, B .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 2002, 20 (04) :398-461

[5]

Dolev D., 1981, 22nd Annual Symposium on Foundations of Computer Science, P159, DOI 10.1109/SFCS.1981.53

[6] Efficient Byzantine broadcast in wireless ad-hoc networks [J].

Drabkin, V ;

Friedman, R ;

Segal, M .

2005 INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS AND NETWORKS, PROCEEDINGS, 2005, :160-169

[7] A Connectivity Model for Agreement in Dynamic Systems [J].

Gomez-Calzado, Carlos ;

Casteigts, Arnaud ;

Lafuente, Alberto ;

Larrea, Mikel .

EURO-PAR 2015: PARALLEL PROCESSING, 2015, 9233 :333-345

[8]

Guerraoui Rachid, 2013, P 2013 ACM S PRINC D, P176

[9] A new parameter for a broadcast algorithm with locally bounded Byzantine faults [J].

Ichimura, Akira ;

Shigeno, Maiko .

INFORMATION PROCESSING LETTERS, 2010, 110 (12-13) :514-517

[10]

Koo C.-Y., 2004, P ACM S PRINC DISTR, P275, DOI [10.1145/1011767.1011807, DOI 10.1145/1011767.1011807]

← 1 2 →