Search Results

Documents authored by De Marco, Gianluca

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.65
Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications

Authors: Gianluca De Marco and Dariusz R. Kowalski

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
A superimposed code is a collection of binary vectors (codewords) with the property that no vector is contained in the Boolean sum of any k others, enabling unique identification of codewords within any group of k. Superimposed codes are foundational combinatorial tools with applications in areas ranging from distributed computing and data retrieval to fault-tolerant communication. However, classical superimposed codes rely on strict alignment assumptions, limiting their effectiveness in asynchronous and fault-prone environments, which are common in modern systems and applications. We introduce Ultra-Resilient Superimposed Codes (URSCs), a new class of codes that extends the classic superimposed framework by ensuring a stronger codewords' isolation property and resilience to two types of adversarial perturbations: arbitrary cyclic shifts and partial bitwise corruption (flips). Additionally, URSCs exhibit universality, adapting seamlessly to any number k of concurrent codewords without prior knowledge. This is a combination of properties not achieved in any previous construction. We provide the first polynomial-time construction of URSCs with near-optimal length, significantly outperforming previous constructions with less general features, all without requiring prior knowledge of the number of concurrent codewords, k. We demonstrate that our URSCs significantly advance the state of the art in multiple applications, including uncoordinated beeping networks, where our codes reduce time complexity for local broadcast by nearly two orders of magnitude, and generalized contention resolution in multi-access channel communication.
Cite as

Gianluca De Marco and Dariusz R. Kowalski. Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 65:1-65:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{demarco_et_al:LIPIcs.ICALP.2025.65,
  author =	{De Marco, Gianluca and Kowalski, Dariusz R.},
  title =	{{Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{65:1--65:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.65},
  URN =		{urn:nbn:de:0030-drops-234429},
  doi =		{10.4230/LIPIcs.ICALP.2025.65},
  annote =	{Keywords: superimposed codes, ultra-resiliency, deterministic algorithms, uncoordinated beeping networks, contention resolution}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact