Difference between revisions of "Case Studies for Robust Self-Organizing Systems"
From Self-Organization Wiki
(New page: ==Parliament== The parliament is (up to a certain minimum size) robust against instant and repeating (spreading) * failures/removals of nodes (i.e., representatives) * faulty/unexpected/...) |
m (→P2P Networks (Example: File Sharing)) |
||
(5 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
+ | ==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== | ==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) | The parliament is (up to a certain minimum size) robust against instant and repeating (spreading) | ||
− | * failures/removals of nodes (i.e., representatives) | + | * failures/removals of nodes (i.e., representatives at the voting procedure) |
− | * faulty/unexpected/unwanted | + | * faulty/unexpected/unwanted behavior of nodes, (e.g., personal decisions made under lack of information) |
− | * malicious | + | * 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: | It shows the following properties: | ||
* Self-healing due to iterated renewals based on elections | * Self-healing due to iterated renewals based on elections | ||
− | * External observation from mass | + | * External observation from mass media |
− | + | ||
− | |||
− | |||
− | |||
* Each representative may act as attractor, detractor, or neutral node | * Each representative may act as attractor, detractor, or neutral node | ||
− | * Adaptive to change in the social environment | + | * 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 | * 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== | ==Ant Nest== | ||
* Goal | * Goal | ||
** dependably find food and bring it back to the nest | ** dependably find food and bring it back to the nest | ||
− | * | + | * Mechanism |
− | ** randomly explore the surroundings leave trails from foodsources back to the nest (via | + | ** randomly explore the surroundings |
− | ** follow the pheromone trail with the highest pheromone concentration - but allow for deviations from that path | + | **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 | * Robustness | ||
** against dynamic food location changes (food churn) | ** against dynamic food location changes (food churn) | ||
Line 36: | Line 102: | ||
* Goal | * Goal | ||
** provide data items to participating peers | ** provide data items to participating peers | ||
− | * | + | * Mechanism |
** distributed storage of data items on the peer nodes | ** distributed storage of data items on the peer nodes | ||
** distributed reference infos on the peer nodes (normally via DHT) | ** distributed reference infos on the peer nodes (normally via DHT) | ||
Line 46: | Line 112: | ||
** manipulations | ** manipulations | ||
** malicious nodes | ** malicious nodes | ||
− | |||
==Self-organizing traffic lights== | ==Self-organizing traffic lights== |
Latest revision as of 18:31, 15 July 2009
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?