104 COMMUNICATIONS OF THE ACM | FEBRUARY 2019 | VOL. 62 | NO. 2
reflect agents’ best responses to system dynamics. These
thresholds produce an equilibrium and agents cannot benefit by deviating from their assigned strategy.
6. 1 Sprinting behavior
Figure 4 compares sprinting policies and resulting system
dynamics as 1000 instances of Decision Tree, a representative application, computes across over time. Sprinting policies determine how often agents sprint and whether sprints
trigger emergencies. Ideally, policies would permit agents
to sprint up until they trip the circuit breaker. In this example, 250 of the 1000 agents can sprint before triggering a
power emergency.
Greedy heuristics are aggressive and inefficient. A
sprint in the present precludes a sprint in the near future,
harming subsequent tasks that could have benefited more
from the sprint. Moreover, frequent sprints risk power
emergencies and require rack-level recovery. G produces
an unstable system, oscillating between full-system
sprints that trigger emergencies and idle recovery that
harms performance.
Control-theoretic approaches are more conservative,
throttling sprints in response to power emergencies. E-B
adaptively responds to feedback, producing a more stable
system with fewer sprints and emergencies. Indeed, E-B may
be too conservative, throttling sprints beyond what is necessary to avoid tripping the circuit breaker. The number of
sprinters is consistently lower than Nmin, which is safe but
leaves sprinting opportunities unexploited. In neither G nor
E-B do agents sprint to full advantage.
In contrast, the computational sprinting game performs
well by embracing agents’ strategies. E-T produces an equi-
librium in which agents play their optimal strategies and
converge to a stationary distribution. In equilibrium, the
number of sprinters is just slightly above Nmin, the number
that causes a breaker to transition from the non-tripped
region to the tolerance band. After emergency and recovery,
the system quickly returns to equilibrium.
Figure 5 shows the percentage of time an agent spends in
each state. E-T and C-T sprints are timely as strategic agents
sprint only when estimated benefits exceed an optimized
threshold. A sprint in E-T or C-T contributes more to performance than one in G or E-B. Moreover, G and E-B ignore the
consequences of a sprint. With G, an agent spends more
than 50% of its time in recovery, waiting for batteries to
recharge after an emergency. With E-B, an agent spends
nearly 40% of its time in active mode but not sprinting.
6. 2 Sprinting performance
Figure 6 shows task throughput under varied policies. The
sprinting game outperforms greedy heuristics and is competitive with globally optimized heuristics. Rather than
sprinting greedily, E-T uses equilibrium thresholds to select
more profitable epochs for sprinting. E-T outperforms G
and E-B by up to 6. 8× and 4. 8×, respectively. Agents who use
their own strategies to play the game competitively produce
outcomes that rival expensive cooperation. E-T’s task
throughput is 90% that of C-T’s for most applications.
Linear Regression and Correlation are outliers, achieving
only 36% and 65% of cooperative performance. For these
applications, E-T performs as badly as G and E-B because
the applications’ performance profiles exhibit little variance
Figure 4. Sprinting behavior for a representative application, Decision Tree. Black line denotes number of sprinters. Gray line denotes the
point at which sprinters risk a power emergency, Nmin.
N
um
b
er
o
f
s
pr
int
in
g
u
se
r
s
0
0 200 400
Epoch index
Equilibrium threshold
Cooperative threshold
Exponential backoff
Greedy
600 800 1000
3
00
6
00
0
3
00
60
0
0
3
0
0
6
0
0
0
3
00
6
0
0