On the Encoding Process in Decentralized Systems
<|reference_start|>On the Encoding Process in Decentralized Systems: We consider the problem of encoding information in a system of N=K+R processors that operate in a decentralized manner, i.e., without a central processor which orchestrates the operation. The system involves K source processors, each holding some data modeled as a vector over a finite field. The remaining R processors are sinks, and each of which requires a linear combination of all data vectors. These linear combinations are distinct from one sink processor to another, and are specified by a generator matrix of a systematic linear error correcting code. To capture the communication cost of decentralized encoding, we adopt a linear network model in which the process proceeds in consecutive communication rounds. In every round, every processor sends and receives one message through each one of its p ports. Moreover, inspired by linear network coding literature, we allow processors to transfer linear combinations of their own data and previously received data. We propose a framework that addresses the decentralized encoding problem on two levels. On the universal level, we provide a solution to the decentralized encoding problem for any possible linear code. On the specific level, we further optimize our solution towards systematic Reed-Solomon codes, as well as their variant, Lagrange codes, for their prevalent use in coded storage and computation systems. Our solutions are based on a newly-defined collective communication operation we call all-to-all encode.<|reference_end|>
@article{wang2024on,
    title={On the Encoding Process in Decentralized Systems},
    author={Canran Wang and Netanel Raviv},
    journal={arXiv preprint arXiv:2408.15203},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.15203},
    primaryClass={cs.DC cs.IT math.IT}
}