| | |
| | |
Stat |
Members: 3645 Articles: 2'500'096 Articles rated: 2609
18 April 2024 |
|
| | | |
|
Article overview
| |
|
Adversarial Multiple Access Channels with Individual Injection Rates | Lakshmi Anantharamu
; Bogdan S. Chlebus
; Mariusz A. Rokicki
; | Date: |
25 Sep 2013 | Abstract: | We study deterministic distributed broadcasting in synchronous
multiple-access channels. Packets are injected into n nodes by a window-type
adversary that is constrained by a window w and injection rates individually
assigned to all nodes. We investigate what queue size and packet latency can be
achieved with the maximum aggregate injection rate of one packet per round,
depending on properties of channels and algorithms. We give a non-adaptive
full-sensing algorithm for channels with collision detection and an adaptive
full-sensing algorithm for channels without collision detection that achieve
O(min(n+w,wlog n)) packet latency. We show that packet latency has to be
either Omega(wfrac{log n}{log w}), for wle n, or Omega(w), for w>n, as a
matching lower bound to these algorithms. We develop a non-adaptive
full-sensing algorithm for channels without collision detection that achieves
O(n+w) queue size and O(n w) packet latency. This is in contrast with the
adversarial model of global injection rates, in which non-adaptive full-sensing
algorithms with bounded packet latency do not exist [15]. Our algorithm avoids
collisions produced by simultaneous transmissions; we show that any algorithm
with this property must have Omega(nw) packet latency. | Source: | arXiv, 1309.6610 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |