{"id":3944,"date":"2021-08-08T07:47:22","date_gmt":"2021-08-08T07:47:22","guid":{"rendered":"http:\/\/network.ee.tsinghua.edu.cn\/niulab\/?p=3944"},"modified":"2022-08-18T08:19:30","modified_gmt":"2022-08-18T08:19:30","slug":"on-the-capacity-of-privacy-preserving-and-straggler-robust-distributed-coded-computing","status":"publish","type":"post","link":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/?p=3944","title":{"rendered":"On the Capacity of Privacy-Preserving and Straggler-Robust Distributed Coded Computing"},"content":{"rendered":"<p><span class=\"paper_subtitle\">LANGUAGE<\/span> English<\/p>\n<p><span class=\"paper_subtitle\">SOURCE<\/span> IEEE\/CIC ICCC\u201921, Xiamen, China, 28-30, July 2021<\/p>\n<p><span class=\"paper_subtitle\">Published Date<\/span>:2021-08<\/p>\n<p><span class=\"paper_subtitle\">ABSTRACT<\/span><\/p>\n<p><span class=\"fontstyle0\">Distributed computing can well exploit the computation resources in edge and cloud for many applications of large-scale machine learning, which also raises concerns on data privacy and straggling effect. A promising method to address these issues is using codes. In our work, we design a general computation framework that incorporates multi-stage computing tasks with multiple inputs and can be expressed as a <\/span><span class=\"fontstyle2\">multi-variable arbitrary-degree <\/span><span class=\"fontstyle0\">polynomial function <\/span><span class=\"fontstyle3\">f<\/span><span class=\"fontstyle0\">, with <\/span><span class=\"fontstyle3\">N <\/span><span class=\"fontstyle0\">distributed servers as workers, over a batch of data <\/span><span class=\"fontstyle3\">D <\/span><span class=\"fontstyle0\">that consists of data from different sources. We propose a privacy-preserving and straggler-robust coding scheme based on Lagrange polynomials, which can address up to <\/span><span class=\"fontstyle3\">S <\/span><span class=\"fontstyle0\">straggling workers <\/span><span class=\"fontstyle2\">and <\/span><span class=\"fontstyle0\">up to <\/span><span class=\"fontstyle3\">L <\/span><span class=\"fontstyle0\">colluding workers. We prove the optimality of the proposed scheme in terms of downlink communication efficiency, defined as the amount of bits of desired results versus that of the downloading results, and obtain an explicit expression of the capacity: <\/span><span class=\"fontstyle3\">C <\/span><span class=\"fontstyle4\">= <\/span><span class=\"fontstyle5\">N<\/span><span class=\"fontstyle6\">-<\/span><span class=\"fontstyle5\">Sd<\/span><span class=\"fontstyle6\">-<\/span><span class=\"fontstyle7\">(<\/span><span class=\"fontstyle5\">Nd<\/span><span class=\"fontstyle7\">(<\/span><span class=\"fontstyle6\">-<\/span><span class=\"fontstyle5\">LS<\/span><span class=\"fontstyle6\">-<\/span><span class=\"fontstyle7\">)1)<\/span><span class=\"fontstyle6\">-<\/span><span class=\"fontstyle7\">1<\/span><span class=\"fontstyle0\">, which is the supremum of downlink communication efficiency over all feasible encoding schemes, and <\/span><span class=\"fontstyle3\">d <\/span><span class=\"fontstyle0\">is the degree of function <\/span><span class=\"fontstyle3\">f<\/span><span class=\"fontstyle0\">.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p><a href=\"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/wp-content\/uploads\/2021\/08\/On_the_Capacity_of_Privacy-Preserving_and_Straggler-Robust_Distributed_Coded_Computing.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>  Qicheng, Zeng and Sheng Zhou, On the Capacity of Privacy-Preserving and Straggler-Robust Distributed Coded Computing, <span class=\"papersource\"> IEEE\/CIC ICCC\u201921, Xiamen, China, 28-30, July 2021 <\/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":[99],"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\/3944"}],"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=3944"}],"version-history":[{"count":1,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/3944\/revisions"}],"predecessor-version":[{"id":3945,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/3944\/revisions\/3945"}],"wp:attachment":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3944"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3944"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3944"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}