Breeding Diameter-Optimal Topologies for Distributed Indexes
Sanket Patil
Srinath Srinivasa
Saikat Mukherjee
Aditya Ramana Rachakonda
Open Systems Laboratory
International Institute of Information Technology
Bangalore - 560100, India
Venkat Venkatasubramanian
Laboratory for Intelligent Process Systems
School of Chemical Engineering
Purdue University
West Lafayette, IN 47906, USA
Abstract
The role of a distributed index from the perspective of an individual actor (node) is to minimize its separation from all other actors (nodes). From a systemwide perspective, an optimal distributed index is one that minimizes the diameter of the index graph. We tackle this optimization problem in an evolutionary fashion by performing a series of topology crossovers and fitness-based selections. A set of constraints regulate the fitness function. Different classes of topologies such as star, circle, and skip lists emerge as diameter-optimal structures under different constraints. Knowledge of the optimal topology class in a given context provides strategic information for distributed agents to (re)construct a global index structure based on local information. We also investigate a deterministic approach called polygon embedding, to build topologies with similar properties to that of the evolved topologies.
