Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao https://doi.org/10.1...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Asynchronous Shared Channel

Authors: De Marco, Gianluca; Stachowiak, Grzegorz;

Asynchronous Shared Channel

Abstract

In this work we address the question whether a simple shared channel could be efficiently utilized, that is, with a constant throughput and linear packet latency. A shared channel (also called a multiple access channel), introduced nearly 50 years ago in the context of the Ethernet [36], is among the most popular and widely studied models of communication and distributed computing. In a nutshell, a number of stations is able to communicate by transmitting and listening to a shared channel, and a message is successfully delivered to all stations if and only if its source station is the only transmitter at a time. Despite of a vast amount of work in the last decades, many fundamental questions remain open, such as: What is the impact of asynchrony on channel utilization? How important is the knowledge/estimate of the number of contenders? Could non-adaptive protocols (i.e., random codes) be asymptotically as efficient as adaptive protocols? In this work we present a broad picture of results answering the above mentioned questions for a fundamental problem of contention resolution, in which each of the contending stations needs to broadcast successfully its message. We show that adaptive algorithms or algorithms with the knowledge of contention size k (i.e., random codes with knowledge of k) achieve constant channel throughput and linear message latency even for very weak channels, i.e., with feedback restricted to simple acknowledgments and in the absence of synchronization. This asymptotically optimal performance cannot be extended to other settings --- we prove that there is no non-adaptive algorithm without the knowledge of contention size k achieving throughput \omega((\log\log k)^2/(\log k)) and/or admitting latency o(k\log k/(\log\log k)^2). This means, in particular, that coding (even random) with acknowledgments is not very efficient on a shared channel without synchronization or estimate of contention size. We also present a non-adaptive algorithm with no knowledge of contention size that almost matches these two complexities. More specifically, it achieves latency O(k\log^2 k) and channel utilization \Omega(1/\log^2 k) even if stations do not switch off after successful transmissions (and thus, could disturb other stations in succeeding), and could be improved by factor \Theta(\log\log k) if stations switch off after acknowledgment. Despite the absense of a collision detection mechanism, our algorithms are also efficient in terms of energy. The maximum number of channel accesses (including transmissions and listenings) for our non-adaptive solutions, with and without knowledge of k, is respectively O(\log k) and O(\log^2 k) whp. Regarding the adaptive algorithm, we argue that a simple modification of our protocol preserves constant throughput and linear latency while achieving O(\log k) maximum number of channel accesses per station whp.

Keywords

Contention resolution; Distributed algorithms; Lower bound; Multiple-access channel; Randomized algorithms; Shared channel; Software; Hardware and Architecture; Computer Networks and Communications

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    18
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
18
Top 10%
Top 10%
Top 10%
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!