Distributed computing with rules of thumb

Aaron D. Jaggard, Michael Schapira, Rebecca N. Wright

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present our recent work (ICS 2011) on dynamic environments in which computational nodes, or decision makers, follow simple and unsophisticated rules of behavior (e.g., repeatedly "best replying" to others' actions, and minimizing "regret") that have been extensively studied in game theory and economics. We aim to understand when convergence of the resulting dynamics to an equilibrium point is guaranteed if nodes' interaction is not synchronized (e.g., as in Internet protocols and large-scale markets). We take the first steps of this research agenda. We exhibit a general non-convergence result and consider its implications across a wide variety of interesting and timely applications: routing, congestion control, game theory, social networks and circuit design. We also consider the relationship between classical nontermination results in distributed computing theory and our result, explore the impact of scheduling on convergence, study the computational and communication complexity of asynchronous dynamics and present some basic observations regarding the effects of asynchrony on no-regret dynamics.

Original languageEnglish (US)
Title of host publicationPODC'11 - Proceedings of the 2011 ACM Symposium Principles of Distributed Computing
Pages333-334
Number of pages2
DOIs
StatePublished - 2011
Event30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC'11, Held as Part of the 5th Federated Computing Research Conference, FCRC - San Jose, CA, United States
Duration: Jun 6 2011Jun 8 2011

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC'11, Held as Part of the 5th Federated Computing Research Conference, FCRC
Country/TerritoryUnited States
CitySan Jose, CA
Period6/6/116/8/11

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • adaptive heuristics
  • convergence
  • game dynamics
  • self stabilization

Fingerprint

Dive into the research topics of 'Distributed computing with rules of thumb'. Together they form a unique fingerprint.

Cite this