Honeysort

Honeysort a framework for adaptive distributed algorithms: 

Honeysort a framework for adaptive distributed algorithms Presented by Yookyung Jo

Motivation: 

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 andamp; high bandwidth) vs. (high CPU andamp; low bandwidth)

Motivation (2): 

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 =andgt; desired global patterns

Honey bees’ foraging :collective decision making: 

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 :: 

State transition : Foraging : Dancing : Following : a1 d1 a2 d2 a3 d3 f

Translation: 

Translation Honey bee Distributed algorithm

Difference equation: 

Difference equation Positive feedback

Difference equation analysis :: 

Difference equation analysis : The only stable equilibrium point :

Brush up : sorting: 

Brush up : sorting Many candidate algorithms with different computational complexity Quick sort, heap sort … : O(N log(N)) Insertion sort, shell sort … : O(N^2) Sensitive to the initial input data Insertion sort : nearly sorted data : O(N) random data : O(N^2)

Sorting : Input data: 

Sorting : Input data Nearly sorted input is common A database table with highly correlated attributes Employee database table Already sorted in 'Work years' Sort it according to 'Salary' ===andgt; Sorting problem on nearly sorted data

Honeysort: 

Honeysort Master : sample sort, data distribution Worker : Advertising message : {local sorting algorithm used, speed}

Honeysort: 

Honeysort : data transfer : bee communication (peer communication of algorithm evaluation )

Experimental setup: 

Experimental setup # of worker machines : 6-40 Candidate local sorting algorithm : quick sort, insertion sort Machines : csil-linux#.cs.uiuc.edu TCP socket connection Sorting data : 2 4byte-integers Written in C++

Experiment : : 

Experiment : Performance with fixed # of segments Random data Pre-sorted data

Experiment :: 

Experiment : Performance with fixed chunk size (1000) Random data Pre-sorted data

Explorative model: 

Explorative model If the characteristic of the input data changes after the convergence, the new best algorithm has no means to attract machines =andgt; Non-zero influx of machines to all candidate algorithms

Experiment :: 

Experiment : Performance with varying degree of homogeneous randomization on input data

Experiment :: 

Experiment : Performance with varying degree of input data character change

Experiment :: 

Experiment : Evolution of local sorting algorithm with heterogeneously changing input data

Experiment :: 

Experiment : Sensitivity to the initial distribution of local sorting algorithms

Conclusion: 

Conclusion Honeysort exhibits good performance Close to the best algorithm on homogeneous input Better than all other algorithms on heterogeneous input Desirable properties Dynamic adaptation without pre-tuning Decentralized control (decision making)

Conclusion(2): 

Conclusion(2) More application Applying honey adaptive distributed algorithm requires The job could be divided and concurrently run Different candidate algorithms exist with different performance on varying conditions Data transfer cost is far smaller than the job Preferably involves a large number of participation 3D rendering algorithms…

Conclusion(3): 

Conclusion(3) Future work To experiment honeysort on a large number of clients to see the benefit of decentralized control To find a good application scenario for honeysort (e.g. stream data sorting) and experiment To apply honey adaptive framework in other problems such as 3D-rendering

Experiment :: 

Experiment :

Experiment : : 

Experiment :