4 Search Results for "De Marco, Gianluca"

Document
DOI: 10.4230/LIPIcs.DISC.2022.17
Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy

Authors: Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
A shared channel, also called a multiple access channel, is among the most popular and widely studied models of communication in distributed computing. An unknown number of stations (potentially unbounded) is connected to the channel and can communicate by transmitting and listening. A message is successfully transmitted on the channel if and only if there is a unique transmitter at that time; otherwise the message collides with some other transmission and nothing is sensed by the participating stations. We consider the general framework without collision detection and in which any participating station can join the channel at any moment. The contention resolution task is to let each of the contending stations to broadcast successfully its message on the channel. In this setting we present the first algorithm which exhibits asymptotically optimal Θ(1) throughput and only an O(log k) energy cost, understood as the maximum number of transmissions performed by a single station (where k is the number of participating stations, initially unknown). We also show that such efficiency cannot be reproduced by non-adaptive algorithms, i.e., whose behavior does not depend on the channel history (for example, classic backoff protocols). Namely, we show that non-adaptive algorithms cannot simultaneously achieve throughput Ω(1/polylog(k)) and energy O((log² k)/(log log k)²).
Cite as

Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak. Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 17:1-17:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{demarco_et_al:LIPIcs.DISC.2022.17,
  author =	{De Marco, Gianluca and Kowalski, Dariusz R. and Stachowiak, Grzegorz},
  title =	{{Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.17},
  URN =		{urn:nbn:de:0030-drops-172081},
  doi =		{10.4230/LIPIcs.DISC.2022.17},
  annote =	{Keywords: Shared channel, Contention resolution, Throughput, Energy consumption, Randomized algorithms, Lower bound}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2018.44
Brief Announcement: Deterministic Contention Resolution on a Shared Channel

Authors: Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
A shared channel, also called multiple-access channel, is one of the fundamental communication models. Autonomous entities communicate over a shared medium, and one of the main challenges is how to efficiently resolve collisions occurring when more than one entity attempts to access the channel at the same time. In this work we explore the impact of asynchrony, knowledge (or linear estimate) of the number of contenders, and acknowledgments, on both latency and channel utilization for the Contention resolution problem with non-adaptive deterministic algorithms.
Cite as

Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak. Brief Announcement: Deterministic Contention Resolution on a Shared Channel. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 44:1-44:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{demarco_et_al:LIPIcs.DISC.2018.44,
  author =	{De Marco, Gianluca and Kowalski, Dariusz R. and Stachowiak, Grzegorz},
  title =	{{Brief Announcement: Deterministic Contention Resolution on a Shared Channel}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{44:1--44:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.44},
  URN =		{urn:nbn:de:0030-drops-98331},
  doi =		{10.4230/LIPIcs.DISC.2018.44},
  annote =	{Keywords: Shared channel, multiple-access channel, distributed algorithm}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.15
Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms

Authors: Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
We consider synchronous distributed systems in which processors communicate by shared read- write variables. Processors are anonymous and do not know their number n. The goal is to assign individual names by all the processors to themselves. We develop algorithms that accomplish this for each of the four cases determined by the following independent properties of the model: concurrently attempting to write distinct values into the same shared memory register either is allowed or not, and the number of shared variables either is a constant or it is unbounded. For each such a case, we give a Monte Carlo algorithm that runs in the optimum expected time and uses the expected number of O(n log n) random bits. All our algorithms produce correct output upon termination with probabilities that are 1−n^{−Ω(1)}, which is best possible when terminating almost surely and using O(n log n) random bits.
Cite as

Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo. Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 15:1-15:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chlebus_et_al:LIPIcs.OPODIS.2017.15,
  author =	{Chlebus, Bogdan S. and De Marco, Gianluca and Talo, Muhammed},
  title =	{{Anonymous  Processors with Synchronous Shared Memory:  Monte Carlo Algorithms}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.15},
  URN =		{urn:nbn:de:0030-drops-86502},
  doi =		{10.4230/LIPIcs.OPODIS.2017.15},
  annote =	{Keywords: anonymous processors, synchrony, shared memory, read-write registers, naming, Monte Carlo algorithms}
}
Document
DOI: 10.4230/LITES-v003-i001-a003
Modeling Power Consumption and Temperature in TLM Models

Authors: Matthieu Moy, Claude Helmstetter, Tayeb Bouhadiba, and Florence Maraninchi

Published in: LITES, Volume 3, Issue 1 (2016). Leibniz Transactions on Embedded Systems, Volume 3, Issue 1

Abstract
Many techniques and tools exist to estimate the power consumption and the temperature map of a chip. These tools help the hardware designers develop power efficient chips in the presence of temperature constraints. For this task, the application can be ignored or at least abstracted by some high level scenarios; at this stage, the actual embedded software is generally not available yet.However, after the hardware is defined, the embedded software can still have a significant influence on the power consumption; i.e., two implementations of the same application can consume more or less power. Moreover, the actual software power manager ensuring the temperature constraints, usually by acting dynamically on the voltage and frequency, must itself be validated. Validating such power management policy requires a model of both actuators and sensors, hence a closed-loop simulation of the functional model with a non-functional one.In this paper, we present and compare several tools to simulate the power and thermal behavior of a chip together with its functionality. We explore several levels of abstraction and study the impact on the precision of the analysis.
Cite as

Matthieu Moy, Claude Helmstetter, Tayeb Bouhadiba, and Florence Maraninchi. Modeling Power Consumption and Temperature in TLM Models. In LITES, Volume 3, Issue 1 (2016). Leibniz Transactions on Embedded Systems, Volume 3, Issue 1, pp. 03:1-03:29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{moy_et_al:LITES-v003-i001-a003,
  author =	{Moy, Matthieu and Helmstetter, Claude and Bouhadiba, Tayeb and Maraninchi, Florence},
  title =	{{Modeling Power Consumption and Temperature in TLM Models}},
  booktitle =	{LITES, Volume 3, Issue 1 (2016)},
  pages =	{03:1--03:29},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2016},
  volume =	{3},
  number =	{1},
  editor =	{Moy, Matthieu and Helmstetter, Claude and Bouhadiba, Tayeb and Maraninchi, Florence},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v003-i001-a003},
  doi =		{10.4230/LITES-v003-i001-a003},
  annote =	{Keywords: Power consumption, Temperature control, Virtual prototype, SystemC, Transactional modeling}
}
  • Refine by Author
  • 3 De Marco, Gianluca
  • 2 Kowalski, Dariusz R.
  • 2 Stachowiak, Grzegorz
  • 1 Bouhadiba, Tayeb
  • 1 Chlebus, Bogdan S.
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms
  • 1 Hardware → Chip-level power issues

  • Refine by Keyword
  • 2 Shared channel
  • 1 Contention resolution
  • 1 Energy consumption
  • 1 Lower bound
  • 1 Monte Carlo algorithms
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2018
  • 1 2016
  • 1 2022

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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact