  How well do existing federated learning algorithms learn from client devices
that return model updates with a significant time delay? Is it even possible to
learn effectively from clients that report back minutes, hours, or days after
being scheduled? We answer these questions by developing Monte Carlo
simulations of client latency that are guided by real-world applications. We
study synchronous optimization algorithms like FedAvg and FedAdam as well as
the asynchronous FedBuff algorithm, and observe that all these existing
approaches struggle to learn from severely delayed clients. To improve upon
this situation, we experiment with modifications, including distillation
regularization and exponential moving averages of model weights. Finally, we
introduce two new algorithms, FARe-DUST and FeAST-on-MSG, based on distillation
and averaging, respectively. Experiments with the EMNIST, CIFAR-100, and
StackOverflow benchmark federated learning tasks demonstrate that our new
algorithms outperform existing ones in terms of accuracy for straggler clients,
while also providing better trade-offs between training time and total
accuracy.
