Cited By
View all- Biswas UChakraborty TYoung M(2024)Softening the Impact of Collisions in Contention ResolutionStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_29(398-416)Online publication date: 20-Oct-2024
Contention Resolution for Coded Radio Networks
Authors: 
Michael A. Bender, Seth Gilbert, Fabian Kuhn, John Kuszmaul, Muriel MédardAuthors Info & Claims
Pages 119 - 130
Abstract
Randomized backoff protocols, such as exponential backoff, are a powerful tool for managing access to a shared resource, often a wireless communication channel (e.g., [1]). For a wireless device to transmit successfully, it uses a backoff protocol to ensure exclusive access to the channel. Modern radios, however, do not need exclusive access to the channel to communicate; in particular, they have the ability to receive useful information even when more than one device transmits at the same time. These capabilities have now been exploited for many years by systems that rely on interference cancellation, physical layer network coding and analog network coding to improve efficiency. For example, Zigzag decoding [56] demonstrated how a base station can decode messages sent by multiple devices simultaneously.
In this paper, we address the following question: Can we design a backoff protocol that is better than exponential backoff when exclusive channel access is not required. We define the Coded Radio Network Model, which generalizes traditional radio network models (e.g., [30]). We then introduce the Decodable Backoff Algorithm, a randomized backoff protocol that achieves an optimal throughput of 1 - o (1). (Throughput 1 is optimal, as simultaneous reception does not increase the channel capacity.) The algorithm breaks the constant throughput lower bound for traditional radio networks [47-49], showing the power of these new hardware capabilities.
References
[1]
2016. IEEE Standard for Information Technology--Telecommunications and Information Exchange Between Systems Local and Metropolitan Area Networks -- Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Std 802.11--2016 (Revision of IEEE Std 802.11--2012) (2016), 1--3534.
[2]
N. Abramson. 1970. The ALOHA System - Another Alternative for Computer Communications. In Proc. of AFIPS FJCC, Vol. 37. 281--285.
[3]
N. Abramson. 1973. The Aloha system. In Computer-Communication Networks, N. Abramson and Frank Kuo (Eds.). Prentice-Hall, Englewood Cliffs, New Jersey, 501--518.
[4]
Norman Abramson. 1977. The throughput of packet broadcasting channels. IEEE Transactions on Communications 25, 1 (1977), 117--128.
[5]
Kunal Agrawal, Michael A. Bender, Jeremy Fineman, Seth Gilbert, and Maxwell Young. 2020. Contention Resolution with Message Deadlines. In Proc. 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 23--35.
[6]
D. Aldous. 1987. Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels. IEEE Transactions on Information Theory 33, 2 (1987), 219--223.
[7]
David J. Aldous. 1987. Ultimate Instability of Exponential Back-Off Protocol for Acknowledgment-Based Transmission Control of Random Access Communication Channels. IEEE Trans. on Inform. Theory IT-33, 2 (March 1987), 219--223.
[8]
Lakshmi Anantharamu, Bogdan S Chlebus, Dariusz R Kowalski, and Mariusz A Rokicki. 2011. Medium access control for adversarial channels with jamming. In International Colloquium on Structural Information and Communication Complexity. Springer, 89--100.
[9]
Lakshmi Anantharamu, Bogdan S Chlebus, Dariusz R Kowalski, and Mariusz A Rokicki. 2019. Packet latency of deterministic broadcasting in adversarial multiple access channels. J. Comput. System Sci. 99 (2019), 27--52.
[10]
Lakshmi Anantharamu, Bogdan S. Chlebus, and Mariusz A. Rokicki. 2009. Adversarial Multiple Access Channel with Individual Injection Rates. In Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS). 174--188.
[11]
J.G. Andrews. 2005. Interference cancellation for cellular systems: a contemporary overview. IEEE Wireless Communications 12, 2 (2005), 19--29. https://doi.org/10. 1109/MWC.2005.1421925
[12]
Antonio Fernández Anta, Chryssis Georgiou, Dariusz R. Kowalski, and Elli Zavou. 2017. Adaptive packet scheduling over a wireless channel under constrained jamming. Theor. Comput. Sci. 692 (2017), 72--89. https://doi.org/10.1016/j.tcs. 2017.06.020
[13]
Antonio Fernández Anta, Miguel A. Mosteiro, and Jorge Ramón Muñoz. 2013. Unbounded Contention Resolution in Multiple-Access Channels. Algorithmica 67, 3 (2013), 295--314.
[14]
Sanjeev Arora, Elad Hazan, and Satyen Kale. 2012. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory Comput. 8, 1 (2012), 121--164. https://doi.org/10.4086/toc.2012.v008a006
[15]
Baruch Awerbuch, Andrea Richa, and Christian Scheideler. 2008. A Jamming- Resistant MAC Protocol for Single-Hop Wireless Networks. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC). 45--54.
[16]
Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, and Charles E. Leiserson. 2005. Adversarial Contention Resolution for Simple Channels. In Proc. 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 325--332.
[17]
Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert. 2006. Contention Resolution with Heterogeneous Job Sizes. In Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11--13, 2006, Proceedings. 112--123. https://doi.org/10.1007/11841036_13
[18]
Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert. 2006. Contention Resolution with Heterogeneous Job Sizes. In Proc. 14th Annual European Symposium on Algorithms (ESA). 112--123.
[19]
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. 2016. How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness. In Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 636--654.
[20]
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. 2019. Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel- Access Attempts, and Robustness. J. ACM 66, 1 (January 2019), 6:1--6:33. https: //dl.acm.org/citation.cfm?id=3276769
[21]
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie. 2020. Contention Resolution without Collision Detection. In Proc. 52st Annual ACM Symposium on the Theory of Computing (STOC). 105--118.
[22]
Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young. 2016. Contention Resolution with Log-Logstar Channel Accesses. In Proc. 48th Annual Symposium on the Theory of Computing (STOC). 499--508.
[23]
Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young. 2018. Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses. SIAM J. Comput. 47, 5 (October 2018), 1735--1754. https://doi.org/10.1137/ 17M1158604
[24]
Giuseppe Bianchi. 2006. Performance Analysis of the IEEE 802.11 Distributed Coordination Function. IEEE Journal on Selected Areas in Communications 18, 3 (Sept. 2006), 535--547.
[25]
R. Binder, N. Abramson, F. Kuo, A. Okinaka, and D. Wax. 1975. ALOHA Packet Broadcasting: A Retrospect. In Proceedings of the APIPS National Computer Conference. 203--215.
[26]
E. Casini, R. De Gaudenzi, and Od. R. Herrero. 2007. Contention Resolution Diversity Slotted ALOHA (CRDSA): An Enhanced Random Access Schemefor Satellite Access Packet Networks. IEEE Transactions on Wireless Communications 6 (2007), 1408--1419. Issue 4.
[27]
Yi-Jun Chang, Wenyu Jin, and Seth Pettie. 2019. Simple Contention Resolution via Multiplicative Weight Updates. In 2nd Symposium on Simplicity in Algorithms (SOSA) (OASICS), Vol. 69. 16:1--16:16.
[28]
Haimin Chen, Yonggang Jiang, and Chaodong Zheng. 2021. Tight Trade-off in Contention Resolution without Collision Detection. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 139--149.
[29]
D. Chiu and R. Jain. 1989. Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks. Journal of Computer Networks and ISDN 17, 1 (1989), 1--14.
[30]
Imrich Chlamtac and Shay Kutten. 1985. On Broadcasting in Radio Networks- Problem Analysis and Protocol Design. IEEE Trans. Commun. 33, 12 (1985), 1240--1246. https://doi.org/10.1109/TCOM.1985.1096245
[31]
Bogdan S. Chlebus, Gianluca De Marco, and Dariusz R. Kowalski. 2016. Scalable Wake-up of Multi-channel Single-hop Radio Networks. Theoretical Computer Science 615, C (Feb. 2016), 23--44.
[32]
Bogdan S. Chlebus, Leszek Gasieniec, Dariusz R. Kowalski, and Tomasz Radzik. 2005. On the Wake-Up Problem in Radio Networks. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). 347--359.
[33]
Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. 2006. Adversarial queuing on the multiple-access channel. In Proc. Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC). 92--101.
[34]
Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. 2012. Adversarial Queuing on the Multiple Access Channel. ACM Transactions on Algorithms 8, 1 (2012), 5.
[35]
Marek Chrobak, Leszek Gasieniec, and Dariusz R. Kowalski. 2007. The Wake-Up Problem in MultiHop Radio Networks. SIAM J. Comput. 36, 5 (2007), 1453--1471.
[36]
Gianluca De Marco, Dariusz R Kowalski, and Grzegorz Stachowiak. 2021. Deterministic Contention Resolution without Collision Detection: Throughput vs Energy. In 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS). 1009--1019.
[37]
Gianluca De Marco and Grzegorz Stachowiak. 2017. Asynchronous Shared Channel. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC '17). 391--400.
[38]
Mohammadreza Ebrahimi, Farshad Lahouti, and Victoria Kostina. 2020. Two- Layer Coded Channel Access With Collision Resolution: Design and Analysis. IEEE Trans. Wirel. Commun. 19, 12 (2020), 7986--7997. https://doi.org/10.1109/ TWC.2020.3018472
[39]
Martín Farach-Colton and Miguel A Mosteiro. 2007. Initializing sensor networks of non-uniform density in the weak sensor model. In Workshop on Algorithms and Data Structures. Springer, 565--576.
[40]
Martín Farach-Colton and Miguel A Mosteiro. 2015. Initializing sensor networks of non-uniform density in the weak sensor model. Algorithmica 73, 1 (2015), 87--114.
[41]
Chen Feng, Danilo Silva, and Frank R. Kschischang. 2013. An Algebraic Approach to Physical-Layer Network Coding. IEEE Transactions on Information Theory 59, 11 (2013), 7576--7596. https://doi.org/10.1109/TIT.2013.2274264
[42]
Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, and Calvin Newport. 2016. Contention Resolution on a Fading Channel. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) (Chicago, Illinois, USA) (PODC '16). 155--164.
[43]
Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, and Calvin Newport. 2019. Contention resolution on a fading channel. Distributed Comput. 32, 6 (2019), 517--533. https://doi.org/10.1007/s00446-018-0323--9
[44]
Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, and Calvin C. Newport. 2016. Contention Resolution on a Fading Channel. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25--28, 2016, George Giakkoupis (Ed.). ACM, 155--164. https://doi.org/10. 1145/2933057.2933091
[45]
Jeremy T. Fineman, Calvin Newport, and Tonghe Wang. 2016. Contention Resolution on Multiple Channels with Collision Detection. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Chicago, Illinois, USA) (PODC '16). 175--184.
[46]
Mihály Geréb-Graus and Thanasis Tsantilas. 1992. Efficient Optical Communication in Parallel Computers. In Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). 41--48.
[47]
Leslie Ann Goldberg. 2000. Notes on Contention Resolution. (2000). http: //www.dcs.warwick.ac.uk/~leslie/contention.html
[48]
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, and Mike Paterson. 2000. A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. In Automata, Languages and Programming, 27th International Colloquium (ICALP). 705--716. https://doi.org/10.1007/3--540--45022-X_59
[49]
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, and Mike Paterson. 2004. A bound on the capacity of backoff and acknowledgment-based protocols. SIAM J. Comput. 33, 2 (2004), 313--331. https://doi.org/10.1137/S0097539700381851
[50]
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, and Mike Paterson. 2004. A bound on the capacity of backoff and acknowledgment-based protocols. SIAM J. Comput. 33, 2 (2004), 313--331.
[51]
Leslie Ann Goldberg, Mark Jerrum, Tom Leighton, and Satish Rao. 1997. Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. 26, 4 (Aug. 1997), 1100--1119.
[52]
Leslie Ann Goldberg and Philip D. MacKenzie. 1999. Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers. J. Comput. System Sci. 58, 1 (1999), 232--258. https://doi.org/10.1006/jcss.1998.1590
[53]
Leslie Ann Goldberg, PhilipD. MacKenzie, Mike Paterson, and Aravind Srinivasan. 2000. Contention resolution with constant expected delay. J. ACM 47, 6 (2000), 1048--1096.
[54]
Leslie Ann Goldberg, Philip D. Mackenzie, Mike Paterson, and Aravind Srinivasan. 2000. Contention Resolution with Constant Expected Delay. J. ACM 47, 6 (2000), 1048--1096.
[55]
Leslie Ann Goldberg, Yossi Matias, and Satish Rao. 1999. An Optical Simulation of Shared Memory. 28, 5 (Oct. 1999), 1829--1847.
[56]
Shyamnath Gollakota and Dina Katabi. 2008. Zigzag decoding: combating hidden terminals in wireless networks. In Proceedings of the ACM SIGCOMM 2008 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (Seattle, WA, USA). 159--170. https://doi.org/10.1145/1402958. 1402977
[57]
Jonathan Goodman, Albert G. Greenberg, Neal Madras, and Peter March. 1988. Stability of Binary Exponential Backoff. Journal of the ACM (JACM) 35, 3 (June 1988), 579--602.
[58]
Jonathan Goodman, Albert G. Greenberg, Neal Madras, and Peter March. 1988. Stability of Binary Exponential Backoff. J. ACM 35, 3 (July 1988), 579--602.
[59]
Albert G. Greenberg, Philippe Flajolet, and Richard E. Ladner. 1987. Estimating the Multiplicities of Conflicts to Speed Their Resolution in Multiple Access Channels. J. ACM 34, 2 (April 1987), 289--325.
[60]
Albert G. Greenberg and Shmuel Winograd. 1985. A Lower Bound on the Time Needed in the Worst Case to Resolve Conflicts Deterministically in Multiple Access Channels. J. ACM 32, 3 (1985), 589--596.
[61]
D. Halperin, J. Ammer, T. Anderson, and D. Wetherall. 2007. Interference Cancellation: Better Receivers for a New Wireless MAC. In Hotnets.
[62]
Johan Håstad, Frank Thomson Leighton, and Brian Rogoff. 1987. Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract). In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), Alfred V. Aho (Ed.). 241--253.
[63]
Johan Håstad, Frank Thomson Leighton, and Brian Rogoff. 1996. Analysis of Backoff Protocols for Multiple Access Channels. SIAM J. Comput. 25, 4 (1996), 740--774. https://doi.org/10.1137/S0097539792233828
[64]
Johan Hastad, Tom Leighton, and Brian Rogoff. 740--774. Analysis of Backoff Protocols for Multiple Access Channels. SIAM J. Comput. 25, 4 (740--774), 1996.
[65]
T. Leighton, and B. Rogoff. 1987. Analysis of Backoff Protocols for Multiple Access Channels. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (New York, New York, USA) (STOC '87). Association for Computing Machinery, New York, NY, USA, 241--253. https: //doi.org/10.1145/28395.28422
[66]
Tomasz Jurdzi'ski and Grzegorz Stachowiak. 2002. Probabilistic algorithms for the wakeup problem in single-hop radio networks. In Proceedings of the International Symposium on Algorithms and Computation. Springer, 535--549.
[67]
Tomasz Jurdzinski and Grzegorz Stachowiak. 2005. Probabilistic algorithms for the wake-up problem in single-hop radio networks. Theory of Computing Systems 38, 3 (2005), 347--367.
[68]
Tomasz Jurdzinski and Grzegorz Stachowiak. 2015. The cost of synchronizing multiple-access channels. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. 421--430.
[69]
Sachin Katti, Shyamnath Gollakota, and Dina Katabi. 2007. Embracing Wireless Interference: Analog Network Coding. ACM SIGCOMM Computer Communication Review 9 (02 2007).
[70]
Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, and Jon Crowcroft. 2006. XORs in the air: practical wireless network coding. In Proceedings of the ACM SIGCOMM 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Pisa, Italy, September 11--15, 2006, Luigi Rizzo, Thomas E. Anderson, and Nick McKeown (Eds.). ACM, 243--254. https://doi.org/10.1145/1159913.1159942
[71]
Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, and Jon Crowcroft. 2008. XORs in the air: practical wireless network coding. IEEE/ACM Trans. Netw. 16, 3 (2008), 497--510. https://doi.org/10.1145/1399562.1399563
[72]
Frank P Kelly and Iain M MacPhee. 1987. The number of packets transmitted by collision detect random access schemes. The Annals of Probability (1987), 1557--1568.
[73]
Dariusz R. Kowalski. 2005. On selection problem in radio networks. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC 2005, Las Vegas, NV, USA, July 17--20, 2005. 158--166. https://doi.org/10.1145/1073814.1073843
[74]
James F. Kurose and Keith Ross. 2002. Computer Networking: A Top-Down Approach Featuring the Internet (2nd ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
[75]
Gianluca De Marco and Dariusz R. Kowalski. 2015. Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel. SIAM J. Comput. 44, 3 (2015), 868--888.
[76]
Gianluca De Marco and Dariusz R. Kowalski. 2017. Contention Resolution in a Non-Synchronized Multiple Access Channel. Theoretical Computer Science 689 (2017), 1--13.
[77]
Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak. 2019. Deterministic Contention Resolution on a Shared Channel. In 39th IEEE International Conference on Distributed Computing Systems, ICDCS. 472--482.
[78]
Gianluca De Marco, Marco Pellegrini, and Giovanni Sburlati. 2007. Faster deterministic wakeup in multiple access channels. Discret. Appl. Math. 155, 8 (2007), 898--903.
[79]
Robert M. Metcalfe and David R. Boggs. 1976. Ethernet: Distributed Packet Switching for Local Computer Networks. Commun. ACM 19, 7 (July 1976), 395-- 404.
[80]
Jeannine Mosely and Pierre Humblet. 1985. A class of efficient contention resolution algorithms for multiple access channels. IEEE transactions on Communications 33, 2 (1985), 145--151.
[81]
Adrian Ogierman, Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2018. Sade: competitive MAC under adversarial SINR. Distributed Computing 31, 3 (01 Jun 2018), 241--254.
[82]
Adrian Ogierman, Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2018. Sade: competitive MAC under adversarial SINR. Distributed Computing 31, 3 (2018), 241--254.
[83]
Prabhakar Raghavan and Eli Upfal. 1995. Stochastic contention resolution with short delays. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC). 229--237.
[84]
Prabhakar Raghavan and Eli Upfal. 1998. Stochastic Contention Resolution With Short Delays. SIAM J. Comput. 28, 2 (1998), 709--719.
[85]
Prabhakar Raghavan and Eli Upfal. 1999. Stochastic Contention Resolution With Short Delays. 28, 2 (April 1999), 709--719.
[86]
Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2010. A Jamming-Resistant MAC Protocol for Multi-Hop Wireless Networks. In Proceedings of the International Symposium on Distributed Computing (DISC). 179--193.
[87]
Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2011. Competitive and Fair Medium Access Despite Reactive Jamming. In Proceedings of the 31 International Conference on Distributed Computing Systems (ICDCS). 507--516.
[88]
Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2012. Competitive and Fair Throughput for Co-Existing Networks Under Adversarial Interference. In Proceedings of the 31 ACM Symposium on Principles of Distributed Computing (PODC). 291--300.
[89]
Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2013. Competitive Throughput in Multi-Hop Wireless Networks Despite Adaptive Jamming. Distributed Computing 26, 3 (2013), 159--171.
[90]
Andréa W. Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2013. An Efficient and Fair MAC Protocol Robust to Reactive Interference. IEEE/ACM Trans. Netw. 21, 3 (2013), 760--771. https://doi.org/10.1109/TNET.2012.2210241
[91]
Lawrence G. Roberts. 1975. ALOHA packet system with and without slots and capture. SIGCOMM Compuer Communications Review 5, 2 (1975), 28--42.
[92]
John F Shoch and Jon A Hupp. 1980. Measured performance of an Ethernet local network. Commun. ACM 23, 12 (1980), 711--721.
[93]
Nah-Oak Song, Byung-Jae Kwak, and Leonard E. Miller. 2003. On the Stability of Exponential Backoff. Journal of Research of the National Institute of Standards and Technology 108, 4 (2003).
[94]
Arash Saber Tehrani, Alexandros G. Dimakis, and Michael J. Neely. 2011. SigSag: Iterative detection through soft message-passing. In INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10--15 April 2011, Shanghai, China. IEEE, 1017--1025. https://doi.org/10.1109/INFCOM.2011.5934874
[95]
David Tse and Pramod Viswanath. 2005. Fundamentals of Wireless Communication. Cambridge University Press.
[96]
B. S. Tsybakov and N. B. Likhanov. 1987. Upper Bound on the Capacity of a Random Multiple-Access System. Problemy Peredachi Informatsii 23, 3 (1987), 64--78.
[97]
Dan E. Willard. 1986. Log-logarithmic Selection Resolution Protocols in a Multiple Access Channel. SIAM J. Comput. 15, 2 (May 1986), 468--477.
[98]
Yang Xiao. 2005. Performance Analysis of Priority Schemes for IEEE 802.11 and IEEE 802.11e Wireless LANs. Wireless Communications, IEEE Transactions on 4, 4 (July 2005), 1506--1515.
Index Terms
- Contention Resolution for Coded Radio Networks
Recommendations
Contention Resolution with Message Deadlines
SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and ArchitecturesIn the contention-resolution problem, multiple players contend for access to a shared resource. Contention resolution is used in wireless networks, where messages must be transmitted on a shared communication channel. When two or more messages are ...
A Distributed Contention Vector Division Multiple Access (D-CVDMA) Protocol for Wireless Networks
Traditional Time Division Multiple Access (TDMA) protocol provides deterministic periodic collision-free data transmissions. However, TDMA lacks flexibility and exhibits low efficiency in dynamic environments such as wireless LANs. On the other hand, ...
On the optimization of the contention resolution mechanism for IEEE 802.16 networks
The IEEE 802.16 standard defines a contention bandwidth request mechanism offering QoS-aware broadband access through a wireless medium. According to the standard, the Base Station (BS) is responsible for granting the requests issued by the Subscriber ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
464 pages
ISBN:9781450391467
DOI:10.1145/3490148
- General Chair:
- Kunal Agrawal,
- Program Chair:
- I-Ting Angelina Lee
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- SIGARCH: ACM Special Interest Group on Computer Architecture
- EATCS: European Association for Theoretical Computer Science
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSF
- Singapore MOE
Conference
SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures
July 11 - 14, 2022
PA, Philadelphia, USA
Acceptance Rates
Overall Acceptance Rate 447 of 1,461 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 156Total Downloads
- Downloads (Last 12 months)53
- Downloads (Last 6 weeks)9
Reflects downloads up to 05 Jan 2025
Other Metrics
Citations
Cited By
View all- Biswas UChakraborty TYoung M(2024)Softening the Impact of Collisions in Contention ResolutionStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_29(398-416)Online publication date: 20-Oct-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in