Case Studies for Robust Self-Organizing Systems
From Self-Organization Wiki
Contents
- 1 Individual Systems
- 2 Collective Systems
- 3 Engineered Systems
- 4 Parliament
- 5 Robustness vs. Fault Tolerance
- 6 Human Body
- 7 Wikipedia
- 8 Fireflies
- 9 Ant Nest
- 10 P2P Networks (Example: File Sharing)
- 11 Self-organizing traffic lights
- 12 Self-organizing network routing
- 13 Viruses and worms (whether this is truly a self-organizing network was left open for discussion)
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.
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
- Mechanism
- randomly explore the surroundings
- leave trails from foodsources back to the nest (via pheromones)
- follow the pheromone trail with the highest pheromone concentration -
- but allow for deviations from that path with a certain probability
- 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
- Mechanism
- 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?