Piggybacking code
A piggybacking code couples code instances by adding functions of earlier messages to later instances while preserving the base code's recovery sets.
The dependency order matters: recover the first message, remove its contribution from the next instance, then decode that instance. With an MDS base code, any k of n nodes still recover all messages. Invertible transformations within individual nodes also preserve those recovery sets. The functions need separate design to reduce repair traffic; the recovery argument alone promises no saving. [1]
Hesela's GF(3) illustration stores (a0,b0), (a1,b1), and (a0+a1,b0+b1+g(a0,a1)) on three nodes. Arithmetic is modulo 3. Each of four tested functions, including a nonlinear product, preserves all 81 messages for every two-node survivor pair: 972 round trips in total. This is a small original recovery example, not an efficient repair construction or a reproduction of a paper's performance results. [3]
An unsafe cyclic variant stores (a0+a1+b0,b0+b1+a0) on the third node instead. Losing the first node leaves only 27 distinct observations for 81 possible messages. For example, messages (0,0,0,0) and (1,0,2,0) become indistinguishable. Arbitrary cross-instance mixing is therefore not covered by the triangular recovery guarantee. This counterexample does not say every cyclic construction fails. [3]
Bandwidth claims also need a helper-set contract. Hulett and Wootters distinguish recovery from any eligible d helpers from recovery using some selected d helpers; their low-substriping impossibility results concern scalar MDS base codes and linear repair. Those restrictions cannot be dropped when comparing piggybacking with general regenerating codes. [2]
Relations
- related
- Hitchhiker, Subpacketization, Maximum distance separable code, Repair-read amplification, Optimal-access repair
Citations
- Rashmi, Shah and Ramchandran. A Piggybacking Design Framework for Read-and Download-efficient Distributed Storage Codes, section II and Appendix.
- Hulett and Wootters. Limitations on the Achievable Repair Bandwidth of Piggybacking Codes with Low Substriping (2017), arXiv:1707.02337v1, sections 3, 5 and 6.
- Hesela: exhaustive GF(3) recovery checks and a cyclic-coupling collision.
Further reading
Sources & caveats
- Primary mathematical sources reviewed beyond their abstracts. This record describes a construction framework, not a default HDFS policy.
- The independently authored finite model is exhaustively enumerated, without sampled data or estimated uncertainty. It checks recovery, not latency, bandwidth savings, disk reads or field reliability.
- Run node --test model.test.js beside model.js; both files are available under /research/piggybacking/. The code introduces no third-party dependencies.