{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/79227"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/79227","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Bounds on contention management in radio networks","abstract":"In this thesis, we study the local broadcast problem in two well-studied wireless network models. The local broadcast problem is a theoretical approach for capturing the contention management issue in wireless networks; it assumes that processes are provided messages, one by one, that must be delivered to their neighbors. We study this problem in two theoretical models of wireless networks, the classical radio network model and its more recent generalization, the dual graph model which includes the possibility of unreliable time-changing links. Both these models are synchronous; the execution proceeds in lock-step rounds and in each round, each node either transmits a message or listens. In each round of the dual graph model, each unreliable link might be active or inactive, whereas in the classical model, all the links are always active. In each round, each node receives a message if and only if it is listening and exactly one of its neighbors, with respect to the the active links of that round, transmits. The time complexity of the local broadcast algorithms is measured by two bounds, the acknowledgment bound and the progress bound. Roughly speaking, the former bounds the time it takes each broadcasting node to deliver its message to all its neighbors and the latter bounds the time it takes a node to receive at least one message, assuming it has a broadcasting neighbor. Typically these bounds depend on the maximum contention and the network size. The standard local broadcast strategy is the Decay protocol introduced by Bar-Yehuda et al. [19] in 1987. During the 25-years period in which this strategy has been used, it has remained an open question whether it is optimal. In this paper, we resolve this long-standing question. We present lower bounds on progress and acknowledgment bounds in both the classical and the dual graph model and we show that, with a slight optimization, the Decay protocol matches these lower bounds in both models. However, the tight progress bound of the dual graph model is exponentially larger than the progress bound in the classical model, in its dependence on the maximum contention. This establishes a separation between the two models, proving that progress in the dual graph model is strictly and exponentially harder than its classical predecessor. Combined, our results provide an essentially complete characterization of the local broadcast problem in these two important models.","abstract_html":"In this thesis, we study the local broadcast problem in two well-studied wireless network models. The local broadcast problem is a theoretical approach for capturing the contention management issue in wireless networks; it assumes that processes are provided messages, one by one, that must be delivered to their neighbors. We study this problem in two theoretical models of wireless networks, the classical radio network model and its more recent generalization, the dual graph model which includes the possibility of unreliable time-changing links. Both these models are synchronous; the execution proceeds in lock-step rounds and in each round, each node either transmits a message or listens. In each round of the dual graph model, each unreliable link might be active or inactive, whereas in the classical model, all the links are always active. In each round, each node receives a message if and only if it is listening and exactly one of its neighbors, with respect to the the active links of that round, transmits. The time complexity of the local broadcast algorithms is measured by two bounds, the acknowledgment bound and the progress bound. Roughly speaking, the former bounds the time it takes each broadcasting node to deliver its message to all its neighbors and the latter bounds the time it takes a node to receive at least one message, assuming it has a broadcasting neighbor. Typically these bounds depend on the maximum contention and the network size. The standard local broadcast strategy is the Decay protocol introduced by Bar-Yehuda et al. [19] in 1987. During the 25-years period in which this strategy has been used, it has remained an open question whether it is optimal. In this paper, we resolve this long-standing question. We present lower bounds on progress and acknowledgment bounds in both the classical and the dual graph model and we show that, with a slight optimization, the Decay protocol matches these lower bounds in both models. However, the tight progress bound of the dual graph model is exponentially larger than the progress bound in the classical model, in its dependence on the maximum contention. This establishes a separation between the two models, proving that progress in the dual graph model is strictly and exponentially harder than its classical predecessor. Combined, our results provide an essentially complete characterization of the local broadcast problem in these two important models.","abstract_has_math":false,"creators":["Ghaffari, Mohsen"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Nancy Lynch."],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013","date_published":"2013","updated_at":"2026-07-22T22:22:00Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/79227","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Nancy Lynch."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Ghaffari, Mohsen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2013-06-17T19:49:06Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2013-06-17T19:49:06Z"]},{"key":"dc:date.issued","label":"Date","values":["2013"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/79227"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 79-82)."]},{"key":"dc:description.abstract","label":"Abstract","values":["In this thesis, we study the local broadcast problem in two well-studied wireless network models. The local broadcast problem is a theoretical approach for capturing the contention management issue in wireless networks; it assumes that processes are provided messages, one by one, that must be delivered to their neighbors. We study this problem in two theoretical models of wireless networks, the classical radio network model and its more recent generalization, the dual graph model which includes the possibility of unreliable time-changing links. Both these models are synchronous; the execution proceeds in lock-step rounds and in each round, each node either transmits a message or listens. In each round of the dual graph model, each unreliable link might be active or inactive, whereas in the classical model, all the links are always active. In each round, each node receives a message if and only if it is listening and exactly one of its neighbors, with respect to the the active links of that round, transmits. The time complexity of the local broadcast algorithms is measured by two bounds, the acknowledgment bound and the progress bound. Roughly speaking, the former bounds the time it takes each broadcasting node to deliver its message to all its neighbors and the latter bounds the time it takes a node to receive at least one message, assuming it has a broadcasting neighbor. Typically these bounds depend on the maximum contention and the network size. The standard local broadcast strategy is the Decay protocol introduced by Bar-Yehuda et al. [19] in 1987. During the 25-years period in which this strategy has been used, it has remained an open question whether it is optimal. In this paper, we resolve this long-standing question. We present lower bounds on progress and acknowledgment bounds in both the classical and the dual graph model and we show that, with a slight optimization, the Decay protocol matches these lower bounds in both models. However, the tight progress bound of the dual graph model is exponentially larger than the progress bound in the classical model, in its dependence on the maximum contention. This establishes a separation between the two models, proving that progress in the dual graph model is strictly and exponentially harder than its classical predecessor. Combined, our results provide an essentially complete characterization of the local broadcast problem in these two important models."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Bounds on contention management in radio networks"]}]}],"canonical_facts":{"dc:contributor.advisor":["Nancy Lynch."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Ghaffari, Mohsen"],"dc:date.accessioned":["2013-06-17T19:49:06Z"],"dc:date.available":["2013-06-17T19:49:06Z"],"dc:date.issued":["2013"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 79-82)."],"dc:description.abstract":["In this thesis, we study the local broadcast problem in two well-studied wireless network models. The local broadcast problem is a theoretical approach for capturing the contention management issue in wireless networks; it assumes that processes are provided messages, one by one, that must be delivered to their neighbors. We study this problem in two theoretical models of wireless networks, the classical radio network model and its more recent generalization, the dual graph model which includes the possibility of unreliable time-changing links. Both these models are synchronous; the execution proceeds in lock-step rounds and in each round, each node either transmits a message or listens. In each round of the dual graph model, each unreliable link might be active or inactive, whereas in the classical model, all the links are always active. In each round, each node receives a message if and only if it is listening and exactly one of its neighbors, with respect to the the active links of that round, transmits. The time complexity of the local broadcast algorithms is measured by two bounds, the acknowledgment bound and the progress bound. Roughly speaking, the former bounds the time it takes each broadcasting node to deliver its message to all its neighbors and the latter bounds the time it takes a node to receive at least one message, assuming it has a broadcasting neighbor. Typically these bounds depend on the maximum contention and the network size. The standard local broadcast strategy is the Decay protocol introduced by Bar-Yehuda et al. [19] in 1987. During the 25-years period in which this strategy has been used, it has remained an open question whether it is optimal. In this paper, we resolve this long-standing question. We present lower bounds on progress and acknowledgment bounds in both the classical and the dual graph model and we show that, with a slight optimization, the Decay protocol matches these lower bounds in both models. However, the tight progress bound of the dual graph model is exponentially larger than the progress bound in the classical model, in its dependence on the maximum contention. This establishes a separation between the two models, proving that progress in the dual graph model is strictly and exponentially harder than its classical predecessor. Combined, our results provide an essentially complete characterization of the local broadcast problem in these two important models."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/79227"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Bounds on contention management in radio networks"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:00Z"}