Computer Science ETDs

Publication Date

Fall 9-27-2019

Abstract

Distributed systems are ubiquitous today: from the Internet used by billions of people around the world to the small scale IoT devices. With this rapidly increasing need to perform computation at scales larger than ever before, comes the need to ensure resilience to adversarial failures so that these systems can continue to behave as intended even when some malicious tampering happens.

In this dissertation, we explore the power of randomness and the difficulty of rationally approximating the Golden Ratio to thwart adversarial behavior in two different problems in distributed computing: interactive communication and robust collaborative search. While randomness helps with unpredictable behavior which protects against adversarial tampering on the communication channels, the Golden Ratio offers uniform spreading which helps locate the target faster.

For interactive communication among a group of nodes, we consider an omniscient adversary that flips an unknown number of bits on the channels between the nodes. We first provide an algorithm for only a single message that needs to be sent between two parties. We then extend our result to the general multiparty case, where our algorithm efficiently simulates any asynchronous noise-free protocol into a robust synchronous protocol, sending an asymptotically optimal number of bits.

Next, we discuss an algorithm for a multi-agent collaborative search on a plane for a target, when the agents can experience adversarial crash failures. This is the well-known Ants Nearby Treasure Search (ANTS) problem, introduced by Feinerman et al earlier this decade. While the problem they consider is only for the case of a point target and no failures, we consider foraging for an adversarially placed pile of unknown diameter, located at an unknown distance, where certain agents can experience crash failures at any point during the algorithm. We provide lower bounds for this problem and prove that our solution is optimal for the class of spoke algorithms -- ones in which the agents move radially away and back to the nest. Our result is one of the first to provide scalable robustness guarantees in this setting. Our key tool is here to exploit the difficulty in rationally approximating the Golden Ratio to spread out the search trajectories for the agents. This not only ensures that the pile is located faster, but we also obtain resilience against arbitrary many crash failures in the system.

Finally, we discuss a problem closely related to the ANTS problem, called Central Place Foraging (CPF). In this problem, the searchers search in a bounded arena around a nest and are allowed communication through pheromones. Moreover, the distribution of food around the nest is assumed to follow some probability distribution, and biological factors like the effects of depletion of food resources and preferential search in areas where food was previously found are important factors. We analyze three well-known algorithms for this problem and report their expected runtimes. We validate our claims using experimental simulations in ARGoS.

Language

English

Document Type

Dissertation

Degree Name

Computer Science

Level of Degree

Doctoral

Department Name

Department of Computer Science

First Committee Member (Chair)

Jared Saia

Second Committee Member

Thomas P. Hayes

Third Committee Member

Melanie E. Moses

Fourth Committee Member

James Aspnes

Download

Share

COinS