  The enormous amount of data produced by mobile and IoT devices has motivated
the development of federated learning (FL), a framework allowing such devices
(or clients) to collaboratively train machine learning models without sharing
their local data. FL algorithms (like FedAvg) iteratively aggregate model
updates computed by clients on their own datasets. Clients may exhibit
different levels of participation, often correlated over time and with other
clients. This paper presents the first convergence analysis for a FedAvg-like
FL algorithm under heterogeneous and correlated client availability. Our
analysis highlights how correlation adversely affects the algorithm's
convergence rate and how the aggregation strategy can alleviate this effect at
the cost of steering training toward a biased model. Guided by the theoretical
analysis, we propose CA-Fed, a new FL algorithm that tries to balance the
conflicting goals of maximizing convergence speed and minimizing model bias. To
this purpose, CA-Fed dynamically adapts the weight given to each client and may
ignore clients with low availability and large correlation. Our experimental
results show that CA-Fed achieves higher time-average accuracy and a lower
standard deviation than state-of-the-art AdaFed and F3AST, both on synthetic
and real datasets.
