Contention resolution with constant throughput and log-logstar channel accesses.

*(English)*Zbl 1400.68258##### MSC:

68W15 | Distributed algorithms |

68M12 | Network protocols |

68W20 | Randomized algorithms |

68W40 | Analysis of algorithms |

##### Keywords:

contention resolution; distributed computing; algorithms; wireless networks; throughput; adversarial scheduling
PDF
BibTeX
XML
Cite

\textit{M. A. Bender} et al., SIAM J. Comput. 47, No. 5, 1735--1754 (2018; Zbl 1400.68258)

Full Text:
DOI

**OpenURL**

##### References:

[2] | L. Anantharamu, B. S. Chlebus, D. R. Kowalski, and M. A. Rokicki, Medium access control for adversarial channels with jamming, in Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Springer, Berlin, 2011, pp. 89–100. |

[3] | L. Anantharamu, B. S. Chlebus, and M. A. Rokicki, Adversarial multiple access channel with individual injection rates, in Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS), Springer, Heidelberg, 2009, pp. 174–188. · Zbl 1410.68379 |

[4] | G. Anastasi, A. Falchi, A. Passarella, M. Conti, and E. Gregori, Performance measurements of motes sensor networks, in Proceedings of the 7th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, MSWiM ’04, ACM, New York, 2004, pp. 174–181. |

[5] | W. C. Anderton and M. Young, Is our model for contention resolution wrong?: Confronting the cost of collisions, in Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’17, ACM, New York, 2017, pp. 183–194. |

[6] | A. F. Anta, M. A. Mosteiro, and J. R. Mun͂oz, Unbounded contention resolution in multiple-access channels, Algorithmica, 67 (2013), pp. 295–314. · Zbl 1311.68012 |

[7] | C. Avin, Y. Emek, E. Kantor, Z. Lotker, D. Peleg, and L. Roditty, SINR diagrams: Towards algorithmically usable SINR models of wireless networks, in Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2009, pp. 200–209. · Zbl 1291.68029 |

[8] | B. Awerbuch, A. Richa, and C. Scheideler, A jamming-resistant MAC protocol for single-hop wireless networks, in Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2008, pp. 45–54. · Zbl 1301.68041 |

[9] | Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal, Balanced allocations, SIAM J. Comput., 29 (1999), pp. 180–200. · Zbl 0937.68053 |

[10] | R. Bar-Yehuda, O. Goldreich, and A. Itai, On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization, J. Comput. System Sci., 45 (1992), pp. 104–126. · Zbl 0752.68009 |

[11] | M. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, and C. E. Leiserson, Adversarial contention resolution for simple channels, in Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, New York, ACM, New York, 2005, pp. 325–332. |

[12] | M. A. Bender, J. T. Fineman, and S. Gilbert, Contention resolution with heterogeneous job sizes, in Proceedings of the 14th Annual European Symposium on Algorithms (ESA), Springer, Berlin, 2006, pp. 112–123. · Zbl 1131.90349 |

[13] | M. A. Bender, J. T. Fineman, S. Gilbert, and M. Young, How to scale exponential backoff: Constant throughput, polylog access attempts, and robustness, in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2016, pp. 636–654. · Zbl 1410.68066 |

[14] | M. A. Bender, T. Kopelowitz, S. Pettie, and M. Young, Contention resolution with log-logstar channel accesses, in Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC ’16, ACM, New York, 2016, pp. 499–508. · Zbl 1373.68075 |

[15] | P. Berenbrink, A. Czumaj, M. Englert, T. Friedetzky, and L. Nagel, Multiple-choice balanced allocation in (almost) parallel, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX-RANDOM), Springer, Berlin, 2012, pp. 411–422. · Zbl 1372.68308 |

[16] | P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking, Balanced allocations: The heavily loaded case, SIAM J. Comput., 35 (2006), pp. 1350–1385. · Zbl 1114.68082 |

[17] | P. Berenbrink, K. Khodamoradi, T. Sauerwald, and A. Stauffer, Balls-into-bins with nearly optimal load distribution, in Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, New York, 2013, pp. 326–335. |

[18] | D. J. Bernstein, qmail, (1998). |

[19] | G. Bianchi, Performance analysis of the IEEE 802.11 distributed coordination function, IEEE J. Sel. Areas Commun., 18 (2006), pp. 535–547. |

[20] | G. Bianchi and I. Tinnirello, Kalman filter estimation of the number of competing terminals in an IEEE 802.11 network, in Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Vol. 2, IEEE, Piscataway, NJ, 2003, pp. 844–852. |

[21] | P. Brandes, M. Kardas, M. Klonowski, D. Pajak, and R. Wattenhofer, Approximating the size of a radio network in beeping model, in Proceedings of the 23rd International Colloquium Structural Information and Communication Complexity (SIROCCO), Springer, Cham, Switzerland, 2016, pp. 358–373. · Zbl 1437.68012 |

[22] | F. Cali, M. Conti, and E. Gregori, Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit, IEEE/ACM Trans. Netw., 8 (2000), pp. 785–799. |

[23] | F. Cali, M. Conti, and E. Gregori, IEEE 802.11 protocol: Design and performance evaluation of an adaptive backoff mechanism, IEEE J. Sel. Areas Commun., 18 (2000), pp. 1774–1786. |

[24] | A. Casteigts, Y. Métivier, J. M. Robson, and A. Zemmari, Counting in One-Hop Beeping Networks, preprints, arXiv:1605.09516, 2016. |

[25] | A. Cerpa, J. L. Wong, L. Kuang, M. Potkonjak, and D. Estrin, Statistical model of lossy links in wireless sensor networks, in Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN), IEEE, Piscataway, NJ, 2005, pp. 81–88. |

[26] | Y. Chang, T. Kopelowitz, S. Pettie, R. Wang, and W. Zhan, Exponential separations in the energy complexity of leader election, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 2017, ACM, New York, 2017, pp. 771–783. · Zbl 1369.68049 |

[27] | B. S. Chlebus, G. De Marco, and D. R. Kowalski, Scalable wake-up of multi-channel single-hop radio networks, Theoret. Comput. Sci., 615 (2016), pp. 23–44. · Zbl 1333.68028 |

[28] | B. S. Chlebus, L. Gasieniec, D. R. Kowalski, and T. Radzik, On the wake-up problem in radio networks, in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), Springer, Berlin, 2005, pp. 347–359. · Zbl 1082.68504 |

[29] | B. S. Chlebus and D. R. Kowalski, A better wake-up in radio networks, in Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2004, pp. 266–274. · Zbl 1321.68019 |

[30] | B. S. Chlebus and D. R. Kowalski, Randomization helps to perform independent tasks reliably, Random Structures Algorithms, 24 (2004), pp. 11–41. · Zbl 1036.68126 |

[31] | B. S. Chlebus, D. R. Kowalski, and M. A. Rokicki, Adversarial queuing on the multiple access channel, ACM Trans. Algorithms, 8 (2012), 5. · Zbl 1295.68047 |

[32] | M. Chrobak, L. Gasieniec, and D. R. Kowalski, The wake-up problem in multihop radio networks, SIAM J. Comput., 36 (2007), pp. 1453–1471. · Zbl 1124.68005 |

[33] | R. Cole, A. M. Frieze, B. M. Maggs, M. Mitzenmacher, A. W. Richa, R. K. Sitaraman, and E. Upfal, On balls and bins with deletions, in Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), Springer, Berlin, 1998, pp. 145–158. |

[34] | A. Cornejo and F. Kuhn, Deploying wireless networks with beeps, in Proceedings of the 24th International Symposium on Distributed Computing (DISC), Springer, Berlin, 2010, pp. 148–162. · Zbl 1290.68020 |

[35] | B. Costales and E. Allman, Sendmail, 3rd ed., O’Reilly, Sebastopol, CA, 2002. |

[36] | Crossbow, MICAz Wireless Measurement System. . |

[37] | G. De Marco and G. Stachowiak, Asynchronous shared channel, in Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’17, ACM, New York, 2017, pp. 391–400. · Zbl 1380.68420 |

[38] | Ericsson, Ericsson Mobility Report, (2016). |

[39] | J. T. Fineman, S. Gilbert, F. Kuhn, and C. Newport, Contention resolution on a fading channel, in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2016, pp. 155–164. · Zbl 1373.68095 |

[40] | S. Ganeriwal, C. Pöpper, S. C̆apkun, and M. B. Srivastava, Secure time synchronization in sensor networks, ACM Trans. Inform. System Security, 11 (2008), pp. 1–35. |

[41] | M. Geréb-Graus and T. Tsantilas, Efficient optical communication in parallel computers, in Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), ACM, New York, 1992, pp. 41–48. |

[42] | S. Gilbert and C. Newport, The computational power of beeps, in Proceedings of the International Symposium on Distributed Computing (DISC), Springer, Berlin, 2015, pp. 31–46. · Zbl 1394.68014 |

[43] | L. A. Goldberg and P. D. MacKenzie, Analysis of practical backoff protocols for contention resolution with multiple servers, J. Comput. System Sci., 58 (1999), pp. 232–258, . · Zbl 0938.68012 |

[44] | L. A. Goldberg, P. D. Mackenzie, M. Paterson, and A. Srinivasan, Contention resolution with constant expected delay, J. ACM, 47 (2000), pp. 1048–1096. · Zbl 1094.68518 |

[45] | J. Goodman, A. G. Greenberg, N. Madras, and P. March, Stability of binary exponential backoff, J. ACM, 35 (1988), pp. 579–602. |

[46] | Google, Google Cloud Messaging: Overview, (2014). |

[47] | A. G. Greenberg, P. Flajolet, and R. E. Ladner, Estimating the multiplicities of conflicts to speed their resolution in multiple access channels, J. ACM, 34 (1987), pp. 289–325. · Zbl 0634.94002 |

[48] | A. G. Greenberg and S. Winograd, A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels, JACM, 32 (1985), pp. 589–596. · Zbl 0628.68026 |

[49] | R. I. Greenberg and C. E. Leiserson, Randomized routing on fat-trees, in Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Angeles, 1985, pp. 241–249. |

[50] | M. M. Halldórsson and R. Wattenhofer, Wireless communication is in APX, in 36th International Colloquium on Automata, Languages and Programming (ICALP), Springer, Berlin, 2009, pp. 525–536. · Zbl 1248.68117 |

[51] | J. H\rastad, T. Leighton, and B. Rogoff, Analysis of backoff protocols for multiple access channels, SIAM J. Comput., 25 (1996), pp. 740–774. · Zbl 0857.60064 |

[52] | M. Herlihy and J. E. B. Moss, Transactional memory: Architectural support for lock-free data structures, in Proceedings of the 20th International Conference on Computer Architecture, IEEE Computer Society, Los Alamitos, CA, 1993, pp. 289–300, . |

[53] | V. Jacobson, Congestion avoidance and control, SIGCOMM Comput. Commun. Rev., 18 (1988), pp. 314–329. |

[54] | T. Jurdzinski and G. Stachowiak, The cost of synchronizing multiple-access channels, in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2015, pp. 421–430. · Zbl 1333.68279 |

[55] | Y. Li, W. Ye, and J. Heidemann, Energy and latency control in low duty cycle MAC protocols, in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), IEEE, Piscataway, NJ, 2005, pp. 676–682. |

[56] | G. D. Marco and D. R. Kowalski, Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel, SIAM J. Comput., 44 (2015), pp. 868–888. · Zbl 1326.68329 |

[57] | G. D. Marco and D. R. Kowalski, Contention resolution in a non-synchronized multiple access channel, Theoret. Comput. Sci., 689 (2017), pp. 1–13. · Zbl 1372.68026 |

[58] | IHS Markit, IoT Trend Watch 2017, (2017). |

[59] | R. M. Metcalfe and D. R. Boggs, Ethernet: Distributed packet switching for local computer networks, Commun. ACM, 19 (1976), pp. 395–404. |

[60] | M. Mitzenmacher, The power of two choices in randomized load balancing, IEEE Trans. Parallel Distrib. Syst., 12 (2001), pp. 1094–1104. |

[61] | A. Mondal and A. Kuzmanovic, Removing exponential backoff from TCP, SIGCOMM Comput. Commun. Rev., 38 (2008), pp. 17–28. |

[62] | T. Moscibroda, The worst-case capacity of wireless sensor networks, in Proceedings of the 6th International Symposium on Information Processing in Sensor Networks (IPSN), IEEE, Piscataway, NJ, 2007, pp. 1–10. |

[63] | K. Nakano and S. Olariu, Uniform leader election protocols for radio networks, IEEE Trans. Parallel Distrib. Syst., 13 (2002), pp. 516–526, . |

[64] | C. Newport, Radio network lower bounds made easy, in Proceedings of the 28th International Symposium on Distributed Computing (DISC), Springer, Berlin, 2014, pp. 258–272, . · Zbl 1373.68051 |

[65] | A. Ogierman, A. Richa, C. Scheideler, S. Schmid, and J. Zhang, Sade: competitive MAC under adversarial SINR, Distrib. Comput., 31 (2018), pp. 241–254. · Zbl 1451.68053 |

[66] | G. A. Platform, Google Documents List API Version 3.0: Implementing Exponential Backoff. , 2011. |

[67] | J. Polastre, R. Szewczyk, and D. Culler, Telos: Enabling ultra-low power wireless research, in Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks (IPSN), IEEE, Piscataway, NJ, 2005, pp. 364–369. |

[68] | P. Raghavan and E. Upfal, Stochastic contention resolution with short delays, SIAM J. Comput., 28 (1998), pp. 709–719. · Zbl 0914.68103 |

[69] | R. Rajwar and J. R. Goodman, Speculative lock elision: Enabling highly concurrent multithreaded execution, in Proccedings of the 34th Annual International Symposium on Microarchitecture, Austin, Texas, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 294–305, . |

[70] | A. Richa, C. Scheideler, S. Schmid, and J. Zhang, A jamming-resistant MAC protocol for multi-hop wireless networks, in Proceedings of the International Symposium on Distributed Computing (DISC), Springer, Berlin, 2010, pp. 179–193. · Zbl 1290.68028 |

[71] | A. Richa, C. Scheideler, S. Schmid, and J. Zhang, Competitive and fair medium access despite reactive jamming, in Proceedings of the 31st International Conference on Distributed Computing Systems (ICDCS), IEEE, Piscataway, NJ, 2011, pp. 507–516. |

[72] | A. Richa, C. Scheideler, S. Schmid, and J. Zhang, Competitive and fair throughput for co-existing networks under adversarial interference, in Proceedings of the 31st ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2012, pp. 291–300. · Zbl 1301.68045 |

[73] | A. W. Richa, M. Mitzenmacher, and R. Sitaraman, The power of two random choices: A survey of techniques and results, Comb. Optimization, 9 (2001), pp. 255–304. · Zbl 1056.68166 |

[74] | G. Rob van der Meulen, Gartner Says 8.4 Billion Connected “Things” Will Be in Use in 2017, Up 31 Percent from 2016, (2017). |

[75] | F. B. Schneider, Implementing fault-tolerant services using the state machine approach: A tutorial, ACM Comput. Surv., 22(4) (1990), pp. 299–319. |

[76] | A. W. Services, Error Retries and Exponential Backoff in AWS, , 2012. |

[77] | N.-O. Song, B.-J. Kwak, and L. E. Miller, On the stability of exponential backoff, J. Res. Natl. Inst. Standards Technol., 108 (2003), pp. 289–297. |

[78] | S. Teymori and W. Zhuang, Queue analysis for wireless packet data traffic, in International Conference on Research in Networking, Springer, Berlin, 2005, pp. 217–227. |

[79] | B. Vöcking, How asymmetry helps load balancing, J. ACM, 50 (2003), pp. 568–589. · Zbl 1325.68254 |

[80] | M. K. Weldon, The Future X Network: A Bell Labs Perspective, 1st ed., CRC Press, Boca Raton, FL, 2015. |

[81] | D. E. Willard, Log-logarithmic selection resolution protocols in a multiple access channel, SIAM J. Comput., 15 (1986), pp. 468–477. · Zbl 0612.94001 |

[82] | J. Yu and A. P. Petropulu, Study of the effect of the wireless gateway on incoming self-similar traffic, IEEE Trans. Signal Process., 54 (2006), pp. 3741–3758. · Zbl 1374.94639 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.