Programming the Swarm

Swarm Computing
at the University of Virginia
1950s... Programming in the Small
1970s... Programming in the Large
2000s... Programming in the Swarm!

Research Summary
Computing is rapidly moving away from traditional computers. Programs in the future will run on collections of mobile processors that interact with the physical world and communicate over ad hoc networks. We can view such collections as swarms. As with natural swarms, such as a beehive or ant colony, the behavior of a computational swarm emerges from the behaviors of its individual members.
Our research focuses on developing methods for creating, understanding and validating properties of programs that execute on swarms of computing devices. We are striving to create and reason about swarm programs in principled ways. A promising approach is to construct swarm programs by combining primitives. The functional and non-functional behavior of a primitive is described using formal notations. We are investigating techniques based on both experimental and analytical approaches for predicting the functional and non-functional properties of compositions of swarm primitives.
Although the practical applications of swarm computing are in their infancy, there is great potential for useful applications. Successful swarm programming will depend on our ability to reason about swarm programs and construct device programs based on high-level goals. Our research seeks the first steps towards that target.

Cellsim Simulator
RoboCup

In the News

TechNewsWorld, Security: What's Good About Computer Viruses, 5 March 2004. [Archive Copy] [Original Article]
Technology Review, From Artificial Intelligence to Artificial Biology?, November 2003. [Archive Copy] [Original Article]

Recent Papers

Chris Frost. Amorphous Shape Mapping. UVa Fourth-Year Thesis Report. 7 May 2004. [PDF, Web Page]
Lingxuan Hu and David Evans. Using Directional Antennas to Prevent Wormhole Attacks . Network and Distributed System Security Symposium, February 2004. [PDF]
T. Abdelzaher, B. Blum B, Q. Cao, Y. Chen, D. Evans, J. George, S. George, L. Gu, T. He, S. Krishnamurthy, L. Luo, S. Son, J. Stankovic, R. Stoleru and A. Wood. EnviroTrack: Towards an Environmental Computing Paradigm for Distributed Sensor Networks. The 24th International Conference on Distributed Computing Systems. March 2004. (PDF, 8 pages)
Selvin George, David Evans and Steven Marchette. A Biological Programming Model for Self-Healing . First ACM Workshop on Survivable and Self-Regenerative Systems , October 31, 2003. [Abstract] [ PDF, 10 pages]
John Lach, David Evans, Jon McCune, Jason Brandon. Power-Efficient Adaptable Wireless Sensor Networks. Military and Aerospace Programmable Logic Devices (MAPLD) International Conference 2003. September 9-11, 2003. [PDF, 2 page abstract]
Lingxuan Hu and David Evans. Secure Aggregation for Wireless Networks. Workshop on Security and Assurance in Ad hoc Networks. January, 2003. (PDF, PS, 8 pages)
Selvin George, David Evans and Lance Davidson. A Biologically Inspired Programming Model for Self-Healing Systems. Workshop on Self-Healing Systems (WOSS'02). November, 2002. (PDF, PS, 3 pages)
Chenxi Wang, Antonio Carzaniga, David Evans, Alexander L. Wolf. Security Issues and Requirements for Internet-Scale Publish-Subscribe Systems. Hawaii International Conference on System Sciences, January 7-10, 2002. (PDF, 8 pages)

Talks

What Biology Can Teach Us About Security [PPT (warning: 35MB)]
Invited talk at Johns Hopkins University Information Security Institute, 14 November 2003.
Biological Programming Models for Intrusion-Tolerant Systems [PPT (warning 18MB)]
Invited presentation at Workshop on Statistical and Maching Learning Techniques in Computer Intrusion Detection, George Mason University (Fairfax, VA), 24 September 2003.
Biological Programming Models for Robustness and Scalability [PPT (warning: 9MB)]
Panel presentation for Dynammic Data-Driven Application Systems (DDAS) Panel at ACM International Conference on Supercomputing, San Francisco, 23 June 2003.
Programming the Way Biology Programs [PPT]
Panel presentation for NSF Advanced Computation Inspired by Biological Processes Conference, Arlington, VA, 7 April 2003.
Secure Aggregation for Wireless Networks (Lingxuan Hu and David Evans) [PPT]
Workshop on Security and Assurance for Ad hoc Wireless Networks, Orlando, 28 January 2003.
Securing Bits with Atoms (and Vices with Verses) [PPT, PDF]
Short talk in "Outrageous Ideas" session at DIMACS Workshop on Software Security, 6-7 January 2003.
A Biologically Inspired Programming Model for Self-Healing Systems (Selvin George, David Evans and Lance Davidson) [PPT, PDF]
Talk by Selvin George at Workshop on Self-Healing Systems (WOSS 02), 18-19 November 2002.

Software
CellSim — Swarm Program Simulator
Authors: Selvin George, David Evans, Qi Wang, Salvatore Guarnieri, Steven Marchette and Zhannan Zhang
Web Page
ShapeSim — Amorphous Shape Mapping simulator by Chris Frost
Code (.tar.gz)

Funding
Our research is supported by the National Science Foundation through these grants:
ITR: A Framework for Environment-Aware, Massively Distributed Computing (with Tarek Abdelzaher and David Brogan), November 2001.
CAREER: Programming the Swarm, July 2000. (PDF, PS, NSF Page)

People

Faculty

David Evans (Project Leader)
Collaborators: Tarek Abdelzaher, David Brogan

Graduate Students

Lingxuan Hu - first-year PhD student, working on security for swarm programs
Nate Paul - first-year PhD student, working on security for swarm programs
Joel Winstead - fourth-year PhD student, working on Differential Program Analysis

Undergraduate Students

Salvatore Guarnieri - composing swarm programs
Steven Marchette - shape forming primitives and compositions
Qi Wang - modeling environments for swarm programming
Chalermpong Worawannotai - sensor network security
Zhannan (Charles) Zhang - simulating swarm programs

Alumni

Keen Browne - swarm programming for RoboCup (BS 2003, now at Microsoft)
John Calandrino - Applying Computer Network Flow Efficiency Techniques to Vehicular Traffic Systems (BS 2002, now a grad student at Cornell)
Mike Cuvelier - Behavior of Composed Swarm Primitives (BS 2002)
Jacques Fournier - biologically-inspired applications (Summer 2002)
Mike Hogye - Achieving Trade-Offs in Swarm Systems (BS 2002)
Selvin George (MS 2003)
Matt Keller - robustness of cell programs in hostile environments (BS 2002)
John David Loizeaux - describing and predicting device capabilities (BS 2001)
Ami Malaviya - programming creatures from cell primitives (Summer 2002)
Jon McCune - Adaptability in Sensor Networks (BS CPE 2003, entering CMU graduate school in Fall 2003)
Ryan Persaud - primitives for swarm programming (BS 2001, now a grad student at UCSD)
Ankush Seth - Scalability and Communication within Swarm Computing (BS 2003)
Matthew Suhocki - how does biology form abstractions (BS 2003)
Adam Trost - Extendable Swarm Programming Architecture, July 2001. (BS 2001)
Errol McEachron - A System for Synthesizing Swarm Applications (BS 2002)
Bill Oliver - Analyzing Group Behavior: Developing a Tool to Evaluate Swarm Programs (BS 2002)
Weilin Zhong - (MCS 2002, now at Cigital)

Links

Amir Azarbad's notes of getting started with GloMoSim
Selvin George's notes on biological development
Mike Hogye's notes on simulating swarms
Security Issues for Publish-Subscribe Systems
Jon McCune's notes on using GloMoSim