Providing both scale and security through a single core probabilistic protocol

Distributed systems are typically designed for scale and performance first, which makes it difficult to add security later without affecting the original properties. This paper proposes the design of the Folklore persistent distributed storage system, which adopts an alternative design methodology. Folklore's design relies on a single core protocol for providing both probabilistic scalability and untraceability, the latter being a special notion of probabilistic security. The core protocol is a biologically inspired model of endemic replication that migrates replicas of files among all hosts in a continuous and proactive manner. The emergent behavior is chaotic, meaning that the exact number and location of all replicas of any file is changing all the time. This makes it difficult for an attacker to target any file. Yet, the protocol is scalable - it consumes constant per-host bandwidth, and the number of replicas per file stays close to a small self-stabilizing value. The self-stabilizing value is reached even if only one replica survives a massive attack. The simplicity of the core protocol allows augmentation with mechanisms that allow data integrity, availability, and updatability. We describe the internals of the Folklore system, present attack analysis, and give experimental results from a prototype that shows high resilience to large-scale attacks.