TY - GEN

T1 - Distributed computing with rules of thumb

AU - Jaggard, Aaron D.

AU - Schapira, Michael

AU - Wright, Rebecca N.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - adaptive heuristics

KW - convergence

KW - game dynamics

KW - self stabilization

UR - http://www.scopus.com/inward/record.url?scp=79959917671&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959917671&partnerID=8YFLogxK

U2 - 10.1145/1993806.1993870

DO - 10.1145/1993806.1993870

M3 - Conference contribution

AN - SCOPUS:79959917671

SN - 9781450307192

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 333

EP - 334

BT - PODC'11 - Proceedings of the 2011 ACM Symposium Principles of Distributed Computing

T2 - 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC'11, Held as Part of the 5th Federated Computing Research Conference, FCRC

Y2 - 6 June 2011 through 8 June 2011

ER -