Berenbrink, Petra, Friedetzky, Thomas and Goldberg, Leslie Ann (2001) The natural work-stealing algorithm is stable. In: 42nd Annual Symposium on Foundations of Computer Science (FOCS 2001), Las Vegas, NV, 14-17 Oct 2001. Published in: 42nd IEEE Symposium on Foundations of Computer Science, 2001. Proceedings. pp. 178-187. ISBN 0769513913. ISSN 0272-5428.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

In this paper we analyse a very simple dynamic work-stealing algorithm. In the work-generation model, there are n generators which are arbitrarily distributed among a set of n processors. During each time-step, with probability A, each generator generates a unit-time task which it inserts into the queue of its host processor. After the new tasks are generated, each processor removes one task from its queue and services it. Clearly, the work-generation model allows the load to grow more and more imbalanced, so, even when lambda < 1, the system load can be unbounded.

The natural work-stealing algorithm that we analyse works as follows. During each time step, each empty processor sends a request to a randomly selected other processor. Any non-empty processor having received at least one such request in turn decides (again randomly) in favour of one of the requests. The number of tasks which are transferred from the non-empty processor to the empty one is determined by the so-called work-stealing function f.

We analyse the long-term behaviour of the system as a function of lambda and f. We show that the system is stable for any constant generation rate lambda < 1 and for a wide class of functions f, We give a quantitative description of the functions f which lead to stable systems. Furthermore, we give upper bounds on the average system load (as a function of f and n).

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Series Name:	ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE
Journal or Publication Title:	42nd IEEE Symposium on Foundations of Computer Science, 2001. Proceedings.
Publisher:	IEEE
ISBN:	0769513913
ISSN:	0272-5428
Official Date:	2001
Dates:	Date Event 2001 Published
Number of Pages:	10
Page Range:	pp. 178-187
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	42nd Annual Symposium on Foundations of Computer Science (FOCS 2001)
Type of Event:	Other
Location of Event:	Las Vegas, NV
Date(s) of Event:	14-17 Oct 2001

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item