On the Encoding Process in Decentralized Systems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918069442445312 |
|---|---|
| author | Wang, Canran Raviv, Netanel |
| author_facet | Wang, Canran Raviv, Netanel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15203 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Encoding Process in Decentralized Systems Wang, Canran Raviv, Netanel Distributed, Parallel, and Cluster Computing Information Theory 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. |
| title | On the Encoding Process in Decentralized Systems |
| topic | Distributed, Parallel, and Cluster Computing Information Theory |
| url | https://arxiv.org/abs/2408.15203 |