English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Work sharing and work stealing are two scheduling paradigms to redistribute work when performing distributed computations.  work sharing, processors attempt to migrate pending jobs to other processors in the hope of reducing response times.  work stealing, on the other hand, underutilized processors attempt to steal jobs from other processors. Both paradigms generate a certain communication overhead and the question addressed in this paper is which of the two reduces the response time the most given that they use the same amount of communication overhead. Prior work presented explicit bounds, for large scale systems, on when randomized work sharing outperforms randomized work stealing in case of Poisson arrivals and exponential job durations and indicated that work sharing is best when the load is below $phi -1 approx 0.6180$, with $phi$ being the golden ratio. In this paper we revisit this problem and study the impact of the job size distribution using a mean field model. We present an efficient method to determine the boundary between the regions where sharing or stealing is best for a given job size distribution, as well as bounds that apply to any (phase-type) job size distribution. The main insight is that work stealing benefits significantly from having more variable job sizes and work sharing may become inferior to work stealing for loads as small as $1/2 + epsilon$ for any $epsilon u003e 0$.

Randomized Work Stealing Versus Sharing in Large-Scale Systems With Non-Exponential Job Sizes