Reducing Scope to Increase Scalability: Decentralization in Graph Processing and UAV Swarms

Doctoral Dissertation

Abstract

Many systems are designed with a central controller that is responsible for managing and coordinating all system components. Examples include the master/slave model for distributed computing, and the command and control of Unmanned Aerial Vehicles (UAVs). In such systems, the existence of the central controller presents a bottleneck that limits system scalability. For the system to expand beyond these limitations, the scope of control must be reduced, with communication increased among components. In this dissertation, I investigate improving scalability through reducing scope, demonstrated through two applications.

The first application is the command and control of UAV swarms. Bandwidth limitations and increased software complexity prevent conventional centralized UAV control methods from being applied to the remote operation of many UAVs. Mission planners are investigating the application of swarm intelligence to UAV swarms, where UAVs communicate between one another and the environment to self-organize and solve problems, absent of explicit central command. For one set of projects, I explore the application of swarm intelligence to UAVs, with attention to specific behaviors and quantifiable performance.

The second application is the distributed processing of large-scale graphs. Large graphs, common for Big Data, exceed the memory capacity of conventional machines and must be partitioned across distributed memory in order to be processed. However, typical centralized graph algorithms presume every node to be randomly accessible, leading to high-latency remote data access and prohibitively large intermediate data structures. Recently developed frameworks provide a platform for executing distributed algorithms on graph data, which reduce algorithmic scope to increase scalability. I comprehensively overview these frameworks, and observe the relationship between graph algorithmic scope and scalability.

Together with these two applications, UAV swarms and distributed graph processing, I illustrate how centralized control must be relaxed, and component communication increased, in order for large systems to overcome limitations of central control and successfully scale.

Attributes

Attribute NameValues
Author R. Ryan McCune
Contributor Dr. Dong Wang, Committee Member
Contributor Dr. Laurel Riek, Committee Member
Contributor Dr. Tim Weninger, Research Director
Contributor Dr. Christian Poellabauer, Committee Member
Contributor Dr. Greg Madey, Research Director
Degree Level Doctoral Dissertation
Degree Discipline Computer Science and Engineering
Degree Name Doctor of Philosophy
Defense Date
  • 2016-03-23

Submission Date 2016-04-29
Subject
  • distributed systems, graph processing, Big Data, distributed algorithms, distributed and parallel processing, graph algorithms, emergence, emergent behavior, swarm intelligence, agent-based modeling, multi-agent systems

Language
  • English

Record Visibility and Access Public
Content License
  • All rights reserved

Departments and Units

Files

Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.