and all epochs benefit similarly from sprinting. When an agent cannot distinguish between epochs, she sets a low threshold and sprints for every epoch. In effect, for such applications, E-T produces a greedy equilibrium.

6. 3 Sprinting strategies

Figure 7 uses density plots for two representative applications, Linear Regression and PageRank, to show how often and how much their tasks benefit from sprinting. Linear Regression presents a narrower distribution and performance gains from sprinting vary in a band between 3× and 5×. In contrast,

PageRank’s performance gains can often exceed 10×.

The coordinator uses density plots to optimize threshold strategies. Linear Regression’s strategy is aggressive and uses a low threshold that often induces sprints. This strategy arises from its relatively low variance in performance gains. If sprinting’s benefits are indistinguishable across tasks and epochs, an agent sprints indiscriminately and at every opportunity. PageRank’s strategy is more nuanced and uses a high threshold, which cuts her bimodal distribution and implements judicious sprinting. She sprints for tasks and epochs that benefit most (i.e., those that see performance gains greater than 10×).

Figure 8 illustrates diversity in agents’ strategies by reporting their propensities to sprint. Linear Regression and Correlation’s narrow density functions and low thresholds cause these applications to sprint at every opportunity. The

Per f orm an ce ( Nor mal ized t o Gre ed y )

0 1 2 3 4 5 6

NaiveDecisionGradient SVM LinearKmeans ALS CorrelationPagerank CCTriangle Greedy Exponential backoff Equilibrium threshold Cooperative threshold

Figure 6. Performance, measured in tasks per second and normalized against greedy, for a single application type.

23456

0.

0

0.1

0.2

0.

3

0.

4

Linear regression

Normalized TPS D en sit y

0 5 10 15

0.

00

0.

1

0

0.2

0

Pagerank

Normalized TPS D en sit y

Figure 7. Probability density for sprinting speedups.

P ro ba bili ty o f sp r inti ng

0.0

0.2

0.4

0.6

0.8

1.0

NaiveDecisionGradient SVMLinearKmeans ALS Correlation Pagerank CCTriangle

Figure 8. Probability of sprinting. Greedy Exponential Equilibrium Cooperative

0%

25%

50%

75%

100%

Active (not sprinting)

Local cooling
Global recovery
Sprinting

Figure 5. Percentage of time spent in agent states for a representative application, Decision Tree.

majority of applications, however, resemble PageRank with higher thresholds and judicious sprints.

6. 4 Equilibrium versus cooperation

Equilibrium thresholds are robust to strategic behavior and perform well, but cooperative thresholds can perform even better. The sprinting game’s equilibrium delivers 90% of the performance from cooperation because the penalties from non-cooperative behavior are low. Figure 9 shows how efficiency falls as recovery from power emergencies become increasingly expensive. Recall that pr is the probability an agent in recovery stays in that state.

The sprinting game fails when an emergency requires indefinite recovery and pr is one. This game has no equilibrium that avoids tripping the breaker and triggering indefinite recovery. If a strategic agent were to observe system dynamics that avoid tripping the breaker, which means Ptrip is zero, she would realize that other agents have set high thresholds to avoid sprints. Her best response would be lowering her threshold and sprinting more often. Others would behave similarly and drive Ptrip higher. In equilibrium, Ptrip would rise above zero and agents would eventually trip the breaker, putting the system into indefinite recovery. Thus, selfish agents would produce inefficient equilibria—the Prisoner’s Dilemma in which each agent’s best response performs worse than a cooperative one.

The Folk theorem guides agents to a more efficient equilibrium by punishing agents whose responses harm the system. The coordinator would assign agents the best cooperative thresholds to maximize system performance from sprinting. When an agent deviates, she is punished such that