Workshop on Stochasticity in Distributed Systems

Research Article

Providing both scale and security through a single core probabilistic protocol

  • @INPROCEEDINGS{10.1109/COLCOM.2005.1651260,
        author={Rams\^{e}s Morales and Indranil Gupta},
        title={Providing both scale and security through a single core probabilistic protocol},
        proceedings={Workshop on Stochasticity in Distributed Systems},
        keywords={Bandwidth  Biological system modeling  Chaos  Design methodology  Large-scale systems  Protocols  Prototypes  Resilience  Scalability  Security},
  • Ramsés Morales
    Indranil Gupta
    Year: 2006
    Providing both scale and security through a single core probabilistic protocol
    DOI: 10.1109/COLCOM.2005.1651260
Ramsés Morales1,*, Indranil Gupta1,*
  • 1: University of Illinois at Urbana-Champaign, Department of Computer Science, Urbana, IL 61801
*Contact email:,


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.