News Archives

Selfishness and Malice in Distributed Systems

April 6, 2015

Selfishness and Malice in Distributed Systems
Where: FEC 145
When: On Monday, April 6th, 2015, at 1:00PM
Committee Members:
1. Prof. Jared Saia, Chairperson
2. Prof. Maxwell Young
3. Prof. Thomas Hayes
4. Prof. Dorian Arnold

Abstract:
Large-scale distributed systems are increasingly prevalent. Two issues can impact the performance of such systems: selfishness and malice. In this dissertation, we provide algorithms to address both of these issues.

One approach to ameliorating selfishness in large networks is the idea of a mediator. A mediator implements a correlated equilibrium when it proposes a strategy to each player privately such that the mediator’s proposal is the best interest for every player to follow. In this dissertation, we present a mediator that implements the best correlated equilibrium for an extended El Farol game with symmetric players. The extended El Farol game we consider has both positive and negative network effects. We study the degree to which this type of mediator can decrease the social cost. In particular, we give an exact characterization of Mediation Value (MV) and Enforcement Value (EV) for this game. MV measures the efficiency of our mediator compared to the best Nash equilibrium, and EV measures the efficiency of our mediator compared to the optimal social cost. This sort of exact characterization is uncommon for games with both kinds of network effects. An interesting outcome of our results is that both the MV and EV values can be unbounded for our game.

Recent years have seen significant interest in designing networks that are self-healing in the sense that they can automatically recover from adversarial attacks. Previous work shows that it is possible for a network to automatically recover, even when an adversary repeatedly deletes nodes in the network. However, there have not yet been any algorithms that self-heal in the case where an adversary takes over nodes in the network. In this dissertation, we address this gap. In particular, we describe a communication network over n nodes that ensures the following properties, even when an adversary controls up to t ≤ (1/4 − ε)n nodes, for any constant ε > 0. First, the network provides point-to-point communication with message cost and latency that are asymptotically optimal in an amortized sense. Second, the expected total number of message corruptions is O(t(log∗ n)2), after which the adversarially controlled nodes are effectively quarantined so that they cause no more corruptions. In the problem of reliable multiparty computation (RMC), there are n parties, each with an individual input, and the parties want to jointly and reliably compute a function f over n inputs, assuming that it is not necessary to maintain the privacy of the inputs.

The problem is complicated by the fact that an omniscient adversary controls a hidden fraction of the parties. We describe a self-healing algorithm for this problem. In particular, for a fixed function f, with n parties and m gates, we describe how to perform RMC repeatedly as the inputs to f change. Our algorithm maintains the following properties, even when an adversary controls up to t ≤ (1/4 − ε)n parties, for any constant ε > 0. First, our algorithm performs each reliable computation with the following amortized resource costs: O(m + n log n) messages, O(m + n log n) computational operations, and O(\ell) latency, where \ell is the depth of the circuit that computes f. Second, the expected total number of corruptions is O(t(log∗ n)2).

Our empirical results show that our self-healing algorithms can reduce message cost by up to a factor of 60 for butterfly communication networks and up to a factor of 66 for tree-based computation networks, when compared with algorithms that are not self-healing.