{'fraction_non_alphanumeric': 0.024391455538996524, 'fraction_numerical': 0.0050173869846001, 'mean_word_length': 4.901788331867488, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Two-Stage Coded Federated Edge Learning: A Dynamic Partial Gradient Coding Perspective

Federated edge learning (FEL) can training a global model from terminal nodes' local dataset, which can make full use of the computing resources of terminal nodes and performs more extensive and efficient machine learning on terminal nodes with protecting user information requirements. Performance of FEL will be suffered from long delay or fault decision as the master collects partial gradients from stragglers which cannot return correct results within a deadline. Inspired by this, in this paper, we propose a novel coded FEL to mitigate stragglers for synchronous gradient with a two-stage dynamic scheme, where we start with part of workers for a duration of before starting the second stage, and on completion of at the first stage, we start remaining workers in the second stage. In particular, the computation latency and transmission latency is essential and should be quantitatively analyzed. Then the dynamically coded coefficients scheme is proposed which is based on historical information including worker completion time. For performance optimization of FEL, a Lyapunov function is designed to maximize admission data balancing fairness and two stage dynamic coding scheme is designed to maximize arrival data among workers. Experimental evidence verifies the derived properties and demonstrates that our proposed solution achieves a better performance for practical network parameters and benchmark datasets in terms of accuracy and resource utilization in the FEL system.


I. INTRODUCTION
With the improvement of mobile device performance and the development of edge networks, the concept of federated learning can be flexibly applied to edge computing scenarios. Because a large number of computing resources are configured in the network at the edge, a centralized data center is no longer necessary for federated learning. Model learning and data training can be done in a distributed manner, and the number of uploads is avoided. Network load and latency caused by huge raw data. At the same time, because federated learning has the advantage of utilizing real data from a large area of user clusters, it greatly facilitates unprecedented large-scale and flexible data training and model learning. Based on the above advantages, wireless federated edge learning has attracted the attention of many people in the industry.
According to the training method of federated learning, training algorithms can be divided into synchronous training [1][2] algorithms, asynchronous training algorithms [3][4] and hybrid training algorithms [5][6][7][8]. In synchronous training, scheduling clients and updating models are synchronously blocked. Each server update needs to receive feedback from enough clients, as shown only waiting for all clients (nodes) to train the model only execute the update global model, and then download it to the client. The asynchronous training method divides the scheduling client and the update model into parallel threads. The training model of each client (node) can be uploaded in parallel to update the global model without waiting for all clients. After the client completes the global update, it can schedule the client periodically, and the server can update the global model after receiving the model parameters uploaded by any client. Hybrid federated learning combines the two methods of synchronization and asynchronous, it can enforce synchronization in a local scope, wait until the training model of some clients. The asynchronous updates are uploaded to the server side together, and then downloaded to the client side after the global update is completed.
Ma et al. [5] proposed a semi-asynchronous federated learning mechanism (FedSA), in which the parameter server selects a certain number of local models for aggregation based on the order in which local models arrive in each round. In [6] they proposed a joint asynchronous and synchronous federated edge learning architecture, SAFA. Before a round of local training, the server classifies the client into three states: up-todate, deprecated, and tolerable, based on the model version currently held by the client. The latest and deprecated clients are forced to update to the latest global model (forced sync), while tolerable clients can continue to use their previous local model results to some extent (tolerate some asynchrony). Zhou et al. [7] grouped the related workers into a community and perform synchronous updates in the same community, which can speed up the training aggregation process, called community-aware parallel synchronization. The asynchronous actor-critic algorithm intelligently determines community deployment. Wang et al. [8] proposed an efficient federated edge learning mechanism, which divides edge nodes into K groups through balanced clustering. The edge nodes in the cluster forward their local updates to the cluster header to aggregate in a synchronous manner, called cluster aggregation, while all clusters perform an asynchronous global aggregation method.
However, in the synchronization part of the hybrid federated edge learning, the parameter server has to wait for the slowest client. Due to the heterogeneity of the edge, the waiting time of idle participants is too long. The asynchronous part requires frequent model transmission, resulting in a lot of communication resource consumption. In addition, the frequency of different clients participating in asynchronous updates may seriously affect the accuracy of training, especially in terms of transmission efficiency and resource utilization, which are not well guaranteed.
Inspired by these, in this paper, we propose a novel coded FEL to mitigate stragglers for synchronous gradient with a twostage dynamic scheme to enhance accuracy and resource utilization in the FEL system. The contributions of this article are listed as follows: 1) We propose a novel coded FEL to mitigate stragglers for synchronous gradient with a two-stage dynamic scheme, where we start with part of workers for a duration of before starting the second stage, and on completion of at the first stage, we start remaining workers in the second stage. 2) In the proposed scheme, the computation latency and transmission latency is essential and quantitatively analyzed. Then the dynamically coded coefficients scheme is proposed which is based on historical information including worker completion time. For performance optimization of FEL, a Lyapunov function is designed to maximize admission data balancing fairness and two stage dynamic coding scheme is designed to maximize arrival data among workers.
3) The extensive experiments demonstrate the effectiveness of the proposed scheme, in which can achieve the performance improvement by reducing the computation time and transmission time while keeping the convergence rate.

II. SYSTEM MODEL AND PROBLEM FORMULATION
In this section, we will describe the system model and use of the coding theory to remove the bottlenecks caused by the data placement phases, data delivery phases, gradient computation phases and model uploading phases, for the proposed the towstage dynamic coded federated learning (TSDCFL) in MEC.
We consider a FEL system with the parameter edge servers, i.e., model owners, each of which aims to develop a model. The set of local workers denoted as {1, 2, 3..., } M   , i.e., worker that have the computation and communication capabilities can support the model owners. The data owner that can associate themselves with workers in order to deliver data to workers. As shown in Fig.1. Then, we note that the whole aggregated gradient is given The parameters server is update by: (2) If the data partition is assigned to the worker, each worker computes the corresponding partial gradient, and the parameter server aggregate the partial gradient. Due to the limited by workers local computation capacity, limited harvested energy and high transmission delay, there exists some straggler. At the each iteration, the data loader assigns redundancy partial gradients to workers, thus, each worker is responsible for coded partial gradient so that parameter server can recover the whole gradient from subset of workers when the machine break down or the partial gradient cannot be transmitted to server. As shown in Fig.2. In each round, the gradient coding can tolerate up to We consider one row of equation and decoding function can also be a linear combination as:

Latency Analysis
As mentioned before, we aim at reducing complexity of encoding and decoding and the local gradient computation latency. Stragglers are inevitable in distributed learning systems, due to various reasons, including network latency, transmission fair among all workers, channel state, and workload imbalance. In order to mitigate the adversarial effects of stragglers, we mitigate the impact from perspective of reducing computation time and transmission time. We dynamically adjust the coded coefficients based on historical information including worker completion time. Therefore, the computation latency and transmission latency is essential and should be quantitatively analyzed. We aim to reduce the number of stragglers in each epoch and ensure the fairness of the transmission among all workers.
We consider that the entire training process is composed of multiple time slots, and maximum length of time slot is T. The system operate in a time slotted structure with length T, which means channels remain unchanged during a time slot and vary between slots. Let , ( ) Let ( ) m R t denotes the required CPU cycles to process gradient computation, can be updated by , , Upon the receipt of gradient from non-stragglers worker in parameter server, the parameter server will update the parameter. Let ( ) server R t be the required CPU cycles to update parameters at the server, and can be updated by where m  is the number of CPU cycles required per bit of the worker m.

Problem Formulation
Due to the existence of stragglers, we must consider the encoding method to reduce the impact of stragglers to ensure that all data partitions can be updated in each epoch. But if the encoding start at the beginning, it will increase complexity of encoding and decoding and increase the burden on each worker, so we first start to calculate the gradient from a part of the workers within the deadline, then we need to count the remaining data partitions, and then predict the stragglers based on the historical status and the historical completion time of each worker, which can improve the utilization of the worker and speed up the time of each We make the following assumptions: 1) Lipschitzian Gradient: The gradient function is Lipschitz continuous with constant L>0. Equivalently, for two parameter , the gradient function satisfies: 2) Unbiase gradient: for all parameter , the computed partial gradient is unbiased Theorem 1: by denoting the minimum loss function, we establish the following theorem for the convergence of TSDCFL. There exist scalar such that where C1 and C2 are the maximum of coding coefficient and decoding coefficient in first stage and second stage, n is the step size, P is the iteration times, k is type of data partitions, and L is assumption coefficient. Proof: see Appendix 1.

Two-stage dynamic coded strategy
In this section, we will show our two-stage dynamic coded strategy for maximizing arrival data in detail. Firstly, our objective P1 is to maximize the arrival data based on the past straggler behavior, code words assignment and data assignment. We specify how to design the coded strategy with the consideration of the heterogeneity worker. In the first phase,  gradients were computed. Conventionally coded strategy should start in the first phase, in our two stage dynamic coded strategy we start in the second phase. Specifically, we random select 1 M workers in the first phase. After finishing executing the gradients of each workers for the duration time Take Fig. 4 for an example, we illustrate the procedure of TSDCFL with 3 workers and i server. For instance, we start worker 1 and worker2, after worker 1 send the parameter to server within duration time in first stage. In second stage, worker 2 continue to update the parameters and woker3 are coded with worker 2 from remaining data partitions g2, until two worker send local update parameter, the epoch1 is finished. In epoch3，the worker2 and worker3 send the local parameter to the server in the first stage, we can say that we are robust to the stragglers in the first stage and encoding scheme is not triggered in second stage, which improve the efficiency and utilization of the workers.
In order to tolerate i s   straggler in each epoch, each of We now assume that the performance of workers are heterogeneous. We define the m W as the number of tasks finished per unit of time, and then define m w by normalizing m W , i.e., We define the m n as the proportions to the worker in the second phase, hence, we have Once the 1 M is fixed, we can assign remaining phase. The support structure of coding matrix is Given the structure of B, we need to assign code words to worker and introduce how to construct B such it can satisfy the span condition. We divide matrix B into two parts corresponding to an auxiliary matrix (  1) Therefore, B satisfies span condition. The proof is completed.

Fairness transmission strategy
Given the arrival data in our system, the next objective is to maximize the throughput and fairness in our coding system, to achieve which reduce the likelihood number of stragglers in communication phase. Specifically, we aim to discourage individual workers to consume excessive energy for little utility gain. It is challenging to get optimal values due to the following reasons. First, the arrival data of gradient of workers are time-varying and unknown a priori, hence it is hard to make decisions to admission data. Secondly, the backlog of gradient data is instability in the long run. In this section, we resort to Lyapunov optimization to solve the optimization problem. Proof: the problem is solved by constructing non-negative auxiliary variables corresponding to admission data. We need to prove that maximum P3 is equivalent to the P2. Since P2 is concave function, this function is monotonically increasing function, C6 guarantees * log(1 ) log(1 ) d y    , by applying Jensen's inequality on the concave function, we can get the log(1 ) log(1 ) y y    and we can conclude that P3 is equivalent to the P2.
Next, we construct a virtual queue for admission data, which can be expressed as  can transform into a queue stability problem. Then, this queue coupled with other queue can be addressed with stability constrains. In specific, given the queue dynamic, we can define a perturbed Lyapunov function as indicate the instantaneous backlogs size at time slot. Then, we can define the one-slot drift-plus-penalty function as A smaller value ( ) V t  indicates stable system utility and backlogs. We aim to minimize upper-bound of ( ) V t  so as to prevent the growth of backlogs and increase stability of system.
The upper bound allows us to make decisions by minimizing the value on upper bound. Therefore, we can maximize the throughput and fairness in our coding scheme, to achieve, which can reduce the likelihood number of stragglers in communication phase. Therefore, by exploiting Lemma 4, it is easy to divide P3 into independent terms, in which can be decomposed equivalently into the following sub-problems (P4, P5, P6 and P7) The parameters of the drift-plus-penalty upper bound can be viewed as an upper bound of ( ) V t  , we are able to maximize the throughput and sum of the system drift by making independent and sequential decision on , ( ) m i t and _ , m store i e   . Therefore, by setting value of these parameters, we can optimize the four separated conditional terms on P4, P5, P6 and P7. By tuning the value, all the queue states are optimized in each time slot. Next, we address these four subproblems by the auxiliary variable determination, optimal schedules for admission data, admission time and scheduling, optimal energy schedule.
the optimization is able to solve by setting the ( )

III. PERFORMANCE EVALUATION
In the experiment, we try to use the KubeEdge with connecting multiple machine, including one cloud host and a number of edge node. KubeEdge is an edge computing framework build on top of Kubernetes. It provides compute resource management, deployment, runtime and operation capabilities on geo-located edge computing resources, from the cloud, which is a natural fit for embedded systems. We build a 7-node consisting of 1 parameter server and 6 workers. All of nodes are established on KubeEdge. We mainly use different CPU cores to simulate the training parallelism. To simulate the stragglers, we inject one or two stragglers into training per epoch. All algorithms are implemented on Python 3.5 and PyTorch 0.4. Furthermore, we rely on an additional library cjltest implemented on PyTorch to partition the dataset and obtain gradients. All algorithm steps run on the CPU, except for loading training data from disk and communicating gradients through the network. To compare the performance of different methods, experiments were conducted on 6 nodes. We compare our algorithms to Cyclic Repetition Scheme and Fractional Repetition Scheme. We use image classification datasets including Mnist and Cifar10 as our benchmarks. We set the batch size as 128 and initial learning rate is 0.01. The entire training process is restricted in 10000 iterations. In this paper, we mainly adopt time-based efficiency and epoch based efficiency as the metrics. Time-based efficiency is affected by the arrival data and admission data in our system. We adopt two stage dynamic coding scheme and fairness transmission scheme to improve efficiency.     Fig. 5 accuracy, loss, and iteration time over TSDCFL in Cifar10. As shown in Fig. 5 and Fig. 6, we can see that TSDCFL is the same epoch based efficiency as the algorithms. The main reason is that all algorithms adopt the full data partitions and synchronous scheme in each iteration, as the consequence, epoch Based have the same converge rate. After compared with other methods with epoch based efficiency, we conduct the experiments on 6 nodes with (2 cores, 2cores, 4 cores, 4 cores, 8 cores, 8 cores) for time-based efficiency of two models. The results show that TSDCFL preforms the better than other algorithms due to its tolerance to the stragglers, higher utilization of the computation resource and fairness transmission among workers. Specifically, as shown in Fig. 5e and Fig. 6e, the iteration time of TSDCFL is lower than the other algorithms. To be summarized, the algorithm with TSDCFL achieves the performance improvement by reducing the computation time and transmission time while keeping the convergence rate.     Fig. 6 accuracy, loss, and iteration time over TSDCFL in Mnist.

IV. CONCLUSION
In this paper, we propose a novel coded FEL to mitigate stragglers for synchronous gradient with a two-stage dynamic scheme to enhance accuracy and resource utilization in the FEL system, where we start with part of workers for a duration of before starting the second stage, and on completion of at the first stage, we start remaining workers in the second stage. In the proposed scheme, the computation latency and transmission latency is essential and quantitatively analyzed. Then the dynamically coded coefficients scheme is proposed which is based on historical information including worker completion time. For performance optimization of FEL, a Lyapunov function is designed to maximize admission data balancing fairness and two stage dynamic coding scheme is designed to maximize arrival data among workers. The extensive experiments demonstrate the effectiveness of the proposed scheme, which can achieve the performance improvement by reducing the computation time and transmission time while keeping the convergence rate.