{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69405"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69405","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fault-Tolerant Distributed Algorithms for Agreement and Election","abstract":"This thesis consists of three parts. In the first part, we characterize completely the shared-memory requirements for achieving agreement in an asynchronous system of fail-stop processes that die undetectably. There is no agreement protocol that uses only read and write operations, even if at most one process dies. This result implies the impossibility of Byzantine agreement in asynchronous message-passing systems. Furthermore, there is no agreement protocol that uses test-and-set operations if memory cells have only two values and two or more processes may die. In contrast, there is an agreement protocol with test-and-set operations if either memory cells have at least three values or at most one process dies.","abstract_html":"This thesis consists of three parts. In the first part, we characterize completely the shared-memory requirements for achieving agreement in an asynchronous system of fail-stop processes that die undetectably. There is no agreement protocol that uses only read and write operations, even if at most one process dies. This result implies the impossibility of Byzantine agreement in asynchronous message-passing systems. Furthermore, there is no agreement protocol that uses test-and-set operations if memory cells have only two values and two or more processes may die. In contrast, there is an agreement protocol with test-and-set operations if either memory cells have at least three values or at most one process dies.","abstract_has_math":false,"creators":["Abu-Amara, Hosame Hassan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Loui, Michael C."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:05:37Z","date_published":"2014-12-15T19:05:37Z","updated_at":"2026-07-22T22:26:00Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8908604"],"render_values":[{"text":"(UMI)AAI8908604","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69405","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Loui, Michael C."]},{"key":"dc:creator","label":"Author","values":["Abu-Amara, Hosame Hassan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:05:37Z","10000-01-01","1988"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"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":["Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69405","(UMI)AAI8908604"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis consists of three parts. In the first part, we characterize completely the shared-memory requirements for achieving agreement in an asynchronous system of fail-stop processes that die undetectably. There is no agreement protocol that uses only read and write operations, even if at most one process dies. This result implies the impossibility of Byzantine agreement in asynchronous message-passing systems. Furthermore, there is no agreement protocol that uses test-and-set operations if memory cells have only two values and two or more processes may die. In contrast, there is an agreement protocol with test-and-set operations if either memory cells have at least three values or at most one process dies.","In the second part, we consider the election problem on asynchronous complete networks when the processors are reliable but some of the channels may be intermittently faulty. To be consistent with the standard model of distributed algorithms in which channel delays can be arbitrary but finite, we assume that channel failures are undetectable. We give an algorithm that correctly solves the problem when the channels fail before or during the execution of the algorithm. Let n be the number of processors in the network, f be the maximum number of faulty channels, and r be a design parameter. The algorithm uses no more than $O(nrf+{nr\\over (r-1)}$log$({n\\over (r-1)f}))$ messages in the worst case, runs in time $O({n\\over (r-1)f})$, and uses at most $O$(log$\\vert T\\vert$) bits per message, where $\\vert T\\vert$ is the cardinality of the set of processor identifiers. If $r$ is chosen to minimize the number of messages, our algorithm uses no more than $O(nf+n$log $n)$ messages.","In the third part, we present the most efficient algorithm that we know of for election in synchronous square meshes. The algorithm uses ${229\\over 18}n$ messages, runs in time $\\Theta$($\\sqrt{n}$) time units, and requires $O$(log$\\vert T\\vert$) bits per message. Also, we prove that any comparison algorithm on meshes requires at least ${57\\over 32}n$ messages.","Made available in DSpace on 2014-12-15T19:05:37Z (GMT). No. of bitstreams: 1 8908604.pdf: 3831681 bytes, checksum: 2497d0b7613f372d8a6cf7f2ad4bca6f (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69571 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","97 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."]},{"key":"dc:title","label":"Title","values":["Fault-Tolerant Distributed Algorithms for Agreement and Election"]}]}],"canonical_facts":{"dc:contributor":["Loui, Michael C."],"dc:creator":["Abu-Amara, Hosame Hassan"],"dc:date":["2014-12-15T19:05:37Z","10000-01-01","1988"],"dc:description":["This thesis consists of three parts. In the first part, we characterize completely the shared-memory requirements for achieving agreement in an asynchronous system of fail-stop processes that die undetectably. There is no agreement protocol that uses only read and write operations, even if at most one process dies. This result implies the impossibility of Byzantine agreement in asynchronous message-passing systems. Furthermore, there is no agreement protocol that uses test-and-set operations if memory cells have only two values and two or more processes may die. In contrast, there is an agreement protocol with test-and-set operations if either memory cells have at least three values or at most one process dies.","In the second part, we consider the election problem on asynchronous complete networks when the processors are reliable but some of the channels may be intermittently faulty. To be consistent with the standard model of distributed algorithms in which channel delays can be arbitrary but finite, we assume that channel failures are undetectable. We give an algorithm that correctly solves the problem when the channels fail before or during the execution of the algorithm. Let n be the number of processors in the network, f be the maximum number of faulty channels, and r be a design parameter. The algorithm uses no more than $O(nrf+{nr\\over (r-1)}$log$({n\\over (r-1)f}))$ messages in the worst case, runs in time $O({n\\over (r-1)f})$, and uses at most $O$(log$\\vert T\\vert$) bits per message, where $\\vert T\\vert$ is the cardinality of the set of processor identifiers. If $r$ is chosen to minimize the number of messages, our algorithm uses no more than $O(nf+n$log $n)$ messages.","In the third part, we present the most efficient algorithm that we know of for election in synchronous square meshes. The algorithm uses ${229\\over 18}n$ messages, runs in time $\\Theta$($\\sqrt{n}$) time units, and requires $O$(log$\\vert T\\vert$) bits per message. Also, we prove that any comparison algorithm on meshes requires at least ${57\\over 32}n$ messages.","Made available in DSpace on 2014-12-15T19:05:37Z (GMT). No. of bitstreams: 1 8908604.pdf: 3831681 bytes, checksum: 2497d0b7613f372d8a6cf7f2ad4bca6f (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69571 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","97 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."],"dc:identifier":["http://hdl.handle.net/2142/69405","(UMI)AAI8908604"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Fault-Tolerant Distributed Algorithms for Agreement and Election"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:00Z"}