## Different aspects of complexity

### Large size

Moore's Law. See previous lecture notes.

### Interconnectivity

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.

### Distribution

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.

### Uncertainty

• Process variation in semiconductor fabrication (Product binning)
• When n is extremely large, cannot afford to treat each node in a deterministic manner. Example: Newton mechanics-->Statistical mechanicsInteraction with external world including humans.
• A distributed system may have asynchronous interactions in parallel

### Heterogeneity

• Combintation to achieve the better of both choices, e.g., cache+memory, hybrid engines. (System design principle of Combination)
• Specialization to serve an important workload, e.g., face detection IC in mobile processors, graphics accelerators
• higher performance, higher efficiency
• Robustness against diverse challenges, e.g., antibodies

The low cost of manufacturing makes combination and specialization profittable

### Security

The need of security makes a system more complex.

### Reliability/Safety

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.

### Emergence

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