3 Search Results for "Ziccardi, Marco"

Document
DOI: 10.4230/LIPIcs.STACS.2026.6
Threshold-Driven Streaming Graph: Expansion and Rumor Spreading

Authors: Flora Angileri, Andrea Clementi, Emanuele Natale, Michele Salvi, and Isabella Ziccardi

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
A randomized distributed algorithm called RAES was introduced in [Becchetti et al., 2020] to extract a bounded-degree expander from a dense n-vertex expander graph G = (V, E). The algorithm relies on a simple threshold-based procedure. A key assumption in [Becchetti et al., 2020] is that the input graph G is static - i.e., both its vertex set V and edge set E remain unchanged throughout the process - while the analysis of raes in dynamic models is left as a major open question. In this work, we investigate the behavior of RAES under a dynamic graph model induced by a streaming node-churn process (also known as the sliding window model), where, at each discrete round, a new node joins the graph and the oldest node departs. This process yields a bounded-degree dynamic graph 𝒢 = {G_t = (V_t, E_t) : t ∈ ℕ} that captures essential characteristics of peer-to-peer networks - specifically, node churn and threshold on the number of connections each node can manage. We prove that every snapshot G_t in the dynamic graph sequence has good expansion properties with high probability. Furthermore, we leverage this property to establish a logarithmic upper bound on the completion time of the well-known PUSH and PULL rumor spreading protocols over the dynamic graph 𝒢.
Cite as

Flora Angileri, Andrea Clementi, Emanuele Natale, Michele Salvi, and Isabella Ziccardi. Threshold-Driven Streaming Graph: Expansion and Rumor Spreading. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{angileri_et_al:LIPIcs.STACS.2026.6,
  author =	{Angileri, Flora and Clementi, Andrea and Natale, Emanuele and Salvi, Michele and Ziccardi, Isabella},
  title =	{{Threshold-Driven Streaming Graph: Expansion and Rumor Spreading}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.6},
  URN =		{urn:nbn:de:0030-drops-254957},
  doi =		{10.4230/LIPIcs.STACS.2026.6},
  annote =	{Keywords: Distributed Algorithms, Randomized Algorithms, Dynamic Random Graphs, Graph Expansion, Rumor Spreading}
}
Document
DOI: 10.4230/OASIcs.WCET.2015.11
Software-enforced Interconnect Arbitration for COTS Multicores

Authors: Marco Ziccardi, Alessandro Cornaglia, Enrico Mezzetti, and Tullio Vardanega

Published in: OASIcs, Volume 47, 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)

Abstract
The advent of multicore processors complicates timing analysis owing to the need to account for the interference between cores accessing shared resources, which is not always easy to characterize in a safe and tight way. Solutions have been proposed that take two distinct but complementary directions: on the one hand, complex analysis techniques have been developed to provide safe and tight bounds to contention; on the other hand, sophisticated arbitration policies (hardware or software) have been proposed to limit or control inter-core interference. In this paper we propose a software-based TDMA-like arbitration of accesses to a shared interconnect (e.g. a bus) that prevents inter-core interference. A more flexible arbitration scheme is also proposed to reserve more bandwidth to selected cores while still avoiding contention. A proof-of-concept implementation on an AURIX TC277TU processor shows that our approach can apply to COTS processors, thus not relying on dedicated hardware arbiters, while introducing little overhead.
Cite as

Marco Ziccardi, Alessandro Cornaglia, Enrico Mezzetti, and Tullio Vardanega. Software-enforced Interconnect Arbitration for COTS Multicores. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015). Open Access Series in Informatics (OASIcs), Volume 47, pp. 11-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{ziccardi_et_al:OASIcs.WCET.2015.11,
  author =	{Ziccardi, Marco and Cornaglia, Alessandro and Mezzetti, Enrico and Vardanega, Tullio},
  title =	{{Software-enforced Interconnect Arbitration for COTS Multicores}},
  booktitle =	{15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)},
  pages =	{11--20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-95-8},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{47},
  editor =	{Cazorla, Francisco J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2015.11},
  URN =		{urn:nbn:de:0030-drops-52526},
  doi =		{10.4230/OASIcs.WCET.2015.11},
  annote =	{Keywords: Multicore, Resource Arbitration, Interference, Mixed-Criticality}
}
Document
DOI: 10.4230/LITES-v002-i001-a001
Randomized Caches Can Be Pretty Useful to Hard Real-Time Systems

Authors: Enrico Mezzetti, Marco Ziccardi, Tullio Vardanega, Jaume Abella, Eduardo Quiñones, and Francisco J. Cazorla

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

Abstract
Cache randomization per se, and its viability for probabilistic timing analysis (PTA) of critical real-time systems, are receiving increasingly close attention from the scientific community and the industrial practitioners. In fact, the very notion of introducing randomness and probabilities in time-critical systems has caused strenuous debates owing to the apparent clash that this idea has with the strictly deterministic view traditionally held for those systems. A paper recently appeared in LITES (Reineke, J. (2014). Randomized Caches Considered Harmful in Hard Real-Time Systems. LITES, 1(1), 03:1-03:13.) provides a critical analysis of the weaknesses and risks entailed in using randomized caches in hard real-time systems. In order to provide the interested reader with a fuller, balanced appreciation of the subject matter, a critical analysis of the benefits brought about by that innovation should be provided also. This short paper addresses that need by revisiting the array of issues addressed in the cited work, in the light of the latest advances to the relevant state of the art. Accordingly, we show that the potential benefits of randomized caches do offset their limitations, causing them to be - when used in conjunction with PTA - a serious competitor to conventional designs.
Cite as

Enrico Mezzetti, Marco Ziccardi, Tullio Vardanega, Jaume Abella, Eduardo Quiñones, and Francisco J. Cazorla. Randomized Caches Can Be Pretty Useful to Hard Real-Time Systems. In LITES, Volume 2, Issue 1 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 1, pp. 01:1-01:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{mezzetti_et_al:LITES-v002-i001-a001,
  author =	{Mezzetti, Enrico and Ziccardi, Marco and Vardanega, Tullio and Abella, Jaume and Qui\~{n}ones, Eduardo and Cazorla, Francisco J.},
  title =	{{Randomized Caches Can Be Pretty Useful to Hard Real-Time Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:10},
  ISSN =	{2199-2002},
  year =	{2015},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v002-i001-a001},
  URN =		{urn:nbn:de:0030-drops-192512},
  doi =		{10.4230/LITES-v002-i001-a001},
  annote =	{Keywords: Real-time systems, Probabilistic WCET, Randomized caches}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2015

  • Refine by Author
  • 2 Mezzetti, Enrico
  • 2 Vardanega, Tullio
  • 2 Ziccardi, Marco
  • 1 Abella, Jaume
  • 1 Angileri, Flora
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 OASIcs
  • 1 LITES

  • Refine by Classification
  • 1 Computer systems organization → Real-time system architecture
  • 1 Computer systems organization → Special purpose systems
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Probabilistic computation
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 Distributed Algorithms
  • 1 Dynamic Random Graphs
  • 1 Graph Expansion
  • 1 Interference
  • 1 Mixed-Criticality
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact