Computer Science

Reliable broadcast in networks with trusted nodes

Document Type

Conference Paper

Abstract

Broadcast is one of the fundamental primitives to enable large-scale networks such as sensor networks and IoT. There is a rich study on achieving reliable broadcast under various kind of failures. In this paper, we use the notion of trust to improve the performance of reliable broadcast. We focus on Certified Propagation Algorithm (CPA), one of the simple algorithms that does not rely on a cryptographic infrastructure and has a proven guarantee on resilience (number of node failures tolerated). Specifically, the paper has two main contributions: (i) A new algorithm Trust-CPA which integrates CPA with trusted nodes has been proposed and shown to increase the resilience from the original CPA, and (ii) A natural optimization problem related to Trust-CPA (i.e., finding the location to place trusted nodes to reduce the broadcast latency) has been proposed as well. We first show that it is NP-hard to find an exact answer and even NP-hard to find a good approximation. A greedy heuristic algorithm has been used and its efficacy has been examined using simulation. We show that our algorithm performs relatively well in geometric random graphs, an appropriate model for large- scale wireless sensor networks.

Publication Title

Proceedings - IEEE Global Communications Conference, GLOBECOM

Publication Date

2019

ISSN

2334-0983

DOI

10.1109/GLOBECOM38437.2019.9013797

Keywords

Certified Propagation Algorithm, hardness result, reliable broadcast, tight condition, trust

APA Citation

Tseng, L., Wu, Y., Pan, H., Aloqaily, M., & Boukerche, A. (2019, December). Reliable broadcast in networks with trusted nodes. In 2019 IEEE global communications conference (GLOBECOM) (pp. 1-6). IEEE.

Link to Full Text

Share

COinS