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 条
  • [41] Collision avoidance and resolution multiple access with transmission queues
    Rodrigo Garcés
    J.J. Garcia-Luna-Aceves
    Wireless Networks, 1999, 5 : 95 - 109
  • [42] Optimization of Collision Resolution Algorithm in Multiple Access Systems
    Gorokhov, A. A.
    Ovchinnikov, A. A.
    2018 WAVE ELECTRONICS AND ITS APPLICATION IN INFORMATION AND TELECOMMUNICATION SYSTEMS (WECONF), 2018,
  • [43] Collision avoidance and resolution multiple access with transmission queues
    Garcés, R
    Garcia-Luna-Aceves, JJ
    WIRELESS NETWORKS, 1999, 5 (02) : 95 - 109
  • [44] Collision avoidance and resolution multiple access with transmission groups
    Garces, R
    GarciaLunaAceves, JJ
    IEEE INFOCOM '97 - THE CONFERENCE ON COMPUTER COMMUNICATIONS, PROCEEDINGS, VOLS 1-3: SIXTEENTH ANNUAL JOINT CONFERENCE OF THE IEEE COMPUTER AND COMMUNICATIONS SOCIETIES - DRIVING THE INFORMATION REVOLUTION, 1997, : 134 - 142
  • [45] FS-ALOHA++, a collision resolution algorithm with QoS support for the contention channel in multiservices wireless LAN
    Vázquez-Cortizo, D
    Blondia, C
    García, J
    GLOBECOM'99: SEAMLESS INTERCONNECTION FOR UNIVERSAL SERVICES, VOL 1-5, 1999, : 2773 - 2777
  • [46] Contention resolution - A new approach to versatile subexpressions sharing in multiple constant multiplications
    Xu, Fei
    Chang, Chip-Hong
    Jong, Ching-Chuen
    IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS, 2008, 55 (02) : 559 - 571
  • [47] A COLLISION RESOLUTION PROTOCOL FOR RANDOM-ACCESS CHANNELS WITH ENERGY DETECTORS
    GEORGIADIS, L
    PAPANTONIKAZAKOS, P
    IEEE TRANSACTIONS ON COMMUNICATIONS, 1982, 30 (11) : 2413 - 2420
  • [48] NEAR OPTIMUM CONTROL OF MULTIPLE-ACCESS COLLISION CHANNELS
    PARIS, BP
    AAZHANG, B
    IEEE TRANSACTIONS ON COMMUNICATIONS, 1992, 40 (08) : 1298 - 1309
  • [49] COLLISION RESOLUTION PROTOCOL WITH SIMPLIFIED ENERGY DETECTION.
    Bose, Sanjay K.
    IETE Journal of Research, 1986, 32 (06) : 446 - 447
  • [50] Unmanned Aircraft Collision Detection and Resolution: Concept and Survey
    Albaker, B. M.
    Rahim, N. A.
    ICIEA 2010: PROCEEDINGS OF THE 5TH IEEE CONFERENCE ON INDUSTRIAL ELECTRONICS AND APPLICATIONS, VOL 1, 2010, : 267 - 272