\begin{table}[t]
\centering
\begin{adjustbox}{width=8.5cm,  center}
\begin{tabular}{|c|c|c|c|c|c|c|} 
\hline
\multirow{2}{*}{\textbf{ Dataset}} & \multirow{2}{*}{\textbf{ Strategy}} & \multicolumn{5}{c|}{\textbf{Experiment Time (mins)}}                               \\ 
\cline{3-7}
                                   &                                     & \textbf{Standard} & \textbf{10\%} & \textbf{30\%} & \textbf{50\%} & \textbf{70\%}  \\ 
\hline
\multirow{3}{*}{MNIST}             & FedAvg                              & 39.7              & 40.2          & 40.0            & \textbf{40.0}            & \textbf{40.0}             \\ 
\cline{2-7}
                                   & FedProx                             & 40.0                & 40.3          & 40.0          & \textbf{40.0}            & \textbf{40.0}             \\ 
\cline{2-7}
                                   & FedLesScan                          & \textbf{23.7}              & \textbf{28.6}          & \textbf{27.3}          & \textbf{40.0}            & \textbf{40.0}             \\ 
\hline
\multirow{3}{*}{FEMNIST}           & FedAvg                              & 75.5              & 86.7          & 86.9          & \textbf{86.7}          & \textbf{86.7}          \\ 
\cline{2-7}
                                   & FedProx                             & 112.4               & 88.2            & 88.1            & 87.8            & 87.4             \\ 
\cline{2-7}
                                   & FedLesScan                          & \textbf{70.9}              & \textbf{75.6}          & \textbf{82.8}          & 86.8          & \textbf{86.7}           \\ 
\hline
\multirow{3}{*}{Shakespeare}       & FedAvg                              & 217.0           & 217.0        & 217.0         & 216.9         & 216.8          \\ 
\cline{2-7}
                                   & FedProx                             & 217.0             & 217.0         & 217.0        & 217.0        & 216.7          \\ 
\cline{2-7}
                                   & FedLesScan                          & \textbf{185.5}             &\textbf{ 215.5  }         & \textbf{205.2}           & \textbf{216.8}           & \textbf{216.6}            \\ 
\hline
\multirow{3}{*}{Google Speech}    & FedAvg                              & 20.3                & 40.1            & 40.1            & 40.0           & \textbf{40.0}             \\ 
\cline{2-7}
                                   & FedProx                             & 21.5              & 40.0           & 40.0           & 40.0           & \textbf{40.0}             \\ 
\cline{2-7}
                                   & FedLesScan                          & \textbf{15.1}                & \textbf{31.1}            & \textbf{28.8}            & \textbf{33.3}            & \textbf{40.0}             \\
\hline
\end{tabular}
\end{adjustbox}
\caption{Comparing total time for the three strategies across different scenarios (\S\ref{sec:scenarios}) and datasets (\S\ref{sec:datasets}). The highlighted values represent the minimum training time for each experiment.}
\label{tab:total-time}
\vspace{-5mm}
\end{table}
The different proposed approaches for straggler mitigation in FL can be divided into three categories, i.e., \textit{synchronous}~\cite{fedprox}, \textit{asynchronous}~\cite{asofed,fed_async}, and \textit{semi-asynchronous}~\cite{fedAt, safa, csafl}. One of the most popular synchronous approaches is \texttt{FedProx}~\cite{fedprox}, which is based on \texttt{FedAvg}~\cite{mcmahan2017communication} with two minor differences. First, a custom loss function for client-side training that limits the varying effects of local model updates. Second, toleration for partial work, i.e., clients can perform a variable amount of work to accommodate constraints in terms of hardware and network. However, incorporating partial work requires tailoring the number of local epochs for each client individually, which might be infeasible for a significantly large number of clients. Moreover, in contrast to \texttt{FedLesScan} it relies on random selection of clients which makes it sensitive to stragglers. In~\cite{fed_async}, Xie et al. propose an asynchronous federated optimization algorithm called \texttt{FedAsync} that relies on a parameter server architecture to invoke and synchronize FL clients. The server consists of two parallel threads, i.e., a \textit{scheduler} and an \textit{updater}. The scheduler thread periodically triggers the FL clients to perform training using the latest global model, while the updater thread receives the client model updates and directly aggregates them to the global
model. However, in the context of serverless, this approach has significantly higher resource and communication costs (\S\ref{sec:faas}, \S\ref{sec:servfl}) since it would require a function invocation to perform aggregation with the global model after each individual client update.

\subsection{Gathering Behavioral Data}
\label{sec:behavedata}
Our client selection strategy (\S\ref{sec:ClientSelection}) depends on the data collected from the clients' behavior in previous training rounds. Towards this, for each client we collect three attributes, i.e., \textit{training time}, \textit{missed rounds}, and \textit{cooldown}. \textit{Training time} is the time taken by the client to complete local model training. \textit{Missed rounds} is a list that contains the round numbers of the rounds missed by a client. We use this to calculate a client's penalty as described in \S\ref{sec:ClientSelection}. \textit{Cooldown} represents the number of rounds a client has to stay in the last tier and cannot participate in clustering (\S\ref{sec:tiers}). We evaluate the cooldown period from the client’s last missed round using Equation~\ref{eq: cooldown}. For instance, if a client missed round $2$, the cooldown is set to $1$. Moreover, if the same client missed round $4$, the cooldown is multiplied by two. As a result, the clients with \textit{cooldown} greater than zero are characterized as \textit{stragglers}. Towards this, using \textit{cooldown} can reduce the impact of temporarily slow or unavailable clients by lowering their priority for a certain number of rounds (\S\ref{sec:tiers}, \S\ref{sec:ClientSelection}).

\textbf{Straggler (\%) Scenario}. In this, we simulate varying percentages of stragglers in the FL system.  Although there might be different reasons for FaaS client failures, such as memory limit, function timeout, or communication issues, these failures can only have one of two effects on the clients. Clients can either push their updates after the training round is finished (slow updates) or can completely crash (not push their updates). To simulate slow updates, we limit the training round time to only fit clients with no issues or delays. Meaning, that clients which experience cold starts, bandwidth limitations, or communication delays do not finish the round in time; therefore, pushing their updates later. On the other hand, to simulate failures, we randomly select a specific ratio of clients to fail their training at the beginning of each experiment. We perform four different experiments for each dataset with 10\%, 30\%, 50\%, and 70\% stragglers in the system. Note that, in all our experiments, stragglers are different from \textit{malicious clients} found in some FL settings~\cite{li2020learning, zhang2022fldetector}. While malicious clients can act as stragglers to deliberately slow training or hinder model performance, they can perform more powerful attacks such as data or model poisoning~\cite{fl_challenges,fl_data_poisoning} to skew the model's performance. In our work, we focus on the problem of stragglers and their behavior rather than the clients' intentions. The number of training rounds for the different datasets and experiment scenarios is shown in Table~\ref{tab:experiment-params}.

The obtained accuracy and EUR values across all our experiments is summarized in Table~\ref{tab:acc-all}. For the \textit{standard scenarios} (\S\ref{sec:scenarios}), we obtained better accuracy and round utlization for our strategy as compared to \texttt{FedAvg} and \texttt{FedProx} across all datasets except Shakespeare. This is because with the Shakespeare dataset, some of the clients contribute to the model accuracy more than others, especially clients with longer training times. Moreover, due to budget constraints and significantly high training costs, we train for a slightly less number of rounds, i.e., 25 for Shakespeare. However, we argue that in a more realistic scenario with more number of rounds, the difference in accuracy will decrease. This is because our strategy utilizes clients more efficiently, i.e., higher EUR. As a result, with more rounds the number of invocations per client will increase and more clients will contribute to the global model, leading to a higher accuracy. Similarly, for the \textit{straggler (\%) scenarios}, we obtained better results for accuracy with our strategy as compared to the other two for the MNIST, FEMNIST, and the Google Speech datasets. On the Shakespeare dataset, our strategy outperformed \texttt{FedAvg} and \texttt{FedProx} in scenarios with 30\%, 50\%, and 70\% stragglers. In terms of EUR, our strategy constantly outperforms the other two strategies across all scenarios and datasets since they use random selection for selecting clients for an FL training round.

For most \textit{standard scenarios} (Table~\ref{tab:acc-all}), \texttt{FedLesScan} obtained better accuracy as compared to the other two strategies due to the better distribution of client invocations. This is because our strategy prioritizes clients with the least number of invocations in a selected client cluster (\S\ref{sec:ClientSelection}) leading to more balanced contributions among the participating clients. On the other hand, with \textit{straggler (\%) scenario}, our strategy reached better accuracies by relying more on robust and reliable clients. Furthermore, the utilization of a staleness-aware aggregation scheme (\S\ref{sec:stalelessaware}) avoids wasting valuable contributions, which in turn increases accuracy.

To offer detailed insights, we present results for the Google Speech dataset~\cite{speech} wrt the metrics accuracy and EUR, across the FL training session as shown in Figures \ref{fig:acc-speech} and \ref{fig:eur-speech} respectively. For the \textit{standard scenarios}, we ran the FL training session for $35$ rounds, while for the \textit{straggler (\%) scenarios}, we ran the experiments for $60$ rounds. For the standard scenario, our strategy reached an accuracy of 79.4\% as compared to 76.6\% and 77.4\% for \texttt{FedAvg} and \texttt{FedProx} respectively. Furthermore, our strategy showed faster convergence by reaching an accuracy of 70\% in 19 rounds as compared to 21 and 22 for \texttt{FedAvg} and \texttt{FedProx} respectively. With 10\% stragglers, our strategy and \texttt{FedAvg} had a similar convergence rate, while \texttt{FedProx} was slightly behind. Moreover, our strategy reached an end accuracy of 76\% which is a 6\% and 10\% increase over \texttt{FedAvg} and \texttt{FedProx} respectively. For an FL system with 30\% stragglers, our strategy consistently outperforms \texttt{FedAvg} by around 8\% towards the end of the training, while outperforming \texttt{FedProx} by a smaller margin of 1\%. We observe a similar trend for our experiments with 50\% and 70\% stragglers in the system, where our strategy outperforms the other two. From our experiments, we observe that the presence of stragglers affects the convergence speed of the DNN models in an FL training session. DNN models trained in \textit{standard scenarios} converge faster as compared to the models trained with \textit{straggler (\%) scenarios} as shown in Figure~\ref{fig:acc-speech} (Table~\ref{tab:experiment-params}). We observe a similar behaviour for the different datasets (\S\ref{sec:datasets}). Moreover, for the \textit{straggler (\%) scenarios}, increasing the percentage of stragglers in the system does not consistently decrease the accuracy of the trained DNN model as shown in Table~\ref{tab:acc-all}. This is especially true for experiments with a higher number of stragglers, i.e., $70\%$. This behavior is not exclusive to our experiments and was also reported by Li et al.~\cite{fedprox} and Wu et al.~\cite{safa}. While the authors do not provide a clear explanation for this behaviour, we argue that due to the non-IID nature of the data, clients do not contribute evenly to the test accuracy. In addition, having fewer number of reliable clients reduces the varying effect of local model updates and local model deviations from the global model, making it easier to reach a consensus on the global model. Therefore, we can reach situations where a system with more stragglers reaches higher overall accuracy at the end. 

\subsection{Comparing time and cost}
\label{sec:timecost}
Although model accuracy is an important metric, fast convergence wrt the number of training rounds does not provide a complete picture of the efficiency of the system. Towards this, in this section, we provide a collective analysis of all experiments wrt total duration and costs. To compute the total experiment duration, we aggregate the total round time during training. For all the three strategies, the round time is determined by the slowest invoked client. As a result, the round time depends on either the response of the slowest client or a predetermined timeout (\S\ref{sec:scenarios}). Furthermore, for \textit{straggler (\%) scenarios}, we simulate real-world behavior by assuming that the stragglers will not respond, thus forcing the controller (\S\ref{sec:sysdesign}) to wait until the round timeout. 

Table~\ref{tab:total-time} shows the total aggregated time per experiment. For the \textit{standard scenario}, training a model with our strategy is significantly faster as compared to \texttt{FedAvg} and \texttt{FedProx} across all datasets. For instance, for the MNIST dataset, our strategy takes 40\% less time as compared to the other strategies. For the \textit{straggler (\%) scenarios}, we see the effect of stragglers on experiment duration. In the scenarios with 10\% and 30\% stragglers, we observe that 
\texttt{FedLesScan} maintains a lower duration across all experiments. However, when the number of stragglers in the system is significantly higher, they must be invoked in almost all training rounds to meet the minimum number of clients required per round. We notice this behavior for our strategy with greater than 50\% stragglers in the system for the MNIST, FEMNIST, and the Shakespeare dataset. However, for the Google Speech dataset, our strategy still has an 18\% lower experiment duration as compared to the other two. This is because the total number of clients for the Google Speech dataset is 542 with 200 concurrent clients participating in a training round (\S\ref{sec:expconfig}). For the scenario with 70\% stragglers in the system, all approaches have similar experiment times across all datasets.
{"value": "10", "type": "Other"} {"value": "30", "type": "Other"} {"value": "50", "type": "Other"} {"value": "70", "type": "Other"} {"value": "39.7", "type": "Other"} {"value": "40.2", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.3", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "23.7", "type": "Other"} {"value": "28.6", "type": "Other"} {"value": "27.3", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "75.5", "type": "Other"} {"value": "86.7", "type": "Other"} {"value": "86.9", "type": "Other"} {"value": "86.7", "type": "Other"} {"value": "86.7", "type": "Other"} {"value": "112.4", "type": "Other"} {"value": "88.2", "type": "Other"} {"value": "88.1", "type": "Other"} {"value": "87.8", "type": "Other"} {"value": "87.4", "type": "Other"} {"value": "70.9", "type": "Other"} {"value": "75.6", "type": "Other"} {"value": "82.8", "type": "Other"} {"value": "86.8", "type": "Other"} {"value": "86.7", "type": "Other"} {"value": "217.0", "type": "Other"} {"value": "217.0", "type": "Other"} {"value": "217.0", "type": "Other"} {"value": "216.9", "type": "Other"} {"value": "216.8", "type": "Other"} {"value": "217.0", "type": "Other"} {"value": "217.0", "type": "Other"} {"value": "217.0", "type": "Other"} {"value": "217.0", "type": "Other"} {"value": "216.7", "type": "Other"} {"value": "185.5", "type": "Other"} {"value": "215.5", "type": "Other"} {"value": "205.2", "type": "Other"} {"value": "216.8", "type": "Other"} {"value": "216.6", "type": "Other"} {"value": "20.3", "type": "Other"} {"value": "40.1", "type": "Other"} {"value": "40.1", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "21.5", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "40.0", "type": "Other"} {"value": "15.1", "type": "Other"} {"value": "31.1", "type": "Other"} {"value": "28.8", "type": "Other"} {"value": "33.3", "type": "Other"} {"value": "40.0", "type": "Other"}