Honeysort
a framework for adaptive distributed algorithms
Presented by Yookyung Jo
Motivation
•
Demand for distributed protocols and
algorithms to adapt to dynamic system
conditions in a preferably decentralized
manner
•
Distributed algorithms are sensitive to
dynamic system conditions
–
Distributed sorting : network bandwidth,
memory, CPU
–
Image compression : (low CPU & high
bandwidth) vs. (high CPU & low bandwidth)
Motivation (2)
•
Existing approaches on adaptive
distributed computing in Grid :
–
Elaborate tuning of adaptation
parameters
–
Centralized control of adaptation
•
Solution : social insect’s collective
decision-making mechanism
–
Individual insect’s local, simple behavior
=> desired global patterns
Honey bees’ foraging :
collective decision making
•
Honey bees’ foraging behavior
–
Given multiple nectar sources
–
All bees forage the best nectar source
–
Without centralized control
•
Distributed algorithms
–
Various candidate algorithms are tried
–
All machines converge to the best
algorithm
State transition :
Foraging
:
Dancing
:
Following :
a1
d
1
a2
d2
a3
d3
f