Pith. sign in

REVIEW 2 major objections 4 minor 29 references

On Hierarchical Coded Caching with Offline Users

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Pith's one-line read This paper proves that a hierarchical hotplug placement delivery array (HHPDA) yields a complete two-layer coded caching scheme with offline users, and that t-designs build such arrays.

desk verdict HHPDA framework is a solid unification, but the t-design construction's A3 uniqueness proof is false for lambda > 1 and needs a localized fix. read the letter →

arxiv 2507.00727 v1 pith:ZZDKXWNJ submitted 2025-07-01 cs.IT math.IT

classification cs.ITmath.IT
keywords codedcachingwithofflineusershierarchicalhotplugplacementdeliveryarraycombinatorialt-designsMDScodes
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper is about delivering cached files over a two-layer network—a server, mirror sites with caches, and users with caches—when some users are offline when delivery starts. The authors propose a combinatorial object, the hierarchical hotplug placement delivery array (HHPDA), that bundles the cache-filling pattern and the transmission pattern into one array, and they prove that any HHPDA yields a complete hotplug hierarchical coded caching scheme. They then show that combinatorial t-designs supply a whole family of HHPDAs, giving explicit memory ratios and transmission loads on both layers. The point is to take the previously studied hotplug hierarchical setting, which only worked when every mirror cache had zero memory, and extend it to mirrors that actually store content.

What carries the argument

The load-bearing object is the HHPDA $(Q,B)$, where $Q$ is a two-layer array and $B$ is a single-layer PDA. Its defining projection condition—for every active-user set $\tau$ with $|\tau|=K'$, a row subset $\zeta$ exists with $Q'_{\zeta,\tau} \stackrel{\star}{=} B$—is what certifies that every active user can cancel interference during delivery. In the t-design construction, block membership in a $t$-$(v,k,\lambda)$ design generates the stars: a mirror column gets a star when a group $D_{k_1}$ is contained in a block, and user entries get stars or integers from the block's remaining points. The array $B$ is produced by a prior t-design hotplug PDA construction, and an $[F,F']$ MDS code converts the $F'$ subpackets of every file into the $F$ coded packets that fill caches and travel in XOR messages.

What would settle it

Take a small instance of the construction, such as the $3$\text{-}$(8,4,1)$ design used in the paper's example, and enumerate all $\binom{8}{3}=56$ possible active-user sets; for each set, compute the array $Q'_{\zeta,\tau}$ for every row subset $\zeta$ of size $F'=9$ and check whether it matches $B$ in star positions. If any active-user set admits no such $\zeta$, the claimed theorem fails for that design.

Watch

Extended reading notes

Core claim

The paper's central claim is that a single array object, the hierarchical hotplug placement delivery array (HHPDA), completely describes both phases of a hotplug hierarchical coded caching scheme: an $F \times (K_1 + K_1 K_2)$ array $Q$ with a mirror part $Q^{(0)}$ and per-mirror user parts $Q^{(k_1)}$, together with an $F' \times K'$ placement delivery array $B$. The defining condition (1) requires that for every possible set $\tau$ of $K'$ active users there is a row subset $\zeta \subseteq [F]$ such that the projected star pattern $Q'_{\zeta,\tau}$ matches $B$ in star positions. Given such a pair, Algorithm 1 produces a $(K_1,K_2,K'; M_1,M_2;N)$ hotplug hierarchical scheme with subpacketization $F'$, memory ratios $M_1/N = Z_1/F'$ and $M_2/N = Z_2/F'$, first-layer load $R_1 = |S|/F'$, and second-layer load $R_2$ expressed through the sets $S(j)$ and $S^{(k_2,\zeta)}_{k_1}$. The paper further claims that every $t$-$(v,k,\lambda)$ design with non-repeated blocks yields such an HHPDA with $K' = t$ and $K_2 \le t$, giving explicit caches and loads as in Corollary 2. This removes the zero-mirror-memory restriction of earlier hotplug hierarchical schemes.

Load-bearing premise

The load-bearing premise is Condition (1): no matter which $K'$ users turn out to be active, the projected star pattern of the big array must exactly match the fixed small PDA $B$; if even one active-user set lacks such a row subset, the delivery phase has no certificate that users can cancel interference.

Editorial extensions

If this is right

  • Every valid HHPDA produces a working hotplug hierarchical scheme with the stated memory ratios and loads, so the array object is a complete design tool rather than a special example.
  • Any $t$-$(v,k,\lambda)$ design with non-repeated blocks gives a concrete scheme with $K'=t$, $K_2\le t$, $M_1/N=\lambda_{K_2}/F'$, and $M_2/N=(\lambda-\lambda_{K_2})/F'$.
  • Because only the number $K'$ of active users must be known during placement, not their identities, the scheme covers the offline-user scenarios that break ordinary hierarchical coded caching.
  • Setting $Z_1=0$ in an HHPDA yields the earlier zero-mirror-cache hotplug hierarchical scheme, showing the new definition generalizes that case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct stress test of the construction would be to enumerate every active-user set for a small t-design and verify Condition (1) row by row; the paper proves the condition in general but does not tabulate this check for its examples.
  • The second-layer load formula suggests that the worst-case choice of which users are offline may make one mirror the bottleneck; comparing $R_2$ across active-user distributions would quantify how robust the scheme is to offline patterns.
  • Because the construction forces $K'=t$ and $K_2\le t$, extending the same idea to arbitrary $K'$ or to more than two layers would require a different combinatorial engine, such as covering arrays or product constructions rather than t-designs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper considers a two-layer hierarchical coded caching network in which only K' of the K1K2 users are active during delivery. It introduces a combinatorial object called a hierarchical hotplug placement delivery array (HHPDA), which is meant to describe both placement and delivery for such a system with nonzero mirror caches. Theorem 1 (with Algorithm 1 and Appendix A) claims that any HHPDA yields a hotplug hierarchical coded caching scheme with specified memory ratios and loads. Section V constructs a family of HHPDAs from t-designs, and Theorem 2 (proved in Appendix B) gives their parameters. The paper positions this as the first general treatment of hotplug hierarchical caching with mirror caches, extending the zero-mirror-cache scheme of [24].

Significance. If sound, the HHPDA framework is a useful unification of hierarchical and hotplug coded caching, and the t-design construction would provide concrete schemes with nonzero mirror memory and flexible subpacketization. The definition of HHPDA and the derivation of the caching scheme in Theorem 1 are coherent, and the worked examples are helpful. The main construction, however, relies on a uniqueness claim in Appendix B that is false for designs with lambda > 1; as written, the array produced in Section V is not always an HHPDA. The flaw is local and likely repairable by prefixing each set label with its mirror index, but the proof of Theorem 2 is currently incomplete.

major comments (2)
  1. [Appendix B, proof of A3, Eq. (6)] The assertion that 'if i != i', then equality in (6) is not possible' is false. For the complete 2-(6,3,4) design with K1=6 and K2=1 (so each mirror group is a singleton), the blocks A={1,2,3} and A'={2,3,4} satisfy A\{1} = A'\{4} = {2,3}. Under Eq. (4), this same set-valued entry appears in the subarrays Q(1) and Q(4), so it belongs to both S1 and S4. Definition 6(A3) requires each integer s in S_{k1} to occur exactly in the subarray Q(k1); a symbol in two different mirror subarrays cannot satisfy this. Therefore the array constructed in Section V is not always an HHPDA, and Theorem 2 is not proved for lambda > 1. The construction can be repaired by relabeling each entry as (k1, A\{i}) or by assigning disjoint integer ranges to the different mirrors; this repair leaves |S_{k1}| and the loads of Theorem 2 unchanged, but it is not stated in the paper.
  2. [Section V, construction around Eqs. (3)-(4)] The construction defines entries of Q(k1) as the sets A\{i}, but Definition 6 requires entries to be integers from pairwise disjoint sets S_{k1}. The only guidance given is in Example 4, which says to replace different sets by different integers; that instruction maps equal sets to equal integers and therefore does not prevent cross-mirror collisions when lambda > 1. The proof of A3 is the only place where uniqueness is addressed, and it is incorrect. The authors should specify the relabeling explicitly (e.g., a bijection from the pairs (k1, A\{i}) to integers) and then prove A3 for that relabeling, rather than treating the set-valued entries themselves as the final integers.
minor comments (4)
  1. [Example 3] The MDS code parameters are written inconsistently: the text says a '[9, 14] MDS code' and later a '[7, 14] MDS code'. Since F=14 and F'=9, the code should be a [14,9] MDS code (or, in the notation of Algorithm 1, an [F,F'] code).
  2. [Section V and Theorem 2] The construction states 'Let K2 be an integer such that K2 < t', but Theorem 2 states K2 <= t. If K2 = t is allowed, the proof of A1 and A2 should be checked at this boundary case; otherwise the theorem statement should be aligned with the construction.
  3. [Appendix A, proof of Theorem 1] The sentence 'consider the row indices f' in zeta of the Z1 rows in which stars appear such that q^(0)_{f',k1} = star' is confusing: the set of such rows need not have size Z1 after restriction to zeta, and not every star of B is necessarily a mirror-cache star. The proof should clarify that rows whose B-star comes from the user cache are already available to the user, so only the mirror-star rows with integer labels in S_{k1} require the second set of mirror transmissions.
  4. [Definition 6, condition A3] The wording 'Each integer s in S_{k1} occurs in exactly the subarray Q(k1)' would be clearer as 'does not occur in Q(k1') for any k1' != k1', and no integer from another S_{k1'} occurs in Q(k1)'; the current phrasing leaves the disjointness of the S_{k1} implicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: HHPDA-to-scheme proof is direct, and reliance on [16] is independent prior support, not an assumption of HHPDA.

full rationale

The derivation chain is not circular. Theorem 1 proves Algorithm 1 from the HHPDA definition by spelling out placement, server transmissions, mirror re-encodings, and MDS decodability; no target load or memory value is inserted as an input. Theorem 2's construction defines Q from (3)-(4) and B from (5), then verifies A1-A4 from t-design counts; condition (1) is reduced to the HpPDA property of (P,B), citing [16]. Although [16] is by overlapping authors (C. Rajput and B. S. Rajan), it is a separate, parameter-free construction whose assumptions (a t-design and the B defined in (5)) do not include HHPDA or Theorem 2, so under the review rules it counts as independent evidence rather than circularity. The only load-bearing weakness I see is a correctness gap, not circularity: Appendix B's A3 uniqueness proof asserts that A\{i}=A'\{i'} forces i=i', which is false for designs with λ>1 (e.g., blocks {1,2,3} and {2,3,4} in a 2-(6,3,4) design), so the labels may repeat across mirror subarrays. Repairable by prefixing labels with k1 or restricting to λ=1, but this does not make any claimed result equivalent to its own input.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central construction takes a t-design as input and chooses the integer coefficients a_s by hand; the only free numerical degrees of freedom are those coefficients. The main external inputs are standard design-theory counting lemmas and the prior HpPDA construction of [16]. No new physical entities are introduced.

free parameters (1)
  • a_s coefficients = 0 <= a_s <= lambda_t^s for s = 1..t-1, with sum_{s} a_s C(t,s) > lambda_1
    Chosen in Section V; they determine F', Z', |S| and the load/memory tradeoff. They are hand-picked integer degrees of freedom, not derived from optimality.
assumptions (4)
  • standard math Counting lemmas for t-designs (Lemmas 4 and 5 of [26]) compute the number of blocks containing point sets; these give Z1, Z2 and |S_k1|.
    Used in Appendix B to verify conditions A1 and A2 of the HHPDA definition.
  • standard math An [F,F'] MDS code over a finite field of sufficient size exists, and any F' coded symbols recover the file.
    Algorithm 1 line 2 and Appendix A rely on this for the placement phase and for decoding by all active users.
  • domain assumption The prior HpPDA construction from t-designs in [16] is valid: B is a PDA and (P,B) satisfies the hotplug star-embedding condition.
    Theorem 2's proof delegates the PDA property and condition (1) to Lemma 3 and to the HpPDA result of [16].
  • domain assumption Hotplug system model: during placement only K' is known; at delivery the active user identities and demands become known, and the scheme must work for every K'-subset.
    Section II and Algorithm 1 require this for the 'for each tau' quantifier in Definition 6.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Hierarchical Coded Caching with Offline Users." pith.science (2026). https://pith.science/paper/ZZDKXWNJ

@misc{pith2026250700727,
  author       = {Pith},
  title        = {Pith review of: On Hierarchical Coded Caching with Offline Users},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZZDKXWNJ}},
  note         = {Machine review of arXiv:2507.00727}
}
read the original abstract

This paper studies a two-layer hierarchical network in which some users are offline during the content delivery phase. A two-layer hierarchical network consists of a single server connected to multiple cache-aided mirror sites, and each mirror site is connected to a distinct set of cache-aided users. A scheme for such a hierarchical system with offline users has been proposed recently but considered a special case where all mirror caches have zero memory, which is a significant limitation. We propose an array known as a hierarchical hotplug placement delivery array (HHPDA), which describes the placement and delivery phases of a coded caching scheme for a general two-layer hierarchical network with offline users. Further, we construct a class of HHPDAs using combinatorial t-designs.

Figures

Figures reproduced from arXiv: 2507.00727 by the authors.

Figure 1
Figure 1. The two-layer (K1, K2; M1, M2; N) hierarchical caching system. from combinatorial designs that are used in this paper are also reviewed. A. Placement Delivery Array (PDA) Definition 1. [3] For positive integers K, F, Z and S, an F × K array P = (pj,k)j∈[F ],k∈[K] , composed of a specific symbol ⋆ and S non-negative integers 1, 2, . . . , S, is called a (K, F, Z, S) PDA if it satisfies the following conditions: C1. T… view at source ↗
Figure 2
Figure 2. Arrays (Q, B) in Example 4. in Fig.2. If we replace all the entries represented as different sets by different integers, we get the HHPDA (Q, B) given in Example 2. The following theorem gives the parameters of a class of HHPDAs constructed above using a t-design. Theorem 2. Given a t-(v, k, λ) design with b number of blocks, there exists a (K1, K2, K′ ; F, F′ ;Z1, Z2, Z′ ; S, S1, . . . , SK1 ) HHPDA (Q, B) with K2 … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 28 canonical work pages

  1. [24]

    Hierarchical Ca ching System with Hotplug Model Using HpPDA,

    A. K. Maurya, C. Rajput and B. S. Rajan, "Hierarchical Ca ching System with Hotplug Model Using HpPDA," 2024 IEEE Information Theo ry Workshop (ITW), Shenzhen, China, 2024, pp. 484-489

  2. [16]

    Improved Hotplug Caching Sch emes Using PDAs and t-Designs

    C. Rajput and B. S. Rajan, "Improved Hotplug Caching Sch emes Using PDAs and t-Designs", Available on arXiv: 2311.02856 [cs.IT ], Nov 2023

  3. [1]

    Available on: https://www.ericsson.com/en/reports-and-papers/mobility- report/reports/november-2024

    Ericsson mobility report-November 2024. Available on: https://www.ericsson.com/en/reports-and-papers/mobility- report/reports/november-2024

  4. [2]

    Fundamental Limits of Ca ching,

    M. A. Maddah-Ali and U. Niesen, "Fundamental Limits of Ca ching," in IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856-2867, May 2014

  5. [3]

    On the Placement Del ivery Array Design for Centralized Coded Caching Scheme,

    Q. Y an, M. Cheng, X. Tang and Q. Chen, "On the Placement Del ivery Array Design for Centralized Coded Caching Scheme," in IEEE Transac- tions on Information Theory, vol. 63, no. 9, pp. 5821-5833, S ept. 2017

  6. [4]

    Placement Delivery Array Design Through Strong Edge Coloring of Bipartite Graphs,

    Q. Y an, X. Tang, Q. Chen and M. Cheng, "Placement Delivery Array Design Through Strong Edge Coloring of Bipartite Graphs," i n IEEE Communications Letters, vol. 22, no. 2, pp. 236-239, Feb. 20 18

  7. [5]

    Placement Delivery Arra y Based on Concatenating Construction,

    X. Zhong, M. Cheng and J. Jiang, "Placement Delivery Arra y Based on Concatenating Construction," in IEEE Communications Lett ers, vol. 24, no. 6, pp. 1216-1220, June 2020

  8. [6]

    Placement Delivery Arrays From Co mbinations of Strong Edge Colorings,

    J. Michel and Q. Wang, "Placement Delivery Arrays From Co mbinations of Strong Edge Colorings," in IEEE Transactions on Communic ations, vol. 68, no. 10, pp. 5953-5964, Oct. 2020

Show all 29 references
  1. [7]

    A Framework of Con struct- ing Placement Delivery Arrays for Centralized Coded Cachin g,

    M. Cheng, J. Wang, X. Zhong and Q. Wang, "A Framework of Con struct- ing Placement Delivery Arrays for Centralized Coded Cachin g," in IEEE Transactions on Information Theory, vol. 67, no. 11, pp. 712 1-7131, Nov. 2021

  2. [8]

    Placement Delivery Arrays Based on Co mbinatorial Designs,

    J. Li and Y . Chang, "Placement Delivery Arrays Based on Co mbinatorial Designs," in IEEE Communications Letters, vol. 26, no. 2, pp . 296-300, Feb. 2022

  3. [9]

    Improved Coded Cachin g from Two New Classes of PDAs from t-Designs,

    Rashid Ummer N. T. and B. S. Rajan, "Improved Coded Cachin g from Two New Classes of PDAs from t-Designs," 2024 IEEE Internati onal Symposium on Information Theory (ISIT), Athens, Greece, 20 24, pp. 1568-1573

  4. [10]

    Design of Placement De livery Arrays for Coded Caching With Small Subpacketizations and F lexible Memory Sizes,

    X. Wu, M. Cheng, C. Li and L. Chen, "Design of Placement De livery Arrays for Coded Caching With Small Subpacketizations and F lexible Memory Sizes," in IEEE Transactions on Communications, vol . 70, no. 11, pp. 7089-7104, Nov. 2022

  5. [11]

    Placement Delive ry Array Construction via Cartesian Product for Coded Caching ,

    J. Wang, M. Cheng, K. Wan and G. Caire, "Placement Delive ry Array Construction via Cartesian Product for Coded Caching ," in IEEE Transactions on Information Theory, vol. 69, no. 12, pp. 760 2-7626, Dec. 2023

  6. [12]

    PDA Construction via Union of Cartesian Product Cache Configurations for Coded Caching

    J. Wang, M. Cheng, K. Wan and G. Caire, "PDA Construction via Union of Cartesian Product Cache Configurations for Coded Caching ", Available on arXiv: 2501.11834 [cs.IT], Jan 2025

  7. [13]

    A New Constructio n Structure on Coded Caching with Linear Subpacketization: Non-Half-S um Disjoint Packing

    M. Cheng, H. Wei, K. Wan, and G. Caire,"A New Constructio n Structure on Coded Caching with Linear Subpacketization: Non-Half-S um Disjoint Packing", Available on arXiv: 2501.11855 [cs.IT], Jan 2025

  8. [14]

    On Coded Caching Systems with Of fline Users,

    Y . Ma and D. Tuninetti, "On Coded Caching Systems with Of fline Users," 2022 IEEE International Symposium on Information T heory (ISIT), Espoo, Finland, 2022, pp. 1133-1138

  9. [15]

    Improved Hotplug Caching Sch eme Using PDAs,

    C. Rajput and B. S. Rajan, "Improved Hotplug Caching Sch eme Using PDAs," 2024 IEEE International Symposium on Information Th eory (ISIT), Athens, Greece, 2024, pp. 1574-1579

  10. [17]

    A New Hotp lug Coded Caching Scheme Using PDAs,

    M. Chinnapadamala, C. Rajput and B. S. Rajan, "A New Hotp lug Coded Caching Scheme Using PDAs," 2024 IEEE Information Theory Wo rkshop (ITW), Shenzhen, China, 2024, pp. 478-483

  11. [18]

    On Demand-Private Hotplug Cach ing Sys- tems,

    Y . Ma and D. Tuninetti, "On Demand-Private Hotplug Cach ing Sys- tems," 2024 IEEE International Symposium on Information Th eory (ISIT), Athens, Greece, 2024, pp. 1652-1657

  12. [19]

    Hierarchical Coded Caching,

    N. Karamchandani, U. Niesen, M. A. Maddah-Ali and S. N. D iggavi, "Hierarchical Coded Caching," in IEEE Transactions on Info rmation Theory, vol. 62, no. 6, pp. 3212-3229, June 2016

  13. [20]

    Combinatorial Designs for C oded Caching on Hierarchical Networks,

    Y . Kong, Y . Wu and M. Cheng, "Combinatorial Designs for C oded Caching on Hierarchical Networks," 2023 IEEE Wireless Comm unica- tions and Networking Conference (WCNC), Glasgow, United Ki ngdom, 2023, pp. 1-6

  14. [21]

    Centralized c aching in two-layer networks: Algorithms and limits,

    L. Zhang, Z. Wang, M. Xiao, G. Wu and S. Li, "Centralized c aching in two-layer networks: Algorithms and limits," 2016 IEEE 12 th Interna- tional Conference on Wireless and Mobile Computing, Networ king and Communications (WiMob), New Y ork, NY , USA, 2016, pp. 1-5

  15. [22]

    Reduce Transmission D elay for Caching-Aided Two-Layer Networks,

    K. Wang, Y . Wu, J. Chen and H. Yin, "Reduce Transmission D elay for Caching-Aided Two-Layer Networks," 2019 IEEE Internation al Sympo- sium on Information Theory (ISIT), Paris, France, 2019, pp. 2019-2023

  16. [23]

    Optimal Placem ent Delivery Arrays from t-Designs with Application to Hierarchical Coded Caching

    Rashid Ummer N. T., and B. Sundar Rajan, "Optimal Placem ent Delivery Arrays from t-Designs with Application to Hierarchical Coded Caching", Available on arXiv: 2402.07188 [cs.IT], Feb 2024

  17. [25]

    Coding theory: a first course,

    S. Ling, and C. Xing, “Coding theory: a first course," Cambridge University Press , 2004

  18. [26]

    Combinatorial designs: cons tructions and analysis

    Stinson, Douglas Robert. Combinatorial designs: cons tructions and analysis. V ol. 480. New Y ork: Springer, 2004

  19. [27]

    C. J. Colbourn and J. H. Dinitz, Handbook of combinatori al designs. CRC press, 2006

  20. [28]

    On t-designs

    Ray-Chaudhuri, Dijen K., and Richard M. Wilson. "On t-designs", Osaka J. Math.12, no.1, pp.737-744, 1975

  21. [29]

    Constructions for t-designs and s-re solvable t- designs

    Trung, Tran van. "Constructions for t-designs and s-re solvable t- designs." Designs, Codes and Cryptography, pp.1-12, Jun 20 24

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.