Computer Science

Delivery delay and mobile faults

Document Type

Conference Paper

Abstract

In this work we address the problem of reaching approximate consensus in a complete network of n nodes, where message deliveries can be delayed by at most d time-steps. We consider a mobile adversary, which corrupts at most f nodes in any step, modeled as a synchronous round. We explicitly study how d affects the feasibility of the problem. More precisely, we propose a framework to analyze mobile fault-tolerance in the presence of message delays. We prove that approximate consensus is feasible if and only if n > 4df. We assume no knowledge of time (round index) by the nodes; instead, in our model, whenever a message is sent, it is timestamped by the communication channel. We propose the tight TimeStamps algorithm, which utilizes timestamps to optimally bound the number of faulty messages.

Publication Title

NCA 2018 - 2018 IEEE 17th International Symposium on Network Computing and Applications

Publication Date

2018

ISBN

9781538676592

DOI

10.1109/NCA.2018.8548345

Keywords

approximate consensus, Byzantine faults, fault-tolerance, message delay, mobile adversary

APA Citation

Sakavalas, D., & Tseng, L. (2018, November). Delivery delay and mobile faults. In 2018 IEEE 17th International Symposium on Network Computing and Applications (NCA) (pp. 1-8). IEEE.

Link to Full Text

Share

COinS