On the Use of Sequences, Phase Changes, and HoneyBees For Designing Adaptive Distributed Systems

Gupta, Indranil; Jo, Yookyung

Permalink

https://hdl.handle.net/2142/10970 Copy

Description

Title

On the Use of Sequences, Phase Changes, and HoneyBees For Designing Adaptive Distributed Systems

Author(s)

• Gupta, Indranil
• Jo, Yookyung

Issue Date

2005-02

Keyword(s)

distributed systems

Abstract

The invention of distributed protocols is an extremely challenging activity. Today however, few design paradigms are available for the creative task of designing scalable and reliable protocols for the Grid, peer to peer systems, etc. This paper first presents a *design methodology* to translate sequence equations, that are extensions of the form x{m+1}=f(xm,x{m-1}, ..., x{m-k}), into distributed protocols that are provably equivalent, i.e., exhibit the same equilibrium points and trajectories. These novel *sequence protocols* are decentralized, simple, scalable, and highly fault-tolerant. We then demonstrate how phase changes in sequence protocols can be used to detect certain global predicates in a decentralized manner. Two such new protocols called the *Multiplicative protocol* and the *Logistic protocol* are presented, rigorously analyzed, and experimentally studied. Finally, we present *HoneySort*, a novel sequence protocol for adaptive Grid computing. HoneySort is derived from sequence equations representing coordination among honeybees in nature. Through rigorous analysis and experiments with a real deployment on a 30-node PC cluster, we show that HoneySort outperforms well-known distributed sorting algorithms such as Quicksort and Insertion sort.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10970

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections