\begin{table}[t]
\centering
\begin{adjustbox}{width=\columnwidth,  center}
\begin{tabular}{|c|ccc|cc|}
\hline
\multirow{2}{*}{\textbf{Dataset}} & \multicolumn{3}{c|}{\textbf{Hyperparameters}}                                                           & \multicolumn{2}{c|}{\textbf{Number of Training Rounds}}                             \\ \cline{2-6} 
                                  & \multicolumn{1}{c|}{\textbf{Epochs}} & \multicolumn{1}{c|}{\textbf{Batch Size}} & \textbf{Learning Rate} & \multicolumn{1}{c|}{\textbf{Standard}} & \textbf{Straggler (\%)} \\ \hline
MNIST                             & \multicolumn{1}{c|}{5}               & \multicolumn{1}{c|}{10}                  & $1e-3$                 & \multicolumn{1}{c|}{60}                & 60                      \\ \hline
FEMNIST                           & \multicolumn{1}{c|}{5}               & \multicolumn{1}{c|}{10}                  & $1e-3$                  & \multicolumn{1}{c|}{40}                & 40                      \\ \hline
Shakespeare                       & \multicolumn{1}{c|}{1}               & \multicolumn{1}{c|}{32}                  & $0.8$                 & \multicolumn{1}{c|}{25}                & 25                      \\ \hline
Speech Command                    & \multicolumn{1}{c|}{5}               & \multicolumn{1}{c|}{5}                   & $1e-3$                  & \multicolumn{1}{c|}{35}                & 60                      \\ \hline
\end{tabular}
\end{adjustbox}
\caption{Experiment hyperparameters for the different datasets (\S\ref{sec:datasets}) and experiment scenarios (\S\ref{sec:scenarios}).}

\vspace{-5mm}
\label{tab:experiment-params}
\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}).

\subsection{Staleness-aware Aggregation}
\label{sec:stalelessaware}
Although our intelligent client selection strategy (\S\ref{sec:ClientSelection}) improves the efficiency of the system, stragglers are not completely eliminated. Stragglers might push their local model updates to the parameter server after the completion of an FL training round. Moreover, these updates might contain valuable information that can improve the performance of the global model. Towards this, we aggregate the delayed updates of the clients with a dampening effect asynchronously, i.e., delayed updates are considered the next time the aggregation function is called. 
Equation~\ref{eq:fedless-aggr} shows our updated aggregation function used to include stale updates. $w^k_{t_k}$ is the local model of client \textit{k} at round $t_k$ and $w_{t+1}$ is the global model after aggregation at round $t$. Furthermore, $n_k$ represents the cardinality of the dataset at client $k$ while $n$ is the total cardinality of the aggregated clients.  If the updates arrive at the same round ($t_k = t$), the equation becomes similar to \texttt{FedAvg}~\cite{mcmahan2017communication}. On the other hand, older updates ($t_k < t$), are dampened by $\frac{t_k}{t}$. To avoid obsolete updates from affecting the training, the aggregator uses a parameter $\tau$ to dictate the maximum age of updates included in the aggregation. Updates with $t - t_k \ge \tau$ are discarded by the aggregator. In our experiments, we use a value of two for $\tau$.

For MNIST, we use a 2-layer Convolutional Neural Network (CNN) with a 5x5 kernel. Each convolutional layer is followed by a 2x2 max-pooling layer.  The model ends with a fully-connected layer with 512 neurons and a ten-neuron output layer. Similarly, for FEMNIST we use a 2-layer CNN with a 5x5 kernel in which each convolutional layer is followed by a 2x2 max-pooling layer. The CNN layers are followed by a fully-connected layer with 2048 neurons, which is followed by an output layer with 62 neurons. For the Shakespeare dataset, we use a Long Short Term Memory (LSTM) recurrent neural network~\cite{hochreiter1997long}. The model consists of an embedding layer of size eight followed by two LSTM layers with 256 units and an output layer of size 82. Our model architecture for Google Speech consists of two identical blocks followed by an average pooling layer and an output layer with 35 neurons. A block contains two convolutional layers with a 3x3 kernel followed by a max-pooling layer. A dropout layer follows the max-pooling layer with a rate of \texttt{0.25} to avoid overfitting. For MNIST, FEMNIST, and Google Speech, we use Adam~\cite{adam} as the optimizer with a learning rate of $1e-3$. On the other hand, for Shakespeare, we use SGD~\cite{sgd} with a learning rate of $0.8$. The clients for the MNIST, FEMNIST, and Speech datasets train for five local epochs with a batch size of $10$, $10$, and five respectively. Due to the limitations of the current commercial FaaS platforms (\S\ref{sec:faas}), the clients for Shakespeare train for one local epoch with a batch size of $32$. The hyperparameters for the different datasets are shown in Table~\ref{tab:experiment-params}.

\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.

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. 
{"value": "5", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "epochs", "dataset": "MNIST"} {"value": "10", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "batch size", "dataset": "MNIST"} {"value": "1e-3", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "learning rate", "dataset": "MNIST"} {"value": "60", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "number of training rounds standard", "dataset": "MNIST"} {"value": "60", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "number of training rounds straggler", "dataset": "MNIST"} {"value": "5", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "epochs", "dataset": "FEMNIST"} {"value": "10", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "batch size", "dataset": "FEMNIST"} {"value": "1e-3", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "learning rate", "dataset": "FEMNIST"} {"value": "40", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "number of training rounds standard", "dataset": "FEMNIST"} {"value": "40", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "number of training rounds straggler", "dataset": "FEMNIST"} {"value": "1", "type": "Hyper-parameter/Architecture", "model": ["LSTM", "Long Short Term Memory"], "parameter/architecture name": "epochs", "dataset": "Shakespeare"} {"value": "32", "type": "Hyper-parameter/Architecture", "model": ["LSTM", "Long Short Term Memory"], "parameter/architecture name": "batch size", "dataset": "Shakespeare"} {"value": "0.8", "type": "Hyper-parameter/Architecture", "model": ["LSTM", "Long Short Term Memory"], "parameter/architecture name": "learning rate", "dataset": "Shakespeare"} {"value": "25", "type": "Hyper-parameter/Architecture", "model": ["LSTM", "Long Short Term Memory"], "parameter/architecture name": "number of training rounds standard", "dataset": "Shakespeare"} {"value": "25", "type": "Hyper-parameter/Architecture", "model": ["LSTM", "Long Short Term Memory"], "parameter/architecture name": "number of training rounds straggler", "dataset": "Shakespeare"} {"value": "5", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "epochs", "dataset": "Speech Command"} {"value": "5", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "batch size", "dataset": "Speech Command"} {"value": "1e-3", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "learning rate", "dataset": "Speech Command"} {"value": "35", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "number of training rounds standard", "dataset": "Speech Command"} {"value": "60", "type": "Hyper-parameter/Architecture", "model": ["CNN", "Convolutional Neural Network"], "parameter/architecture name": "number of training rounds straggler", "dataset": "Speech Command"}