Work in progress: A novel range-queryable distributed data structure
Charles Noyes · 2016
We present the design of a novel data structure. We aim to solve the issue of window/range-based queries of distributed data stores in peer to peer architectures. Traditional models, for example, distributed hash tables (DHTs), are hostile towards window queries because their hashing operations are designed to uniformly distribute stored data across a defined key space; the hashing operations used to achieve this even key distribution inherently erase all characteristics of the target data that could be used to classify it. We solve this problem of erasure by defining a scheme in which higher-order data is mapped to a first-dimensional key space, while preserving locality. The resulting key space is not uniformly distributed, so we define a distributed consensus protocol in which participants in our network agree to target highly populated regions of the key space, through deterministic redistribution. This consensus scheme also provides protection from Sybil attacks, as it is a series of stratified hash-based proof-of-work systems. A peer to peer communication system acts as the underlying network for participants, providing all of the traditional benefits of a P2P architecture, while allowing our solution to operate reliably in the presence of adversaries.