{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/78379"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/78379","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Zorro: zero-cost reactive failure recovery in distributed graph processing","abstract":"Distributed graph processing frameworks have become increasingly popular for processing large graphs. However, existing frameworks either lack the ability to recovery from failures or support proactive recovery methods. Proactive recovery methods like checkpointing incur high overheads during failure-free execution making failure recovery an expensive operation. Our hypothesis is that reactive recovery of failures in graph processing that provides a zero-overhead alternative to expensive proactive failure recovery mechanisms is feasible, novel and useful. We support the hypothesis with Zorro, a recovery protocol that reactively recovers from machine failures. Zorro utilizes vertex replication inherent in existing graph processing frameworks to collectively rebuild the state of failed servers. Surviving servers transfer the states of inherently replicated vertices back to replacement servers, which rebuild their state using the received values. This fast recovery mechanism prioritizes high degree vertices ensuring high accuracy of graph processing applications. We have implemented our approach in two existing distributed graph processing frameworks: LFGraph and PowerGraph. Experiments using graph applications on real-world graphs show that Zorro is able to recover between 87-92% graph state when half the cluster fails and maintains at least 97% accuracy in all experimental failure scenarios.","abstract_html":"Distributed graph processing frameworks have become increasingly popular for processing large graphs. However, existing frameworks either lack the ability to recovery from failures or support proactive recovery methods. Proactive recovery methods like checkpointing incur high overheads during failure-free execution making failure recovery an expensive operation. Our hypothesis is that reactive recovery of failures in graph processing that provides a zero-overhead alternative to expensive proactive failure recovery mechanisms is feasible, novel and useful. We support the hypothesis with Zorro, a recovery protocol that reactively recovers from machine failures. Zorro utilizes vertex replication inherent in existing graph processing frameworks to collectively rebuild the state of failed servers. Surviving servers transfer the states of inherently replicated vertices back to replacement servers, which rebuild their state using the received values. This fast recovery mechanism prioritizes high degree vertices ensuring high accuracy of graph processing applications. We have implemented our approach in two existing distributed graph processing frameworks: LFGraph and PowerGraph. Experiments using graph applications on real-world graphs show that Zorro is able to recover between 87-92% graph state when half the cluster fails and maintains at least 97% accuracy in all experimental failure scenarios.","abstract_has_math":false,"creators":["Pundir, Mayank"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-07-22T22:16:44Z","date_published":"2015-07-22T22:16:44Z","updated_at":"2026-07-22T22:26:11Z","subjects":["distributed graph processing","failure recovery","reactive approaches"],"languages":["en"],"rights":["Copyright 2015 Mayank Pundir"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/78379","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Pundir, Mayank"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-07-22T22:16:44Z","2015-05","2015-04-28","2015-5"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["distributed graph processing","failure recovery","reactive approaches"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Mayank Pundir"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/78379"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Distributed graph processing frameworks have become increasingly popular for processing large graphs. However, existing frameworks either lack the ability to recovery from failures or support proactive recovery methods. Proactive recovery methods like checkpointing incur high overheads during failure-free execution making failure recovery an expensive operation. Our hypothesis is that reactive recovery of failures in graph processing that provides a zero-overhead alternative to expensive proactive failure recovery mechanisms is feasible, novel and useful. We support the hypothesis with Zorro, a recovery protocol that reactively recovers from machine failures. Zorro utilizes vertex replication inherent in existing graph processing frameworks to collectively rebuild the state of failed servers. Surviving servers transfer the states of inherently replicated vertices back to replacement servers, which rebuild their state using the received values. This fast recovery mechanism prioritizes high degree vertices ensuring high accuracy of graph processing applications. We have implemented our approach in two existing distributed graph processing frameworks: LFGraph and PowerGraph. Experiments using graph applications on real-world graphs show that Zorro is able to recover between 87-92% graph state when half the cluster fails and maintains at least 97% accuracy in all experimental failure scenarios.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2015-07-22 without embargo terms","The student, Mayank Pundir, accepted the attached license on 2015-04-27 at 20:26.","The student, Mayank Pundir, submitted this Thesis for approval on 2015-04-27 at 20:35.","This Thesis was approved for publication on 2015-04-28 at 08:58.","DSpace SAF Submission Ingestion Package generated from Vireo submission #7845 on 2015-07-22 at 10:31:54","Made available in DSpace on 2015-07-22T22:16:44Z (GMT). No. of bitstreams: 2 PUNDIR-THESIS-2015.pdf: 1213393 bytes, checksum: b0556dba8ebcb267956b2b0301018a5d (MD5) LICENSE.txt: 4210 bytes, checksum: f41fd4071cf6388e4f91c83707e55101 (MD5) Previous issue date: 2015-04-28"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Zorro: zero-cost reactive failure recovery in distributed graph processing"]}]}],"canonical_facts":{"dc:creator":["Pundir, Mayank"],"dc:date":["2015-07-22T22:16:44Z","2015-05","2015-04-28","2015-5"],"dc:description":["Distributed graph processing frameworks have become increasingly popular for processing large graphs. However, existing frameworks either lack the ability to recovery from failures or support proactive recovery methods. Proactive recovery methods like checkpointing incur high overheads during failure-free execution making failure recovery an expensive operation. Our hypothesis is that reactive recovery of failures in graph processing that provides a zero-overhead alternative to expensive proactive failure recovery mechanisms is feasible, novel and useful. We support the hypothesis with Zorro, a recovery protocol that reactively recovers from machine failures. Zorro utilizes vertex replication inherent in existing graph processing frameworks to collectively rebuild the state of failed servers. Surviving servers transfer the states of inherently replicated vertices back to replacement servers, which rebuild their state using the received values. This fast recovery mechanism prioritizes high degree vertices ensuring high accuracy of graph processing applications. We have implemented our approach in two existing distributed graph processing frameworks: LFGraph and PowerGraph. Experiments using graph applications on real-world graphs show that Zorro is able to recover between 87-92% graph state when half the cluster fails and maintains at least 97% accuracy in all experimental failure scenarios.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2015-07-22 without embargo terms","The student, Mayank Pundir, accepted the attached license on 2015-04-27 at 20:26.","The student, Mayank Pundir, submitted this Thesis for approval on 2015-04-27 at 20:35.","This Thesis was approved for publication on 2015-04-28 at 08:58.","DSpace SAF Submission Ingestion Package generated from Vireo submission #7845 on 2015-07-22 at 10:31:54","Made available in DSpace on 2015-07-22T22:16:44Z (GMT). No. of bitstreams: 2 PUNDIR-THESIS-2015.pdf: 1213393 bytes, checksum: b0556dba8ebcb267956b2b0301018a5d (MD5) LICENSE.txt: 4210 bytes, checksum: f41fd4071cf6388e4f91c83707e55101 (MD5) Previous issue date: 2015-04-28"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/78379"],"dc:language":["en"],"dc:rights":["Copyright 2015 Mayank Pundir"],"dc:subject":["distributed graph processing","failure recovery","reactive approaches"],"dc:title":["Zorro: zero-cost reactive failure recovery in distributed graph processing"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:11Z"}