Spinglass

Adaptive Probabilistic Tools for Advanced Networks
 

Some Details

Over a 15-year period, our DARPA-supported Cornell-based research has produced 3 generations of distributed computing tools that focus on introducing guarantees of various kinds to the communications layer and exploiting them in systems that run over these new communications layers.. We believe this effort has been remarkably successful: Our solutions are the basis of Hiper-D (the prototype of a new generation of AEGIS warships and the Navy's NCW communications standard) and were used in a major NSA information gathering and analysis application. Our software tools operate the New York and Swiss Stock Exchanges, the fault-tolerant console clustering architecture of the French Air Traffic Control System (PHIDEAS), the large accelerator ring at CERN, and much of Southwestern Bell Telephone’s cellular network, to name just a few examples. Our success inspired copy-cats: Professor Keith Marzullo, for example, visiting the team that built the Boeing 777 integrated modular avionics architecture (Safebus) was told that the system is basically just a stripped down version of Cornell’s Horus system. Microsoft’s NT Cluster architecture cites our work under its plans for future evolution.  And we're currently helping the Air Force develop its Joint Battlespace Infosphere system.

The fundamental technology underlying these projects involves software support for building communication systems and implementing applications which make use of group membership information, multicasts and synchronization properties. In our work on Isis, Horus and Ensemble, we pioneered the dominant execution model for such group communication (virtual synchrony) and have contributed to standards efforts.  We also innovated in showing how reliable data replication can be used for secure key sharing in multipoint security architectures, including partitionable ones.

But virtual synchrony turns out to have significant limitations, which motivate the Spinglass project.  Virtual synchrony works well for groups of 3 to perhaps 100 participating processes, but is found to be increasingly “fragile” as the size of the group grows.  In particular, data throughput rates become unstable as a group grows large.  For example, a network that can sustain 200 8kbyte messages per second sent from one member of a group with 8 processes in it to the others might only be able to sustain 25 per second to a group of 250 members, when this reliability model is employed.  The scalability problems of virtual synchrony can potentially be overcome, but doing so is challenging and introduces significant complexity.

The Spinglass project is based on a completely new approach in which the core protocols supporting data transmission give probabilistic reliability guarantees.  The multicast formulation of this model is described in our paper Bimodal Multicast, and can be implemented using extremely scalable protocols that guarantee steady throughput even under various forms of attack, and even in very large groups which could have many thousands or even millions of members.  Spinglass seeks to implement a system around this class of protocols, embedding them into the most important of the major software architectures and network operating systems, and to show how applications can be constructed on the resulting probabilistic infrastructure.

In very large settings, multicast raises a "dual" problem of tracking the state of a large set of processes which are all changing their states concurrently.  If we use multicast to solve this kind of problem, we get an n² data flow pattern and obvious scalability issues.  Accordingly, our group has developed Astrolabe, a completely new kind of system for tracking evolving process states and data mining within the resulting data set.  Astrolabe is a peer-to-peer information system that looks like a hierarchical database, but is assembled, like a jigsaw puzzle, from information spread among the participants in the network.  Astroabe scales to huge networks, can be rapidly reconfigured (within seconds) and reports new events within seconds. 

Topics that we hope to explore in the future include:

·        Adaptive behavior, whereby the Spinglass protocols can optimize their patterns of communication to exploit the properties of an underlying network.  We're especially interested in adaptation within the network itself, so as to provide better QoS properties to applications running over the network.

·        Exploiting wireless networks and applying our technology to mobile systems.

·        Using Astrolabe to solve peer-to-peer data mining, system management and distributed control problems in large distributed computing settings,.

·        Development of architectures for management and administration, and control of very large numbers of small devices, such as one might find in a sensor network.

·        Security issues, such as the use of Spinglass for key dissemination and the use of security keys to increase confidence in the Spinglass protocols

·        System issues, including the best ways of presenting Spinglass to the user and of embedding these tools into conventional O/S mechanisms such as distributed shared memory or management information base subsystems.  Presentation in object oriented architectures.

·        Theoretical issues, including both reasoning about the behavior of the protocols and the broader question of designing applications that take direct advantage of the Spinglass properties.

An initial version of the software is available here.  Our publications can be found here.