Different aspects of complexity

Large size

Moore's Law. See previous lecture notes.


Computers are connected with each other. For N computers, there are N(N-1)/2 pairs of connections. Metcalfe's Law says the value of the network is proportional to N^2.

Interconnectivity introduces complexity. Each node has limited capability to deal with connections. That is, a computer cannot be directly connected with a very large number of computers; a human cannot be good friends with a large number of humans (~150): we are just unable to maintain that many relationships. Network architectures have been developed to form Internet with computers. Social institutes (legal system, currency etc.), myths, ideology, religion have evolved because they allow a large number of human beings to collaborate without being a good friend with each other: they allows a more ``scalble'' human network

Chapter 2: The Tree of Knowledge of this book provides a good summary about the history and evolutionaly importance of scalable human networks.


Distributed systems with computers at different sites but connected provide many advantages: (i) reliability in that it reduces the consequence of site-specific problems, e.g., natural disasters; (ii) speed in serving users that are likely to be geographically distributed. (Read about Akamai and content delivery network)

Distribution introduces complexity because computers at all sites need to coordinate. In particular, they must maintain the consistency of states replicated on them, in order to provide a consistent view to users accessing them anywhere. Read more about this topic from this short book (accessible from computers with Rice IP.

The CAP theorem: impossibility for a distributed system to simultaneously provide all three properties: conistency, availability, and parition tolerance.



The low cost of manufacturing makes combination and specialization profittable


The need of security makes a system more complex.


Fault tolerance requires redundancy and a new layer of logic.(Triple modular redundancy)

The reliability of the new layer of logic, due to its small size and simplicity, can be ensured without redundancy, e.g., using more expensive design process like formal verification and more expensive building materials.


Question: if we consider a tree in a rainforest as a neuron, would the rainforst have some form of intelligence? If so, how would that intelligence be different from our own? Hollywood already had an answer. A large number of the same plant species can team up together to eradicate other species and take over an ecological niche, which begets the question: is there intelligence emerging from the team? YouTube: Kudzu the Wicked Plant and How The Fig Tree Strangles Other Plants