Delivery Delay and Mobile Faults
Dimitris Sakavalas, Lewis Tseng · 2018
In this work we address the problem of reaching approximate consensus in a complete network ofnnodes, where message deliveries can be delayed by at mostdtime-steps. We consider a mobile adversary, which corrupts at mostfnodes in any step, modeled as asynchronousround. We explicitly study howdaffects 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 ifn> 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 tightTimeStampsalgorithm, which utilizes timestamps to optimally bound the number of faulty messages.