Contention Resolution on Multiple Channels with Collision Detection

被引:7
|
作者
Fineman, Jeremy T. [1 ]
Newport, Calvin [1 ]
Wang, Tonghe [1 ]
机构
[1] Georgetown Univ, Washington, DC 20057 USA
来源
PROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'16) | 2016年
关键词
contention resolution; collision detection; symmetry breaking; ACCESS CHANNELS;
D O I
10.1145/2933057.2933110
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper, we consider the classical contention resolution problem in which an unknown subset of n possible nodes are activated and connected to a shared channel. The problem is solved in the first round that an active node transmits alone (thus breaking symmetry). Contention resolution has been an active research topic for over four decades. Accordingly, tight upper and lower bounds are known for most major model assumptions. There remains, however, an important case that is unresolved: contention resolution with multiple channels and collision detection. (Tight bounds are known for contention resolution with multiple channels, and contention resolution with collision detection, but not for the combination of both assumptions.) Recent work [14] proved the first non-trivial lower bound for randomized solutions to this problem in this setting. The optimality of this lower bound was left an open question. In this paper, we answer this open question by describing and analyzing new contention resolution algorithms that match, or come within a log log log n factor of matching, this bound for all relevant parameters. By doing so, we help advance our understanding of an important longstanding problem. Of equal importance, our solutions introduce a novel new technique in which we leverage a distributed structure we call coalescing cohorts to simulate a well-known parallel search strategy from the structured PRAM CREW model [16] in our unstructured distributed model. We conjecture that this approach is relevant to many problems in the increasingly important setting of distributed computation using multiple shared channels.
引用
收藏
页码:175 / 184
页数:10
相关论文
共 50 条
  • [31] 2-LEVEL CONTENTION RESOLUTION SCHEME FOR WDM NETWORKS WITH CONTROL CHANNELS
    KIM, DS
    UN, CK
    ELECTRONICS LETTERS, 1993, 29 (24) : 2140 - 2142
  • [32] COLLISION DETECTION AND MULTITONE TREE-SEARCH FOR MULTIPLE-ACCESS PROTOCOLS ON RADIO CHANNELS
    LO, WF
    MOUFTAH, HT
    IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 1987, 5 (06) : 1035 - 1040
  • [33] Carrier Sense Multiple Access with Collision Resolution
    Choi, Hyun-Ho
    Moon, Jung-Min
    Lee, In-Ho
    Lee, Howon
    IEEE COMMUNICATIONS LETTERS, 2013, 17 (06) : 1284 - 1287
  • [34] Collision avoidance and resolution multiple access (CARMA)
    Rodrigo Garcés
    J.J. Garcia–Luna–Aceves
    Cluster Computing, 1998, 1 (2) : 197 - 212
  • [35] Contention Resolution with Predictions
    Gilbert, Seth
    Newport, Calvin
    Vaidya, Nitin
    Weaver, Alex
    PROCEEDINGS OF THE 2021 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC '21), 2021, : 127 - 137
  • [36] A Contention/Collision Resolution Scheme for Large-Scale Sensor Networks based on IEEE 802.15.4
    Lee, Hyo-Ryun
    Jung, Kyoung-Hak
    Suh, Young-Joo
    2013 FOURTH INTERNATIONAL CONFERENCE ON THE NETWORK OF THE FUTURE (NOF), 2013,
  • [37] Fast collision detection for multiple robots
    Bordon, U
    Salonia, M
    Wörn, W
    ROBOTIK 2002, 2002, 1679 : 145 - 151
  • [38] Relax: Automatic Contention Detection and Resolution for Configuration related Performance Tuning
    Feng, Zhimin
    Li, Shanshan
    Liao, Xiangke
    Liu, Xiaodong
    Li, Yunfeng
    Zhou, Shulin
    2018 25TH ASIA-PACIFIC SOFTWARE ENGINEERING CONFERENCE (APSEC 2018), 2018, : 239 - 248
  • [39] A QoS framework for stabilized collision channels with multiuser detection
    Bruvold, K
    Mudumbai, R
    Madhow, U
    ICC 2005: IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, VOLS 1-5, 2005, : 250 - 254
  • [40] An efficient collision resolution scheme for wireless multiple access
    Chen, PN
    Wu, CS
    Ma, GK
    48TH IEEE VEHICULAR TECHNOLOGY CONFERENCE, VOLS 1-3, 1998, : 1341 - 1345