{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/34467"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/34467","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Failure diagnosis in distributed systems","abstract":"Failures in computing systems are unavoidable. Therefore, it is important to detect and diagnose failures early to improve the reliability of systems. In this dissertation, new approaches on root-cause diagnosis for two notorious types of failures in distributed systems are introduced. This dissertation first focuses on the failures that are caused by software bugs triggered by race conditions. Due to the non-deterministic manifestation, these bugs are much harder to diagnose, fix and test than the bugs in sequential logic. To understand the concurrency bugs, we first study the characteristics of concurrency bugs using 105 bugs of four representative open-source programs. Motivated by the interesting findings from the study, we also propose an automatic bug diagnosis tool for distributed programs that finds the minimal causal orders of related events that trigger the bugs. Our tool is a significant extension to the previous tools that can find only bug-triggering sequence of events. The second focus of this dissertation is on the failures that are caused by propagating errors. An error started by a single network component propagates and contaminates other components. As a result, a large number of network components are infected by errors. To fix the problem, root-cause of this problem, the single component that started the error propagation, needs to be identified. It is assumed that only a limited view on the status of components -- whether they are infected or not -- are available through monitors, a set of pre-selected network components. For this problem, we propose two root-cause diagnosis tools. The first tool relies on a simple intuition that the root-cause component is likely to be close to the infected monitors and far from the uninfected monitors. We also compare six different monitor selection methods. The second tool makes use of additional information -- failure propagation probability and time of infections -- to improve the accuracy of root-cause diagnosis. We propose approximation algorithms to calculate the likelihood that a node is the failure source. In addition, we also propose a new monitor selection algorithm that maximizes the number of infected monitors for best accuracy of root-cause diagnosis.","abstract_html":"Failures in computing systems are unavoidable. Therefore, it is important to detect and diagnose failures early to improve the reliability of systems. In this dissertation, new approaches on root-cause diagnosis for two notorious types of failures in distributed systems are introduced. This dissertation first focuses on the failures that are caused by software bugs triggered by race conditions. Due to the non-deterministic manifestation, these bugs are much harder to diagnose, fix and test than the bugs in sequential logic. To understand the concurrency bugs, we first study the characteristics of concurrency bugs using 105 bugs of four representative open-source programs. Motivated by the interesting findings from the study, we also propose an automatic bug diagnosis tool for distributed programs that finds the minimal causal orders of related events that trigger the bugs. Our tool is a significant extension to the previous tools that can find only bug-triggering sequence of events. The second focus of this dissertation is on the failures that are caused by propagating errors. An error started by a single network component propagates and contaminates other components. As a result, a large number of network components are infected by errors. To fix the problem, root-cause of this problem, the single component that started the error propagation, needs to be identified. It is assumed that only a limited view on the status of components -- whether they are infected or not -- are available through monitors, a set of pre-selected network components. For this problem, we propose two root-cause diagnosis tools. The first tool relies on a simple intuition that the root-cause component is likely to be close to the infected monitors and far from the uninfected monitors. We also compare six different monitor selection methods. The second tool makes use of additional information -- failure propagation probability and time of infections -- to improve the accuracy of root-cause diagnosis. We propose approximation algorithms to calculate the likelihood that a node is the failure source. In addition, we also propose a new monitor selection algorithm that maximizes the number of infected monitors for best accuracy of root-cause diagnosis.","abstract_has_math":false,"creators":["Seo, Eunsoo"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Abdelzaher, Tarek F.","Han, Jiawei","Vaidya, Nitin H.","Ko, Steven"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-09-18T21:18:33Z","date_published":"2012-09-18T21:18:33Z","updated_at":"2026-07-22T22:25:31Z","subjects":["Debugging","Bug Diagnosis","Concurrency Bugs","Error Propagation"],"languages":["en"],"rights":["Copyright 2012 Eun Soo Seo"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/34467","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Abdelzaher, Tarek F.","Han, Jiawei","Vaidya, Nitin H.","Ko, Steven"]},{"key":"dc:creator","label":"Author","values":["Seo, Eunsoo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-09-18T21:18:33Z","2014-09-18T10:01:01Z","2012-08"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Debugging","Bug Diagnosis","Concurrency Bugs","Error Propagation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 Eun Soo Seo"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/34467"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Failures in computing systems are unavoidable. Therefore, it is important to detect and diagnose failures early to improve the reliability of systems. In this dissertation, new approaches on root-cause diagnosis for two notorious types of failures in distributed systems are introduced. This dissertation first focuses on the failures that are caused by software bugs triggered by race conditions. Due to the non-deterministic manifestation, these bugs are much harder to diagnose, fix and test than the bugs in sequential logic. To understand the concurrency bugs, we first study the characteristics of concurrency bugs using 105 bugs of four representative open-source programs. Motivated by the interesting findings from the study, we also propose an automatic bug diagnosis tool for distributed programs that finds the minimal causal orders of related events that trigger the bugs. Our tool is a significant extension to the previous tools that can find only bug-triggering sequence of events. The second focus of this dissertation is on the failures that are caused by propagating errors. An error started by a single network component propagates and contaminates other components. As a result, a large number of network components are infected by errors. To fix the problem, root-cause of this problem, the single component that started the error propagation, needs to be identified. It is assumed that only a limited view on the status of components -- whether they are infected or not -- are available through monitors, a set of pre-selected network components. For this problem, we propose two root-cause diagnosis tools. The first tool relies on a simple intuition that the root-cause component is likely to be close to the infected monitors and far from the uninfected monitors. We also compare six different monitor selection methods. The second tool makes use of additional information -- failure propagation probability and time of infections -- to improve the accuracy of root-cause diagnosis. We propose approximation algorithms to calculate the likelihood that a node is the failure source. In addition, we also propose a new monitor selection algorithm that maximizes the number of infected monitors for best accuracy of root-cause diagnosis.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-07-12T13:54:54Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Seo_Eunsoo.pdf: 6267189 bytes, checksum: 2e35a23744fe5e5f997f7f80e7c9e162 (MD5)","Made available in DSpace on 2012-09-18T21:18:33Z (GMT). No. of bitstreams: 2 Seo_Eunsoo.pdf: 6267189 bytes, checksum: 2e35a23744fe5e5f997f7f80e7c9e162 (MD5) license.txt: 4054 bytes, checksum: 5e1dfcf8e499ba3cb9cb0a6b3e0e9d87 (MD5)","Restriction data tranferred 2014-07-01T11:35:05-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2014-09-18 16:21:01 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (srobbins@illinois.edu) on 2012-09-18T21:21:10Z Item is restricted until 2014-09-18T21:21:01Z","U of I Only Restriction Lifted for Item 34741 on 2014-09-18T10:01:01Z."]},{"key":"dc:title","label":"Title","values":["Failure diagnosis in distributed systems"]}]}],"canonical_facts":{"dc:contributor":["Abdelzaher, Tarek F.","Han, Jiawei","Vaidya, Nitin H.","Ko, Steven"],"dc:creator":["Seo, Eunsoo"],"dc:date":["2012-09-18T21:18:33Z","2014-09-18T10:01:01Z","2012-08"],"dc:description":["Failures in computing systems are unavoidable. Therefore, it is important to detect and diagnose failures early to improve the reliability of systems. In this dissertation, new approaches on root-cause diagnosis for two notorious types of failures in distributed systems are introduced. This dissertation first focuses on the failures that are caused by software bugs triggered by race conditions. Due to the non-deterministic manifestation, these bugs are much harder to diagnose, fix and test than the bugs in sequential logic. To understand the concurrency bugs, we first study the characteristics of concurrency bugs using 105 bugs of four representative open-source programs. Motivated by the interesting findings from the study, we also propose an automatic bug diagnosis tool for distributed programs that finds the minimal causal orders of related events that trigger the bugs. Our tool is a significant extension to the previous tools that can find only bug-triggering sequence of events. The second focus of this dissertation is on the failures that are caused by propagating errors. An error started by a single network component propagates and contaminates other components. As a result, a large number of network components are infected by errors. To fix the problem, root-cause of this problem, the single component that started the error propagation, needs to be identified. It is assumed that only a limited view on the status of components -- whether they are infected or not -- are available through monitors, a set of pre-selected network components. For this problem, we propose two root-cause diagnosis tools. The first tool relies on a simple intuition that the root-cause component is likely to be close to the infected monitors and far from the uninfected monitors. We also compare six different monitor selection methods. The second tool makes use of additional information -- failure propagation probability and time of infections -- to improve the accuracy of root-cause diagnosis. We propose approximation algorithms to calculate the likelihood that a node is the failure source. In addition, we also propose a new monitor selection algorithm that maximizes the number of infected monitors for best accuracy of root-cause diagnosis.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-07-12T13:54:54Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Seo_Eunsoo.pdf: 6267189 bytes, checksum: 2e35a23744fe5e5f997f7f80e7c9e162 (MD5)","Made available in DSpace on 2012-09-18T21:18:33Z (GMT). No. of bitstreams: 2 Seo_Eunsoo.pdf: 6267189 bytes, checksum: 2e35a23744fe5e5f997f7f80e7c9e162 (MD5) license.txt: 4054 bytes, checksum: 5e1dfcf8e499ba3cb9cb0a6b3e0e9d87 (MD5)","Restriction data tranferred 2014-07-01T11:35:05-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2014-09-18 16:21:01 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (srobbins@illinois.edu) on 2012-09-18T21:21:10Z Item is restricted until 2014-09-18T21:21:01Z","U of I Only Restriction Lifted for Item 34741 on 2014-09-18T10:01:01Z."],"dc:identifier":["http://hdl.handle.net/2142/34467"],"dc:language":["en"],"dc:rights":["Copyright 2012 Eun Soo Seo"],"dc:subject":["Debugging","Bug Diagnosis","Concurrency Bugs","Error Propagation"],"dc:title":["Failure diagnosis in distributed systems"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:31Z"}