Transcript Document

Distributed Computing
Rik Sarkar
Distributed Computing
•Old style: Use a computer for computation
Distributed Computing
•New style: Use many computers for computation
Examples:
•Computing clusters (data analysis and storage,
hadoop etc)
•Networks of sensors
•Mobile systems
Why Study Distributed
Computing?
Important Applications
–Networks, Internet, power grids,
social networks, data mining….
Interesting Ideas
–Algorithms, graphs, probability,
geometry, machine learning…
Example: large network analysis
•The computers
know only the
edges, they can’t
see the graph
Example: large network analysis
•The computers
know only the
edges, they can’t
see the graph
•Problem: find the
real shape of the
graph.
Spectral Analysis
Algorithm
Network from the graph
Find the structure
behind a network.
Use that to
design better algorithms
Network from the graph
Many uses:
Routing in networks.
What are the important
links?
What are the important
web pages? (distributed
spectral analysis is
Google’s secret)
Social Networks
•Who are influential people or groups?
•What are the important topics?
•What causes communities to form?
•How do epidemics spread?
Mobile networks
•Can we analyze the location data of people?
•How do they move?
•Where do they go?
Computation in Sensor Networks
•Process the sensor data
•Find sums, averages, max, min,
distribution etc.
•Do computations using the sensors
themselves
•Use distributed algorithms
•Has to be very efficient, very fast
Summary: Distributed Computing
•Important applications in many areas
–Large scale data analysis, Sensing and
understanding the environment, Energy systems,
Mobile systems, robotics…
•Interesting (fun) techniques
–Algorithms, Graph Theory, Learning, Signal
processing…
Distributed Computing
Rik Sarkar
[email protected]