We study the parallel scheduling problem for a new modality of paralle
l computing: having one workstation ''steal cycles'' from another. We
focus on a draconian mode of cycle-stealing, in which the owner of wor
kstation a allows workstation A to take control of B's processor whene
ver it is idle, with the promise of relinquishing control immediately
upon demand. The typically high communication overhead for supplying w
orkstation B with work and receiving its results militates in favor of
supplying B with large amounts of work at a time; the risk of losing
work in progress when the owner of B reclaims the workstation militate
s in favor of supplying B with a sequence of small packets of work. Th
e challenge is to balance these two pressures in a way that maximizes
the amount of work accomplished. We formulate two models of cycle-stea
ling. The first attempts to maximize the expected work accomplished du
ring a single episode, when one knows the probability distribution of
the return of B's owner. The second attempts to match the productivity
of an omniscient cycle-stealer, when one knows how much work that ste
aler can accomplish. We derive optimal scheduling strategies for sampl
e scenarios within each of these models. Perhaps our most important di
scovery is the as-yet unexplained coincidence that two quite distinct
scenarios lead to almost identical unique optimizing schedules. One sc
enario falls within our first model; it assumes that the probability o
f the return of Bs owner is uniform across the lifespan of the episode
; the optimizing schedule maximizes the expected amount of work accomp
lished during the episode. The other scenario falls within our second
model; it assumes that B's owner will interrupt our cycle-stealing at
most once during the lifespan of the opportunity; the optimizing sched
ule maximizes the amount of work that one is guaranteed to accomplish
during the lifespan.