{"id":{"repo_id":"msu","oai_identifier":"oai:d.lib.msu.edu:etd_52163"},"canonical_url":"https://search.ndltd.org/etd/msu/oai:d.lib.msu.edu:etd_52163","repository":{"repo_id":"msu","name":"Michigan State University","base_url":"https://d.lib.msu.edu/oai"},"display":{"title":"Convergence Sans Synchronization","abstract":"Thesis (Ph.D.)--Michigan State University. Computer Science - Doctor of Philosophy, 2024","abstract_html":"Thesis (Ph.D.)--Michigan State University. Computer Science - Doctor of Philosophy, 2024","abstract_has_math":false,"creators":["Gupta, Arya Tanmay"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Kulkarni, Sandeep S","Esfahanian, Abdol-Hossein","Torng, Eric","Bopardikar, Shaunak D"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024","date_published":"2024","updated_at":"2026-11-18T18:58:52Z","subjects":["Computer science","Computer engineering"],"languages":["eng"],"rights":["Attribution 4.0 International"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:52163","local:Gupta_grad.msu_0128D_21057"],"render_values":[{"text":"etd:52163","href":null,"code":true},{"text":"local:Gupta_grad.msu_0128D_21057","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://doi.org/doi:10.25335/kmxr-2d15","outbound_label":"DOI","outbound_source":"dc:identifier","record_url":"https://doi.org/doi:10.25335/kmxr-2d15","record_label":"Repository record","record_kind":"doi","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://d.lib.msu.edu/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Ad.lib.msu.edu%3Aetd_52163","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kulkarni, Sandeep S","Esfahanian, Abdol-Hossein","Torng, Eric","Bopardikar, Shaunak D"]},{"key":"dc:creator","label":"Author","values":["Gupta, Arya Tanmay"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024"]},{"key":"dc:relation","label":"Dc Relation","values":["Electronic Theses & Dissertations"]},{"key":"dc:type","label":"Dc Type","values":["text","Electronic dissertations"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science","Computer engineering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution 4.0 International"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:52163","local:Gupta_grad.msu_0128D_21057","https://doi.org/doi:10.25335/kmxr-2d15"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph.D.)--Michigan State University. Computer Science - Doctor of Philosophy, 2024","We currently see a steady rise in the usage and size of multiprocessor systems, and so the community is evermore interested in developing fast parallel processing algorithms. However, most algorithms require a synchronization mechanism, which is costly in terms of computational resources and time.If an algorithm can be executed in asynchrony, then it can use all the available computation power, and the nodes can execute without being scheduled or locked. However, to show that an algorithm guarantees convergence in asynchrony, we need to generate the entire global state transition graph and check for the absence of cycles. This takes time exponential in the size of the global state space.In this dissertation, we present a theory that explains the necessary and sufficient properties of a multiprocessor algorithm that guarantees convergence even without synchronization. We develop algorithms for various problems that do not require synchronization. Additionally, we show for several existing algorithms that they can be executed without any synchronization mechanism.A significant theoretical benefit of our work is in proving that an algorithm can converge even in asynchrony. Our theory implies that we can make such conclusions about an algorithm, by only showing that the local state transition graph of a computing node forms a partial order, rather than generating the entire global state space and determining the absence of cycles in it. Thus, the complexity of rendering such proofs, formal or social, is phenomenally reduced.Experiments show a significant reduction in time taken to converge, when we compare the execution time of algorithms in the literature versus the algorithms that we design. We get similar results when we run an algorithm, that guarantees convergence in asynchrony, under a scheduler versus in asynchrony. These results include some important practical benefits of our work.","Description based on online resource. Title from PDF t.p. (Michigan State University Fedora Repository, viewed ).","Includes bibliographical references."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf","1 online resource (160 p.) : ill."]},{"key":"dc:title","label":"Title","values":["Convergence Sans Synchronization"]}]}],"canonical_facts":{"dc:contributor":["Kulkarni, Sandeep S","Esfahanian, Abdol-Hossein","Torng, Eric","Bopardikar, Shaunak D"],"dc:creator":["Gupta, Arya Tanmay"],"dc:date":["2024"],"dc:description":["Thesis (Ph.D.)--Michigan State University. Computer Science - Doctor of Philosophy, 2024","We currently see a steady rise in the usage and size of multiprocessor systems, and so the community is evermore interested in developing fast parallel processing algorithms. However, most algorithms require a synchronization mechanism, which is costly in terms of computational resources and time.If an algorithm can be executed in asynchrony, then it can use all the available computation power, and the nodes can execute without being scheduled or locked. However, to show that an algorithm guarantees convergence in asynchrony, we need to generate the entire global state transition graph and check for the absence of cycles. This takes time exponential in the size of the global state space.In this dissertation, we present a theory that explains the necessary and sufficient properties of a multiprocessor algorithm that guarantees convergence even without synchronization. We develop algorithms for various problems that do not require synchronization. Additionally, we show for several existing algorithms that they can be executed without any synchronization mechanism.A significant theoretical benefit of our work is in proving that an algorithm can converge even in asynchrony. Our theory implies that we can make such conclusions about an algorithm, by only showing that the local state transition graph of a computing node forms a partial order, rather than generating the entire global state space and determining the absence of cycles in it. Thus, the complexity of rendering such proofs, formal or social, is phenomenally reduced.Experiments show a significant reduction in time taken to converge, when we compare the execution time of algorithms in the literature versus the algorithms that we design. We get similar results when we run an algorithm, that guarantees convergence in asynchrony, under a scheduler versus in asynchrony. These results include some important practical benefits of our work.","Description based on online resource. Title from PDF t.p. (Michigan State University Fedora Repository, viewed ).","Includes bibliographical references."],"dc:format":["application/pdf","1 online resource (160 p.) : ill."],"dc:identifier":["etd:52163","local:Gupta_grad.msu_0128D_21057","https://doi.org/doi:10.25335/kmxr-2d15"],"dc:language":["eng"],"dc:relation":["Electronic Theses & Dissertations"],"dc:rights":["Attribution 4.0 International"],"dc:subject":["Computer science","Computer engineering"],"dc:title":["Convergence Sans Synchronization"],"dc:type":["text","Electronic dissertations"]},"updated_at":"2026-11-18T18:58:52Z"}