Long-Term Over One-Off: Heterogeneity-Oriented Dynamic Verification Assignment for Edge Data Integrity
Yao Zhao, Youyang Qu, Yong Xiang, Chaochen Shi, Feifei Chen, Longxiang Gao
Abstract
<underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</u> dge <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">I</u> ntelligence (EI), a burgeoning research area, motivates App vendors to cache data replicas on geographically distributed edge servers to deliver better services. On the downside, this benefit also incurs more data integrity audit overhead on App vendors, which calls for more efficient <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</u> dge <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</u> ata <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">I</u> ntegrity (EDI) verification approaches. However, existing EDI solutions totally rely on an implicit <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">resource homogeneity assumption</i> -edge servers have identical resource availability throughout EDI inspection execution in each round-but it rarely holds in reality. The edge servers with insufficient computation and/or communication capacity greatly limit overall EDI verification efficiency from a round perspective. Thus, in this work, we release the identified impractical assumption and accordingly study the EDI <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</u> ynamic <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">V</u> erification <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</u> ssignment (DVA) problem for the first time. The problem aims to maximize the number of data replicas being verified in the long term under the constraints of verification delay in resource-limited environments. In this way, App vendors merely need to check the integrity of selected data replicas in each round for efficiency improvement. Specifically, we first formalize the DVA problem as a delay-constrained long-term stochastic optimization problem and further prove its <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {NP}$</tex-math></inline-formula> -hardness. To resolve the problem efficiently, we decompose it to an easy-to-handle form and then develop a polynomial-time <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</u> riority-based approach named DVA-P with a theoretical analysis of its time complexity and performance bound. Finally, experimental evaluations validate that DVA-P can be seamlessly incorporated into existing EDI solutions to enhance overall verification efficiency while guaranteeing verification performance.