Search

Cadambe and Lyu 2021 presents an erasure coding based algorithm called CausalEC that ensures causal consistency based on cross-object erasure coding. This note shows that the algorithm presented in Cadambe and Lyu 2021 and the main ideas behind it are in essence the same as the algorithm developed in Lyu, Cadambe, Ali and Urgaonkar 2018.

Secure aggregation is a critical component in federated learning, which enables the server to learn the aggregate model of the users without observing their local models. Conventionally, secure aggregation algorithms focus only on ensuring the privacy of individual users in a single training round. We contend that such designs can lead to significant privacy leakages over multiple training rounds, due to partial user selection/participation at each round of federated learning. In fact, we empirically show that the conventional random user selection strategies for federated learning lead to leaking users' individual models within number of rounds linear in the number of users. To address this challenge, we introduce a secure aggregation framework with multi-round privacy guarantees. In particular, we introduce a new metric to quantify the privacy guarantees of federated learning over multiple training rounds, and develop a structured user selection strategy that guarantees the long-term privacy of each user (over any number of training rounds). Our framework also carefully accounts for the fairness and the average number of participating users at each round. We perform several experiments on MNIST and CIFAR-10 datasets in the IID and the non-IID settings to demonstrate the performance improvement over the baseline algorithms, both in terms of privacy protection and test accuracy.

We introduce Info-Commit, an information-theoretic protocol for polynomial commitment and verification. With the help of a trusted initializer, a succinct commitment to a private polynomial $f$ is provided to the user. The user then queries the server to obtain evaluations of $f$ at several inputs chosen by the user. The server provides the evaluations along with proofs of correctness which the user can verify against the initial commitment. Info-Commit has four main features. Firstly, the user is able to detect, with high probability, if the server has responded with evaluations of the same polynomial initially committed to. Secondly, Info-Commit provides rigorous privacy guarantees for the server: upon observing the initial commitment and the response provided by the server to $m$ evaluation queries, the user only learns $O(m^2)$ symbols about the coefficients of $f$. Thirdly, the verifiability and the privacy guarantees are unconditional regardless of the computational power of the two parties. Lastly, Info-Commit is doubly-efficient in the sense that in the evaluation phase, the user runs in $O(\sqrt{d})$ time and the server runs in $ O(d)$ time, where $d-1$ is the degree of the polynomial $f$.

Motivated by applications of distributed storage systems to cloud-based key-value stores, the multi-version coding problem has been recently formulated to efficiently store frequently updated data in asynchronous decentralized storage systems. Inspired by consistency requirements in distributed systems, the main goal in multi-version coding is to ensure that the latest possible version of the data is decodable, even if the data updates have not reached some servers in the system. In this paper, we study the storage cost of ensuring consistency for the case where the data versions are correlated, in contrast to previous work where data versions were treated as being independent. We provide multi-version code constructions that show that the storage cost can be significantly smaller than the previous constructions depending on the degree of correlation between the different versions of the data. Our achievability results are based on Reed-Solomon codes and random binning. Through an information-theoretic converse, we show that our multi-version codes are nearly-optimal in certain regimes., Comment: arXiv admin note: substantial text overlap with arXiv:1708.06042 We will update a new version of arXiv:1708.06042 instead