{"id":3935,"date":"2021-07-18T07:12:37","date_gmt":"2021-07-18T07:12:37","guid":{"rendered":"http:\/\/network.ee.tsinghua.edu.cn\/niulab\/?p=3935"},"modified":"2022-08-18T07:17:28","modified_gmt":"2022-08-18T07:17:28","slug":"coded-computation-over-heterogeneous-workers-with-random-task-arrivals","status":"publish","type":"post","link":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/?p=3935","title":{"rendered":"Coded Computation Over Heterogeneous Workers With Random Task Arrivals"},"content":{"rendered":"<p><span class=\"paper_subtitle\">LANGUAGE<\/span> English<\/p>\n<p><span class=\"paper_subtitle\">SOURCE<\/span> IEEE COMMUNICATIONS LETTERS, VOL.25, NO.7, JULY2021\uff0c2338-2342<\/p>\n<p><span class=\"paper_subtitle\">Published Date<\/span>:2021-07<\/p>\n<p><span class=\"paper_subtitle\">ABSTRACT<\/span><\/p>\n<p><span class=\"fontstyle0\">Considering the scheduling and allocation of tasks among multiple servers, distributed machine learning faces the problem of the straggler effect as well as system heterogeneity,<br \/>\ne.g., the computation time of the slowest worker can be much longer than that of the normal workers. This letter studies the distributed online tasks assignment problem under heterogeneous conditions where different workers have different computing capacities, in order to minimize the task completion time. We consider the task scheduling with random task arrivals, and introduce task cancellation after completion scheme to clear the unfinished parts after the completion of the task to further reduce redundant calculations. To address the challenge of finding the optimal solution, we propose an approximate online algorithm based on convex optimization and time recursion. Simulation results show that the proposed algorithm can reduce the completion delay by over 30% as compared with the one-shot counterpart, and maintain a relatively stable delay in the case of fluctuating arrival rates.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p><a href=\"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/wp-content\/uploads\/2021\/07\/Coded-Computation-Over-Heterogeneous-Workers-With-Random-Task-Arrivals.pdf\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignleft size-full wp-image-117\" title=\"pdf\" src=\"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/wp-content\/uploads\/2010\/08\/pdf.gif\"alt=\"\" width=\"95\" height=\"50\" \/><\/a>  Fan Zhang, Yuxuan Sun, and Sheng Zhou, Coded Computation Over Heterogeneous Workers With Random Task Arrivals, <span class=\"papersource\">IEEE COMMUNICATIONS LETTERS, VOL.25, NO.7, JULY 2021\uff0c2338-2342 <\/span><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[7],"tags":[100],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/3935"}],"collection":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3935"}],"version-history":[{"count":1,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/3935\/revisions"}],"predecessor-version":[{"id":3936,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/3935\/revisions\/3936"}],"wp:attachment":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3935"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3935"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3935"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}