1 Search Results for "De Bonis, Annalisa"


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

Authors: Annalisa De Bonis

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)


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.

Cite as

Annalisa De Bonis. Generalized Selectors and Locally Thin Families with Applications to Conflict Resolution in Multiple Access Channels Supporting Simultaneous Successful Transmissions. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{debonis:LIPIcs.OPODIS.2016.22,
  author =	{De Bonis, Annalisa},
  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 =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.22},
  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}
}
  • Refine by Author
  • 1 De Bonis, Annalisa

  • Refine by Classification

  • Refine by Keyword
  • 1 Conflict Resolutions
  • 1 Multi Access Communication
  • 1 Multiple-Access channels
  • 1 New Combinatorial Structures
  • 1 Selectors

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail