Case Studies for Robust Self-Organizing Systems

Individual Systems

• Starfish, human body

• Cope with lost/damaged parts
• Regrow/relearn capabilities (self-healing) for survivability
• Adaptable

• • It's not clear if self-organization occurs with external excitement (disturbance) or just centralized control; e.g., if the healing/adaptation happens because the genes are coded that way or they evolve and adapt.

Collective Systems

• Wealth distribution (pareto), file sharing

• Cope with environmental conditions, resource value, government interventions, wars, closed platforms, law suits
• Regroup, redistribute, reopen
• Adaptable

• Self-organization with external disturbance, but no centralized control.

Engineered Systems

• Routing, TCP behavior

• Cope with environmental conditions, disasters, unknowns
• Regroup, reroute, retransmit
• Adaptable

• Self-organization with external disturbance, but no centralized control.

National Parliament

• Well-defined structure and function
  • Mandate distribution is defined by distributions of citizens' votes
  • Goal is to make joint decisions in the interest of the citizens (or own electors) by voting

The parliament is (up to a certain minimum size) robust against instant and repeating (spreading)

• failures/removals of nodes (i.e., representatives at the voting procedure)
• faulty/unexpected/unwanted behavior of nodes, (e.g., personal decisions made under lack of information)
• malicious behavior of nodes (corruption; voting against clear interest of citizens, but in pure interests of a person/small group/party; not disclosing decision-important information)

It shows the following properties:

• Self-healing due to iterated renewals based on elections
• External observation from mass media

• Each representative may act as attractor, detractor, or neutral node
• Adaptive to change in the social environment (e.g., role of women in the societies)
• Shows the emergent property of issued laws initiated by some voters, set up by its representatives, and valid for all citizens
• Reflects attributes of dependability: availability, reliability, safety, maintainability, and security

Robustness vs. Fault Tolerance

• Fault Tolerance
  • Functionality is not harmed
  • Tolerance with respect to random failures

• Robustness
  • includes fault tolerance
  • robustness against intended failure(malicous elements)

• Systems cannot be robust against completly unknown events
  • Systems can only be robust with respect to known/defined perturbations
  • Definition of robustness has to include assumptions

Human Body

• Immune system of human body
  • Adapts to new bacteria/viruses
• Body recovers from little accidents
  • Decentralized reproduction of cells

Wikipedia

• Self-organizing pool of information
• Fault Tolerance against faulty information
  • Users correct random errors
• Robust against malicous information to a certain degree
  • Vulnerable to distributed attacks (large number of users), e.g. members of political party insert malicous information about opponent

Fireflies

• Popular example from biology
• Blink together to achieve synchronization
• For adaption a single firefly observes blinking of neighbors (local information)
• Robust against failures of individual fireflies
  • Assumption: Network stays in connected state

Ant Nest

• Goal
  • dependably find food and bring it back to the nest
• Mechansim
  • randomly explore the surroundings leave trails from foodsources back to the nest (via pheromone)
  • follow the pheromone trail with the highest pheromone concentration - but allow for deviations from that path
• Robustness
  • against dynamic food location changes (food churn)
  • against obstacles appearing on the path
  • against ants disappearing
• Problems
  • degradation of robustness if high concentration of artificial pheromones are deposited

P2P Networks (Example: File Sharing)

• Goal
  • provide data items to participating peers
• Mechansim
  • distributed storage of data items on the peer nodes
  • distributed reference infos on the peer nodes (normally via DHT)
• Robustness
  • against leaving/failing and joining peer nodes (node churn)
  • against bottlenecks in underlying IP network
• Problems
  • attacks
  • manipulations
  • malicious nodes

Self-organizing traffic lights

• Waiting time depends on number of cars waiting (only sensor being a single camera)
• No explicit communication between the lights - communication media = cars
• Emergence of grups of cars that propagate on a green wave
• Robust to changes in traffic situation, break-down of single lights (if they fall into a fail-safe state, such as a flashing yellow light or shutting down completely).
• Discussion: Depends a lot on the density of the traffic (jamming situations). Explicit communication for traffic may be desirable, even though that may go against the self-organizing nature of the system.

Self-organizing network routing

• Any routing protocol broadcasting to discover a specific route (example: choose route which contains the packet with the highest TTL)
• Ant routing
• Robustness: break-down of nodes/lines, overload in parts of the network are handled in a self-organized way.
• Limits: Package loss (needs to be handled by the upper layers)

Viruses and worms (whether this is truly a self-organizing network was left open for discussion)

• Worms start out as sngle "agent" that broadcasts itself throughout the network
• Infected network-node is closed and can't be infected again.
• Is this "epidemic" distribution a kind of self-organization?
  • Multiple agents
  • Distribution
• But:
  • Emergence of structure?
  • Adaptability to changes from the environment?