University of Notre Dame
Browse
McCuneRR042016D.pdf (5.59 MB)

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

Download (5.59 MB)
thesis
posted on 2016-04-29, 00:00 authored by R. Ryan McCune

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.

History

Date Modified

2017-06-05

Defense Date

2016-03-23

Research Director(s)

Dr. Tim Weninger

Committee Members

Dr. Dong Wang Dr. Laurel Riek Dr. Christian Poellabauer

Degree

  • Doctor of Philosophy

Degree Level

  • Doctoral Dissertation

Language

  • English

Program Name

  • Computer Science and Engineering

Usage metrics

    Dissertations

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC