.png){kind=icon}
.png){kind=icon}
Return
Vers: Coded Computing System With Distributed Encoding
.png){kind=icon}
PRE
AI
DOI：10.1109/TIT.2025.3591523.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Coded computing has proved to be useful in distributed computing, and has addressed challenges such as straggler workers. We have observed that almost all coded computing systems studied so far consider a setup of one leader and some workers. However, recently emerging technologies such as blockchain, internet of things, and federated learning introduce new requirements for coded computing systems. In these systems, data is generated (and probably stored) in a distributed manner, so central encoding/decoding by a leader is not feasible and scalable. This paper presents a multi-leader distributed coded computing system that consists of k is an element of N data owners and N is an element of N workers, where data owners employ workers to do some computations on their data, as specified by a target function f of degree d is an element of N . As there is no central encoder, workers perform encoding themselves, prior to computation phase. The challenge in this system is the presence of adversarial data owners that do not know the data of honest data owners but cause discrepancies by sending different versions of data to different workers, which is detrimental to local encodings in workers. There are at most beta is an element of N adversarial data owners, and each distributes at most v is an element of N different versions of data. Since the adversaries and their possibly colluded behavior are not known to workers and honest data owners, workers compute tags of their received data, in addition to their main computational task, and send them to data owners in order to help them in decoding. We introduce a tag function that allows data owners to partition workers into sets that previously had received the same data from all data owners. Then, we characterize the fundamental limit of this multi-leader distributed coded computing system, denoted by t & lowast; , which is the minimum number of workers whose work can be used to correctly calculate the desired function of data of honest data owners. We show that t(& lowast;)=v(beta)d(K-1)+1 , and present converse and achievable proofs.
Keywords:
Encoding
Federated learning
Security
Internet of Things
Decoding
Blockchains
Training
Servers
Prevention and mitigation
Polynomials
Distributed systems
blockchains
encoding
fundamental limit
coded computing
adversarial attack
Journal
I
IF:
2.9
Papers:
317
Citations:
0