Federated learning (FL) has attracted tremendous attention due to its capability to preserve data privacy. In FL, a parameter server (PS) without accessing clients' raw data can assist decentralized clients in completing model training by aggregating and distributing model parameters for multiple iterations. From the clients' perspective, exposing model parameters to the PS can still result in privacy leakage. To further enhance privacy protection, differentially private federated learning (DPFL) is invented, in which clients add differentially private (DP) noises to distort their parameters to be exposed. However, the main challenge of DPFL lies in inferior model accuracy due to DP noises. To overcome this challenge, in this paper we propose a novel algorithmic framework for DPFL, which is called CODP, by cascading and offsetting DP noises between iterations. In existing works, each DPFL client only considers how to protect its model parameters based on the number of iterations to expose parameters overlooking the underlying relation of model parameters in consecutive iterations. The novelty of CODP lies in cascading DP noises from each iteration to its subsequent iteration so that DP noises can be offset in the subsequent iteration, and hence model accuracy can be improved. Additionally, we theoretically prove that CODP can substantially improve the convergence rate of DPFL without compromising privacy preservation by leveraging the most widely used Laplace and Gaussian mechanisms, respectively. We conduct comprehensive experiments using MNIST, Fashion-MNIST, and Lending Club datasets to demonstrate that the model accuracy of DPFL can be remarkably improved by CODP with a fixed privacy budget.

Hierarchical federated learning (HFL) improves the scalability and efficiency of traditional federated learning (FL) by incorporating a hierarchical topology into the FL framework. In a typical HFL system, clients are divided into multiple tiers, and the training process involves both local and global model aggregation. However, existing HFL approaches have several significant drawbacks. Firstly, the root parameter server (PS) is vulnerable to single-point failure and also acts as a bottleneck for global aggregation. Additionally, frequent global aggregation over the wide area network (WAN) incurs substantial communication costs, which negatively affect training efficiency. In this paper, we propose a novel HFL algorithm called CPFedAvg to address the aforementioned challenges. CPFedAvg introduces a root-free hierarchical topology, where the top tier consists of multiple PSes, effectively resolving the issues associated with the root PS. Additionally, we substitute the expensive global aggregation with parameter mixing operations between the PSes in the top tier. We analyze the convergence rate of CPFedAvg under non-convex loss. Based on this analysis, we formulate a convex optimization problem to optimize the frequency of executing local aggregations between consecutive parameter mixing operations. To simulate real-world communication networks, we develop FedNetSimulator to simulate a diverse range of FL communication processes. Finally, we conduct extensive experiments using real datasets (i.e., CIFAR-10 and CIFAR-100). The experimental results demonstrate that CPFedAvg can improve model accuracy by up to 18% and the speedup can be as high as 6 compared with the state-of-the-art baselines.

Gaze prediction is essential for enhancing user experiences of virtual reality (VR) applications. However, existing methods seldom considered the privacy nature of gaze data, which may reveal both psychological and physiological characteristics of VR users. Moreover, the commonly adopted one-sizefits-all prediction model cannot well capture behavioral patterns of different VR users. In this paper, we propose a privacyaware personalized gaze prediction framework called GazeFed, which can train a personalized gaze prediction model for each user in a collaborative manner. In GazeFed, only intermediate computations are exchanged between users and the server. The raw gaze data samples are locally preserved to protect user privacy. The global model is shared among all users, which can be further trained with local gaze data to generate a personalized prediction model for each individual user. We also propose a deep neural network tailored for VR gaze prediction called GazeNet, which can effectively extract features from VR contents, gaze data and other user behaviors, and improve the accuracy of gaze prediction. Moreover, the technique of differential privacy (DP) is also integrated to provide more privacy protection, and we theoretically prove that GazeFed can well converge and satisfy the requirement of differential privacy in the meanwhile. Last, we conduct extensive experiments to evaluate the effectiveness of our proposed GazeFed on real datasets and various VR scenarios. The experimental results demonstrate that GazeFed outperforms the state-of-the-art approaches.

Federated learning (FL) emerges as an attractive collaborative machine learning framework that enables training of models across decentralized devices by merely exposing model parameters. However, malicious attackers can still hijack communicated parameters to expose clients’ raw samples resulting in privacy leakage. To defend against such attacks, differentially private FL (DPFL) is devised, which incurs negligible computation overhead in protecting privacy by adding noises. Nevertheless, the low model utility and communication efficiency makes DPFL hard to be deployed in the real environment. To overcome these deficiencies, we propose a novel DPFL algorithm called FedDP-SA (namely, federated learning with differential privacy by splitting Local data sets and averaging parameters). Specifically, FedDP-SA splits a local data set into multiple subsets for parameter updating. Then, parameters averaged over all subsets plus differential privacy (DP) noises are returned to the parameter server. FedDP-SA offers dual benefits: 1) enhancing model accuracy by efficiently lowering sensitivity, thereby reducing noise to ensure DP and 2) improving communication efficiency by communicating model parameters with a lower frequency. These advantages are validated through sensitivity analysis and convergence rate analysis. Finally, we conduct comprehensive experiments to verify the performance of FedDP-SA compared with other state-of-the-art baseline algorithms.

The differentially private federated learning (DPFL) paradigm emerges to firmly preserve data privacy from two perspectives. First, decentralized clients merely exchange model updates rather than raw data with a parameter server (PS) over multiple communication rounds for model training. Secondly, model updates to be exposed to the PS will be distorted by clients with differentially private (DP) noises. To incentivize clients to participate in DPFL, various incentive mechanisms have been proposed by existing works which reward participating clients based on their data quality and DP noise scales assuming that all clients are honest and genuinely report their DP noise scales. However, the PS cannot directly measure or observe DP noise scales leaving the vulnerability that clients can boost their rewards and lower DPFL utility by dishonestly reporting their DP noise scales. Through a quantitative study, we validate the adverse influence of dishonest clients in DPFL. To overcome this deficiency, we propose a robust incentive mechanism called client selection with reverse auction (CSRA) for DPFL. We prove that CSRA satisfies the properties of truthfulness, individual rationality, budget feasibility and computational efficiency. Besides, CSRA can prevent dishonest clients with two steps in each communication round. First, CSRA compares the variance of exposed model updates and claimed DP noise scale for each individual to identify suspicious clients. Second, suspicious clients will be further clustered based on their model updates to finally identify dishonest clients. Once dishonest clients are identified, CSRA will not only remove them from the current round but also lower their probability of being selected in subsequent rounds. Extensive experimental results demonstrate that CSRA can provide robust incentive against dishonest clients in DPFL and significantly outperform other baselines on three real public datasets.

Given that devices (i.e., clients) participating in federated edge learning (FEL) are autonomous and resource-constrained in nature, it is critical to design effective incentive mechanisms to encourage client participation so as to improve the performance of FEL. In this article, we aim to boost the FEL training efficiency by answering how much compute resource should clients autonomously contribute to maximize their utilities. To this end, we develop AutoFL, an autonomous client participation decision framework for federated learning at the network edge without assuming that each client possesses complete information. We first model the problem of autonomous client participation as a Bayesian game with incomplete information, where each player in the game is associated with a set of types according to network conditions. We optimize an individual client's decision based on the dynamics of the population estimated following the Bayes rule. We prove that AutoFL can converge to a unique Bayesian Nash equilibrium point. Empirical results on three real datasets show that AutoFL achieves a higher model accuracy with only 15.5-24.5% model aggregation time per global training round, and its energy cost saving on mobile devices is 82.2-86.8% compared to the state-of-the-art algorithms. Moreover, we can achieve a 2.75-3.2x long-term fairness compared to classical solutions.

Federated learning (FL) empowers distributed clients to collaboratively train a shared machine learning model through exchanging parameter information. Despite the fact that FL can protect clients’ raw data, malicious users can still crack original data with disclosed parameters. To amend this flaw, differential privacy (DP) is incorporated into FL clients to disturb original parameters, which however can significantly impair the accuracy of the trained model. In this work, we study an imperative question which has been vastly overlooked by existing works: what are the optimal numbers of queries and replies in FL with DP so that the final model accuracy is maximized. In FL, the parameter server (PS) needs to query participating clients for multiple global iterations to complete training. Each client responds a query from the PS by conducting a local iteration. We consider FL that will uniformly and randomly select participating clients to conduct local iterations with the FedSGD algorithm. Our work investigates how many times the PS should query clients and how many times each client should reply the PS by incorporating two most extensively used DP mechanisms (i.e., the Laplace mechanism and Gaussian mechanisms). Through conducting convergence rate analysis, we can determine the optimal numbers of queries and replies in FL with DP so that the final model accuracy can be maximized. Finally, extensive experiments are conducted with publicly available datasets: MNIST and FEMNIST, to verify our analysis and the results demonstrate that properly setting the numbers of queries and replies can significantly improve the final model accuracy in FL with DP.

In vanilla Federated Learning (FL) systems, a centralized parameter server (PS) is responsible for collecting, aggregating and distributing model parameters with decentralized clients. However, the communication link of a single PS can be easily overloaded by concurrent communications with a massive number of clients. To overcome this drawback, multiple PSes can be deployed to form a parallel FL (PFL) system, in which each PS only communicates with a subset of clients and its neighbor PSes. On one hand, each PS conducts iterations with clients in its subset. On the other hand, PSes communicate with each other periodically to mix their parameters so that they can finally reach a consensus. In this paper, we propose a novel parallel federated learning algorithm called Fed-PMA, which optimizes such parallel FL under constrained communications by conducting parallel parameter mixing and averaging with theoretic guarantees. We formally analyze the convergence rate of Fed-PMA with convex loss, and further derive the optimal number of times each PS should mix with its neighbor PSes so as to maximize the final model accuracy within a fixed span of training time. Theoretical study manifests that PSes should mix their parameters more frequently if the connection between PSes is sparse or the time cost of mixing is low. Inspired by our analysis, we propose the Fed-APMA algorithm that can adaptively determine the near-optimal number of mixing times with non-convex loss under dynamic communication conditions. Extensive experiments with realistic datasets are carried out to demonstrate that both Fed-PMA and its adaptive version Fed-APMA significantly outperform the state-of-the-art baselines.

Eye tracking techniques have been widely adopted by a wide range of devices (e.g., AR/VR headsets, smartphones) to enhance user experiences. However, eye gaze data is private in nature, which can reveal users’ psychological and physiological features. Privacy protection techniques can be incorporated to preserve privacy of eye tracking information. Yet, most existing solutions based on Differential Privacy (DP) mechanisms cannot well protect privacy for individual users without sacrificing user experience. In this paper, we are among the first to propose a novel gaze model-based privacy control framework called Otus for eye tracking applications, which incorporates local DP (LDP) mechanisms to preserve user privacy and improves user experience in the meanwhile. First, we conduct a measurement study on real traces to illustrate that direct noise injection on raw gaze trajectories can significantly lower the utility of gaze data. To preserve utility and privacy simultaneously, Otus injects noises in two steps: (1) Extracting model features from raw data to depict gaze trajectories on individual users; (2) Adding LDP noises into model features so as to protect privacy. On one hand, established models can be used to recover user gaze data in order to improve service quality of eye tracking applications. On the other hand, we only need to add LDP noises to distort a small number of model parameters rather than every point on a trajectory to preserve privacy, which has less impact on the utility of gaze data given the same privacy budget. By applying the tile view graph model in step (1), we illustrate the entire workflow of Otus and prove its privacy protection level. For evaluation, we conduct extensive experiments using real gaze traces and the results show that Otus can effectively protect privacy for individual users without significantly compromising gaze data utility.

Instead of training a single global model to fit the needs of all clients, personalized federated learning aims to train multiple client-specific models to better account for data disparities across participating clients. However, existing solutions suffer from serious unfairness among clients in terms of model accuracy and slow convergence under non-lID data. In this paper, we propose a novel personalized federated learning framework, called D PFed, which employs deep reinforcement learning (D RL) to identify relationship between clients and enable closer collaboration among similar clients. By exploiting such relationships, DPFed can personalize model aggregation for each client and achieve fast convergence. Moreover, by regularizing the reward function of DRL, we can reduce the variance of model accuracy across clients and achieve a higher level of fairness. Finally, we conduct extensive experiments to evaluate the effectiveness of our proposed framework under a variety of datasets and degrees of non-lID data distribution. The results demonstrate that DPFed outperforms other alternatives in terms of convergence speed, model accuracy, and fairness.

With the growth of participating clients, the centralized parameter server (PS) will seriously limit the scale and efficiency of Federated Learning (FL). A straightforward approach to scale up the FL system is to construct a Parallel FL (PFL) system with multiple parallel PSes. However, it is unclear whether PFL can really accelerate FL or reduce the training time of FL. Even if the answer is yes, it is non-trivial to design a highly efficient parameter average algorithm for a PFL system. In this paper, we propose a completely parallelizable FL algorithm called P-FedAvg under the PFL architecture. P-FedAvg extends the well-known FedAvg algorithm by allowing multiple PSes to cooperate and train a learning model together. In P-FedAvg, each PS is only responsible for a fraction of total clients, but PSes can mix model parameters in a dedicatedly designed way so that the FL model can well converge. Different from heuristic-based algorithms, P-FedAvg is with theoretical guarantees. To be rigorous, we theoretically analyze the convergence rate of P-FedAvg in terms of the number of conducted iterations, the communication cost of each global iteration and the optimal weights for each PS to mix parameters with its neighbors. Based on theoretical analysis, we conduct a case study on five typical overlay topolgoies formed by PSes to further examine the communication efficiency under different topologies, and investigate how the overlay topology affects the convergence rate, communication cost and robustness of a PFL system. Lastly, we perform extensive experiments with real datasets to verify our analysis and demonstrate that P-FedAvg can significantly speed up FL than traditional FedAvg and other competitive baselines. We believe that our work can help to lay a theoretical foundation for building more efficient PFL systems.

The rapidly evolving technology of edge computing shows great potential in revolutionizing the market of cloud gaming. Edge computing can significantly lower the latency for better gaming experiences by performing computation at the proximity of game players. However, the acceleration of latency-sensitive cloud gaming services at the edge is challenging due to the heterogeneity of edge servers, different requirements among game players, and so on. In this paper, we propose an efficient latency-sensitive scheduling algorithm called EGSA to satisfy latency constraints for cloud gaming services at the edge. We first formulate the problem as a weighted congestion game, which takes a number of key factors (e.g., game genres, user strategies, latency constraint and device heterogeneity) into account. Based on the weighted congestion game model, we further design an efficient latency-sensitive scheduling algorithm, which can approximate the pure Nash equilibrium under Shapley cost-sharing method. We also perform theoretic analysis to prove that our proposed algorithm converges in polynomial steps. Finally, we conduct a set of experiments and the results show that our algorithm outperforms alternative strategies with up to 46% performance improvement.

A typical stateful (resp. stateless) group key distribution (GKD) protocol is composed of a secret assignment algorithm, and stateful join/leave rekeying algorithms (resp. a stateless group rekeying algorithm). Any design flaw in any of these algorithms could lead to attacks on GKD protocols. We show how two recently-proposed stateful GKD protocols based on asymmetric cryptographic primitives suffer from collusion attacks due to security flaws in either secret assignment algorithms or leave rekeying algorithms. A variety of single-user attacks and improvements on stateless group rekeying algorithms of a number of GKD protocols based on Shamir's Secret-Sharing Scheme (SSS) have been put forward. We show the stateless group rekeying algorithms of one improved protocol and its variant (proposed by us) still suffer from attacks. In addition, we prove a lower bound on the size of a user's long-term secret for perfectly secure multi-session stateless GKD protocols. This bound reveals that (i) it is impossible to design an infinite-session stateless GKD protocol that is both perfectly secure and practical; (ii) all the considered SSS-based stateless GKD protocols are bound to be either incorrect or vulnerable to attacks. This work highlights the urgent necessity of adopting the provable security approach in this research field.

A replay tool aiming to reproduce a program's execution interposes itself at an appropriate replay interface between the program and the environment. During recording, it logs all non-deterministic side effects passing through the interface from the environment and feeds them back during replay. The replay interface is critical for correctness and recording overhead of replay tools.

Message Passing Interface (MPI) is a widely used standard for managing coarse-grained concurrency on distributed computers. Debugging parallel MPI applications, however, has always been a particularly challenging task due to their high degree of concurrent execution and non-deterministic behavior. Deterministic replay is a potentially powerful technique for addressing these challenges, with existing MPI replay tools adopting either data-replay or order-replay approaches. Unfortunately, each approach has its tradeoffs. Data-replay generates substantial log sizes by recording every communication message. Order-replay generates small logs, but requires all processes to be replayed together. We believe that these drawbacks are the primary reasons that inhibit the wide adoption of deterministic replay as the critical enabler of cyclic debugging of MPI applications.

Soft hang is an action that was expected to respond instantly but instead drives an application into a coma. While the application usually responds eventually, users cannot issue other requests while waiting. Such hang problems are widespread in productivity tools such as desktop applications; similar issues arise in server programs as well. Hang problems arise because the software contains blocking or time-consuming operations in graphical user interface (GUI) and other time-critical call paths that should not.

Region-based memory management is a popular scheme in systems software for better organization and performance. In the scheme, a developer constructs a hierarchy of regions of different lifetimes and allocates objects in regions. When the developer deletes a region, the runtime will recursively delete all its subregions and simultaneously reclaim objects in the regions. The developer must construct a consistent placement of objects in regions; otherwise, if a region that contains pointers to other regions is not always deleted before pointees, an inconsistency will surface and cause dangling pointers, which may lead to either crashes or leaks.

No abstract available.

Failure detector class Omegakappahas been defined in (G. Neiger, 1995) as an extension to failure detector Omega, and an algorithm has been given in (A. Mostefaoui et al., 2005) to solve k-set agreement using Omegakappain asynchronous message-passing systems. In this paper, we extend these previous work in two directions. First, we define two new classes of failure detectors Omegakappa'and Omegakappa",which are new ways of extending Omega and show that they are equivalent to Omegakappa. Class Omegakappa'is more flexible than Omegakappain that it does not require the outputs to stabilize eventually, while class Omegakappa"does not refer to other processes in its outputs. Second, we present a new algorithm that solves k-set agreement using Omegakappa"when a majority of processes do not crash. The algorithm is a faithful extension of the Paxos algorithm (L. Lamport, 1998), and thus it inherits the efficiency, flexibility, and robustness of the Paxos algorithm. In particular, it has better message complexity than the algorithm in (A. Mostefaoui et al., 2005). Both the new failure detectors and the new algorithm enrich our understanding of the k-set agreement problem.

A correct system is only derived from a correct implementation of a correct specification. Unfortunately, this imposes a heavy burden in the development process, especially for complex, distributed system ranging from machine room computing and storage services as well as large-scale P2P applications. A specification, if authored in formal language such as TLA+, Spec#, SPIN etc., is ready for model checking. The state explosion problem, however, prohibits all specification states to be thoroughly traversed. Often ad hoc heuristics are applied to drastically reduce the scale so as to make the model checking phase tractable. A correct implementation can be even more challenging, especially when we encounter non-deterministic bugs that are hard to reproduce. The gap between spec and implementation often leaves one to wonder whether the implementation or the spec is faulty, or even both. Motivated by our experiences in developing several complete large scale distributed systems, we are designing and implementing a suite of testing and debugging facility on top of our previously developed WiDS platform.

This paper presents a new approach to motion blur identification based on Bayesian paradigm and maximum a posteriori (MAP) method. To represent general spatial-invariant motion blurs, especially those caused by nonuniform and nonstraight motions, a new blur model is proposed by incorporating the knowledge of blur type or partially known motion shape as a blur priori. Based on this model, an iterative method is adopted for the MAP blur identification. Experimental result shows that the proposed method offers an efficient way to precisely estimate the motion blur and to generate better restoration result, especially for the widely existing motion blurs caused by complicated motions and cannot be simplified as straight-and-uniform motion blurs.