Communication Cost for Updating Linear Functions when Message Updates are Sparse: Connections to Maximally Recoverable Codes
© 2018 IEEE. We consider a communication problem in which an update of the source message needs to be conveyed to one or more distant receivers that are interested in maintaining specific linear functions of the source message. The setting is one in which the updates are sparse in nature, and where...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135830 |
| _version_ | 1826209956450271232 |
|---|---|
| author | Prakash, N Medard, Muriel |
| author_facet | Prakash, N Medard, Muriel |
| author_sort | Prakash, N |
| collection | MIT |
| description | © 2018 IEEE. We consider a communication problem in which an update of the source message needs to be conveyed to one or more distant receivers that are interested in maintaining specific linear functions of the source message. The setting is one in which the updates are sparse in nature, and where neither the source nor the receiver(s) is aware of the exact difference vector, but only know the amount of sparsity that is present in the difference vector. Under this setting, we are interested in devising linear encoding and decoding schemes that minimize the communication cost involved. We show that the optimal solution to this problem is closely related to the notion of maximally recoverable codes (MRCs), which were originally introduced in the context of coding for storage systems. In the context of storage, MRCs guarantee optimal erasure protection when the system is partially constrained to have local parity relations among the storage nodes. In our problem, we show that optimal solutions exist if and only if MRCs of certain kind (identified by the desired linear functions) exist. We consider point-to-point and broadcast versions of the problem and identify connections to MRCs under both these settings. For the point-to-point setting, we show that our linear-encoder-based achievable scheme is optimal even when non-linear encoding is permitted. The theory is illustrated in the context of updating erasure coded storage nodes. We present examples based on modern storage codes, such as the minimum bandwidth regenerating codes. |
| first_indexed | 2024-09-23T14:37:11Z |
| format | Article |
| id | mit-1721.1/135830 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:37:11Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1358302022-04-01T16:18:07Z Communication Cost for Updating Linear Functions when Message Updates are Sparse: Connections to Maximally Recoverable Codes Prakash, N Medard, Muriel © 2018 IEEE. We consider a communication problem in which an update of the source message needs to be conveyed to one or more distant receivers that are interested in maintaining specific linear functions of the source message. The setting is one in which the updates are sparse in nature, and where neither the source nor the receiver(s) is aware of the exact difference vector, but only know the amount of sparsity that is present in the difference vector. Under this setting, we are interested in devising linear encoding and decoding schemes that minimize the communication cost involved. We show that the optimal solution to this problem is closely related to the notion of maximally recoverable codes (MRCs), which were originally introduced in the context of coding for storage systems. In the context of storage, MRCs guarantee optimal erasure protection when the system is partially constrained to have local parity relations among the storage nodes. In our problem, we show that optimal solutions exist if and only if MRCs of certain kind (identified by the desired linear functions) exist. We consider point-to-point and broadcast versions of the problem and identify connections to MRCs under both these settings. For the point-to-point setting, we show that our linear-encoder-based achievable scheme is optimal even when non-linear encoding is permitted. The theory is illustrated in the context of updating erasure coded storage nodes. We present examples based on modern storage codes, such as the minimum bandwidth regenerating codes. 2021-10-27T20:29:32Z 2021-10-27T20:29:32Z 2018 2019-06-21T12:34:20Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135830 en 10.1109/TIT.2018.2865750 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Prakash, N Medard, Muriel Communication Cost for Updating Linear Functions when Message Updates are Sparse: Connections to Maximally Recoverable Codes |
| title | Communication Cost for Updating Linear Functions when Message Updates are Sparse: Connections to Maximally Recoverable Codes |
| title_full | Communication Cost for Updating Linear Functions when Message Updates are Sparse: Connections to Maximally Recoverable Codes |
| title_fullStr | Communication Cost for Updating Linear Functions when Message Updates are Sparse: Connections to Maximally Recoverable Codes |
| title_full_unstemmed | Communication Cost for Updating Linear Functions when Message Updates are Sparse: Connections to Maximally Recoverable Codes |
| title_short | Communication Cost for Updating Linear Functions when Message Updates are Sparse: Connections to Maximally Recoverable Codes |
| title_sort | communication cost for updating linear functions when message updates are sparse connections to maximally recoverable codes |
| url | https://hdl.handle.net/1721.1/135830 |
| work_keys_str_mv | AT prakashn communicationcostforupdatinglinearfunctionswhenmessageupdatesaresparseconnectionstomaximallyrecoverablecodes AT medardmuriel communicationcostforupdatinglinearfunctionswhenmessageupdatesaresparseconnectionstomaximallyrecoverablecodes |