In this paper, we study gradient coding in a hierarchical setting, where there are intermediate nodes between the server and the workers. This structure reduces the bandwidth requirements at the server, which is a significant bottleneck in conventional gradient coding systems. In this paper, the intermediate nodes, referred to as relays, process the data received from workers and send the results to the server for the final gradient computation. Our main contribution is deriving the optimal communication-computation trade-off by designing a linear coding scheme inspired by coded computing techniques, considering straggling and adversarial nodes among both relays and workers. The processing of the data in the relays makes it possible to achieve both the relay-to-server and the worker-to-relay communication loads simultaneously optimal with regard to the computation load.

In a typical formulation of the private information retrieval (PIR) problem, a single user wishes to retrieve one out of$ K$files from N servers without revealing the demanded file index to any server. This paper formulates an extended model of PIR, referred to as multi-message private computation (MM-PC), where instead of retrieving a single file, the user wishes to retrieve$P\gt 1$linear combinations of files while preserving the privacy of the demand information. The MM-PC problem is a generalization of the private computation (PC) problem (where the user requests one linear combination of the files), and the multi-message private information retrieval (MM-PIR) problem (where the user requests$P\gt 1$files). A baseline achievable scheme repeats the optimal PC scheme by Sun and Jafar P times, or treats each possible demanded linear combination as an independent file and then uses the near optimal MM-PIR scheme by Banawan and Ulukus. In this paper, we propose a new MM-PC scheme that significantly improves upon the baseline schemes. In doing so, we design the queries inspired by the structure in the cache-aided scalar linear function retrieval scheme by Wan et al., which leverages the dependency between linear functions to reduce the amount of communications. To ensure the decodability of our scheme, we propose a new method to benefit from the existing dependency, referred to as the sign assignment step. In the end, we use Maximum Distance Separable matrices to code the queries, which allows the reduction of download from the servers, while preserving privacy. By the proposed schemes, we characterize the capacity within a multiplicative factor of 2.

Federated learning (FL), as a promising machine learning paradigm for large-scale distributed data, faces two security challenges of privacy and robustness: the transmitted model updates potentially leak sensitive user information, and the lack of central control over local model updates leaves the global model susceptible to malicious attacks. Current solutions attempting to address both problems under the one-server FL setting fall short in the following aspects: 1) design for simple validity checks that are insufficient against advanced attacks (e.g., checking norm of individual update); and 2) have partial privacy leakage for more complicated robust aggregation algorithms (e.g., distances between model updates are leaked for multi-Krum). In this work, we formalize a novel security notion ofaggregated privacythat characterizes the minimum amount of user information, in the form of aggregated statistics of users’ updates, that is necessary to be revealed to accomplish more advanced robust aggregation. We develop a general framework PriRoAgg, utilizing Lagrange coded computing and distributed zero-knowledge proof, to execute a wide range of robust aggregation algorithms while satisfying aggregated privacy. As concrete instantiations of PriRoAgg, we construct two secure and robust protocols based on state-of-the-art robust algorithms, for which we provide full theoretical analyses on security and complexity. Extensive experiments are conducted for these protocols, demonstrating their robustness against various model integrity attacks, and their efficiency advantages over baselines.

In this paper, we propose ByzSecAgg, an efficient secure aggregation scheme for federated learning that is resistant to Byzantine attacks and privacy leakages. Processing individual updates to manage adversarial behavior, while preserving privacy of data against colluding nodes, requires some sort of secure secret sharing. However, the communication load for secret sharing of long vectors of updates can be very high. In federated settings, where users are often edge devices with potential bandwidth constraints, excessive communication overhead is undesirable. ByzSecAgg solves this problem by partitioning local updates into smaller sub-vectors and sharing them using ramp secret sharing. However, this sharing method does not admit bi-linear computations, such as pairwise distance calculations, which are needed for distance-based outlier-detection algorithms, and effective methods for mitigating Byzantine attacks. To overcome this issue, each user runs another round of ramp sharing, with a different embedding of data in the sharing polynomial. This technique, motivated by ideas from coded computing, enables secure computation of pairwise distance. In addition, to maintain the integrity and privacy of the local update, ByzSecAgg also uses a vector commitment method, in which the commitment size remains constant (i.e., does not increase with the length of the local update), while simultaneously allowing verification of the secret sharing process. In terms of communication load, ByzSecAgg significantly outperforms the related baseline scheme, known as BREA.

Integrated sensing and communications (ISAC) is envisioned to be a key to advanced applications in future wireless networks. In this paper, we study the coded modulation designs for ISAC transmissions with short block lengths over correlated Rayleigh fading channels. In line with the short block length transmission, we consider the non-coherent communication detection and coherent radar sensing, where a neural network (NN)-assisted frame-wise constellation design is proposed. Specifically, we first derive the optimal communication and radar receivers. Then, we present some heuristic understandings of the code designs by considering special cases, based on which a conjecture on the optimal codes for the considered ISAC transmissions is developed. The constellation obtained from the proposed NN agrees with our conjecture and shows an important conclusion that the optimal codes of the considered problem may be a combination of the “on-off keying” and phase-shifted keying signalings. Our numerical results show that the proposed code exhibits promising communication and sensing performance simultaneously and outperforms the transmissions with a standard channel code and symbol-wise modulation.

In a typical formulation of the private information retrieval (PIR) problem, a single user wishes to retrieve one out of$K$files from$N$servers without revealing the demanded file index to any server. This paper formulates an extended model of PIR, referred to as multi-message private computation (MMPC), where instead of retrieving a single file, the user wishes to retrieve$P > 1$linear combinations of files while preserving the privacy of the demand information. The MM-PC problem is a generalization of the private computation (PC) problem (where the user requests one linear combination of the files), and the multi-message private information retrieval (MM-PIR) problem (where the user requests$P > 1$files). A baseline achievable scheme repeats the optimal PC scheme by Sun and Jafar$P$times, or treats each possible demanded linear combination as an independent file and then uses the near optimal MM-PIR scheme by Banawan and Ulukus. In this paper, we propose an achievable MM-PC scheme that significantly improves upon the baseline scheme. Doing so, we design the queries inspired from the structure in the cache-aided scalar linear function retrieval scheme, where they leverage the dependency between messages to reduce the amount of communication. To ensure the decodability of our scheme, we propose a new method to benefit from the existing dependency, referred to as the sign assignment step. In the end, we use Maximum Distance Separable matrices to code the queries, which allows the reduction of download from the servers, while preserving privacy.

We proposeSwiftAgg+, a novel secure aggregation protocol for federated learning systems, where a central server aggregates local models of$N \in \mathbb {N}$distributed users, each of size$L \in \mathbb {N}$, trained on their local data, in a privacy-preserving manner.SwiftAgg+can significantly reduce the communication overheads without any compromise on security, and achieve optimal communication loads within diminishing gaps. Specifically, in presence of at most$D=o(N)$dropout users,SwiftAgg+achieves a per-user communication load of$\left({1+\mathcal {O}\left({\frac {1}{N}}\right)}\right)L$symbols and a server communication load of$\left({1+\mathcal {O}\left({\frac {1}{N}}\right)}\right)L$symbols, with a worst-case information-theoretic security guarantee, against any subset of up to$T=o(N)$semi-honest users who may also collude with the curious server. Moreover, the proposedSwiftAgg+allows for a flexible trade-off between communication loads and the number of active communication links. In particular, for$T< N-D$and for any$K\in \mathbb {N}$,SwiftAgg+can achieve the server communication load of$\left({1+\frac {T}{K}}\right)L$symbols, and per-user communication load of up to$\left({1+\frac {T+D}{K}}\right)L$symbols, where the number of pair-wise active connections in the network is$\frac {N}{2}(K+T+D+1)$.

One of the major challenges in using distributed learning to train complicated models with large data sets is to deal with stragglers effect. As a solution, coded computation has been recently proposed to efficiently add redundancy to the computation tasks. In this technique, coding is used across data sets, and computation is done over coded data, such that the results of an arbitrary subset of worker nodes with a certain size are enough to recover the final results. The major drawbacks with those approaches are (1) they are limited to polynomial functions, (2) the number of servers that we need to wait for grows with the degree of the model, (3) they are not numerically stable for computation over real numbers. In this paper, we propose Berrut Approximated Coded Computing (BACC), as an alternative approach, as a numerically stable solution, which works beyond polynomial functions computation and with any number of servers. The accuracy of the approximation is established theoretically and verified by simulation. In particular, BACC is used to train a deep neural network on a cluster of servers, which outperforms alternative uncoded solutions in terms of the rate of convergence.

We propose SwiftAgg, a novel secure aggregation protocol for federated learning systems, where a central server aggregates local models of N distributed users, each of size L, trained on their local data, in a privacy-preserving manner. Compared with state-of-the-art secure aggregation protocols, SwiftAgg significantly reduces the communication overheads without any compromise on security. Specifically, in presence of at most D dropout users, SwiftAgg achieves a server communication load of (T +1)L and a per-user communication load of up to (T+D+1)L, with a worst-case information-theoretic security guarantee, against any subset of up to T semi-honest users who may also collude with the curious server. The key idea of SwiftAgg is to partition the users into groups of size T+D+1, then in the first phase, secret sharing and aggregation of the individual models are performed within each group, and then in the second phase, model aggregation is performed on T +D+1 sequences of users across the groups. If a user in a sequence drops out in the second phase, the rest of the sequence remains silent. This design allows only a subset of users to communicate with each other, and only the users in a single group to directly communicate with the server, eliminating the requirements of 1) all-to-all communication network across users; and 2) all users communicating with the server, for other secure aggregation protocols. This helps to substantially slash the communication costs of the system.

In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that the master node needs to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count-sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count-sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count-sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes. The proposed scheme provides an upper-bound on the recovery threshold as a function of the required accuracy of computation and the probability that the required accuracy can be violated. In addition, it provides an upper-bound on the recovery threshold for the case that the result of the multiplication is sparse, and the exact result is required.

In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that the master node needs to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count-sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count-sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count-sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes.