License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.22
URN: urn:nbn:de:0030-drops-70916
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7091/
Go to the corresponding LIPIcs Volume Portal


De Bonis, Annalisa

Generalized Selectors and Locally Thin Families with Applications to Conflict Resolution in Multiple Access Channels Supporting Simultaneous Successful Transmissions

pdf-format:
LIPIcs-OPODIS-2016-22.pdf (0.4 MB)


Abstract

We consider the Conflict Resolution Problem in the context of a multiple-access system in which several stations can transmit their messages simultaneously to the channel. We assume that there are n stations and that at most k, k <= n, stations are active at the same time, i.e, are willing to transmit a message over the channel. If in a certain instant at most d, d <= k, active stations transmit to the channel then their messages are successfully transmitted, whereas if more than d active stations transmit simultaneously then their messages are lost. In this latter case we say that a conflict occurs. The present paper investigates non-adaptive conflict resolution algorithms working under the assumption that active stations receive a feedback from the channel that informs them on whether their messages have been successfully transmitted. If a station becomes aware that its message has been correctly sent over the channel then it becomes immediately inactive, that is, stops transmitting. The measure to optimize is the number of time slots needed to solve conflicts among all active stations. The fundamental question is how much this measure decreases with the number d of messages that can be simultaneously transmitted with success. In this paper we prove that it is possible to achieve a speedup linear in d by providing a conflict resolution algorithm that uses a 1/d ratio of the number of time slots used by the optimal conflict resolution algorithm for the particular case d = 1. Moreover, we derive a lower bound on the number of time slots needed to solve conflicts non-adaptively which is within a log(k/d) factor from the upper bound. To the aim of proving these results, we introduce a new combinatorial structure that consists in a generalization of Komlós and Greenberg codes. Constructions of these new codes are obtained via a new kind of selectors, whereas the non-existential result is implied by a non-existential result for a new generalization of the locally thin families. We believe that the combinatorial structures introduced in this paper and the related results may be of independent interest.

BibTeX - Entry

@InProceedings{debonis:LIPIcs:2017:7091,
  author =	{Annalisa De Bonis},
  title =	{{Generalized Selectors and Locally Thin Families with Applications to Conflict Resolution in Multiple Access Channels Supporting Simultaneous Successful Transmissions}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7091},
  URN =		{urn:nbn:de:0030-drops-70916},
  doi =		{10.4230/LIPIcs.OPODIS.2016.22},
  annote =	{Keywords: Multiple-Access channels, Multi Access Communication, Conflict Resolutions, New Combinatorial Structures, Selectors}
}

Keywords: Multiple-Access channels, Multi Access Communication, Conflict Resolutions, New Combinatorial Structures, Selectors
Seminar: 20th International Conference on Principles of Distributed Systems (OPODIS 2016)
Issue Date: 2017
Date of publication: 29.03.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI