CasGroup - User contributions [en]

Main Page

2011-03-06T19:40:08Z

Admin: Changed protection level for "Main Page" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))

<big>'''Welcome to the CAS Group Wiki.'''</big>

[[Image:Emergence.gif|left|Weak Emergence]] The CAS Group is a community for people interested in the science and theory of [[Complex_Adaptive_System|complex adaptive systems]] (CAS), and in their [[Basic_System_Theory|basic principles]] and [[Applied_System_Theory|applied principles]]. CASs are perhaps the most interesting complex systems, they are not only 'complex' - they are diverse and made up of multiple interconnected elements - and 'adaptive' - they have also the capacity to change and learn from experience. The basic element of CAS theory is the [[Agent-Based_Model|agent-based model]]. The logo describes the phenomenon of [[Emergence|emergence]], as it can be observed for example in swarms and flocks. Like [[Self-Organization|self-organization]] it is a essential principle in the theory of complex adaptive systems.

There are also pages about the [[Chaos_in_the_mind|role of chaos in neural networks]], [[Self-Consciousness|self-consciousness]], [[Beyond_AI|new forms of AI]], [[New_Kinds_of_Science|new kinds of science]], and new forms of technology and interesting philosophical questions as well, for
example if we can describe the mind as a [[Society_of_Mind|society of agents]].

Sources and related projects are [http://en.wikipedia.org Wikipedia], [http://www.cscs.umich.edu/~crshalizi/notebooks/ C.R. Shalizi's Notebooks], and the [http://pespmc1.vub.ac.be/ Principia Cybernetica]. Related Wikis are for example the [http://www.swarm.org/wiki/Main_Page SwarmWiki] specialized on Swarm Intelligence and agent-based modelling, the [http://intersci.ss.uci.edu/wiki/index.php/Main_Page InterSciWiki] on cross-disciplinary and complexity sciences research,
the [http://www.aaai.org/AITopics/pmwiki/pmwiki.php AITopics Library], and the [http://www.scholarpedia.org/ Scholarpedia]. Recommendable resources are also [http://mathworld.wolfram.com/ Wolfram MathWorld] and [http://atlas.wolfram.com/ The Wolfram Atlas of Simple Programs].

At this time the Wiki contains [[Special:Allpages|{{NUMBEROFARTICLES}} articles.]] A complete overview about [[Special:Allpages|all pages]] and [[Special:Categories|all categories]] also exists.

CasGroup:Community portal

2011-03-06T14:46:53Z

Admin: Created page with "Take a look at the complete overview of all pages and all categories."

Take a look at the complete overview of [[Special:Allpages|all pages]] and [[Special:Categories|all categories]].

Collective intelligence

2011-03-06T13:03:57Z

Admin: moved Collective intelligence to Collective Intelligence: wording

#REDIRECT [[Collective Intelligence]]

Collective Intelligence

2011-03-06T13:03:57Z

Admin: moved Collective intelligence to Collective Intelligence: wording

'''Collective intelligence''' is a shared or group intelligence that emerges from the collaboration and competition of many individuals in a group. A group of people can act smarter than a single individual. A [[Crowd|crowd]] for example can show surprising levels of wisdom ("The Wisdom of the Crowd").

== Links ==

* Wikipedia entry for [http://en.wikipedia.org/wiki/Collective_intelligence collective intelligence]

[[Category:Psychology]] [[Category:Social Systems]] [[Category:Collective Processes]]

Main Page

2011-02-26T12:29:29Z

Admin:

Main Page

2011-02-26T12:28:51Z

Admin:

<big>'''Welcome to the CAS Group Wiki.'''</big>

[[Image:Emergence.gif|left|Weak Emergence]] The CAS Group is a community for people interested in the science and theory of [[Complex_Adaptive_System|complex adaptive systems]] (CAS), and in their [[Basic_System_Theory|basic principles]] and [[Applied_System_Theory|applied principles]]. CASs are perhaps the most interesting complex systems, they are not only 'complex' - they are diverse and made up of multiple interconnected elements - and 'adaptive' - they have also the capacity to change and learn from experience. The basic element of CAS theory is the [[Agent-Based_Model|agent-based model]]. The logo describes the phenomenon of [[Emergence|emergence]], as it can be observed for example in swarms and flocks. Like [[Self-Organization|self-organization]] it is a essential principle in the theory of complex adaptive systems.

There are also pages about the [[Chaos_in_the_mind|role of chaos in neural networks]], [[Self-Consciousness|self-consciousness]], new [[Beyond_AI|forms of AI]], [[New_Kinds_of_Science|new kinds of science]], and new forms of technology and interesting philosophical questions as well, for
example if we can describe the mind as a [[Society_of_Mind|society of agents]].

Sources and related projects are [http://en.wikipedia.org Wikipedia], [http://www.cscs.umich.edu/~crshalizi/notebooks/ C.R. Shalizi's Notebooks], and the [http://pespmc1.vub.ac.be/ Principia Cybernetica]. Related Wikis are for example the [http://www.swarm.org/wiki/Main_Page SwarmWiki] specialized on Swarm Intelligence and agent-based modelling, the [http://intersci.ss.uci.edu/wiki/index.php/Main_Page InterSciWiki] on cross-disciplinary and complexity sciences research,
the [http://www.aaai.org/AITopics/pmwiki/pmwiki.php AITopics Library], and the [http://www.scholarpedia.org/ Scholarpedia]. Recommendable resources are also [http://mathworld.wolfram.com/ Wolfram MathWorld] and [http://atlas.wolfram.com/ The Wolfram Atlas of Simple Programs].

At this time the Wiki contains [[Special:Allpages|{{NUMBEROFARTICLES}} articles.]] A complete overview about [[Special:Allpages|all pages]] and [[Special:Categories|all categories]] also exists.

Main Page

2011-02-16T22:22:55Z

Admin:

<big>'''Welcome to the CAS Group Wiki.'''</big>

[[Image:Emergence.gif|left|Weak Emergence]] The CAS Group is a community for people interested in the science and theory of [[Complex_Adaptive_System|complex adaptive systems]] (CAS), and in their [[Basic_System_Theory|basic principles]] and [[Applied_System_Theory|applied principles]]. CASs are perhaps the most interesting complex systems, they are not only 'complex' - they are diverse and made up of multiple interconnected elements - and 'adaptive' - they have also the capacity to change and learn from experience. The basic element of CAS theory is the [[Agent-Based_Model|agent-based model]]. The logo describes the phenomenon of [[Emergence|emergence]], as it can be observed for example in swarms and flocks. Like [[Self-Organization|self-organization]] it is a essential principle in the theory of complex adaptive systems.

There are also pages about the [[Chaos_in_the_mind|role of chaos in neural networks]], [[Self-Consciousness|self-consciousness]], new [[Beyond_AI|forms of AI]], new kinds of science, and new forms of technology and interesting philosophical questions as well, for
example if we can describe the mind as a [[Society_of_Mind|society of agents]].

Sources and related projects are [http://en.wikipedia.org Wikipedia], [http://www.cscs.umich.edu/~crshalizi/notebooks/ C.R. Shalizi's Notebooks], and the [http://pespmc1.vub.ac.be/ Principia Cybernetica]. Related Wikis are for example the [http://www.swarm.org/wiki/Main_Page SwarmWiki] specialized on Swarm Intelligence and agent-based modelling, the [http://intersci.ss.uci.edu/wiki/index.php/Main_Page InterSciWiki] on cross-disciplinary and complexity sciences research,
the [http://www.aaai.org/AITopics/pmwiki/pmwiki.php AITopics Library], and the [http://www.scholarpedia.org/ Scholarpedia]. Recommendable resources are also [http://mathworld.wolfram.com/ Wolfram MathWorld] and [http://atlas.wolfram.com/ The Wolfram Atlas of Simple Programs].

At this time the Wiki contains [[Special:Allpages|{{NUMBEROFARTICLES}} articles.]] A complete overview about [[Special:Allpages|all pages]] and [[Special:Categories|all categories]] also exists.

Meme

2011-02-16T21:06:03Z

Admin: Created page with "A meme identifies ideas or beliefs that are transmitted from one person or group of people to another. The concept comes from an analogy: as genes transmit biological in..."

A meme identifies ideas or beliefs that are transmitted from one person or group of people to another. The concept comes from an analogy: as [[Gene|genes]] transmit biological information, memes can be said to transmit idea and belief information.

== Reconstruct a Mind ==

Can we (re-)construct minds from different
parts or pieces ? Is there a blueprint for
a soul (whatever that is)? If [[Gene|genes]] are
blueprints used to construct bodies, then
maybe [[Meme|memes]] can be considered as
blueprints to construct [[Mind|minds]].

== Links ==

* Wikipedia entry for [http://en.wikipedia.org/wiki/Meme meme]

Mind

2011-02-16T21:04:47Z

Admin:

The '''mind''' is simply what the brain does. It is related to the [[Self]] and is considered
as responsible for one's thoughts and feelings.
It is an abstract concept which describes all of the brain's conscious and unconscious cognitive processes.
Although it does not exist as a single, unified substance, it emerges from the coordinated action of a group
of agents and acts to orchestrate them in turn. In this sense, the coordinated hallucination of people
is often associated with team spirit or god, while the coordinated hallucination of neurons is associated
with the personal spirit, the soul or the mind.

There are are many theories of the mind and its function,
the [[Society_of_Mind|society of mind]] approach tries to
explain the mind as a society of agents (or CAS).

== Reconstruct a Mind ==

Can we (re-)construct minds from different
parts or pieces ? Is there a blueprint for
a soul (whatever that is)? If [[Gene|genes]] are
blueprints used to construct bodies, then
maybe [[Meme|memes]] can be considered as
blueprints to construct minds.

An autobiography is maybe the thing which
is perhaps the most similar to such a
blueprint. One difference to genetic blueprints
is the temporal relationship: genetic blueprints
exist before the life of the individual, whereas
autobiographies exist only after the life of
the individual. During our life, our personality
is reinforced and we become more like ourselves.

Yet autobiographies of other people and
ancestors can be used to "build new souls".
"Holy books" are often autobiographies of
famous prophets or represent the history of
whole countries and cultures. Maybe stories,
fairy tales, myths, "holy books" and belief systems
in general (or all set of rules and ideas which specify
the right kind of behavior) can be considered
as "memetic blueprints" to build souls? Are
they the scripts which contain the rules that
direct our plays?

If a body is a 3-dimensional entity, how much
dimensions does a mind or a soul have? How many
memes are needed to "make a mind"? I would
say it depends. Maybe at least as many dimensions
as roles which a person plays. A person plays
many roles, related to nationality, language, family,
work, etc. Each role is associated with a bundle
of behavior patterns or a set of memes. Do you
agree?

== Links ==

* Wikipedia entry for [http://en.wikipedia.org/wiki/Mind Mind]

[[Category:Consciousness]]

Mind

2011-02-16T21:02:34Z

Admin:

The '''mind''' is related to the [[Self]] and is considered as responsible for one's thoughts and feelings.
It is an abstract concept which describes all of the brain's conscious and unconscious cognitive processes.
Although it does not exist as a single, unified substance, it emerges from the coordinated action of a group
of agents and acts to orchestrate them in turn. In this sense,

: god = coordinated hallucination of people
: mind = coordinated hallucination of neurons

There are are many theories of the mind and its function,
the [[Society_of_Mind|society of mind]] approach tries to
explain the mind as a society of agents (or CAS).

== Reconstruct a Mind ==

Can we (re-)construct minds from different
parts or pieces ? Is there a blueprint for
a soul (whatever that is)? If [[Gene|genes]] are
blueprints used to construct bodies, then
maybe [[Meme|memes]] can be considered as
blueprints to construct minds.

An autobiography is maybe the thing which
is perhaps the most similar to such a
blueprint. One difference to genetic blueprints
is the temporal relationship: genetic blueprints
exist before the life of the individual, whereas
autobiographies exist only after the life of
the individual. During our life, our personality
is reinforced and we become more like ourselves.

Yet autobiographies of other people and
ancestors can be used to "build new souls".
"Holy books" are often autobiographies of
famous prophets or represent the history of
whole countries and cultures. Maybe stories,
fairy tales, myths, "holy books" and belief systems
in general (or all set of rules and ideas which specify
the right kind of behavior) can be considered
as "memetic blueprints" to build souls? Are
they the scripts which contain the rules that
direct our plays?

If a body is a 3-dimensional entity, how much
dimensions does a mind or a soul have? How many
memes are needed to "make a mind"? I would
say it depends. Maybe at least as many dimensions
as roles which a person plays. A person plays
many roles, related to nationality, language, family,
work, etc. Each role is associated with a bundle
of behavior patterns or a set of memes. Do you
agree?

== Links ==

* Wikipedia entry for [http://en.wikipedia.org/wiki/Mind Mind]

[[Category:Consciousness]]

Main Page

2011-02-11T21:49:24Z

Admin: Protected "Main Page" ([edit=sysop] (indefinite) [move=sysop] (indefinite))

<big>'''Welcome to the CAS Group Wiki.'''</big>

[[Image:Emergence.gif|left|Weak Emergence]] The CAS Group is a community for people interested in the science and theory of [[Complex_Adaptive_System|complex adaptive systems]] (CAS), and in their [[Basic_System_Theory|basic principles]] and [[Applied_System_Theory|applied principles]]. CASs are perhaps the most interesting complex systems, they are not only 'complex' - they are diverse and made up of multiple interconnected elements - and 'adaptive' - they have also the capacity to change and learn from experience. The basic element of CAS theory is the [[Agent-Based_Model|agent-based model]]. The logo describes the phenomenon of [[Emergence|emergence]], as it can be observed for example in swarms and flocks. Like [[Self-Organization|self-organization]] it is a essential principle in the theory of complex adaptive systems.

There are also pages about the [[Chaos_in_the_mind|role of chaos in neural networks]], [[Self-Consciousness|self-consciousness]], new [[Beyond_AI|forms of AI]], new kinds of science, and new forms of technology and interesting philosophical questions as well, for
example if we can describe the mind as a [[Society_of_Mind|society of agents]].

Sources and related projects are [http://en.wikipedia.org Wikipedia], [http://www.cscs.umich.edu/~crshalizi/notebooks/ C.R. Shalizi's Notebooks], and the [http://pespmc1.vub.ac.be/ Principia Cybernetica]. Related Wikis are for example the [http://www.swarm.org/wiki/Main_Page SwarmWiki] specialized on Swarm Intelligence and agent-based modelling, the [http://intersci.ss.uci.edu/wiki/index.php/Main_Page InterSciWiki] on cross-disciplinary and complexity sciences research,
the [http://www.aaai.org/AITopics/pmwiki/pmwiki.php AITopics Library], and the [http://www.scholarpedia.org/ Scholarpedia]. At this time the Wiki contains [[Special:Allpages|{{NUMBEROFARTICLES}} articles.]] A complete overview about [[Special:Allpages|all pages]] and [[Special:Categories|all categories]] also exists.

Loose Coupling

2011-02-11T21:46:21Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Loose coupling''' means low dependency between two [[System|systems]].
It is a way to achieve high [[Fault Tolerance|fault tolerance]]
and often used in association with [[Web Service|Web Services]] and [[Service-Oriented_Architecture|Service-Oriented Architecture (SOA)]].
Loosely coupled systems are not strongly connected with each other,
they have only a minimal coupling between the components in the system.
They are obviously the opposite of tightly coupled systems with
strong dependencies between the components.
In loosely coupled systems, there is a low probability that changes
within one module or component will create unanticipated changes
within other modules or components.
The modular approach to design and develop systems
associated with loose coupling makes the applications more
agile and flexible, and enables quicker change.
A common way to achieve low coupling is to use interfaces
and messages: one module does not have to be concerned
with the internal implementation of another module,
and interacts with another module with a stable
interface.

== References ==

[http://dev2dev.bea.com/pub/a/2004/02/orchard.html Achieving Loose Coupling], David Orchard

Emergent Entity

2011-02-11T21:46:18Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Emergent entities''' are properties, patterns or substances which 'arise' out of more fundamental entities through an [[Emergence|emergence]] process. A property of a system is emergent, if it is not a property of any fundamental element. Emergent entities are not reducible. Although they arise out of more fundamental items, they are 'novel' or 'irreducible' with respect to them. Emergent properties are dependent on underlying processes, and yet independent from underlying processes. This is the paradox of emergence.

The difference between the different terms is:

* '''Emergent Property''': A property of a system is emergent, if it is not a property of any fundamental element. If a property is not necessary (or does not appear) in the description of all properties of the fundamental elements, elementary actors or basic building blocks, it can only be an emergent property.

* '''Emergence''': Emergence is the appearance of emergent properties on a higher level of organization without central organizer. It can be observed in complex systems due to the pattern of interactions between the elements of a system over time.

* '''Entity''': Emergent properties lead to the appearance of new entities and objects on a larger scale. They play an important role in the definition of general terms like being, entity and substance. Russ Abbott defined an entity as follows: "An aggregation counts as an entity if it has emergent properties", see his talk [http://abbott.calstatela.edu/PapersAndTalks/EmergenceAndEntities.pdf Emergence and Entities]

== Agent based Models ==

The basic [[Agent-Based Model|agent-based model]]s explain the emergence of fundamental properties:

* [[Boids Model]]: swarms
* [[Dissemination Model]]: culture
* [[Segregation Model]]: ghettos and segregation
* [[Tribute Model]]: power
* [[El_Farol_Bar_Model|El Farol Bar Model]]: chaos

== Links ==

* [http://plato.stanford.edu/entries/properties-emergent/ Emergent Properties] at SEP
* Talk from Russ Abbott about [http://abbott.calstatela.edu/PapersAndTalks/EmergenceAndEntities.pdf Emergence and Entities]

Edge of Chaos

2011-02-11T21:46:13Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Edge of Chaos''' is a loosely defined concept and a phrase coined by Christopher Langton in 1990. The phrase originally refers to an area in the range of a variable, λ (lambda), which was varied while examining the behavior of a [[Cellular Automata|cellular automata]] (CA). As λ varied, the behavior of the CA went roughly through a [[phase transition]] of behaviors. It is a general, vague and ambiguous phrase, sometimes used in a more or less concrete context, but more often it is used as a coarse metaphor for a phase transition, a critical point with maximal complexity or a boundary between order and disorder, stability and instability, regularity and irregularity, organization and chaos. In other words it marks the boundary between order and chaos.

[[Image:Edge_of_Chaos.png|right|thumb|400px|Edge of Chaos]]

== General meaning ==

In the sciences in general, the phrase has come to refer to a metaphor that some physical, biological, economic and social systems operate in a region between order and disorder (characterized by randomness or chaos), where the [[Complexity|complexity]] is maximal. In this general case it describes a point of transition between order and chaos, between stable, solid, frozen and crystalline behavior on one side and unstable, chaotic and noisy behavior on the other side. The LINUX community for example is sometimes addressed as
[http://www.firstmonday.org/issues/issue5_3/kuwabara/ A bazaar at the edge of chaos].

The edge of chaos is the point between order and
chaos with the highest complexity where the most
interesting things happen. The complexity has a price,
since this point is often also the most unstable point,
where things are barely stable due to the clash of opposite
forces. The edge of chaos in this sense is the point
with the highest complexity and lowest stability.

== Definitions ==

=== To or At the Edge ? ===

The following frequent statement is obviously very imprecise: many complex adaptive systems, including life itself, seem to evolve naturally towards a regime that is delicately poised between order and chaos. Do living system evolve ''to'' the edge of chaos, or preferably ''at'' the edge of chaos?

The term edge of chaos refers originally to an area in the range of λ, which was varied while examining the behavior of a cellular automata (CA). As λ varied, the behavior of the CA went through a phase transition of behaviors. For a given CA rule table, λ can be computed as follows: one state q is chosen arbitrarily to be quiescent for a CA. The λ value of a given CA rule is then the fraction of non-quiescent output states in the rule table.

For a two-state CA, λ=1/2 is a critical point or "phase transition" between two phases, one phase near lambda=0 where are cells have value 0, and one phase near λ=1 where are cells have value 1. This definition of the "edge of chaos" would be identical or similar to a critical point.

If you consider only λ in the range 0 <= λ <= 1/2, because every CA with λ > 1/2 corresponds to a CA with λ < 1/2 after interchanging the roles of black and white cells, you can observe another "edge of chaos". As λ increases, CA roughly go through the four basic Wolfram classes in this order: I (fixed), II (periodic), IV (complex), III (chaotic). Class IV can be seen as the edge of chaos at the boundary between class II (order) and III (chaos), see
[http://classes.yale.edu/Fractals/CA/CAPatterns/Langton/Langton.html]

If the four Wolfram classes are ill-defined, as [http://www.ics.uci.edu/~eppstein/ca/wolfram.html Eppstein] argues, it is doubtful that this definition still valid. There are roughly two useful definitions of "edge of chaos", one in the more specific sense of ''Self-organized criticality'' and ''Phase-Transition'', the other in the more general and descriptive sense of border between order and chaos:

{{SelfOrg}}

=== Self-organized criticality ===

The first definition is a specific definition related to [[Self-Organized Criticality|self-organized criticality]]:
The edge of chaos can be found at a critical point with strong fluctuations and
scale-free correlations. Systems can cross this point more or less rapidly, but
usually they evolve to this point, i.e. they are '''evolving to the edge of chaos'''.
A sandpile for example evolves naturally towards a certain shape if we add grains to it,
until it has a certain critical slope. This point can often be measured precisely (for example
lambda=1/2 for Langton's parameter, a certain critical slope, or a critical temperature like 100 Degrees).

The criticial point is point of high complexity, because
it combines stability and instability: the system evolves
automatically to a certain state (which increases stability,
certainty, and predictability), but at these state chain
reactions can lead to avalanches and cascades of any size
(which increases instability, uncertainty and unpredictability).
Thus the criticial point in self-organized criticality is a
"metastable" and complex state characterized by instability in
stability, uncertainty in certainty, or unpredictability in
predictability.

=== Phase Transition ===

The second definition is a more general and less precise definition: The edge of chaos is
the general point of highest complexity between order and disorder or regularity and chaos.
It defines the small region with highest complexity between order (stability, no change or
periodic change, rigid or fixed structures, too static) and chaos (instability, constant
or aperiodic change, no rigid or fixed structures, too noisy). The evolution at this point,
'''at the edge of chaos''', produces naturally the most complex structures in
[[Adaptation|adaptive]] systems, because the complexity in the environment reaches its
peak here. This point can often not be measured precisely (for example lambda somewhere
between 0 and 1/2, except the transition or accumulation point on the period doubling
route to chaos.)

As you go from the unified, ordered and regular phase stepwise to the diverse, disordered and
chaotic phase, you reach a complex phase transition point between unity and diversity which
can be characterized as unity in diversity (or vice versa).
Similar to the peak of complexity at the border between order and chaos, we get in fact
complex small-world networks if we add randomness to order in regular networks, and complex
scale-free networks if we add order to randomness (through preferential attachment) in
random networks, see also the entry about [[Complex_Network|complex networks]].

=== Comparison ===

The first definition (1) related to self-organized criticality describes a point
and a state where the system evolves to, where the overall system is evolving ''to''
the edge of chaos, whereas the second definition (2) related to phase transitions
describes a point and place in an environment where other systems can evolve, where
systems are evolving ''at'' the edge of chaos.

What both definitions or "edge of chaos" types have in common is the following:

* the behavior of the system can change abruptly at this critical point
* point of high(est) complexity: neither a diverse system with extreme disorder (for example a gas), nor a unified system with extreme order (for example a crystal or magnet) is very complex. Complexity reaches its peak between order and disorder, in (1) as instability in stability, and in general in (2) as diversity in unity
* Power-law behavior: critical exponents and scale-free correlations in (1) and scale-free distributions of events in (2)
* a delicate balance between two opposite complementary forces, for example one organizing and regulatory force, and one random or chaotic force, or one expanding and one contracting force, or one attracting and one repulsive force

At the edge of chaos local microscopic influcences can have far-reaching macroscopic effects.
Therefore another definition maybe a system near a point with sensitive dependence on initial
conditions ("[[Butterfly Effect]]"). A small step ("over the edge") can have a large and
dramatic effect, or nearly no effect at all. The macroscopic behavior of such a system
can change dramatically as a result of small changes in microscopic conditions.

== Examples ==

=== Game of Life ===

The activity in the Game of Life is on the edge of chaos in several
ways. It is on the edge between growing and shrinking, between expansion
and contraction. Some clusters grow, others shrink.
In the Game of Life you can observe all different forms of behavior:
[http://llk.media.mit.edu/projects/emergence/life-zoo.html stable objects],
[http://llk.media.mit.edu/projects/emergence/life-intro.html propagating objects] like gliders or spaceships and
[http://llk.media.mit.edu/projects/emergence/on-the-edge.html instable objects] like the R Pentomino.
A Glider has five active cells, and propagates virtuously and silently
through the empty space. The R Pentomino has a five-square shape, too.
It looks very simple, but it creates a wild flurry of activity. Both
structures seem to be near the edge of chaos: with a change in only
two cells you can switch between both, but the one creates a chaotic
proliferation of activity, while the other remains harmless.

=== Habitable Zones ===

Within each galaxy there is an area that could
support life, a ring around the center called
the "Galactic Habitable Zone" (GHZ) (see the
Scientific American article "Refugees of Life in a Hostile Universe" from
Gonzalez et al. (2001) [http://atropos.as.arizona.edu/aiz/teaching/a204/etlife/SciAm01.pdf]).
Within each plantery system there is a again an
area that could support life, the planetary
or "Circumstellar Habitable Zone" (CHZ).
On each planet, there is again an area that
could support life: life is only possible near
the surface, and at the surface in turn at the
edge between icy and hot regions, between fluid
and dry areas. One could classify all these habitable
areas as the "edge of chaos" between order and chaos.

==Emergence of rules and evolution of laws==

The "edge of chaos" is related to the evolution of laws
and to the [[Emergence|emergence]] of rigid rules from lax rules.
Lax rules are similar to a liquid phase, rigid rules are
similar to a solid phase, and they are connected by
a critical point or a phase transition.
To speak in social terms, if only the interests of the
individual count (the liquid phase with lax rules), we get too
much chaos and anarchy, disorder and disorientation, and no
coherent structure or order can emerge. If only the interests of
the group matter (the solid phase with rigid rules), we got
too much order, stagnation and suppression. A suitable
compromise between the interests of the individual and
the interests of the group can therefore possibly be found
at the "edge of chaos".

Selfish agents and people will recognize the need
for conventions, rules, norms and laws (most) notably
if their personal interests are heavily violated.
People will cry for a law against theft or murder if
it happens to themselves, if their things are robbed
or relatives are murdered. They will long for rigid and
strict traffic rules if they are seriously injured
or killed in a traffic accident. They will appreciate culture
and long for justice and peace after times of trouble, after
"dark ages" with constant conflicts, battles and wars
(the "warring states period" in ancient China, the Middle
Ages in Europe, the Dark Ages in ancient Greece,
the "intermediate periods" in ancient Egypt). In other
words, conflicts, battles and wars will increase the threshold
of constraints and restrictions that people are willing to
accept.

Yet too much order, organization, and stagnation is just
as bad as too much chaos, terror, and anarchy. Too much
tyranny will increase the wish for freedom. The interests
of the individuals can be violated if there is too litte
order and organization (Hobbes' war of everyone against everyone)
or too much order (tyranny and bureaucracy). Rules, norms and
laws will evolve in an oscillating process at this "edge
of chaos" between too much chaos and too much order, as a
compromise between the interests of the group and the
interests of the individual.

If we consider for example the transition from loosely
coupled tribes to the first cultures and states, we can not
observe a clear self-organization into more and more complexity.
People in the Bronze Age didn't sit together and said "we need
to create a society based on parliamentary democracy". What we
observe is first war, fight and terror. War of everybody
against everybody. After one has won, usually a kingship,
a tyranny or dictatorship is established. That's a transition
from chaos and anarchy to chiefdom and hierarchical order.
Because many people are not satisfied with tyranny or
dictatorship, eventually a revolution breaks free, chaos
prevails, and the same process starts all over again.

==Articles==

* Christopher G. Langton. "Computation at the edge of chaos:phase transitions and emergent computation". ''Physica D'', '''42''', 1990.
* [http://cse.ucdavis.edu/~cmg/papers/wlboac.pdf What Lies Between Order and Chaos ?], James P. Crutchfield in Art and Complexity, J. Casti, editor, Oxford University Press (2002).
* [http://cse.ucdavis.edu/~cmg/papers/CompOnset.pdf Computation at the Onset of Chaos], James P. Crutchfield and K. Young, in ''Entropy, Complexity, and the Physics of Information'', W. Zurek, editor, SFI Studies in the Sciences of Complexity, VIII, Addison-Wesley, Reading, Massachusetts (1990) pp. 223-269.
* [http://cse.ucdavis.edu/~evca/Papers/DynCompEdge.pdf Dynamics, Computation, and the 'Edge of Chaos': A Re-examination], M. Mitchell, J. P. Crutchfield, and P. T. Hraber, In Complexity: Metaphors, Models, and Reality. G. Cowan, D. Pines, and D. Melzner, editors. SFI Series in the Sciences of Complexity, volume XIX, Reading, MA: Addison-Wesley, 1994: 497-513.
* [http://www.cs.pdx.edu/~mm/RevEdge.html Revisiting the Edge of Chaos], Melanie Mitchell, Peter T. Hraber, and James P. Crutchfield, ''Complex Systems'', '''7''':89--130, 1993.

==Links and References==

* Ko Kuwabara, [http://www.firstmonday.org/issues/issue5_3/kuwabara/ A Bazaar at the Edge of Chaos], First Monday, volume 5, number 3 (2000)

* Shalizi's notebook entry on [http://cscs.umich.edu/~crshalizi/notebooks/edge-of-chaos.html the Edge of Chaos]

[[Category:Basic Principles]]

Cognitive dissonance

2011-02-11T21:46:10Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Cognitive dissonance''' is an uncomfortable and unpleasant feeling caused by holding two contradictory ideas simultaneously. It is a psychological term denoting the mental state in which two or more incompatible or contradictory ideas are both held to be true. The "ideas" or "cognitions" in question may include attitudes and beliefs, the awareness of one's behavior, and facts. The theory of cognitive dissonance proposes that people have a motivational drive to reduce dissonance by changing their attitudes, beliefs, and behaviors, or by justifying or rationalizing their attitudes, beliefs, and behaviors.

In an [[Agent-Based Model]], cognitive dissonance can be described as a conflict between agents. Conflicts and contradictions are unpleasant for the mind, society or population as a whole, because they damage the group integrity. They lead to confusion and displeasure, while the mind wants to gain insights and pleasure.

Cognitive dissonance is the opposite of [[Cognitive consonance|cognitive consonance]].

== Links ==

* Wikipedia page on [http://en.wikipedia.org/wiki/Cognitive_dissonance cognitive dissonance]

AOSE

2011-02-11T21:46:05Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Agent Oriented Software Engineering''' (AOSE) is the name for the attempt to construct and engineer
new forms of flexible and robust software with [[Agent|Agents]] and [[Multi-Agent System|Multi-Agent Systems]].
Without doubt agents are well suited to simulate complex systems. If you can use them
to build and construct complex software systems in order to achieve
a kind of [[Agent-Based Computing|agent-based computing]] is still an
open question.

== Problems and Challenges ==

=== Basic Problems ===

There are many problems related to AOSE. The first problem is for instance an agreement about the basic terms:
what is an [[Agent|agent]], what characteristics define an [[Agent|agent]], what types of architectures are possible,
what forms of organization are available, what kind of methodology is suitable...
There is no doubt that you can use object-oriented software to construct useful software
applications. One can also use object-oriented software to construct agents, but if it is possible
to build useful applications out of software agents is still another question.
What forms of software you can create in turn with agents is still controversial. Probably
these types of software are different from traditional applications in software engineering.
Yet the situation is even worse: there are not only many problems related to AOSE,
AOSE itself is more a name for a problem than a solution.

=== A Name for a Problem ===

Each technology for building software has advantages and disadvantages. Agent technology
is not an exception, it has advantages and positive properties, but there are also many
pitfalls and drawbacks, see the section "Potentials and Pitfalls" of the [[Agent|agent]] page.
The advantage of traditional software techniques is the "easy" analysis, engineering and design
of predictable object-oriented systems with [[Unified Modeling Language|UML]]. The drawbacks
are brittleness and rigidity, low fault-tolerance and low scalability.
Agents and [[Multi-Agent System]]s offer on the contrary robustness, scalability and
fault-tolerance, but they go hand in hand with heavy problems in engineering, design
and predictability.

Thus [[Agent|agents]] are a promising approach to get rid of traditional drawbacks
like brittleness and low scalability, but they introduce (often unnoticed) new problems
through the backdoor: the engineering and design of
[[Multi-Agent System|Multi-Agent Systems]], especially those with desirable
[[Emergence|emergent]] properties is notoriously difficult. Therefore
"Agent Oriented Software Engineering" or AOSE is more a name for a problem than
a name for a solution, like many other names as for example
"Agent Based Software Engineering" (ABSE), "Agent Based Software Development" (ABSD),
"Agent Oriented Programming" (AOP), or "Interaction Oriented Programming" (IOP).
The problem in AOSE is familiar and well-known to many researchers: "I
have a Multi-Agent System, but what is its purpose and function ?"
If an agent decides itself what it needs to do, how can we make sure that
it does something useful or something we want it to do?

The '''Engineering of Self-Organizing Applications''' ([[ESOA|ESOA]]) is
like AOSE a name for a central problem, not its solution. The problem in ESOA
is this: "I know some self-organizing systems in nature, but how do I engineer a
specific system for a certain problem?" In other words "How do I organize
a system which is allowed to organize itself?" Whereas AOSE focuses
on the conflict between autonomy and service-delivery (between agents and
objects, autonomy vs. heteronomy), ESOA is about the conflict
between engineering and emergence (between imposed purpose and independent goals,
or planned organization vs. self-organization).

== Proposed Solutions and Methodologies ==

=== Demands and Methodologies ===

There is a huge number of agent systems and frameworks, which have
been developed because they are certainly an interesting research object.
The AOSE problem arises if we want to do something useful with them.
It manifests itself in the huge number and diversity of
AOSE Methodologies. These methodologies are not a real solution
of the AOSE problem, otherwise we would have a huge number
of useful new applications. They document a demand for a solution,
and the demand for AOSE is mainly self-made: I have build a
[[Multi-Agent System]], but what do I do with it?
The huge number of different methodologies seem to prove that there
is a big need for such a methodology, yet it points at the same
time to the existence of a major obstacle:
engineering (in form of software applications) and
[[Autonomy|autonomy]] (in form of [[Multi-Agent System|Multi-Agent Systems]]
(MAS) with emergent properties) don't fit well together.

There are two possible potential solutions for this core
problem 'autonomy' of AOSE: (1) to limit autonomy by external
constraints, i.e. to organize MASs through roles and
organizational structures, or (2) to limit autonomy by internal
constraints, i.e. let the system organize itself and try to apply the
concept of self-organization, which is known as [[ESOA]].
Most methodologies try the first way.
The most favorite and famous methodologies are
ADELFE, GAIA, Tropos, MASSIVE, MaSE, Prometheus.
Each country has proposed at least one methodology:

* French, '''ADELFE''' (Atelier de Développment de Logiciels à Fonctionnalité Emergente) from Bernon and Gleizes [Ber03]
* British, '''GAIA''' 1st version from Wooldridge, Jennings & Kinny [Woo00], refined version from Zambonelli, Jennings & Wooldridge [Zam03]
* Italian/Canadian, '''Tropos''' 1st Version from Bresciani, Perini, Giorgini, Giunchiglia, Mylopoulos, [Bre01], refined version from Kolp, Giorgini and Mylopoulos [Kol02]
* German, '''MASSIVE''' (Multi Agent Systems Iterative View Engineering) Lind [Lin01]
* American, '''MaSE''' (Multiagent Systems Engineering) from Wood and DeLoach [DeLo99]
* Australian, '''Prometheus''' from Padgham and Winikoff [Pad02]

Unfortunately, [[Autonomy|autonomy]] is one of the major characteristics
of agents. If we limit autonomy too much, we have no longer a multi-agent system.
[[Autonomy]] makes [[Multi-Agent System|Multi-Agent Systems]] and
agent oriented systems interesting, but it also is the reason why they
are not always useful and often very prolematic.

=== A possible general solution ===

A possible solution to the problem of AOSE is the combination of modern agent-oriented
techniques and classic object-oriented software. If agents are used for
self-management and other [[Self-Star_Properties|self-* properties]],
a combination of [[Agent|agents]] and servies can be a promising extension of
normal software, especially for distributed applications (i.e. applications in
[[Distributed_System|distributed systems]]). Such a combination can potentially
solve the AOSE conflict between autonomy (agents) and heteronomy (objects and services).
Agents can be used to achieve autonomy, services to guarantee service-delivery.
Since [[Agent|agents]] (esp. mobile agents) are usually part of a distributed system,
[[Distributed_System|distributed systems]], and especially distributed software
applications are a natural application for agent oriented software engineering.

== References and Links ==

=== Books ===

Proceedings of the Workshops AOSE 2000, AOSE 2001, AOSE 2002, AOSE 2003 and AOSE 2004,
published by Springer as Lecture Notes in Computer Science (LNCS) Vol. 1957,
2222, 2585, 2935, and 3382. These Workshops were hosted by the International
Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS).

=== General Articles ===

* [http://citeseer.ist.psu.edu/242172.html Agent-Oriented Software Engineering], Nicholas R. Jennings, Michael Wooldridge (2000)

* [http://citeseer.ist.psu.edu/wooldridge00agentoriented.html Agent-Oriented Software Engineering: The State of the Art], Michael Wooldridge, Paolo Ciancarini (2000)

* [http://citeseer.ist.psu.edu/zambonelli04challenges.html Challenges and Research Directions in Agent-Oriented Software Engineering], Franco Zambonelli (2004)

=== Methodology Articles ===

[Ber03]
ADELFE, a Methodology for Adaptive Multi-Agent Systems Engineering
Carole Bernon, Marie-Pierre Gleizes, Sylvain Peyruqueou, Gauthier Picard
Proceedings of the 3rd International Workshop on
"Engineering Societies in the Agents World III" (ESAW 2002),
Paolo Petta, Robert Tolksdorf, Franco Zambonelli (Eds.) LNCS 2577, Springer (2003) 156-169

[Bre01]
Paolo Bresciani, Anna Perini, Paolo Giorgini, Fausto Giunchiglia, John Mylopoulos
A knowledge level software engineering methodology for agent oriented programming.
In Proceedings of the 5th International Conference on Autonomous Agents, pages 648–655.
ACM Press (2001)

[DeLo99]
Scott A. DeLoach
Multiagent Systems Engineering: A Methodology And Language for Designing Agent Systems (1999)
Procs. Agent-Oriented Information Systems '99 (AOIS'99), Seattle, WA, USA, 1 May (1999) 1999

[Kol02]
Manuel Kolp, Paolo Giorgini, John Mylopoulos.
A goal-based organizational perspective on multiagent architectures.
In Intelligent Agents VIII: Agent Theories, Architectures, and Languages,
LNAI 2333, Springer (2002) 128–140

[Lin01]
Jürgen Lind
Iterative Software Engineering for Multiagent Systems - The MASSIVE Method.
LNCS 1994, Springer, 2001

[Pad02]
Lin Padgham and Michael Winikoff,
Prometheus: A Methodology for Developing Intelligent Agents,
Proceedings of the First International Joint Conference
on Autonomous Agents and Multi-Agent Systems (AAMAS 2002),
ACM Press (2002) 37-38

[Woo00]
Michael Wooldridge, Nicholas R. Jennings, David Kinny,
The Gaia methodology for agent-oriented analysis and design.
Journal of Autonomous Agents and Multi-Agent Systems, Vol. 3 No. 3 (2000) 285–312

[Zam03]
Franco Zambonelli, Nicholas R. Jennings, Michael Wooldridge,
Developing multiagent systems: the Gaia Methodology.
ACM Transactions on Software Engineering and Methodology 12(3) (2003) 317-370

Scaling Laws

2011-02-11T21:46:02Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

Geoffrey B. West and James H. Brown discovered that allometric
'''scaling laws''', including the 3/4 power law for metabolic rates,
are characteristic of all organisms.
One factor which increases biological diversity is body size,
which varies over 21 orders of magnitude in biological organisms.
Yet some universal rates and regular relationships stay constant.
The metabolic rate of biological life-forms scales approximately as
the 3/4-power of mass from complex molecules up to the largest
multicellular organisms.

Similarly, time-scales (such as lifespans and growth-rates) and
sizes (such as genome lengths, RNA densities, and tree heights)
scale as power laws with exponents which are typically simple
multiples of 1/4.
West and Brown have shown that these 1/4 power scaling laws
follow from underlying principles embedded in the dynamical
and geometrical structure of space-filling, fractal-like,
hierarchical branching networks.

These scaling laws can be applied to artificial structures as
well. Like biological systems, counties and cities have evolved
branching networks that transport a variety of resources.

== Links ==

* Wikipedia Entry for [http://en.wikipedia.org/wiki/Power_law Power Law]

== Papers ==

* Geoffrey B. West, James H. Brown, and Brian J. Enquist [http://biology.unm.edu/jhbrown/Documents/Publications/WestBrown&Enquist1997S.pdf A General Model for the Origin of Allometric Scaling Laws in Biology], Science Vol 276 April (1997) 122-126

* Geoffrey B. West and James H. Brown, [http://biology.unm.edu/jhbrown/Documents/Publications/West&Brown2004PT.pdf Life's Universal Scaling Laws], Physics Today, September (2004) 36-42

[[Category:Basic Principles]]

Flexibility

2011-02-11T21:45:57Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Flexibility''' is defined as the ability to react to changes in the environment,
for example to expand or contract in response to external requirements.
It is the opposite of stiffness and brittleness, and related to [[Scalability|scalability]], [[Adaptation|adaptation]] and [[Robustness|robustness]].

[[Category:Applied Principles]]

Organic Computing

2011-02-11T21:45:54Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Organic Computing''' is a German Initiative launched by the two
German national computer societies GI (German Informatics Society) and
ITG (Informationstechnische Gesellschaft), and a group of researchers
from three German universities (Universität Hannover, Universität Karlsruhe
and Universität Augsburg). It defines an Organic Computing
system as "a technical system which adapts dynamically to the current conditions of its
environment. It is self-organizing, self-optimizing, self-configuring, self-healing,
self-protecting, self-describing, self-explaining and context-aware”.
Thus it is very similar to IBM's [[Autonomic Computing|autonomic computing]] Initiative,
which also is based on systems with [[Self-* Properties]].
Like Autonomic Computing, it is a vision for future information
processing systems.

While Autonomic Computing focuses mainly on servers, computing centers
and large-scale Internet software,
Organic Computing aims at the development of robust, flexible
and highly adaptive embedded systems, [[Ubiquitous Computing]] and
Hardware (Embedded Processors, Microcontroller, etc.).

== History - Organic IT vision ==

The idea of organic computing and [[Autonomic Computing|autonomic computing]] goes
back to research reports from Forrester. In a report from April 2002 about
''Organic IT'', the report defines ''Organic IT'' as a "Computing infrastructure
built on cheap, redundant components that automatically shares and manages
enterprise computing resources -- software, processors, storage, and
networks -- across all applications within a datacenter".

The vision of ''Organic IT '' is based on a next-generation data center
architecture, and was the precursor for the
organic computing and [[Autonomic Computing|autonomic computing]] initiatives.
Forrester has proposed for example the "principle of least escalation",
meaning that in an layered organic architecture with many management
layers the lowest capable level solves urging problems immediately and
informs the higher levels later (similar to biological reflexes).

Like many of the later initiatives and visions, ''Organic IT'' envisioned
an IT architecture which solves the basic problems in many
[[Distributed System|distributed systems]], namely
[[Fault Tolerance|fault tolerance]], [[Failover|failover]],
[[Flexibility|flexibility]], [[Robustness|robustness]], [[Scalability|scalability]]
with the help of [[Self-Star Properties|self-* properties]] and [[redundancy]].
[[Scalability|Scalability]] for instance means that applications can scale up
and down to match demand, [[Robustness|robustness]] and [[Fault Tolerance|fault tolerance]]
(including failover and recovery) mean an application can run 24/7,
non-stop 24 hours per day and seven days a week,
[[Flexibility|flexibility]] means automated server provisioning, application
installation and maintenance.

== Objectives ==

The objective of Organic Computing is the technical usage of principles
observed in natural systems, to create biologically inspired life-like
computer systems. As computers and the tasks they perform become increasingly
complex, researchers are looking to nature -- as model and as
metaphor -- for inspiration.

There are many examples how biology has alredy been affecting
computer science. Many attempts exist for example to develop artificial neural networks,
evolvable hardware, evolutionary algorithms, nanoscale self-assembly, and security systems
that mimic nature's immune systems (see the book "Imitation of Life" by Nancy Forbes).

The overall objectives of organic computing are the same goals
as in biologically inspired computing:
* the use of biology as a metaphor or inspiration for the development of algorithms and systems;
* the construction of information processing systems that use biological materials or are modeled on biological processes, or both;
* the effort to understand how biological organisms "compute," or process information.

== Biologically Inspired Computing ==

Another name for Organic Computing is '''biologically inspired computing'''
or short bio-inspired computing. Organic means having properties
associated with living organisms:
its original meaning is "Part of or derived from living matter".
Organic Computing is the use of the self-* principles found in organic,
living and evolving systems (self-management, self-organization and
self-healing) to reach scaleability, robustness and autonomy.
Organic systems grow, change, evolve, suffer illnesses and recover
again. They are robust and flexible. If organic computing can
identify and use some of the basic principles behind organic
systems to reach similar properties in artificial systems, then
this would be a success.

Biological [[Evolution|evolution]] has managed to produce a
wide variety of complex organisms and lifeforms that build,
adapt, repair and reproduce themselves.
There have always been similarities, exchange and overlap between
the worlds of biology and computer science. The basic terminology
of viruses and infection in the field of computer security
is borrowed from biology, and the modern biomedicine and molecular
biology would not be possible without computers at all.

By studying biological phenomena such as brains, swarming insects,
evolution and immune systems, scientists try to make computers
do the same sorts of things and to reach the same amount of
flexibility and robustness. Using ideas from biology to improve
artificial systems can be a useful way to stimulate thought
and to inspire new architectures. Biologically inspired computing
methods and systems are:

* Reinforcement Learning
* Neural Networks
* Evolutionary Computing
* Swarm Intelligence and Collective Systems
* Artificial Immune Systems
* DNA Computing and Biological Haardware
* Biologically Inspired Robotics

== Papers ==

* [http://www.gi-ev.de/download/VDE-ITG-GI-Positionspapier%20Organic%20Computing.pdf Positionspapier Organische Computersysteme (German)]

* [http://www.cs.virginia.edu/~evans/bio/Embryonics_ProcIEEE.pdf D. Mange et al., Toward robust integrated circuits: The embryonics approach], Proc. of the IEEE, vol. 88, no. 4 (2000) 516-541

== Books ==

Nancy Forbes, ''Imitation of Life : How Biology Is Inspiring Computing'', The MIT Press, 2004, ISBN 0262062410

== Links ==

* [http://en.wikipedia.org/wiki/Biologically-inspired_computing Biologically-inspired computing]

* [http://www.cs.unibo.it/bison/index.shtml BISON Biology-Inspired techniques for Self-Organization in dynamic Networks]

* [http://www.organic-computing.org/ The Organic Computing Home Page]

* [http://www.informatik.uni-augsburg.de/lehrstuehle/sik/research/organiccomputing/ Organic Computing @ University of Augsburg]

[[Category:x-Computing_Techniques]]

Level of Organization

2011-02-11T21:45:51Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

Scientific knowledge is organized hierarchically in '''levels of organization''',
where each level describes nature on a certain scope or resolution,
from [[Microlevel|microscopic]] to [[Macrolevel|macroscopic]] levels.
Although at any given level of organization the behavior emerges from
the behavior of the subsystems at the immediately lower level of
organization, it can be described in an independent way.

: Scientific knowledge is organised in levels, not because reduction in principle is impossible, but because nature is organised in levels, and the pattern at each level is most clearly discerned by abstracting from the detail of the levels far below. [. . .] And nature is organised in levels because hierarchic structures – systems of Chinese boxes – provide the most viable form for any system of even moderate complexity. — Herbert A. Simon ('The Organisation of Complex Systems’ in "Hierarchy Theory: The Challenge of Complex Systems", 1973, p. 26)

In ecology, the levels of organizations are the five known levels of environmental classification:

* Biosphere
* Ecosystem
* Community
* Population
* Organism

In the first chapter of their book "The Superorganism", Bert Hölldobler and E.O. Wilson provide an elegant description of life as a scale-free hierarchy of biological complexity:

: "Life is a self-replicating hierarchy of levels. Biology is the study of the levels that compose the hierarchy. No phenomenon at any level can be wholly characterized without incorporating other phenomena that arise at all levels. Genes prescribe proteins, proteins self-assemble into cells, cells multiply and aggregate to form organs, organs arise as parts of organisms, and organisms gather sequentially into societies, populations and ecosystems. Natural selection that targets a trait at any of these levels ripples in effect across all the others."

In anatomy and biology, the levels of organic life-forms and organisms are

* Organism
* Organ System
* Organ
* Tissue
* Cell
* Proteins
* Genes

In physics, the levels of organizations for matter in general are:

* Molecule (biomolecule, cells)
* Atom
* Elementary particle

[[Category:Organization]]

Distributed Algorithm

2011-02-11T21:45:47Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

A '''distributed algorithm''' is an decentralized algorithm that is executed in a [[Distributed System|distributed system]], on more than one machine, node or processor.

== Definition ==

A distributed algorithm for a collection P of processes is, according to Gerard Tel and his book ''Introduction to Distributed Algorithms'', simply a collection of local algorithms, one for each process in P. In his
earlier work ''Topics in Distributed Algorithms'' he defined it as follows: "a distributed algorithm executes
as a collection of sequential processes, all executing their part of the algorithm independently, but
coordinating their activity through communication." Nancy A. Lynch argues "Distributed algorithms are algorithms
designed to run on hardware consisting of many interconnected processors. The algorithms are supposed to work
correctly, even if the individual processors and communication channels operate at different speeds and even if
some of the components fail."

In sequential algorithms steps are taken in a strict sequence and well-defined order. In distributed systems
steps are taken in a strict sequence only locally, gloablly the sequence of steps depends on the
transmission of messages and can be unpredictable. The order of events is not always well-defined,
and failures make the situation even worse.
Nearly all distributed algorithms are based on more or less sophisticated communication through message passing. Since a [[Distributed System|distributed system]] consists of many nodes, processors or processes interconnected by a message passing network, any algorithm which involves more than one node must use some form of message passing, if there is no [[Distributed Shared Memory|distributed shared memory]] or other way of [[Interprocess Communication|interprocess communication]]. The complexity analysis of distributed algorithms involves therefore usually the attempt to measure the total number of messages.

Distributed algorithms are to sequential algorithms what Einstein's physics is to Newton's physics:
sequential algorithms are a special, simplified case of distributed algorithms, and in
distributed alogrithms there is no global time or common clock, and the observer and speed
may influence causality. There are more similarities: for instance according to F. Mattern, the Lorentz
transformation corresponds roughly to the Rubberband transformation which leaves causality invariant.

== Different Forms and Types ==

=== Asynchronous and Synchronous ===

In general, one can distinguish between asynchronous and synchronous algorithms, as Nancy Lynch does in her book.
In asynchronous algorithms, the nodes and processes are not acting at the same time, no timing assumptions
exist and messages can have an arbitrary delay, while in synchronous algorithms the nodes are acting in lockstep
at the same time. Asynchronous algorithms are not synchronized, they are not occurring at predetermined or
regular intervals, and messages can be delivered in any order.

Totally synchronous algorithms are easy to handle, because they all nodes act like
a single node at the same time, but they are not practical. They are difficult to justify
in real-world situations and difficult to achieve in general distributed systems, because there
is no absolute global time in general, unsynchronized processes operate at different speeds and
messages have often a considerable time delay.
In summary, systems with pure synchrony (perfect timing) or no faults at all would be nice,
but they are not realistic: nodes and links fail, and messages may have a time delay.

Totally asynchronous algorithms are powerful in theory, because they are meant to work with
arbitrary time delay, but they are notoriously difficult to design as well. They are
often very hard or even impossible to construct, because they are too general
(for example a node which sends arbitrary slow messages is indistinguishable
from a node that really failed).
Some problems proved impossible or expensive in the fully asynchronous model can
indeed be solved in practice.
Therefore elegant theoretical assumptions such as pure asynchrony
(no timing assumptions whatsoever), or Byzantine faults (no assumptions limiting faulty behavior)
are not practical, too, they lead to pessimistic and frustrating results that are not useful
for complex real world systems.

Real systems are complex, they tend to fall somewhere in between the two extreme classes
of full synchrony and full asynchrony, for example asynchronous systems with
finite average response times or upper bounds for message delivery times.

=== Topologies and Graphs ===

Besides asynchronous and synchronous forms, one can differentiate further between algorithms for particular topologies
(rings, trees, etc.). There are also a number of [[Distributed Graph Algorithm]]s, which is not surprising, because nearly all [[Distributed System|distributed systems]] based on message passing can be described by a graph (except those who use only some form of shared common memory).

=== Fundamental algorithms ===

A fundamental block used in many distributed algorithms are tokens (which circulate in rings) and
waves (which spread through arbitrary topologies). A token which moves through a ring can
be considered as a wave for a ring topology. The importance of waves is not surprising, since a wave is
one of the most basic forms of [[Emergence|emergence]] in a system. If all nodes are visited
sequentially, or an action like "inform all" or "query all" is required, a kind of wave must be used.
Fundamental algorithms where all nodes of a network are visited are [[Total Algorithm]]s and
[[Heart Beat Algorithm]]s.

A common problem besides "inform all" and "query all" is "select one", "elect one", "admit one", etc.
The resulting algorithms are named [[Election Algorithm|election algorithms]], where a single node or
process (for example the leader) that is to play a distinguished role in a subsequent computation must
be (s)elected. Further typical algorithms in this area are distributed [[mutal exclusion]] and
[[deadlock detection]] algorithms, where the concurrent use of un-shareable resources must be
avoided.

Finally it is problem to determine and change the "global state" or the "global order", the associated
distributed algorithms are named [[Termination Detection|termination detection]], where the end of a
distributed computation has to be detected, and distributed [[garbage collection]], where unused memory and
references must be released. A basic "toy" algorithm used to explain distributed algorithms
in classes is the [[Distributed GCD Algorithm|distributed GCD algorithm]].

== Problems and Difficulties ==

=== Uncertainties and Failures ===

Distributed algorithms are like [[Distributed System|distributed systems]]
hard to understand and hard to design, because of their high complexity.
Algorithms are the step-by-step definitions of computations,
detailed instructions, rules and recipes for producing a solution
to a given problem in a finite number of steps.
The problem with many real [[Distributed System|distributed systems]] is
that every node and every link can fail at any time, messages
can get lost or arrive with an arbitrary time delay.
One cannot say for sure what will happen in the next step.
One can specify the behavior for each node, but the overall global
behavior which results from the local interactions is often
hard to predict.

The accidental or intended [[Emergence|emergence]] of a
desirable behavior is more the exception than the rule.
Analysis, design, verification and correctness proofs of
distributed algorithms are difficult issues. Among the different
types of uncertainties and difficulties are for example
(according to Nancy Lynch, 1996):

# processor and link failures (node or message loss)
# uncertain message delivery (arbitrary transmisson time)
# unknown message ordering
# unknown network topologies
# unknown number of processors

Some problems which are characteristic and unique for distributed algorithms are

# [[Race Condition|race conditions]] (where the result depends on the timing of events)
# deadlock detection, esp. phantom- or pseudo-deadlocks
# termination detection

The detection if a centralized, serial or non-distributed algorithm
is terminated is trivial, since there is only one
processor, one clock and one well-defined state or time.
The detection if a distributed algorithm is terminated or
not is a problem of its own, since there is no global state or time in
a general [[Distributed System|distributed system]]. Another
problem which occurs in distributed algorithms but not in serial
ones is deadlock: mutual blocking of processes, where each process
is waiting for a resource one of the other processes holds.
Obviously it does not occur in serial algorithms for one processors,
and was first met in implementing operating systems.

=== Problem Fields ===

Termination detectection is difficult, because a distributed system has no global state which can be detected instantly, and there is no global time which is valid for all computers, nodes or entities. In order to define a global state, some authors have proposed algorithms for consistent [[Global Snapshots|global snapshots]], for example the Chandy-Lamport algorithm. A snapshot is "consistent" if it appears as if it were take at the same instant everywhere in the system, without any violation of causality. In order to define a global time, some authors have proposed methods for consistent global time (logical clocks by Lamport, which find their extension in vector clocks and vector time, etc.). The concept of a "logical time" or timestamps introduced by Lamport allows an asynchronous system to simulate one in which the nodes have access to synchronized clocks. Both real and logical time are monotonically increasing, but the real time is uniformly continuous, whereas the logical time can have discontinuous jumps. But these methods are problematical and doubtful, because they attempt to make distributed computing follow the model of local, centralized computing. As Waldo noticed in 1994, this method ignores "the different failure modes and basic indeterminacy inherent in distributed computing" and leads to systems that are neither reliable and nor scalable.

Thus we have roughly the following problem fields:

# Attempts to imitate local computing (Synchronous Communication or Synchronization, Logical Time)
# Attempts to determine global state (Global Snapshots, Deadlock Detection, Termination)
# Attempts to reach unified state (Agreement or Consensus)
# Attempts to coordinate access (Contention Problems as Election and Mutual Exclusion)

=== Impossibility Results ===

Given these difficulties, it is not surprising that the analysis and design of distributed algorithms that work in a general [[Distributed System|distributed system]] (where each node and link can fail at any time, and messages can have an arbitrary time delay) is very hard and sometimes even impossible. Already one faulty process can render any guaranty about achieving of a common consensus impossible, as the famous "FLP impossibility argument" says. The "FLP impossibility result" or "FLP impossibility argument" from Fisher, Lynch and Patterson says it is impossible to reach consensus in a distributed, asynchronous systems if only one process is faulty. To be more precise it says there is no guruantee a common consensus can be reached, if a faulty process exists. This fact is intuitive plausible, since a faulty process that is not responding anymore is indistinguishable from a process that answers slowly (if there is an arbitrary time delay in the connection of the asynchronous network).

Consensus and agreement problems are a fundamental challenge in [[Distributed System|distributed systems]]. The consensus problem is one of the most thoroughly investigated problem in [[Distributed Computing|distributed computing]], where several process have to agree on a certain value or decision. Processes in a database system may need to agree whether or not a transaction should be commited or aborted. Processes in a control or monitoring system may need to agree whether or not a particular other process is faulty. Processes in a general distributed system may need to agree whether or not a message has been received. As Nancy Lynch says (in "Chapter 12" Consensus of her book), "the impossibility result implies that there is no purely asynchronous algorithm that reaches the needed agreement and tolerates any failures at all."

== Proof and Verification ==

The design and verification of distributed programs and algorithms is without
doubt a very difficult task. A common way to verify distributed algorithms
despite these difficulties is to verify liveness and safety properties.
The traditional definition of liveness and safety are:

* '''Liveness''' means "something good will eventually occur" or "something good eventually happens"
* '''Safety''' means "something bad will never happen" or "no bad thing ever happens"

Liveness and safety are two complementary properties, one says that
the system is changing, the other that the system is not changing. One
claims that the program never enters an unacceptable state, the other
assumes that the program always enters a desirable state after a finite
number of steps.

=== Liveness ===

Liveness implies that the '''system is changing'''. There is a guarantee of progress,
which in turn is guaranteed by lack of deadlocks, the absence of infinite
loops and the ensurance of termination. It is a property stating that eventually
(after a finite number of steps) some requirement holds. The program eventually enters a desirable
state, and some assertion will eventually hold. In other words, every computation contains
finally a state where a certain assertion is true. A liveness requirement requires that some
property in some configuration which is reachable will eventually hold in every execution.
Typical liveness properties are
* Program termination: the algorithm will terminate in a finite amount of time
* Upper/Lower bounds: a numerical value or parameter must reach a certain upper (lower) bound (in this case liveness can be proved if the value is monotonically increasing or (decreasing), and never remains constant for an infinite amount of time)

=== Safety ===

Safety implies the '''system does not change''', it means that the program does nothing wrong,
and there is a guarantee that no bad or evil change takes place, which in turn is often proved
by invariants. Invariants are assertions that always hold during the execution
of the algorithms and are not affected by any action or operation of the algorithm.
An invariant property must hold in every execution and in each reachable
configuration. Safety properties specify that 'something bad never happens',
the program never enters an unacceptable state and some assertion always holds.
In other words, a certain assertion is true in every state of every
computation of the algorithm. Typical safety properties are
(see Owicki and Lamport, [http://research.microsoft.com/users/lamport/pubs/liveness.pdf Proving Liveness Properties of Concurrent Programs])
* Partial correctness: if the algorithm begins with the precondition true, then it can never terminate with the postcondition false.
* Absence of deadlock: the algorithm never enters a state in which no further progress is possible.
* Absence of infinite loops: the algorithm never enters a state where one or more processes are involved in an infinite loop
* Mutual exclusion: two different processes are never in their critical sections at the same time.

== Articles and Papers ==

Many classic publications from Leslie Lamport can be found on his [http://research.microsoft.com/users/lamport/pubs/pubs.html website] at Microsoft Research. Papers from Edsger W. Dijkstra can be found in the [http://www.cs.utexas.edu/users/EWD/ Dijkstra archives].

General:

[http://www.sunlabs.com/techrep/1994/abstract-29.html A Note on Distributed Computing], Jim Waldo et al., Sun Technical Report (1994) TR-94-29

Impossibility Theorems and Results:

[http://portal.acm.org/citation.cfm?id=214121 Impossibility of distributed consensus with one faulty process] M. Fisher, N. Lynch, and M. Patterson, Journal of the ACM, Vol. 32 No. 2 April (1985) 274-382

[http://doi.ieeecomputersociety.org/10.1109/MC.1992.10061 The Many Faces of Consensus in Distributed Systems] John Turek and Dennis Shasha, IEEE Computer Vol. 25 No. 6 (1992) 8-17

[http://citeseer.ist.psu.edu/572373.html A Hundred Impossibility Proofs for Distributed Computing] Nancy Lynch

[http://citeseer.ist.psu.edu/623509.html Hundreds of Impossibility Results for Distributed Computing]
Faith Fich and Eric Ruppert

== Books ==

* Nancy A. Lynch, ''Distributed Algorithms'', Morgan Kaufmann 1996, ISBN 1558603484

* Gerard Tel, ''Introduction to Distributed Algorithms'', Cambridge University Press, 2nd edition, 2001, ISBN 0521794838

* Gerard Tel, ''Topics in Distributed Algorithms'', Cambridge University Press, 1991, ISBN 0521403766

* Valmir C. Barbosa, ''An Introduction to Distributed Algorithms'', The MIT Press, 1996, ISBN 0262024128

* Michel Raynal, ''Distributed algorithms and protocols'', John Wiley and Sons, 1988, ISBN 0471917540

* Hagit Attiya and Jennifer Welch, ''Distributed Computing'', John Wiley and Sons, Inc., 2nd edition, 2004, ISBN 0471453242

* Friedemann Mattern, ''Verteilte Basisalgorithmen'', Springer, 1989, ISBN 3540518355

== Lectures ==

Lecture in German from Hans P. Reiser and Rüdiger Kapitza, University Erlangen-Nuremberg

2003
[http://www4.informatik.uni-erlangen.de/Lehre/WS03/V_VA/Skript/]

Lectures in German from Prof. Dr. Friedemann Mattern, ETH Zurich

1999/2000
[http://www.vs.inf.ethz.ch/edu/WS9900/VA/]

2001/2002
[http://www.vs.inf.ethz.ch/edu/WS0102/VA/]

2002/2003
[http://www.vs.inf.ethz.ch/edu/WS0203/VA/]

2003/2004
[http://www.vs.inf.ethz.ch/edu/WS0304/VA/]

2004/2005
[http://www.vs.inf.ethz.ch/edu/WS0405/VA/]

Autocatalysis

2011-02-11T21:45:45Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

Autocatalysis occurs in a (chemical) reaction, if the reaction product itself catalyzes further reactions. It is a form of catalysis in which one of the products of a reaction serves as a
catalyst for the reaction. In chemistry and biology,
[http://en.wikipedia.org/wiki/Catalysis catalysis] is the acceleration
the reaction rate of a chemical reaction by means of a substance, called a [http://en.wikipedia.org/wiki/Catalyst catalyst]
or [http://en.wikipedia.org/wiki/Enzyme enzyme] (in biology). A catalyst accelerates, facilitates
and enhances a bio-chemical reation. Nearly all biochemical processes are catalyzed by enzymes.

Autocatalysis describes a self-enhancing and self-amplifying reaction, and
is a special form of positive [[Feedback|feedback]]. An example of
autocatalysis is the hypercycle, in which self-replicating entities or reations catalyze each other.
M. Eigen and P. Schuster proposed the model of hypercycles to explain the origin of the DNA through self-replicating molecules.

== Books ==

Manfred Eigen and Peter Schuster, ''The Hypercycle: A Principle of Natural Self Organization'', Springer-Verlag 1979, ISBN 0387092935

== References ==

* [http://en.wikipedia.org/wiki/Hypercycle Wikipedia Hypercycle Entry]
* [http://en.wikipedia.org/wiki/Autocatalysis Wikipedia Autocatalysis Entry]
* [http://en.wikipedia.org/wiki/Catalysis Wikipedia Catalysis Entry]
* [http://en.wikipedia.org/wiki/Catalyst Wikipedia Catalyst Entry]

[[Category:Basic Principles]]

Total Algorithm

2011-02-11T21:45:41Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

A '''total algorithm''' is a [[Distributed_Algorithm|distributed algorithm]] where the participation of all nodes or processes in the network is required before a decision can be taken. It is sometimes also named '''wave algorithm'''. A special form of total algorithm is a '''traversal algorithm''' where all events of a wave a strictly ordered by a causality relation and in which the last event occurs in the same process as the first event, namely in the initiator node.

Total algorithms and wave algorithms can be considered as [[Distributed_Algorithm|distributed algorithms]] initiated by a single event where the participation of all processes in the network is required before a particular final event, often a decision, takes place. In wave algorithms and related flooding techniques a node sends new information to all of its neighbors. The activity spreads like a wave or a controlled chain-reaction through the network, and all nodes are visited until the decision can take place and the algorithm is finally terminated. They can be used to spread and disseminate information in a [[Distributed System|distributed system]], to calculate the topology of a network, or to collect and gather information in a distributed system.

Examples for a total algorithm are the

* [[Echo Algorithm]]
* [[Heart Beat Algorithm]]
* [[Phase Algorithm]]

In order to reach all nodes of a system, the algorithm has to broadcast the corresponding
information through the whole system. Often this is done in a first phase.
There are two possibilities to

* '''Flooding''': a node receiving data sends it immediately to all its neighbors by broadcasting
* '''Gossiping''': a node selects from time to time randomly one of its neighbors to send the data

Both result in an epidemic spread of information.
Gossiping is of course much slower than flooding.
Flooding leads to an ordered wave, whereas gossiping leads
to disordered epidemic spread of information.

[[Category:Distributed Algorithms]]

Mind

2011-02-11T21:45:34Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

Cloud Computing

2011-02-11T21:45:31Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Cloud Computing''' a style of computing where IT-related capabilities are provided "as a service", allowing users to access technology-enabled services "in the cloud" without knowledge of, expertise with, or control over the technology infrastructure that supports them. The cloud is a metaphor for the Internet.

== Relations ==

The idea of Web-based applications is old, Sun proposed "the Network is the Computer" many years before cloud computing became popular. The idea of computing as a commodity or utility can also be found in [[Grid Computing|grid computing]] visions. Cloud computing became ultimately possible through large companies like Amazon, Google, Sun, IBM, and Microsoft who offer a part of their huge computational capacity and extremely large scale infrastructures (including storage, servers, etc.) as a service. Only these large companies can deliver reliable services through their large data centers. Like any next big trend and buzzword it sounds nebulous, and means many things to different people, and it is based on many different previous trends.

Cloud computing combines ideas of [[Distributed Computing|distributed computing]] and [[Grid Computing|grid computing]] ("a 'super and virtual computer' is composed of a cluster of networked, loosely-coupled computers, acting in concert to perform very large tasks"), utility computing (the "packaging of computing resources, such as computation and storage, as a metered service similar to a traditional public utility such as electricity") and [[Autonomic Computing|autonomic computing]] ("computer systems capable of self-management"). Indeed many cloud computing deployments are today powered by grids, have autonomic characteristics and are billed like utilities, but cloud computing can be seen as a natural next step from the grid-utility model.

== Links ==

* Wikipedia entry for [http://en.wikipedia.org/wiki/Cloud_computing Cloud Computing]

* InfoWorld article [http://www.infoworld.com/article/08/04/07/15FE-cloud-computing-reality_1.html What cloud computing really means]

* Technology Review article [http://www.technologyreview.com/Infotech/19397/?a=f Computer in the Cloud]

* NYTimes.com article about [http://www.nytimes.com/2008/05/25/technology/25proto.html Cloud Computing]

* HPCC 2008 keynote [http://arxiv.org/abs/0808.3558 Market-Oriented Cloud Computing] - Vision, Hype, and Reality for Delivering IT Services as Computing Utilities

[[Category:X-Computing_Techniques]]

Category:Systems

2011-02-11T21:45:28Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

The category page contains links to various systems

Redundancy

2011-02-11T21:45:25Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Redundancy''' is related to duplication and [[Replication|replication]] and refers in general to the quality or state of being redundant, i.e. there are more components than needed to perform a function. This can have a negative connotation, superfluous, but also positive, serving as a duplicate for preventing failure of an entire system. It is a common way to achieve high levels of [[Fault Tolerance|fault tolerance]] in a computer system. If one subsystem, element or component fails, there is an redundant
replacement ready to begin operating.

== TMR and NMR ==

In engineering, redundancy means simply the duplication of critical components of a system with the intention of increasing reliability. In safety-critical systems, such as fly-by-wire aircraft, some parts of the control system may be triplicated. An error in one component then may then be out-voted by the other two. In a triply redundant system, the system has three sub components, all three of which must fail before the system fails. Since each one rarely fails, and the sub components are expected to fail independently, the probability of all three failing is calculated to be extremely small.

This common form of redundancy is also known as '''triple modular redundancy''' (TMR):
the threefold replication of a component to compensate and correct
the failure of a single component. The primary flight computer of the Boeing 777
for example uses triple modular redundancy [1]. Triplex or triple redundancy was originally
envisaged by John Von Neumann. Having three units or components or elements
offers an essential advantages, because three redundant components are
enough elements to reach an unambiguous decision in a majority voting,
as long as at least two components still work correctly.
Systems with dual redundancy have difficulties to come to an
agreement and to correct each other in most cases because the two
redundant components can end up in a continuous loop of chatter about
which one is the more correct (as in some marriages).
'''N modular redundancy''' (NMR) is a generalization of TMR. A system
of N = 2n + 1 redundant elements can mask or tolerate n faulty elements,
if the elements act as voters and make a majority decision.
The basic structure of TMR and NMR is very simple: in TMR (NMR)
you have three (n) units with a voter.

In the Space Shuttle computer control system [2], four redundant computers are used to achieve
reliability during flight-critical phases of a mission. Flight-critical or [[Mission-critical|mission-critical]]
phases are at the beginning (launch/ascent) and the end (landing/entry), periods where a loss of the
system might mean loss of the vehicle. Before launch and during the on-orbit
phase, the degree of active [[Replication|replication]] is reduced and different computers are
running different applications. The four redundant computers during flight-critical phases
are synchronized at the applications level and provide bit-for-bit identical output. The system is designed
to cope with two successive failures. If a computer becomes defective, it is overruled
by the other three and further ignored. If another computer fails, it is overruled by
the remaining two. A fifth computer which was independently programmed can perform
critical functions if all four computers fail. It can only be engaged manually by
crew action.

== Hybrid Redundancy ==

'''Hybrid redundancy''' offers the highest reliability.
It is a combination of NMR (for error masking)
and spare switching (for fault prevention and rejuvenation).
An NMR system masks permanent and intermittent
failures but its reliability drops below that
of a single module for very long operation or mission
times. Hybrid redundancy overcomes this by adding spare
modules to renew the system by replacing active
modules. A hybrid NMR system with spares consists of
a core of N processors (NMR), and M spares.

There are other forms of hybrid redundancy, for
example self-purging redundancy: all units actively
participate in a NMR system, and each module
has a capability to remove itself from the
system if its faulty

== Related Concepts ==

Contrary to traditional software programs or machines, [[Self-Organization|self-organizing systems]] and [[Multi-Agent System|agent based systems]] have often a high redundancy. This can be observed for example in nature, where the death of a single ant, termite, or honey bee does not affect the existence of the whole colony. Likewise the failure of a single neuron does not affect the function of a whole brain, although this does not mean that the principle of [[Self-Organization|self-organization]] explains how the brain works or that a brain functions in the same way as an ant colony. However, it is clear that traditional software programs have a very low redundancy:

* a program does not work if arbitrary code lines are removed
* a self-organizing network/system usually still works if arbitrary nodes/agents are removed

== Literature ==

[1] Y.C. (Bob) Yeh, ''Triple-triple redundant 777 primary flight computer'',
Proceedings of the 1996 IEEE Aerospace Applications Conference,
Vol. 1, New York (1996) 293-307

[2] Alfred Spector and David Gifford,
[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=358246 The space shuttle primary computer system], Communications of the ACM Volume 27, Issue 9 (September 1984)

[3] B. J. Flehinger, [http://www.research.ibm.com/journal/rd/022/ibmrd0202G.pdf Reliability Improvement through Redundancy at Various System Levels], IBM J. Res. and Dev., vol. 2, April (1958) 148-158

[[Category:Applied Principles]]

Aging

2011-02-11T21:45:22Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

All [[System|systems]] are subject to '''aging''', even machines and software systems. Besides [[Cancer|cancer]], understanding and controlling the aging process is a central problem of applied biology. Aging means the accumulation of changes in a system, organism or object over time. For organic lifeforms, the problems of aging are senescence (the general deterioration of the body with increasing age). It is still unclear why senescence — the general deterioration of vitality and resistance to adversity with advancing age — occurs and how it works. Reasons may be:

* normal wear and tear damage, damage that naturally and inevitably occurs in daily life
* accumulation of waste products that interfere with metabolism
* accumulation of mutations which violates the genetic integrity and gradually damage the genetic code
* suppression of mechanisms that prevent further regeneration (e.g. by shortened telomeres)

== Links ==

* Wikipedia link for [http://en.wikipedia.org/wiki/Aging Aging]

[[Category:Systems]]

Autopoiesis

2011-02-11T21:45:18Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

{{SelfOrg}}

'''Autopoiesis''' literally means "self-production", "self-producing" or "self-making" (from the Greek: auto for self- and poiesis for creation or production) and expresses a fundamental relationship between structure and function of a [[Self-Organization|self-organizing system]]. The idea of autopoiesis is simply that living things are produced and maintained by themselves. It is not a theory, rather an observation or phenomenon that describes systems with the [[Self-Star Properties|self-* property]] of self-production. It should be emphasized that autopoiesis is like [[Self-Organization|self-organization]] an abstract concept, similar to metabolism, but more general.

The term was originally introduced by Chilean biologists Francisco Varela (1946-2001) and Humberto Maturana in the early 1970s. Maturana and Varela take this form of autopoiesis (metabolic selforganization) to be the real essence of life and all living systems. The canonical example of an autopoietic system, and one of the entities that motivated Varela and Maturana to define autopoiesis, is the biological cell. The eukaryotic cell, for example, is made of various biochemical components such as nucleic acids and proteins, and is organized into bounded structures such as the cell nucleus, various organelles, a cell membrane and cytoskeleton. These structures, based on an external flow of molecules and energy, produce the components which, in turn, continue to maintain the organized bounded structure that gives rise to these components. An autopoietic system is to be contrasted with an allopoietic system, such as a car factory, which uses raw materials (components) to generate a car (an organized structure) which is something other than itself (a factory).

More generally, the term autopoiesis refers to the dynamics of [[Self-Organization|self-organizing]] non-equilibrium structures; that is, organized states (sometimes also called dissipative structures) that remain stable for long periods of time despite matter and energy continually flowing through them. A vivid example of such a non-equilibrium structure is the Great Red Spot on Jupiter, which is essentially a gigantic whirlpool of gases in Jupiter's upper atmosphere. This vortex has persisted for a much longer time (on the order of centuries) than the average amount of time any one gas molecule has spent within it. From this very general point of view, the notion of autopoiesis is often associated with that of [[Self-Organization|self-organization]].

An application of the concept to sociology can be found in Luhmann's systems theory. John von Neumann tried to create a self-reproducing machine which resulted in a self-reproducing [[Cellular Automata|cellular automaton]].

==Relations==

Autopoiesis is closely related to [[Self-Star Properties]], [[Autocatalysis|autocatalysis]] and the biological principle of [http://en.wikipedia.org/wiki/Metabolism metabolism], because it means "self-production". Metabolism enables the built-up of own complex molecular material (anabolism) through breakdown of other material (catabolism).

==References==

* [http://en.wikipedia.org/wiki/Autopoiesis Wikipedia Entry for Autopoiesis]

* Capra, Fritjof (1997). ''The Web of Life''. Random House. ISBN 0385476760 —general introduction to the ideas behind autopoiesis
* Maturana, Humberto & Varela, Francisco ([1st edition 1973] 1980). ''Autopoiesis and Cognition: the Realization of the Living''. Robert S. Cohen and Marx W. Wartofsky (Eds.), Boston Studies in the Philosophy of Science '''42'''. Dordecht: D. Reidel Publishing Co. ISBN 9027710155 (hardback), ISBN 9027710163 (paper) —the main published reference on autopoiesis
* Mingers, John (1994). ''Self-Producing Systems''. Kluwer Academic/Plenum Publishers. ISBN 0306447975 —a book on the autopoiesis concept in many different areas
* Luisi, Pier L. (2003). Autopoiesis: a review and a reappraisal. ''Naturwissenschaften'' '''90''' 49–59. —biologist view of autopoiesis
* Varela, Francisco J.; Maturana, Humberto R.; & Uribe, R. (1974). Autopoiesis: the organization of living systems, its characterization and a model. ''Biosystems'' '''5''' 187–196. —one of the original papers on the concept of autopoiesis

== Articles ==

Margaret A. Boden, [http://cognition.iig.uni-freiburg.de/csq/pdf-files/boden.pdf Autopoiesis and Life]

[[Category:Basic Principles]]

Category:Consciousness

2011-02-11T21:45:16Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

This category contains topics related to consciousness, self-consciousness and self-awareness.

Self-Protection

2011-02-11T21:45:12Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Self-Protection''' is a [[Self-Star_Properties|Self-* Property]]. It means proactive identification and protection from arbitrary attacks. Central mechanisms to protect the body in organic lifeforms are [[Stress|stress]] and unpleasant
sensations. Pain is the most prominent member of a class of unpleasant sensations known as bodily sensations, which
include itches:

* itches: sensation indicating light physical annoyance (for example by parasites), evokes the desire or reflex to scratch
* pain: sensation indicating severe physical damage of the system, evokes the desire or reflex to avoid the situation

Pain is an unpleasant sensation resulting from the intricate interplay between
sensory and cognitive mechanisms. It is associated with actual or
potential tissue damage in natural organisms. Although it is unpleasant,
it is a necessary mechanism of systems with the capability of effective self-protection.
Effective self-protection means fast self-protection. The rapid
warning through pain is a critical component of the body’s defense system.

Pain seems to be a general, necessary mechanism of systems with the
capability of self-protection, because it signals the place where the
self-protecting mechanisms fail or where they are badly needed.
A painful stimulus leads to a massive activation of multiple units, and prevents
at the same time any actions associated with it. It draws the attention of the whole
system to a certain part, but inhibits any action associated with it.
It is characterized by a loss in the flow of information, or
in the members of the system.

It is for every person and organization unpleasant if the income drops
while the spendings increase. For an organization, especially the
departments which have very high costs and zero revenue contribute
to this unpleasant situation. In companies, there is a capital inflow
and capital outflow (usually in form of products). If there is a sink
for the capital flow in between, it becomes painful for the company:
a department or product which has cost lots of time and money but
never results in real money from customers is very unpleasant.

A conflict between members or a loss of good members is unpleasant,
especially if they cannot be replaced by suitable members of the same value:

* A trainer of a sports team feels pain if his best players are banned from the field, and he cannot replace them with suitable new players
* A general feels pain if his army loses in a continued campaign lots of soldiers, and he cannot replace them with new ones
* A bishop feels pain if his church loses lots of members, while the number of new members is sinking, too. A chief of a political party will do the same
* A CEO feels pain if his company loses a lot of employees which take valuable experience with them, if he cannot replace them with suitable new ones

Like other self-properties, self-protection can have severe consequences
and side-effects if the integrity of the self is affected: if the self
is not recognized correctly.
A negative side-effect of self-protection are autoimmune diseases
and allergies. In autoimmune diseases the body attacks the ‘self’ and its
own cells, examples are Diabetes Mellitus (type 1) or Multiple Sclerosis. In
allergies, the body attacks harmless targets which are normal parts of the
body: allergens such as dust, pollen, or certain foods. In both cases, the body
attacks parts of itself which are harmless. The distinction between self/nonself
and harmless/harmful goes wrong. In autoimmune diseases, parts of the
self are mistaken for hostile agents, and in allergies, harmless targets are
mistaken for harmful intruders.
Most autoimmune diseases are probably the result of multiple circumstances,
for example, a genetic predisposition triggered by an infection. Autoimmune
diseases result from at least three different interacting components:
genetic, environmental and regulatory.

== Links ==

* SEP Entry for [http://plato.stanford.edu/entries/pain/ Pain]

[[Category:Self-Star Properties]]

Level of Abstraction

2011-02-11T21:45:08Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

A '''level of abstraction''' describes a system at a certain scope or resolution, and it used to explain the system at a certain [[Level_of_Organization|level]]. The relationship between different levels of abstraction is described by [[Emergence|emergence]]. The different types and classes of [[Emergence|emergence]] describe different relationships between higher and lower levels of abstractions. Strong emergence requires at least one completely new level of abstraction, if it is defined as the appearance of a new code. The "level of abstraction" is related to the "level of detail", the "scope of view" or the "degree of generality". The higher the level, the less detail. The lower the level, the more detail. The highest level of abstraction is the single system itself. The next level would be only a handful of components, and so on, while the lowest level could be millions of objects or agents. Abstraction comes from the Latin word 'abstrahere', which means to 'drag away from, remove, abort': we remove the details associated with any specific instance of the system.

A "level of abstraction" for computing is the number of abstraction layers between the physical layer (of bits and binary code) and the current representation. A layer is a code, language or protocol which offers a certain service. For example in a computer we have the language cascade from binary code to machine code, byte code and high level code, or the OSI Reference Model. The most common abstraction layer is the programming interface (API) between an application and a framework or operating system. High-level calls are made to the system, which executes the necessary instructions to perform the task.

Russ Abbott has argued in "The reductionist blind spot" that the best way to understand [[Emergence|emergence]] is through the lens of implementation - emergent properties can be described as a high level abstraction which is implemented by low level elements. The lower level of abstraction implements the higher level.

== Links ==

* Wikipedia entry for [http://en.wikipedia.org/wiki/Abstraction_(computer_science) Abstraction (computer science)]

* Russ Abbott, [http://cs.calstatela.edu/wiki/images/c/ce/The_reductionist_blind_spot.pdf The reductionist blind spot]

[[Category:Organization]]

Random Boolean Network

2011-02-11T21:45:05Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Random Boolean Networks''' are networks of boolean nodes that can
be in one of two possible states, 0 or 1, and whose evolution
from one time point to another is governed by simple boolean
transition rules. The nodes change their states according to
this boolean transition rules that depend on their current states
and those of their neighbors.
RBNs are closely related to [[Cellular Automata]] (CA) and are
used to study [[Complex System|complex systems]]. Both are usually
based on local boolean transition functions.
In RBNs we have nodes instead of Cells in CA, and connections
to remote neighbors instead of a local neighborhood grid as in CA.
RBNs and NK Networks have been proposed as a biological
model by Stuart Kauffman, see his book "The Origins of Order".

== NK Network ==

An NK-Boolean network is defined as a network of N nodes with connectivity K,
where K refers to the maximum number of nodes that regulate some othernode,
i.e. each of the N nodes has K inputs and one output.
It can be considered as a network of N light bulbs. At every timestep,
each bulb changes the state: the light bulbs can only be on or off, and each
of the bulbs influences K other bulbs in the network.

* [http://www-users.cs.york.ac.uk/susan/cyc/n/nk.htm Applet for NK networks]

== Links ==

Tutorials

* [http://www.itee.uq.edu.au/~kaiw/RBN/ RBN Tutorial] from Kai Willadsen

* [http://homepages.vub.ac.be/~cgershen/rbn/tut/index.html RBN Tutorial] from Carlos Gershenson

arXiv papers

* [http://www.arxiv.org/abs/nlin.AO/0408006 Introduction to Random Boolean Networks] from Carlos Gershenson

* [http://arxiv.org/abs/nlin/0204062 Boolean Dynamics with Random Couplings] from Leo Kadanoff et al.

== Examples ==

The Finite State Machine (FSM) for the whole boolean network reveals
the attractor structures and the basins of attraction. The
attractor - if one exists - is a fixed point or a discrete
limit cycle. The limit cycle is of course shorter than the
total number of states, which is 2^N for N nodes (2^3=8 for
3 nodes).

[[Image:RBNExample1.png|left|RBN Examples]]

[[Image:RBNExample2.png|left|RBN Examples]]

Termination Detection

2011-02-11T21:45:02Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

[[Distributed Algorithm|Distributed algorithms]] for '''termination detection''' are unique for [[Distributed System|distributed systems]] because the problem of termination detection does not exist in non-distributed systems. A large variety of algorithms exist, for instance the ones proposed by

* Mattern (e.g. "Vectoralgorithm" or "Credit-Recovery")
* Dijkstra-Feijen-Van Gasteren (1983)
* Dijkstra-Scholten (1980)

[[Category:Distributed Algorithms]]

Complex Network

2011-02-11T21:44:58Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

A '''complex network''' forms the backbone of a [[Complex System|complex system]]: the nodes correspond to the agents, entities or parts of the complex system, the edges to the interactions between them. A network is essentially anything which can be represented by a graph: a set of points, nodes or vertices, connected by links, ties or edges. In social networks, the nodes are people, and the ties between them are (variously) acquaintance, friendship, political alliance or professional collaboration. In [[Multi-Agent System|multi-agent systems]], the nodes are agents, and two nodes are connected if they interact with each other. In [[Distributed Computing|distributed computing]] and [[Distributed System|distributed systems]], the nodes are computers or processes, and the links are channels for messages. In the case of the Internet, the nodes are actual machines, and they are joined by a link when they are physically tied together. In the case of the World Wide Web (WWW), the nodes are Web sites, and they are joined when there is a hyper-link from one to the other, see C.R. Shalizi's Article "Growth, Form, Function, Crashes" below. Complex networks are special networks at the edge of chaos where the degree of connectivity is neither regular nor random. The most complex networks of the real world are either small-world networks or scale-free networks at the border between regular and random networks, between order and randomness.

== Scale-Free Networks ==

A network is named scale-free, if it does not have a certain scale. A network
with a single scale is similar to grid: every node has the same degree or the
same number of links/edges. In a [[scale-free network]], some nodes have a huge number of connections to other nodes, whereas most nodes have only a few. Typically the degree of connectivity can be described by a [[power law]].

According to Mark Newman in [http://arxiv.org/abs/cond-mat/0412004], "when the probability of measuring a particular value of some quantity varies inversely as a power of that value, the quantity is said to follow a power law, also known variously as Zipf's law or the Pareto distribution. The distributions of the sizes of cities, earthquakes, solar flares, moon craters, wars and people's personal fortunes all appear to follow power laws".

Scale-free networks and networks which can be described by power-laws are robust against accidental failures but vulnerable to deliberate attacks against hubs and supernodes.

== Small-World Networks ==

A network is called [[small-world network]] by analogy with the [[small-world phenomenon]], (popularly known as [[six degrees of separation]]). The small world hypothesis,
which has been tested in experiments (see [http://smallworld.columbia.edu/results.html The Small World Project]), is the idea that two arbitrary people are connected by only six degrees of separation, i.e. the diameter of the corresponding graph of social connections
is not much larger than six.

Small-world networks have been described first by Duncan J. Watts and Steven H. Strogatz. They appear to be 'small' because they have a small average and characteristic path length, like random or complete graphs. Yet they can be highly clustered, like regular lattices. They can be found at the edge or boundary between regular networks and random networks, and are created from regular networks through rewiring of a few short cuts.

== Common characteristics ==

Both classes of complex networks, small-world and scale-free networks
are very similar. They can be found at the edge of chaos between
complete randomness and total order. Small-world networks or graphs
emerge through the random rewiring of regular grids or lattices:
''you add randomness to order''. Scale-free networks arise in
networks if ''you add order to randomness'': instead of considering
a pure random growth of a network, you consider a random growth with
preferential attachment.

The small-world property can be associated with global connectivity
and the shortest path length, it arises in regular networks through
the addition of random shortcuts.
The scale-free property can be associated with local connectivity,
it arises in random networks through clustering.

== Researchers and Scientists ==

*[http://amaral.chem-eng.northwestern.edu/ L.A.N. Amaral]
*[http://tam.cornell.edu/Strogatz.html Steven Strogatz]
*[http://www.nd.edu/~alb/ Albert-László Barabási]
*[http://smallworld.columbia.edu/watts.html Duncan J. Watts]
*[http://www-personal.umich.edu/~mejn/ Mark Newman]
*[http://www.ingenuitygap.com/ Thomas Homer-Dixon]
== Links ==

*[http://www.nd.edu/~networks Self-Organized Networks]
*[http://www.sfu.ca/~insna/INSNA/Hot/scale_free.htm Scale-Free and Small-World Networks]

== Articles ==

* C.R. Shalizi, ''Growth, Form, Function, Crashes'', Santa Fe Institute Bulletin 15:2 (2000) [http://discuss.santafe.edu/dynamics/stories/storyReader$54]
* C.R. Shalizi, ''Complex Networks'' Notebook-Entry [http://cscs.umich.edu/~crshalizi/notebooks/complex-networks.html]

*L.A.N. Amaral and J.M. Ottino , ''Complex networks - Augmenting the framework for the study of complex systems'', Eur. Phys. J. B 38 (2004) 147-162
*A. Barabasi and E. Bonabeau, ''Scale-Free Networks'', Scientific American, May 2003, 50-59
*K. Wiesenfeld, P. Colet, S.H. Strogatz, ''Exploring Complex Networks'', Nature Vol 410 (2001) 268-276
*D.J. Watts and S. H. Strogatz., ''Collective dynamics of 'small-world' networks'', Nature Vol 393 (1998) 440-442

*M. E. J. Newman [http://arxiv.org/abs/cond-mat/0412004 Power laws, Pareto distributions and Zipf's law]
*M. E. J. Newman [http://arxiv.org/abs/cond-mat/0303516 The structure and function of complex networks]

== Books ==

*Duncan J. Watts, ''Six Degrees: The Science of a Connected Age'', W. W. Norton & Company, 2003, ISBN 0393041425
*Duncan J. Watts, ''Small Worlds : The Dynamics of Networks between Order and Randomness'', Princeton University Press, 2003, ISBN 0691117047
*Albert-László Barabási, ''Linked: How Everything Is Connected to Everything Else and What It Means'', Plume, 2003, ISBN 0452284392
*Mark Buchanan, ''Nexus: Small Worlds and the Groundbreaking Theory of Networks'', W. W. Norton & Company, 2003, ISBN 0393324427
*E. Ben-Naim, H. Frauenfelder, Z. Toroczkai, ''Complex Networks'', Springer, 2004, ISBN 3540223541

Group Selection

2011-02-11T21:44:55Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Group selection''' describes the interaction of two distinct evolutionary processes on two different scales: the level of the gene,
and the level of group (or meme). It is a special case of [[Multilevel Selection|multilevel selection]], where two processes of [[Natural Selection|natural selection]] interact with each other. In group selection, different forms of replicators support each other: genes increase the fitness of the memes in the groups of the individuals, and memes increase in turn the fitness of genes in their groups.

== Links ==

see also
* Wikipedia Entry for [http://en.wikipedia.org/wiki/Group_selection Group Selection]

* Nicholas S. Thompson, [http://www.behavior.org/journals_BP/2000/thompson.pdf Shifting the Natural Selection Metaphor to the Group Level], Behavior and Philosophy, 28, 83-101 (2000)

* David S. Wilson & Elliott Sober, [http://www.bbsonline.org/Preprints/OldArchive/bbs.wilson.html Reintroducing group selection to the human behavioral sciences], Behavioral and Brain Sciences 17 (4) (1994) 585-654

[[Category:Basic Principles]] [[Category:Evolutionary Principles]]

Self-Rejuvenation

2011-02-11T21:44:51Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Self-Rejuvenation''' or '''Self-Renewal''' is a [[Self-Star_Properties|Self-* Property]]. It is related to [[Self-Regeneration|self-regeneration]] and means that a system is able to rejuvenate and regenerate itself by replacing old parts with new ones. The major drawback of systems with [[Self-Regeneration|self-regeneration]] or [[Self-Rejuvenation|self-rejuvenation]] is related to [[Cancer|cancer]]: such a system can obviously generate a new system which destroys the old one, especially if the rejuvenation or regeneration process is organic and associated with growth, see [[Rejuvenation and Cancer]]. Self-renewal is stem cells's most fundamental property and most dangerous property.

== Related ==

* [[Rejuvenation and Cancer]]

[[Category:Self-Star Properties]]

Category:Organization

2011-02-11T21:44:48Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

Pages about organization and levels of organization

Causality Violation

2011-02-11T21:44:42Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

Causality means the cause of an event is observed before its effect is observed.
'''Causality violation''' means that the cause of an event is observed after its
effect is observed.
Violation of causality are a problem in [[Distributed System|distributed systems]]
and [[Distributed Algorithm|distributed algorithms]], because causes and causal relations
are essential to any scientific explanation. If the causal structure is unclear,
it is hard to understand a system.

Tribute Model

2011-02-11T21:44:38Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

The '''Tribute Model''' from Robert Axelrod captures the essential properties of power and explains the origin of nations and empires. The model is based upon a dynamic of "pay or else". It shows that this dynamics combined with mechanisms to
increase and decrease commitments can lead to clusters of actors that behave largely according to the criteria for independent political states.

In the model an active actor, A, may demand tribute from one of the other actors, which then have a choice of paying tribute to the demander, or fighting. The model uses two decision making '''rules''':

* demanding rule: determines which actor is selected for tribute demands. The ideal target of a demand is weak enough so that it might choose to pay rather than fight, and so that it won't cause much damage if it does choose to fight. And it should be strong enough to be able to afford to pay as much possible. A suitable decision rule combining both of these considerations is to choose among the potential targets the one that maximizes the product of target's vulnerability times its possible payment.

* fighting rule: determines if the target pays the tribute. The decision rule used for the target is simpler: fight if and only if it would cause less than the paying would.

Furthermore, the actors develop degrees of commitment to each other. The commitments are caused by their choices to pay or fight, and in turn have consequences for how they will pay or fight in the future. The '''rules for commitment''' are as follows. Initially, no agent has any commitments to other agents, and each agent is fully committed to itself. Commitment of i to j increases when:

* i pays tribute to j (subservience),
* i receives tribute from j (protection), or
* i fights on the same side as j (friendship).

Similarly, commitment decreases whenever: i fights on the opposite side as j (hostility).

== Links ==

* Axelrod paper about [http://www-personal.umich.edu/~axe/research/Building.pdf Building New Political Actors]

[[Category:Agent-Based Model]]

Replication

2011-02-11T21:44:35Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Replication''' in computer science refers to the creation and the use of redundant resources, such as
software or hardware components, to improve availability, reliability, [[Fault Tolerance|fault tolerance]], or performance.
Replication typically involves replication in space, in which the same application or data is stored on multiple
file systems or the same computing task is executed on multiple devices, or replication in time, in which
a computing task is executed repeatedly on a single device.

One can distinguish roughly between two types of replication

* '''Active Replication''' all replicas work productively, each replica plays the same role and is active in every operation
* '''Passive Replication''' only one replica works productively (the primary), the other replicas become active only if the primary fails

Strong usage of active replication increases of course the [[Redundancy|redundancy]] among the
active components of the systems, and leads therefore to a higher probability of inconsistencies
and consistency problems.
'''Optimistic replication''' tries to achieve a trade-off between high consistency and
low latency by assuming that problems and conflicts during updates will occur rarely,
if at all.

== References ==

[http://portal.acm.org/citation.cfm?id=1057980&dl=GUIDE&coll=GUIDE Optimistic replication], Yasushi Saito and Marc Shapiro, ACM Computing Surveys (CSUR), Volume 37, Issue 1 (March 2005)

[[Category:Applied Principles]]

Dissemination Model

2011-02-11T21:44:32Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

The '''Dissemination Model''' describes the emergence of culture. Culture means here the differences between individuals and groups which continue to exist in beliefs, attitudes, and behavior. It was created by Robert Axelrod. The model shows how local convergence can create global polarization of cultural "traits".

In the model the agents are placed at fixed sites. The basic premise is that the more similar an agent is to a neighbor, the more likely that that agent will adopt one of the neighbor's traits:

* step1: at random, pick a site to be active, and pick one of its neighbors
* step2: with probability equal to their cultural similarity, these two sites interact. An interaction consists of selecting at random a feature on which the active site and its neighbor differ (if there is one) and changing the active site's trait on this feature to the neighbor's trait on this feature

== Links ==

* Axelrod's paper about [http://www-personal.umich.edu/~axe/research/Dissemination.pdf The Dissemination of Culture]

[[Category:Agent-Based Model]]

MML

2011-02-11T21:44:26Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

The '''micro-macro link''' (MML) problem in sociology and distributed artificial intelligence (DAI) is the connection of [[Microlevel|microscopic]] and [[Macrolevel|macroscopic]] levels, how actors give rise to macroscopic social patterns and structures, and how these structures influence in turn individual actors. Understanding the micro-macro link means to understand the possible [[Emergence|emergent properties]] of the system. A solution of the MML is needed for the engineering of self-organizing systems ([[ESOS]]).

== Links ==

* [http://www.sociologica.mulino.it/journal/article/index/Article/Journal:ARTICLE:179 The Micro-Macro Link in Social Simulation]

* [http://www.virtosphere.de/data/publications/articles/schillo+.lnai1979.pdf The Micro-Macro Link in DAI and Sociology]

[[Category:Organization]]

ESOS

2011-02-11T21:44:24Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

The '''engineering of self-organizing systems''' (ESOS) is a contradiction in itself: how can you organize something which organizes itself? If we want to build a self-organizing system with autonomous agents, then how can we ensure the function ? Agents do by defintion what they want. How can you construct a self-organizing system? The answer is: in a balanced, iterative process which combines top-down analysis with bottom-up simulation, where we step by step define the 'rules of the game'. The bottom-up process is needed ensure diversity (innovative, random, surprising elements). The top-down process ensure unity (e.g. function, quality and goal-orientation). Together they form a cyclic round-trip process, which can be named synthetic microanalysis.

== A Two-Way Approach to the MML ==

The [[MML|micro-macro link]] (MML) problem probably needs a two-way or two-phase approach to find the necessary micro-macro connections, including a bottom-up and a top-down process. The way up means synthesis, simulation or experiments, and determines how individual actions are combined and aggregated to collective behavior. The way down means analysis, creation of testable hypotheses, or translation of requirements, and defines how collective forces influence and constrain individual actions.

We can only generate complex [[Self-Organization|self-organizing]] systems with [[Emergence|emergent]] properties in a goal-directed, straightforward way if we look at the microscopic level and the macroscopic level (for local and global patterns, properties and behaviors), examine causal dependencies across different scale and levels, and if we consider the congregation and composition of elements as well as their possible interactions and relations. A complex system can only be understood in terms of its parts and the interactions between them, if we consider static and dynamic aspects. In other words we need a combination of top-down and bottom-up approach, which considers all sides: static parts and dynamic interactions between them, together with the macroscopic states of the system and the microscopic states of the constituents. Sunny Y. Auyang has proposes a method named “synthetic microanalysis” which claims to combine synthesis and analysis, composition and decomposition, a bottom-up and a top-down view, and finally micro- and macrodescriptions. She describes the idea vividly in chapter 2 of her interesting book, but unfortunately she does not say how her approach works for MAS exactly. The book focuses on complex systems in general, and physical systems (with particles instead of agents) in particular.

The general idea is a “bottom-up deduction guided by a top-down view”. You have to delineate groups of “microstates” according to causal related macroscopic criteria (by “partitioning the microstate space”, for instance through selection of all elements with a certain property or role related to some macroscopic structure). Making a round trip from the whole to its parts and back, you can use the desired global macroscopic phenomena to design suitable local properties and interactions. This two-way approach is a generalization of the “experimental method” proposed by Bruce Edmonds and Joanna Bryson. In the theoretical top-down phase you have to create testable hypotheses, which have to be verified in the experimental bottom-up phase. Instead of “Synthetic Microanalysis” you could also name it iterative goal-directed simulations (where the goals are determined by high-level objectives and overall requirements).
The experimental bottom-up approach alone is successful only for small and simple systems like 1-dim Cellular Automata, where you can enumerate all possible systems. For large systems the amount of possibilities and number of configurations grows so large (or even "explodes") that the goal gets lost or the thicket of microscopic details becomes impenetrable. To quote Auyang again: “blind deduction from constituent laws can never bulldoze its way through the jungle of complexity generated by large-scale composition” (p.6).
The macroscopic view is useful and necessary to delineate possible configurations, to identify composite subsystems on medium and large scales, to set goals for microscopic simulations and finally to prevent scientists from losing sight of desired macroscopic phenomena when they are immersed in analytic details.

== Iterations and Refinements ==

[[Image:Topdown_vs_Bottomup.png|300px|thumb|left|Top-Down vs. Bottom Up]]
One round trip from the whole to its parts and back is probably not enough to generate complex self-organizing systems with emergent phenomena. If the two-way method of “synthetic microanalysis” works at all, you will certainly need some iterations and a number of stepwise refinements until the method converges to a suitable solution.
It is important to identify and refine before each iteration suitable subsystems, basic compounds and essential phenomena on the macroscopic level, which are big and frequent enough to be typical or characteristic of the system, but small and regular enough to be explained well by a set of microscopic processes. Many macroscopic descriptions are only an approximation, idealization and simplification of real processes.

In the first top-down phase towards the bottom level, we must find the significant, relevant and salient properties, events and interactions, especially the crucial events responsible for butterfly effects, avalanches and cascades. We seek the concrete, precise and deterministic realization of abstract concepts. Many microscopic details are insignificant, irrelevant and inconsequential to macroscopic phenomena. In the second bottom-up phase towards the top level, you have to compare the results of the synthesis and simulation which the desired structure.

In a typical iteration of “synthetic microanalysis”, you start from the “top” and work your way down to the micro-level, constructing agent roles and interaction rules in just the way necessary to generate the behavior observed on “top”. This procedure can be iterated by stepwise refinement of agents and their interactions, which should include necessary changes in the environment, until the desired function is achieved.
In the next round, you start start again from the global structure or macroscopic pattern, and try to refine the possible underlying microstates and micromechanisms.
Could these states and mechanisms lead to the desired large-scale structure? What kind of coordination, conflict-resolution and local guidance is needed additionally? What kind of roles and role-transitions are possible?

Thus you would proceed roughly like this while trying to determine possible states, roles and role transitions:

:'''Phase 1. Analysis and Delineation'''
:Starting from requirements and global objectives, what macroscopic and microscopic patterns, configurations, :situations and contexts are possible in principle? From the answers you can try to delineate what roles, behaviors, :local states and local interactions are roughly possible or necessary:
:a) What roles and local behavior are possible? Try to determine and deduce local behavior from global behavior, :identify possible roles and role transitions.
:b) What states possible? Determine and define local properties from global properties.
:c) What kind of local communication and coordination mechanisms possible? Determine tolerable conflicts and :inconsistencies.

:'''Phase 2. Synthesis and Simulation'''
:Is the desired global behavior achievable with the set of roles and role transitions? In the second phase, you work :your way up to the top again through comprehensive simulations and experiments.
:Since emergent properties are possible, simulation is the only major way up from the bottom to the top. As Giovanna :Di Marzo Serugendo says “the verification task turns out to be an arduous exercise, if not realized through :simulation”.
:Sometimes the term “emergence” itself is even defined through simulation, for instance in the following way: a :macrostate is weakly emergent if it can be derived from microstates and microdynamics but only by simulation.

The way up is simpler than the way down and requires mainly simulations. Since these simulations can be quite time consuming, it can be slower than the top-down process. In mathematical calculus, the situation is quite similar: many integrals can only be solved and determined numerical by numeric calculations, whereas differentiation is much easier and requires often only sophisticated analysis and analytic techniques.
There are more similarities: the fundamental theorem of calculus also connects the purely algebraic indefinite integral and the purely analytic (or geometric) definite integral. Likewise, a method of synthetic microanalysis should combine simulations (preferably bottom-up) and “analytic” (preferably top-down) considerations.

== Genetic Algorithms ==

[[Image:SMA.png|300px|thumb|right|Synthetic Microanalysis]]
The methods of synthetic microanalysis and evolutionary algorithms are quite similar, see the figure for a comparison. Both require the use of simulation, experimentation and selection. In the case of evolutionary algorithms without “humans in the loop”, the fitness evaluation is done automatically by fitness functions, in the case of synthetic microanalysis with “humans in the loop” it is done by the human engineer.

These two approaches – Synthetic Microanalysis and Genetic Algorithms – are probably the only two systematic solutions to create self-organizing Multi-Agent Systems with emergent properties. There are two obvious solutions to build a self-organizing system that meets the requirements and objectives: The imitation of natural systems, for instance in form of biologically and sociologically inspired system, or manual trial-and-error. The first method can only be applied to transfer existing solutions, the second is not systematic. As Edmonds says, “we are to do better than trial and error…we will need to develop explicit hypotheses about our systems and these can only become something we rely on via replicated experiment.”

* The advantage of '''Synthetic Microanalysis''' is that we are able to understand the solution. The drawback is that is still requires a human-in-the-loop: constant manual intervention, observation, consideration, delineation and design are essential.

* The advantage of '''Genetic Algorithms''' is that they do not require a human-in-the-loop. The drawback is that we are often not able to understand the result. It is often hard to understand why the result is optimal (and none of the other solutions) and how it works exactly.

== Science vs. Engineering ==

[[Image:Scientific_Method.png|320px|thumb|left|The Scientific Method]]
This SMA method is nothing else but the
scientific method applied to engineering,
the combination of engineering and science.
The application of the scientific method by the engineer
is the solution to the fundamental [[ESOA]] and ESOS problem
It is the step-by-step investigation of hypotheses with experiments
and simulations.

The scientific method is an iterative process that is the basis for any scientific inquiry, and it can also be used to examine artificial systems and simulated worlds (for instance synthetic societies of multi-agent systems). The scientific method follows a series of four basic steps: observe-formulate-predict-test

:(1) identify a problem you would like to solve,
:(2) formulate a hypothesis,
:(3) test the hypothesis,
:(4) collect and analyze the data,
:(5) make conclusions and restart with (1)

Remarkably, some computer scientists do not
want to hear this: the scientific method applied
to engineering. They are of course scientists,
and as scientists they use of course the
scientific method. How do we dare to question
this? Yet there is a clear difference between science
and engineering, between the scientist and the engineer.
The scientist tries to explain complexity by simple rules,
the engineer tries to hide complexity by simple user interfaces.
The scientist tries to explore nature by building machines,
the engineer tries to build machines by exploring possible constructions.

The scientist seeks to understand what is,
the engineer seeks to create what never was.
The engineer explores in order to build,
the scientist builds in order to explore.

What happens if both meet each other, if we
combine the characteristics of pure engineering
with pure science? Surprisingly, the best
and worst. The worst are "buzzword engineers" who
produce only hot air and "engineering scientists"
who only seek to create problems that never were before.
They are scientists and engineers who have got it wrong:
engineers should not conceal the truth and produce
complexity, they should hide complexity and produce the truth.
(unfortunately, many computer scientists fall in
this category. There are so many hot air merchants
at the universities.. In German you call them
"Schwindler" or "Schaumschläger". All they do is
producing hot air and complex useless frameworks
while inventing new buzzwords and acronyms.
In Marketing this is ok, but in computer science..
They are a bit like intelligent ELIZA bots,
which never will achieve real intelligence, they
only produce a perfect illusion of intelligence.
Likewise, Schaumschläger will never produce any
real progress to science, but a perfect illusion
of progress. They are good in selling themselves,
in getting jobs and grants, and in pretending
to be important.).

But there are also the opposite
cases. The best cases are "theory engineers" or "scientific
engineers": scientists who construct new theories,
or engineers who discover new laws in engineering,
and new ways to build new types of systems.
Albert Einstein comes to mind.

These are the extremes.
Between the extremes, if we leave the best and
the worst cases behind, we find the
engineer who seeks to understand the
useful system he his building,
and the scientist who seeks to create
new kind of interesting theories that never
existed before.
Exactly what we need for a cyclic
round-trip process, which can be named
synthetic microanalysis (the scientifc method
for the engineer which means rapid prototyping
and agile development).

== Books and References ==

* Ottino, J. M., Engineering complex systems, Nature 427 (2004) 399
* Johnson, S., Emergence, Scribner, 2002
* Holland, J. H., Emergence from chaos to order, Oxford University Press, 1998
* Axelrod, R., Chapter 6 “Building New Political Actors” of Complexity of Cooperation, Princeton University Press, 1997
* Maes, P, Modeling Adaptive Autonomous Agents, in Artificial Life, Christopher G. Langton (Ed.), The MIT Press, (1995)
* Edmonds, B. & Bryson, J. (2004) The Insufficiency of Formal Design Methods - the necessity of an experimental approach for the understanding and control of complex MAS. In Proceedings of the 3rd Internation Joint Conference on Autonomous Agents & Multi Agent Systems (AAMAS'04), New York, ACM Press
* Edmonds, B. (2004) Using the Experimental Method to Produce Reliable Self-Organised Systems. In Brueckner, S. et al. (eds.) Engineering Self Organising Sytems: Methodologies and Applications, Springer LNAI 3464, (2005) 84-99
* Yamins, D., Towards a Theory of "Local to Global" in Distributed Multi-Agent Systems, In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2005), Utrecht, ACM Press
* Jonathan Rauch, Seeing Around Corners, The Atlantic Monthly, April 2002
* Conte, R. and Castelfranchi, C., Simulating multi-agent interdependencies. A two-way approach to the micro-macro link, in Klaus G. Troitzsch et al. (Eds.), Social science microsimulation, Springer (1995) 394-415
* Auyang, S.Y., Foundations of Complex-system theories, Cambridge University Press, 1998
* Serugendo, G.D.M., Engineering Emergent Behaviour: A Vision, Multi-Agent-Based Simulation III. 4th International Workshop, MABS 2003 Melbourne, Australia, July 2003, David Hales et al. (Eds), LNAI 2927, Springer, 2003
* Mark A. Bedau, Weak Emergence, In J. Tomberlin (Ed.) Philosophical Perspectives: Mind, Causation, and World, Vol. 11, Blackwell (1997) 375-399
* Suzuki, J. and Suda, T., A Middleware Platform for a Biologically Inspired Network Architecture Supporting Autonomous and Adaptive Applications, In IEEE Journal on Selected Areas in Communications (JSAC), Special Issue on Intelligent Services and Applications in Next Generation Networks, vol. 23, no. 2 (2005) 249-260
* Montresor, A., Meling, H. and Babaoglu, O., Messor: Load-Balancing through a Swarm of Autonomous Agents, In Proceedings of the 1st International Workshop on Agents and Peer-to-Peer Computing, Bologna, Italy, July 2002, also a Technical Report UBLCS-2002-11, University of Bologna, Italy.
* Gershenson, C., A General Methodology for Designing Self-Organizing Systems, submitted preprint at http://uk.arxiv.org/abs/nlin.AO/0505009

== Links ==

Henry Petroski, [http://www.americanscientist.org/issues/pub/2008/3/scientists-as-inventors Scientists as Inventors], American Scientist Vol. 96 Sep-Oct. (2008) 368-371

Kin Selection

2011-02-11T21:44:20Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Kin Selection''' is the [[Natural Selection|natural selection]] of shared genes in the genotype by altruistic behavior in the related phenotypes. Organisms tend to favor the reproductive success of their relatives, even at a cost to their own survival and/or reproduction, because they share genes with them, and therefore indirectly increase the reproductive success of their own genes.

== Links ==

* Wikipedia Entry for [http://en.wikipedia.org/wiki/Kin_selection Kin Selection]

[[Category:Basic Principles]] [[Category:Evolutionary Principles]]

Supervenience

2011-02-11T21:44:17Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Supervenience''' is a form of strong [[Emergence|emergence]] characterized by independence in interdependence: a system A is causal independent from a system B, and yet physically embedded in it. To say that A supervenes on B means that B implements A: there can be no change in A without a change in B. In this sense, implementation is the opposite of supervenience. If a system A is embedded in and implemented by a system B, it is usually not possible to say who chances in system B affect system A. The system A can be unaffected, or it can stop to work at all. They are causal independent of each other. And yet there cannot be a difference in the system A without difference in the underlying system B, because the system A is embedded, realized and implemented by system B.

In a more formal way, supervenience is a kind of dependency relationship, typically held to obtain between sets of properties. A set of properties A is supervenient on a set of properties B, if and only if any two objects x and y which share all properties in B (are "B-indiscernible") must also share all properties in A.

Supervenience is related to trancendence, the state of being or existence above and beyond the limits of a system. It can be considered as a first step towards trancendence: if a system A which supervenes B is embedded and implemented in a system C, it has transcended B, because it exists above and beyond the limits of system B.

== Examples ==

A common example is the mind (system A) which supervenes on the brain (system B): any change in one's mental state implies that there has been some kind of change in one's brain state. Another example is a virtual machine which runs on a host computer. A virtual machine is a software implementation of a machine (computer) that executes programs like a real machine. A program which is executed on the virtual machine is independent from the hardware of the host machine, and yet it is executed by it. The commom examples are:

* biological properties supervene on physical properties
* mental states supervene on neurophysiological states
* software supervenes on hardware
* a virtual machine supervenes on a a real computer

== Links ==

* [http://en.wikipedia.org/wiki/Supervenience Supervenience] in Wikpedia
* [http://plato.stanford.edu/entries/supervenience/ Supervenience] in Stanford Encyclopedia of Philosophy

Invisible Hand

2011-02-11T21:44:13Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

In economics, the '''invisible hand''' is used to describe the self-regulating nature of the marketplace. The invisible hand is a metaphor coined by the economist Adam Smith in "The Wealth of Nations". For Smith, the invisible hand was created by the conjunction of the forces of self-interest, competition, and supply and demand, which he believed would provide the best outcome for society provided that government did not interfere with these forces.

== Origin of the Metaphor ==

Adam Smith (1723-1790) uses the metaphor in Book IV of ''The Wealth of Nations'', arguing that people in any society will employ their capital in foreign trading only if the profits available by that method far exceed those available locally. In such a case, Smith argues, it is better for society as a whole if they so do.

: "[An individual is] led by an '''invisible hand''' to promote an end which was no part of his intention. Nor is it always the worse for the society that it was not part of it. By pursuing his own interest he frequently promotes that of the society more effectually than when he really intends to promote it. I have never known much good done by those who affected to trade for the public good. It is an affectation, indeed, not very common among merchants, and very few words need be employed in dissuading them from it."

== Interpretation ==

Adam Smith argued that, in a free market where actions are not orchestrated or organized by a central command, an individual pursuing his own interests tends also to promote that of the society as a whole through a principle that he called “the invisible hand”. Producers and consumers, in the pursuit of profits, are led, as if by an invisible hand, to do what is best for the community. This sounds paradox: a population of self-centered, selfish human beings, working in their own self-interest, can make the world a better place for the whole population. Everyone creates value for himself, and as a side-effect valuable contribution is made for the community as a whole.

Adam Smith's invisible hand can be considered as [[Self-Organization|self-organization]], but the mystery behind the invisible hand is just the free market and the principle of supply and demand. A market is a mechanism which finds for every lack of supply someone who is responsible to organize it, by connecting the interests of the individual (making profit) with the interests of the public (guarantee supply). A severe lack of supply is an irresistible incentive to make money by founding or opening a business because it creates a true market niche. A surplus of supply an incentive to shut down a business, because the market niche closes and one can no longer make profit. Therefore greed will drive actors to beneficial behavior which is good for the society as a whole, because there is no lack of products and the supply is evenly distributed. And when all people constantly struggle to become wealthier, then they will increase therefore the total sum of wealth.

Thus by pursuing their private self-interest, people can create a common public good as a side-effect. This works well if the interests of the self and the collective are closely connected.

== Links ==

* Wikipedia Entry for the [http://en.wikipedia.org/wiki/Invisible_hand Invisible Hand]

Cellular Automata

2011-02-11T21:44:10Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Cellular Automata''' are regular arrays of identical finite state automata whose next state is determined solely by their
current state and the state of their neighbours, usually by a boolean transition function. They are closely related to
[[Random Boolean Network|Random Boolean Networks (RBN)]]. A CA contains many cells and each cell is a finite-state automaton
connected to its neighbors - and so the whole machine or device is called a cellular automaton (pl. cellular automata). They
were introduced by the mathematician John von Neumann in the 1950s as simple models of biological self-reproduction, and they
are elementary models for [[Complex System|complex systems]] and processes consisting of a large number of simple, homogeneous,
locally interacting components.

== Definition ==

A suitable definition of [http://en.wikipedia.org/wiki/Cellular_Automata Cellular Automata] is according to [http://mathworld.wolfram.com/CellularAutomaton.html mathworld] the following statement: "A cellular automaton
is a collection of colored cells on a grid that evolves through a number of discrete time steps according to a set
of rules based on the states of neighboring cells." The two most common neighborhoods in the case of a
two-dimensional cellular automaton on a square grid are the
[http://mathworld.wolfram.com/MooreNeighborhood.html Moore neighborhood] (a square neighborhood) and the
[http://mathworld.wolfram.com/vonNeumannNeighborhood.html von Neumann neighborhood] (a diamond-shaped neighborhood).

== Types ==

Stephen Wolfram proposed a classification of cellular automaton rules into four types, according to the results of evolving the system from a "disordered" initial state:

* I. Evolution leads to a homogeneous state.
* II. Evolution leads to a set of separated simple stable or periodic structures.
* III. Evolution leads to a chaotic pattern.
* IV. Evolution leads to complex localized structures, sometimes long-lived.

David Epstein proposed a [http://www.ics.uci.edu/~eppstein/ca/wolfram.html classification] of cellular automaton rules into only three types:

* Contraction impossible
* Expansion impossible
* Both expansion and contraction possible

== Applets ==

Good Cellular Automata applets, including 1-dimensional CA and 2-dimensional CA where you can edit the rules online, can be found at the site [http://www.sussex.ac.uk/space-science/ca.html]. Rules with complex patterns are for instance Wolfram's [http://mathworld.wolfram.com/Rule30.html Rule 30] and or [http://mathworld.wolfram.com/Rule110.html Rule 110]. Mirek's Java Cellebration [http://psoup.math.wisc.edu/mcell/mjcell/mjcell.html MJCell] is a Java applet that allows playing 300+ Cellular Automata rules and 1400+ patterns. It can play rules from 13 CA rules families. A nice tutorial from David J. Eck about Cellular Automata and "the edge of chaos" can be found [http://math.hws.edu/xJava/CA/index.html here].

== Game of Life ==

[http://en.wikipedia.org/wiki/Conway's_Game_of_Life Conway's Game of Life] is one of the most popular two-dimensional CA.
It was invented by John H. Conway. The rules are very simple:

'''Birth''' If an unoccupied cell has 3 occupied neighbors, it becomes occupied.
'''Survival''' If an occupied cell has 2 or 3 neighbors, the organism survives to the next generation.
'''Death''' If an occupied cell has 0..1 or 4..8 occupied neighbors,
the organism dies (0,1: of loneliness; 4-8: of overcrowding).

A description of the game can be found at the [http://mathworld.wolfram.com/Life.html mathworld] site.

Interactive Website by Paul Callahan: [http://www.math.com/students/wonders/life/life.html What is the Game of Life]

More about Conway's Game of Life :
http://www.tech.org/~stuart/life/rules.html

Interactive Essay: Exploring Emergence [http://llk.media.mit.edu/projects/emergence/life-intro.html The Facts of Life]

John Conway's Game of Life - Applet by Edwin Martin
[http://www.bitstorm.org/gameoflife/]

John Conway's Game of Life - Applet by Alan Hensel
[http://www.ibiblio.org/lifepatterns/]

== Larger than Life ==

Available in MJCell: Larger than Life
(an extension of the Game of Life to a larger radius or diameter)
[http://psoup.math.wisc.edu/mcell/mjcell/mjcell.html]

== Scientists ==

[http://en.wikipedia.org/wiki/Stephen_Wolfram Stephen Wolfram] is the author
of the computer program Mathematica, the founder of Wolfram Research, and mainly
known for his work about cellular automata.
Andrew Ilachinski works for the [http://www.cna.org/ Center for Naval Analyses (CNA)], USA.

Tommaso Toffoli is a Professor in the Electrical and Computer Engineering Department at Boston University. He has done a lot of work about Cellular Automata (CA), and a large parts of his CA work resembles Stephen Wolfram's and Edward Fredkin's approach to understand physical systems trough CA simulations. Some Publications can be found [http://pm1.bu.edu/~tt/publ.html here].

== References ==

* [http://cscs.umich.edu/~crshalizi/notebooks/cellular-automata.html C.R. Shalizi's Notebook Entry on CA]
* [http://mathworld.wolfram.com/CellularAutomaton.html Mathworld Entry for CA]
* [http://en.wikipedia.org/wiki/Cellular_automaton Main Wikipedia Entry for CA]
* [http://en.wikipedia.org/wiki/Conway's_Game_of_Life Main Wikipedia Entry for Conway's Game of Life]

== Books ==

There are two major books on Cellular Automata:

* Stephen Wolfram, ''A new kind of science'', Wolfram Media, Inc., 2002 [http://www.wolframscience.com/nksonline]
* Andrew Ilachinski, ''Cellular Automata: A Discrete Universe'', World Scientific, 2001, ISBN 9810246234

Other, less popular books:

* Tommaso Toffoli and Norman Margolus, ''Cellular Automata Machines: A New Environment for Modeling'', MIT Press, 1987, ISBN 0262200600
* Howard Gutowitz (editor), ''Cellular Automata: Theory and Experiment'', MIT Press, 1990, ISBN 0262570866

Context

2011-02-11T21:44:07Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

The '''context''' of an entity is specified by the current
situation, the actual state of the environment,
and the circumstances and conditions which "surround"
it. For mobile entities (for example mobile [[Agent|agents]],
mobile robots or mobile phones) it is determined by the
the current place and position in space and time.

== References ==

Wikipedia Entries for [http://en.wikipedia.org/wiki/Context Context],
[http://en.wikipedia.org/wiki/Context_adaptation Context_adaptation], and
[http://en.wikipedia.org/wiki/Context_awareness Context_awareness]

Scalability

2011-02-11T21:44:03Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

'''Scalability''' means how well a solution to some problem will
work when the size of the problem increases. The degree of scalability
determines how much a system can be expanded without performance degradation or
alteration of the internal structure of the system.

== Definition ==

Scalability can be defined formally as the capability of a system or application
or product to continue to function well without performance loss under increasing
load by adding additonal resources or instances of the system. Couloris et al.
[http://www.cdk4.net/] define scalability as follows: "a distributed system is ''scalable''
if the cost of adding a user is a constant amount in terms of the resources that must be added".
The system can serve an increasing demand or a larger number of users by adding additional instances
or devices. The IEEE definition says it is "the ability to grow the power or capacity of a system by adding components" [http://www.ieeetcsc.org/content/tfcc-4-1-gray.shtml]. The key scalability technique
is just as in [[Fault Tolerance|fault tolerance]] replication: a service can be replicated at many nodes to serve a larger demand. Scalability is also related to and sometimes required for [[Load Balancing|load balancing]]. A large-scale Internet application must be parallelized and replicated to scale well.

Werner Vogels, CTO of Amazon.com, mentions on his personal weblog: "A service is said to be scalable
if when we increase the resources in a system, it results in increased performance in a manner
proportional to resources added." (see [http://www.allthingsdistributed.com/2006/03/a_word_on_scalability.html]).
Scalability refers to the property of a system architecture which
determines the limit of the ability to grow and to scale up.
Ken Birman gives in his article "Can Web Services Scale Up ?" the following definition
of a scalable system: "In a nutshell, a scalable system is one that can flexibly accommodate
growth in its client base. Such systems typically run on a clustered computer
or in a large data center and must be able to handle high loads or sudden
demand bursts and a vast number of users. They must reliably respond even
in the event of failures or reconfiguration. Ideally, they’re self-managed and
automate as many routine services such as backups and component upgrades as possible".

== Ways and Means ==

The key to scalablity are the [http://en.wikipedia.org/wiki/Kiss_principle KISS principle]
and the four "S": to keep it simple, stateless, scriptable and small.
'''Simple''' components have their advantages.
It is well-known in software engineering that simple
components and simple processes offer less possibilities
to make errors and mistakes. The less code you write, the less can go wrong
and the less there is to maintain. Hotmail engineer Phil Smoot said
in an [http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=355 ACM interview]
(ACM queue, Vol. 3 No. 10, December/January 2005-2006):
"New hires tend to want to do complex things,
but we know that complex things break in complex ways. The veterans
want simple designs, with simple interfaces and simple constructs
that are easy to understand and debug and easy to put back together
after they break." A lot of relatively small and simple commodity
machines will not only be cheaper than a few big and expensive machines, they
also scale much better and offer a better fault-tolerance.

Statelessness is often the essential key.
'''Stateless''' nature of the system means high scalability.
If servers, objects, components or EJBs are stateless
and have no private state, they can be replicated easily.
[[Redundancy]] and replication become very difficult
subjects if the corresponding entities or objects are stateful:
the state must be consistent among all replicated instances
(consistency), and an access should either affect all or none
of the replicated objects (atomicity).

Stateless means simple processes, and simple solutions are
always good. Communication with Web Servers over pure
HTTP is stateless - probably one reason why the world-wide
web is very scalable and successful.
Phil Smoot said about the MSN service in the ACM interview
"In general, we try to keep no session affinity between a
Web server that is performing a given page paint
and the middle-tier servers that manage the transactions
against the underlying data stores."

In order to reach statelessness, one can store something
for instance in the database layer, if it needs to be
stateful. This is sometines considered as "push all state
down to the database".
A typical request in such a logical three tier architecture
triggers the following actions: "loading state for a set of
objects from the database, operating on them, pushing their
state back down into the database (if needed), writing the
response, and then getting the hell out of there i.e. releasing
all references to objects loaded for this request, leaving them
for garbage collection", see [http://naeblis.cx/rtomayko/2005/05/28/ibm-poop-heads].

'''Scriptable''' applications are easy to automate.
Hotmail engineer Phil Smoot said in an ACM interview:
"Our operation group never wants to rely on any
sort of user interface [or complex GUI]. Everything
has to be scriptable and run from some sort of command
line. That's the only way you're going to be able
to execute scripts and gather the results over
thousands of machines".

In a large system, you have to assume that everything
is going to fail, whether software or hardware.
Failure of components in any small-scale system is the exception, not
the rule, whereas failure of components in any large-scale system is
the rule, not the exception. Therefore you have to design "for failure"
in any large-scale system, i.e. you have to design the system as
if any component could fail at any time.
Thus an important means to achieve scalability is to make
[[Self-Star Properties|self-* properties]] a part of the system
(self-configuration, self-management, self-inspection, self-repair), the
system has to observe, heal and regenerate itself constantly.
There are completely new problems on massive scales
(the probability of failures and faults increases,
and there is always some node that fails, thus
assume that nodes fail and try to keep the system
healthy through continuous refresh and recovery
oriented computing).

== Multi Tier Architecture ==

A physical three tier architecture alone is not necessarily
more scalable than a two tier architecture, because it
expands in the wrong direction and can cause "remote object
hell". This is illustrated nicely by Ryan Tomayko in his blog, see [http://naeblis.cx/rtomayko/2005/05/28/ibm-poop-heads]

"Many large enterprise web applications tried really hard to implement a Physical Three Tier Architecture, or they did in the beginning. The idea is that you have a physical presentation tier (usually JSP, ASP, or some other *SP) that talks to a physical app tier via some form of remote method invocation (usually EJB/RMI, CORBA, DCOM) that talks to a physical database tier (usually Oracle, DB2, MS-SQL Server). The proposed benefits of this approach is that you can scale out (i.e. add more boxes) to any of the physical tiers as needed.

Great, right? Well, no. It turns out this is a horrible, horrible, horrible way of building large applications and no one has ever actually implemented it successful. If anyone has implemented it successfully, they immediately shat their pants when they realized how much surface area and moving parts they would then be keeping an eye on.
The main problem with this architecture is the physical app box in the middle. We call it the remote object circle of hell. This is where the tool vendors solve all kinds of interesting what if type problems using extremely sophisticated techniques, which introduce one thousand actual real world problems, which the tool vendors happily solve, which introduces one thousand more real problems, ad infinitum... It's hard to develop, deploy, test, maintain, evolve; it eats souls, kills kittens, and hates freedom and democracy."

== Examples and Applications ==

Open source software is an important factor in achieving
scalability. Yahoo uses open source software as - FreeBSD,
Apache, Python, PHP, Perl, and MySQL - to achieve scalability.
Like Yahoo, Google is an academic organization and has
an open source attitude.

Massively scalable architectures are rare. They can be found
in the proprietary systems of the large IT companies, which
have literally thousands of servers, millions of users and
billions of transactions per day. The question if you
get better performance or not if you are adding more and more
boxes and computers is of crucial importance to these
companies.

'''Google''' has a special design of its hardware infrastructure - Google uses a highly redundant cluster architecture of custom made commodity desktop PCs - and an own Google file system (GFS). The principle is to use lots of relatively small and inexpensive machines instead of a few big and expensive machines. Goolge has also functional server pools (for instance web servers, index servers and document servers) like eBay. Google uses Python extensively since the beginning, and they
have even hired the Python creator Guido van Rossum. Many components of the Google spider and
search engine seem to be written in Python.

'''Amazon''' uses mainly its own proprietary custom software in C/C++, Java, SQL, Perl, on Linux servers, and partially Oracle's Real Application Clusters (RAC) software. It uses "a homegrown message queuing architecture and Web services to wire together its collection of internally written applications." (see [http://www.baselinemag.com/article2/0,3959,1455549,00.asp]) The large-scale system from Amazon is built out of many different custom-made applications or "services", about 100-150. Each of this applications has different requirements in respect of availability and consisteny, for example the order service (taking an order), the customer service (updating customer records), the reviewer service (storing customer reviews), or the catalog service (checking the availability of a particular item). Amazon uses a massive parallel and modular architecture: all small pieces of business functionality is encapsulated by different isolated and separated services, and each service is responsible for the corresponding data and data management. Amazon also uses the autonomous "team method":the same team of developers that has built and developed the service is also responsible for operating it. It can use the tools and methods it wants, as long as the desired functionality is delivered. Amazon finally uses a simple [http://www.amazon.com/gp/browse.html/104-4296443-9698339?node=13584001&no=14256891 queue service] to connect the applications of the auonomous teams that offers a reliable, highly scalable hosted queue for buffering messages between distributed application components. Components of the huge distributed application are decoupled with messages and queues so that they run independently.

'''Yahoo''' has it's own page rendering [http://patft.uspto.gov/netacgi/nph-Parser?u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=1&l=50&f=G&d=PALL&s1=5983227.WKU.&OS=PN/5983227&RS=PN/5983227 patent]. Yahoo uses like Microsoft's Hotmail service the FreeBSD operating system [http://www.serverwatch.com/stypes/servers/article.php/15915_1299361], besides the Apache Web Server and other open source software. Similar to Google, Yahoo uses open source software extensively, for example Python for its groups site. The Yahoo online groups, a comprehensive public archive of Internet mailing lists, was originally implemented in pure Python.

'''Microsoft''' MSN's services include e-Mail, Instant Messenger, news, weather, sport, etc. The Hotmail e-Mail is one of MSN's larger services and relies on more than 10,000 servers spread around the globe: they have special mail servers and storage servers. They use of course Microsoft
products (what else), "clusters" as a unit which can be build in and out on demand, and scriptable applications which can be automated.

'''eBay''' uses since the Version 3 eBay architecture J2EE technologies and IBM WebSphere [[Application Server]]. They emphasize stateless design and functional server pools (partitioning of application servers based on use cases). They don't seem to use entity beans very much. "In general, the approach that eBay is alluding to (and Google has confirmed) is that architectures that consist of pools or farms of machines dedicated on a use-case basis will provide better scalability and availability as compared to a few behemoth machines." [http://www.manageability.org/blog/j2ee?b_start:int=5]

== Links ==

* General

[http://www.allthingsdistributed.com/2006/03/a_word_on_scalability.html Werner Vogels: A word on scalability]

* eBay:

[http://www.manageability.org/blog/j2ee?b_start:int=5 Nuggets of Wisdom from eBay's Architecture]

[http://www.sun.com/service/about/success/recent/Sun_eBay6-2_forWeb.pdf eBay Creates Technology Architecture for the Future]

* Amazon

[http://www.baselinemag.com/article2/0,3959,1455549,00.asp Amazon.com at LinuxWorld: All Linux, All the Time]

* Google:

[http://www.google.com/corporate/facts.html Google's facts]

[http://www.networkworld.com/newsletters/accel/2001/00991542.html Google's secrets (from 2001)]

[http://insight.zdnet.co.uk/hardware/servers/0,39020445,39175560,00.htm The magic that makes Google tick] (ZDNet 2004)

[http://www.fastcompany.com/magazine/69/google.html How Google Grows]

[http://labs.google.com/papers/gfs.html The Google File System]

[http://labs.google.com/papers/googlecluster.html Web Search For A Planet: The Google Cluster Architecture]

* IBM:

[http://www-128.ibm.com/developerworks/websphere/library/techarticles/hipods/scalability.html Design for Scalability - an Update]

== Papers ==

* [http://www.cs.cornell.edu/projects/quicksilver/public_pdfs/webtech2.pdf Can Web Services Scale Up ?], Ken Birman

[[Category:Applied Principles]]

Segregation Model

2011-02-11T21:43:59Z

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

Thomas Schelling's '''model of segregation''' is a classic study of the effects of local decisions on the global dynamics of housing segregation patterns. It describes the emergence of segregated areas or "ghettos". In the model residents are described as agents. Agents with mild preferences for same-type neighbors, but without preferences for segregated neighborhoods, can end up producing complete segregation.

It is one of the first [[Agent-Based Model|agent-based models]] at all, where agents represent people and agent interactions represent a socially relevant process. In 1971, Thomas Schelling published an article dealing with racial dynamics called "Models of Segregation". In this paper he showed that a small preference for one's neighbors to be of the same color could lead to total segregation. He used coins on graph paper to demonstrate his theory by placing pennies and nickels in different patterns on the "board" and then moving them one by one if they were in an "unhappy" situation. The positive feedback cycle of segregation - prejudice - in-group preference can be found in most human populations, with great variation in what are regarded as meaningful differences – gender, age, race, ethnicity, language, sexual preference, religion, etc. Once a cycle of separation-prejudice-discrimination-separation has begun, it has a self-sustaining momentum.

In the model, agents interact only locally, with their direct neighbors. Each agent agrees to stay in a neighborhood with people that are mainly of another color, on condition that there are at least 37,5% with the same color in the neighborhood. More specifically, Schelling uses the following '''rules''':

* an agent with one or two neighbors will try to move if there is not at least one neighbor of the same color
* an agent with three to five neighbors needs at least two like him
* an agent with six to eight wants at least three agents of the same colour

== Links ==

* NetLogo model of Schelling's [http://ccl.northwestern.edu/netlogo/models/Segregation Segragation Model]

[[Category:Agent-Based Model]]