Logical structure of programs - typically hierarchical

Computations are usually done by divide and conquer method - broken down into separate functions and subroutines

Large software system structures generally resemble the structures of the organizations that created them

In a hierarchical organization information is pushed up and down the communication lines

All nodes in the hierarchy are important to the functionality of the total system

Survivability has to do with preserving an organization’s mission, or purpose

Concerns with survivability: How many nodes should be preserved to fulfill the mission?

How many can we lose?

Standard protections for survivability: security, redundancy, diversity, control system

Diversity involves different implementations for different copies

Control system involves observing the system, i.e. intrusion detection, and will try to remedy any problems

However, the control system represents a single point of failure. For example, even though the control system is placed outside of the Internet, it can be spoofed should certain nodes be taken control of

Other single points of failure include nodes, links / communication paths, and data repositories

We’ve talked mainly about logical views. It is worth noting that logical and physical views are often mapped 1: 1

Let’s play with an algorithm! Consider an unbounded number of nodes in an unbounded two-dimensional space. Each node executes the algorithm:

1. Start at (x, y), face direction a, move forward distance k - the result is a series of random dots
2. Same start position - random distribution, different distances
3. Same direction - random distribution, different distances in straight lines
4. Same distance - random distribution, equal distance in different directions
5. Same distance and direction - random distribution, equal distance and direction
6. Same point and direction - half line
7. Same point and distance - circle
8. Same point with distance in the range 0 to 10 - filled circle
9. Same point, some have same distance k and direction 90 degrees to 45 degrees, and some have same direction and distance in the range 0 to k - the letter ‘G’ (the first part gives 270 degrees of the circumference of the circle and the second part gives the radius)

Moving on….

With n (unbounded) nodes you can remove any number and see no difference

We can ‘take out’ (attack) any constant number and still be OK, BUT, if we take any fraction out we’re in trouble

The constant number of attacks - < O ( N ) - versus the number of proportional attacks - ³ O ( C )

O( logN ) is in between - it’s smaller than N and greater than C

As N increases arbitrarily, so does logN

Anything less than O (N) is acceptable

How much are these algorithms dependent on central control? Some are at the start with similar algorithms, but after that, none

With the Internet we don’t like central control

With respect to nodes, the participants don’t know when they’re successful

THE ANT CEMETARY ALGORITHM!!!!!!!!!!!!!!!!!! (Or, I will never look at another ant in the same way again)

Basically, all ants can move around and wander aimlessly until they encounter one of their dead brothers or sisters. They then pick up their fallen comrade and proceed to wander some more. If they are unfortunate enough to come across yet another stiff relative, they are obliged to drop the first carcass, pick up the new one, and wander some more. Somehow, eventually, this leads to all the dead ants winding up in the same pile. Cool. I’d love to see this.

There is no central control involved here, no global visibility, no feedback involved

There is local visibility involved, which is exactly what we want in a network - that nodes will know their neighbors

(I personally question the ‘no feedback’ issue - what if an ant runs into a buddy that’s also carrying a dead ant? Do they just ignore it? I would think someone would say something, like, ‘I couldn’t help notice that you’ve got ole Jeremiah draped over your shoulder. What’s up?’)

CHARACTERISTICS OF UNBOUNDED NETWORKS

• Absence of central administrative control
• Absence of global visibility
• Non-functional global properties
• Emergent properties: survivability, reliability, and safety

THE END