Self Organization and Complex Systems Project List

Introduction

This is a list of concrete projects that deal with self organizion and complex systems.  It was motivated by my attending the Santa Fe Institute's Complex Systems Summer School, and noting that, although they have very interesting, concrete, and effective topics they address, they have not included computing and networking as we consider them in the computing industry.
        http://playground.sun.com/~owen/csss/trip.html
        http://playground.sun.com/~owen/csssid/

This led to proposing to both Sun Labs and to the SFI BusNet, which Sun is a member of, to begin an interest group in this area.
        http://www.santafe.edu/
        http://discuss.santafe.edu/busnetannmtg2000/discuss/
        BusNet Computing <busnetcomp@santafe.edu>

The Lab effort is starting with this list of projects, both as a way to communicate the general idea more exactly, and as a strawman for identification of an initial project here in the lab.

The projects cluster under a few general headings:

  1. Peer-to-Peer systems: As computing systems become more decentralized and networked, prior hierarchic, client-server models break down.  They are hard to administer and are slow to change. Napster, Gnutella, Freenet are popular examples of newer "peer to peer" systems avoiding these weaknesses.  The Stanford - Sun Labs collaboration LOCKSS, which federates loosly aligned library digital collections and maintains their integrity, is another.

    2.     The self organizing part of P2P systems is the focus for the projects in the list.  How can they be managed from the bottom up rather than the top down?  How can they be robust in the face of reduced services or services temporally offline?  How can they form an effective, resilient community?
  2. Self organizing hardware: Computing and networking is moving off the desktop into smaller, simpler, more mobile devices such as phones, cameras, PDAs, automobiles.  Here too, the "network is the computer".  PDAs talk to each other and to home and work networks.  Phones send/receive email.  Cameras take digital pictures, uploading them to a digital picture frame at grandmother's house with a modem.

    3.     The hardware focus for the list is self organizing, self administrating devices on ad-hoc networks.  How do they join and leave sessions?  How are they upgraded?  How do they find services like printers and speakers?  How can they be more efficient and route better?  How can they be robust?
  3. Scaling: Chips are doubling in component count each 18-24 months.  Feature sizes are approaching physical, electrical, and thermal limits.  The systems using these chips are more complex, offering fail safe, scalable, always on, hot pluggable, redundant, clustered operation.  The software running on these systems is extremely complicated, not only in the code, but in its runtime environment (a "site" which is measured in acres and tons), its connectivity (a cluster of systems, often separated geographically), and its life cycle (components being added, removed, upgraded while the system continues to opperate)

    4.     The focus for the list is "doing different" rather than the more traditional "adding more".  Can we build large systems that self organize?  Can recent Scaling in Biology findings help with chip thermal and electrical "metabolism" problems?  Can complex system analysis help move these systems from highly hierarchical design to a swarm or community of more independent elements?
  4. Analysis and Modeling: Understanding aggrigate systems, made of many smaller interacting parts, can be aided via analytic tools that model the systems being studied. Agent modeling systems such as StarLogo, Swarm, and Repast allow constructing a simulated world and letting it "run" as a simulation.  Statistical packages, Java numerics packages, Matlab, Mathematica, and more all make a variety of statistical investigations such as very involved Baysian networks much more approachable than before.  Maturing aggrigate techiques such as Neural Nets and Genetic Algorithms are finding ready use solving "large" problems.  Recently, "Small Worlds" analysis has shed new light upon routing and community anomolies.

    5.     The list suggests a few practical analysis projects which can provide a new way for us to approach problems of interest to the labs.

Projects

This list is a set of strawman proposals and in no way are exhaustive. They do, however, have sufficient "first cut" depth to illustrate the use of complex systems analysis applied to computing and networking.
  1. P2PDir: Multicast Directory Service for P2P.

    2. Napster and others rely on a central server which makes the service dependent and fragile, loosing some of the benefits of pure P2P systems.
        This project distributes the central server via mcast groups to simple, dumb mcast hubs.  It starts with FURI, a Java based Napster, and retools it to use a distributed directory service. It graduates to a general service usable by a wide variety of P2P clients.
        http://www.oreillynet.com/pub/q/p2p_category
  2. Self Organizing Device Net

    3. Devices are becoming networked.  This includes phones, PDAs, home appliances, toys (lego, game systems), cars and so on. Infrastructure devices such as Dallas Semi's TINI promise to put any device on the net.
        This project builds a simple, self organizing network component architecture with no central server.    Instead the components are peers who support and discover each other.  As an extension, this will span selected networks such as home nets, work nets, and car nets.  Possibly extends to friends nets.
        http://playground.sun.com/~owen/critters/
        http://www.labs.bt.com/library/cochrane/telegraph/1999/23-12-99.htm
  3. Self Organizing Communities

    4. Internet Communities still have a centralized server for organizing the individuals within the community. They also are organized around a hierarchical community structure.
        This project builds a tiny community sharing infrastructure requiring no centralized server, and promotes individual as opposed to hierarchy community interactions.  It allows a BOF to organize and flurish independent of servers.
        http://www.businessweek.com/1997/18/b35251.htm
        http://www.rheingold.com/vc/book/
        http://www.calresco.org/sos/sosfaq.htm
  4. P2P Combinatorial Client Framework

    5. Much P2P work depends on a spoke and hub model, using a central server to aggrigate client resources.  Although very efficient, a much greater return is available to combinatorial networks of peers; ones which collaborate directly.
        This project builds a sequence of Combinatoral P2P services, teasing out a general framework for simple serverless services.  It would begin with a simple serverless chat client and progress to more ambitious tasks such as auctions, teasing out a general reusable framework.
        http://www.hyperorg.com/misc/stupidnet.html
  5. Modeling and Simulation

    6. New math and modeling tools are emerging which use various statistical techniques for discovering underlying (emergant) behavior.
        This project will look at one of several short term (6-months) tasks, including:     http://www.swarm.org/
        http://lockss.stanford.edu/
  6. Automotive/JavaCar II

    7. The initial JavaCar prototype focused on building a car device subnet with wireless infrastructure.  The core JavaCar future project focuses on portal services for automotive.  It lacks, however, car to car, peer services based on location.
        This project focuses on services that can be provided with "car clouds"; fast autonomous networks between cars located within a geometric factor of each other.  Initial service: lane change information for safty via PATH (Berkeley research) GPS IP networks.
        http://playground.sun.com/~owen/javacar/
        http://www.path.berkeley.edu/
  7. Random Net Routing

    8. If Kevin Bacon has 6 degrees of separation, why does my router have 12-20 hops for fairly "near" servers?
        This project explores the possibility of improving router connectivity via Small World "random" networks.  (Random networks, such as human acquantances have random jumps which result in far faster closure between any two points within human populations.)
        Note: This project will serve as a springboard into more formal network topology studies such as CAIDA (Cooperative Assoc. for Internet Data Analysis)
        http://www.santafe.edu/sfi/research/focus/networkDynamics/
        http://www.caida.org/
  8. Self Organizing Distributed Disk Storage

    9. Today's computer user accesses their data from multiple sites: Home, Hotel, Work, Conference Rooms, and so on.  Storing this data safely in publicly available way, yet not subject to the control and administration of centralized servers, has become the focus of several projects such as Freenet, LOCKSS, TAZ, Publius and others.
        This project looks into generalizing such schemes witin a Java framework for greater portability and server flexibility. It will initially build a small web replicator for read-only files.  A second project will look into migration of updates for read-write files.
        http://www.cs.nyu.edu/~waldman/publius/
        http://freenet.sourceforge.net/
        http://www.nytimes.com/library/tech/00/07/circuits/articles/27next.html
  9. Cyber Law

    10. Lawrence Lessig's book, Code and Other Laws of Cyperspace introduces the idea of a Constitution as a goal statement, and technical artifacts such as network transparency, proposing that the artifacts contribute to or create the goal .. or render it impossible.
        This project introduces formal connections between cyber "goals" and "attributes".  Examples: The project identifies "knobs" that can be controled for achieving goals.
        http://www.law.stanford.edu/faculty/lessig/
        http://www.law.stanford.edu/e2e/
  10. Peer based Boot and Administration Services

    11. Current infrastructure requirements for adding and removing components from networks are large.
        This project considers the possibility of having an all-peer, friends helping friends, network which provides self organizing replacements for DHCP, DNS, SLP and even HTTP proxy services and other higher level protocols.
        http://www.ietf.org/html.charters/zeroconf-charter.html
  11. Parasitic Ad-Hoc Networks

    12. Ad-Hoc networks are "self-organising/managing" with little structure i.e. nodes come online / go offline / move etc. and the network adjusts itself appropriately. They are typically wireless, but also can be a hybrid of mobile & fixed.  Nodes would be heterogeneous in capabilities. e.g. mobile phones, fridge, car, PDA, people.
        This project begins with a simple wireless adhoc network built from off-the-shelf 802.11 components, with a variety of end node client devices (MP3 player, PDA, ...).  The initial project is  designed to better understand the area, potentially partnering with BT who has approached Sun for collaboration.
        http://www.ics.uci.edu/~atm/adhoc/
        http://www.labs.bt.com/people/heatledj/projects/parasitic/parasitic.html
        http://www.salon.com/tech/feature/2000/12/01/wireless_ethernet/print.html
  12. Scaling in Hardware/Software

    13. Big isn't just more; its different: Designing systems of such massive scale requires aggrigation via Cells, Modules and Methods/Functions.  The coupling between units involves hierarchies of differing speeds and capacities. Getting bigger means getting different, not just larger. (This could be multiple projects, not just one)
        This project seeks ways to analyse, simplify and improve huge systems by focusing on their agrigate behavior and characteristics.  Clearly this is a potentially huge area, thus the initial project focuses on one simple scaling project, bootstrapping into the wider area.  Initial simple projects can include analysing an IDE for decreased "I" and increased deployability, building a simulation environment for large software runtime environments, or a similar simulator for large site clusters.
        http://www.ee.ic.ac.uk/research/information/www/Bobs.html
        http://www.nap.edu/html/making_IT_better/ch3.html