Transcript From Scale-Free Networks to Avogadro

From the scale-free Web to Avogadro-scale
Engineering
Complexity Science Symposium, London, March 2004
Scott Kirkpatrick, Hebrew University, Jerusalem
With thanks to: Byung-Gon Chun, Johannes J
Schneider, Uri Gordon, Erik Aurell
The physical Internet:
Outline of this talk

Information networks: vast in scale and scale-free




Designed objects also reach 10^9 units




Physical Internet – 10^9 hosts, 10^4 AS’s, accelerating growth
Web of online information – 10^14 B on surface alone
Genetic expression data – 10^9
Microprocessors and systems on a chip
Logistics for airlines, modern armies
New methods for optimal design on these scales
Methods for distributed management of growth
VLSE: very large scale engineering.

Engineering has become a study of open systems
 “Avogadro scale” a serious possibility


Physical methods and insights relevant
System properties known to be “good” or “not good enough”
at the extremes of their parameter space



What happens in between these phases?
We have limited tools for understanding such transitions.
Physics of disordered materials:



Combinatorics on large scales


Sharp vs. smeared – Harris criterion
Glass transitions
Sharp property crossovers – Friedgut’s theorem
We should care because computing is HARD at phase
boundaries.
SAT and 3-SAT: classic test cases


Parameters: N variables, M constraining clauses, M/N constant
For 3-SAT, phase diagram is known:

M/N






< 3.9
“easy,” satisfiable (probably P)
WALKSAT gives linear cost in easy regime
3.9 < M/N < 4.27 “hard,” but still satisfiable
4.15 < M/N < 4.27 1-RSB stable, implies solutions cluster
4.27… < M/N
unsatisfiable, exponential cost
Recent advances, applying message-passing, push boundary of
solubility in the “hard-SAT” region from N = 300 (exact methods) to
N = 10^7(using survey propagation as heuristic).
General technique – soften discrete variables into beliefs or surveys
Cost of WALKSAT
Random walk search is linear in N, diverges in hard-SAT region
SIDecimation truncates WALKSAT cost
Surveys and Beliefs for the SAT problem

Beliefs – probabilities that the spin is up or down


Avg. over satisfying configurations, as estimated by the local tree
Surveys – probabilities that the spin is up or down (In all
sat configurations)



This leaves a third possibility – spins that do both at different times.
Equations for beliefs and for surveys are nearly identical. We can
define hybrid methods by interpolating. They prove useful.
Use beliefs or surveys to guide decimation – this solves problem.
Propagating surveys or beliefs in a “cavity”
Self-organizing Networks, e.g. the Internet

Model introduced by Papadimitriou






Recently studied by Fabrikant et al, others.



Who pays for a network to come into existence?
What happens when only selfish incentives are acted on?
This is the domain of game theory
The “price of anarchy” is the ratio of best to worst case Nash
equilibria
(Trivia question: of what utility function is TCP/IP a Nash
equilibrium?)
Can compare selfish optimization (Nash equilibria) to “social”
equilibria (global optimization).
Available results characterize best and bound worst case
Both selfish and global optimization are in fact sharply
distributed.
A Model for Network Formation


Each link is purchased at a cost of A. Once purchased, it is
available to all.
Each site minimizes cost of their links plus sum of all distances in
hops to all other sites. Network must be connected.







Can improve this to model real asynchronous decision processes.
Sum of the costs to all sites is the “social” cost.
Ratio of the social cost of worst-case Nash Equilibrium to the social
optimum is the price of anarchy.
This is 4/3 if A < 2, and bounded between 3 and A for A large.
A < 2  equilibria range from clique to star
A > 2  equilibria include star, complex stars, trees
A > N  trees stable
Experiments to compare selfish and social optimization(BG
Chun, UCB Oceanstore group; Johannes J Schneider, Mainz)


100 “overlay network” sites
Distance metric in data presented – hops





In more realistic studies, built a realistic underlay network, used
estimated delays
Selfish optima found by allowing each site to make
asynchronous single greedy moves until Nash
equilibrium is reached
Social optima found by annealing
Neither worst nor best case seen in practice for large A
Social optimization uses more links, gives more robust
networks
Optimal solutions to the selfish network
Either a complete
graph, A < 2
Or a star configuration if
A>2
Selfish solutions with finite information horizon
Open star
Tree
10 < A < 20
N<A
2-core (sites not in tree)
3-core
Implications for design of P2P networks

Routing solutions for P2P delivery of stored material
take two forms: unstructured, structured



Structured (Chord, Butterfly, …) use rules for assigning all
links, with some local optimization
Unstructured (Gnutella, E-Donkey, all present
deployments) discover their links.
There appears to be significant potential for
optimization of either selfish or social cost.


Start with always sharing the cost of a link between 2 ends.
Doing this within unstructured networks is easiest
And on the Avogadro scale?
As presently conceived, both
Biological nanoscale fabrication, and
Quantum Computing
may involve Avogadro’s number (10^21 molecules),
but are not scale-free
Typically a unique product is manufactured
Designers unwilling to accept risk of randomized control
When flexible manufacturing reaches nanoscale, all this must change,
requiring distributed scale-free management, and soft measures of
quality to replace the rigid agent policy approach now prevalent.