Distributed Computing with Adaptive Heuristics
This project is partly supported by the NSF Interface between Computer Science and Economics & Social Sciences (ICES) program through grant CCF-1101690. (Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.)
Description
Dynamic environments where computational nodes or decision makers interact repeatedly over time arise in a variety of settings, such as Internet protocols, large-scale markets, social networks, and multi-processor computer architectures. In many such settings, the prescribed behavior of the nodes is simple, natural, and myopic, reflecting either the desire or necessity for computational nodes (whether humans or computers) to provide quick responses and have a limited computational burden. These "adaptive heuristics" can often, in the long run, move the global system in good directions and yield highly rational and sophisticated behavior, such as in game-theoretic results demonstrating the convergence of best-response or no-regret dynamics to equilibrium points. However, these positive results for adaptive heuristics in game theory are primarily based on the often unrealistic premise that nodes' actions are somehow synchronously coordinated. In many settings, where nodes can act at any time, this kind of synchrony is not available; it has long been known that asynchrony introduces substantial difficulties in distributed systems. The project draws ideas from distributed-computing theory and from game theory to investigate provable properties and possible worst-case system behavior of adaptive heuristics in asynchronous computational environments. A central thrust of project research is understanding the convergence behavior of distributed computing with adaptive heuristics. Identifying dynamics that provably converge to equilibria even in the presence of asynchrony both strengthens classic results regarding game dynamics and has implications across a wide domain of applications, including: convergence of game dynamics to pure Nash equilibria; stabilization of asynchronous circuits; and convergence to a stable routing tree of the Border Gateway Protocol, which handles Internet routing.
Project results strengthen classic results regarding game dynamics and guide the design of new protocols for routing, congestion control, and other Internet environments. The outcomes of this project include new applications of existing techniques from game theory and distributed computing and the development of new techniques that are of use to both communities. A thorough understanding of convergence behaviors of systems is both of scientific interest and has significant potential to affect real-world systems and policy decisions. With an improved understanding of the impact that assumptions about the environment and participants of a complex system have on possible global and local outcomes, policy makers, system designers, and system participants can engage in more informed discussion and make better decisions.
People
Senior Personnel
Collaborators
Alex Fabrikant,
Sergiu Hart,
Swara Kopparty,
Vijay Ramachandran
Papers
-
Aaron D. Jaggard, Neil Lutz, Michael Schapira, Rebecca N. Wright, "Self-stabilizing uncoupled dynamics"
- Alex Fabrikant, Aaron D. Jaggard, and Michael Schapira, "On the Structure of Weakly Acyclic Games"
- Aaron D. Jaggard, Swara Kopparty, Vijay Ramachandran, and Rebecca N. Wright, "The Design Space of Probing Algorithms for Network-Performance Measurement"
- Aaron D. Jaggard, Michael Schapira, and Rebecca N. Wright, "Brief Announcement: Distributed Computing with Rules of Thumb"
- Aaron D. Jaggard, Michael Schapira, and Rebecca N. Wright, "Distributed Computing with Adaptive Heuristics"
Sunday, June 16, 2013 at 00:03