"Delivery delay and mobile faults" by Dimitris Sakavalas and Lewis Tseng
 

Computer Science

Delivery delay and mobile faults

Dimitris Sakavalas, Boston College
Lewis Tseng, Boston College

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.