On Optimal Strategies for Stealing Cycles
Sandeep N. Bhatt, Fan Chung, Frank Thomson Leighton, Arnold L. Rosenberg · 1995
. The growing importance of networked workstations as a computing milieu has created a new modality of parallel computing, namely, the possibility of having one workstation "steal cycles" from another. In a typical episode of cycle-stealing, the owner of workstation B allows the owner of workstation A to take control of B's processor whenever it is idle, with the promise of relinquishing control immediately upon the demand of the owner of B. Typically, the costs for an episode reside in the overhead required to supply workstation B with work (data and, perhaps, the programs to process the data), coupled with the fact that work in progress when the owner of B reclaims the workstation is lost to the owner of A. The first cost militates toward supplying B with a large amount of work at once; the second cost militates toward repeatedly supplying B with small amounts of work. It is this tension that makes the problem interesting. In this paper, we formulate two models of cycle-s...