Automatic Discovery of Distributed Algorithms for Large-Scale Systems

Abstract

In recent years, large-scale systems have become mainstream at a very high pace. Typical examples of large-scale systems are MANETs, Wireless Sensor Networks, Pervasive Computing, Swarm Robotics, etc. These systems distinguish them- selves by the large number of devices they embody, and emergent behaviors they exhibit: Behavior that is globally perceivable, but that is made up of only local interactions of the system elements. Because of the vast amount of devices that make up a large-scale system, it is infeasible to exhibit centralized control. As an alternative, we need to leverage distributed algorithms to create and control emergent behaviors for the global goal we want the system to exhibit. Since there is no linear mapping from local interactions to global behavior, we present a global-to-local compiler to automatically generate these distributed algorithms for large-scale systems. By using Genetic Programming to combine already known building blocks from other distributed algorithms, we provide a high-level, goal-driven framework for algorithm designers to design distributed algorithms. Evaluation shows that the framework we present is indeed a valuable tool for designing distributed algorithms for large-scale systems. Improving the develop- ment speed, allowing the designer to be agnostic to the underlying details, but nevertheless providing a flexible interface, to acquire the algorithm desired.