Analog Lagrange Coded Computing
- 2 February 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 2 (1) , 283-295
Abstract
A distributed computing scenario is considered, where the computational power of a set of worker nodes is used to perform a certain computation task over a dataset that is dispersed among the workers. Lagrange coded computing (LCC), proposed by Yu et al., leverages the well-known Lagrange polynomial to perform polynomial evaluation of the dataset in such a scenario in an efficient parallel fashion while keeping the privacy of data amidst possible collusion of workers. This solution relies on quantizing the data into a finite field, so that Shamir's secret sharing, as one of its main building blocks, can be employed. Such a solution, however, is not properly scalable with the size of dataset, mainly due to computation overflows. To address such a critical issue, we propose a novel extension of LCC to the analog domain, referred to as analog LCC (ALCC). All the operations in the proposed ALCC protocol are done over the infinite fields of \mathbb R/ \mathbb C but for practical implementations floating-point numbers are used. We characterize the privacy of data in ALCC, against any subset of colluding workers up to a certain size, in terms of the distinguishing security (DS) and the mutual information security (MIS) metrics. Also, the accuracy of outcome is characterized in a practical setting assuming operations are performed using floating-point numbers. Consequently, a fundamental trade-off between the accuracy of the outcome of ALCC and its privacy level is observed and is numerically evaluated. Moreover, we implement the proposed scheme to perform matrix-matrix multiplication over a batch of matrices. It is observed that ALCC is superior compared to the state-of-the-art LCC, implemented using fixed-point numbers, assuming both schemes use an equal number of bits to represent data symbols.Keywords
All Related Versions
Funding Information
- National Science Foundation (CCF–1763348, CCF–1909771, CCF–1941633)
This publication has 44 references indexed in Scilit:
- Semantically Secure Lattice Codes for the Gaussian Wiretap ChannelIEEE Transactions on Information Theory, 2014
- Highly dynamic distributed computing with byzantine failures2013
- Sharemind: A Framework for Fast Privacy-Preserving Computations2008
- Privacy-preserving Bayesian network structure computation on distributed heterogeneous data2004
- Privacy-preserving distributed mining of association rules on horizontally partitioned dataIEEE Transactions on Knowledge and Data Engineering, 2004
- Tools for privacy preserving distributed data miningACM SIGKDD Explorations Newsletter, 2002
- Probabilistic encryptionJournal of Computer and System Sciences, 1984
- The Fast Fourier Transform1981
- How to share a secretCommunications of the ACM, 1979
- Communication Theory of Secrecy Systems*Bell System Technical Journal, 1949