The Optimality of Allocation Methods for Bounded Disagreement Search Queries: The Possible and the Impossible

摘要

Data Allocation on multiple I/O devices manifests itself in many computing systems, both centralized and distributed. Data is partitioned on multiple I/O devices and clients issue various types of queries to retrieve relevant information. In this paper, we derive necessary and sufficient conditions for a data allocation method to be optimal for two important types of queries: partial match and bounded disagreement search queries. We formally define these query types and derive the optimality conditions based on coding-theoretic arguments. Although these conditions are fairly strict, we show how to construct good allocation methods for practical realistic situations. Not only are the response times bounded by a small value, but also the identification of the relevant answer set is efficient.