4 Search Results for "Finocchi, Irene"


Document
Resilient Dictionaries for Randomly Unreliable Memory

Authors: Stefano Leucci, Chih-Hung Liu, and Simon Meierhans

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
We study the problem of designing a dictionary data structure that is resilient to memory corruptions. Our error model is a variation of the faulty RAM model in which, except for constant amount of definitely reliable memory, each memory word is randomly unreliable with a probability p < 1/2, and the locations of the unreliable words are unknown to the algorithm. An adversary observes the whole memory and can, at any time, arbitrarily corrupt (i.e., modify) the contents of one or more unreliable words. Our dictionary has capacity n, stores N<n keys in the optimal O(N) amount of space, supports insertions and deletions in O(log n) amortized time, and allows to search for a key in O(log n) worst-case time. With a global probability of at least 1-1/n, all possible search operations are guaranteed to return the correct answer w.r.t. the set of uncorrupted keys. The closest related results are the ones of Finocchi et al. [Irene Finocchi et al., 2009] and Brodal et al. [Brodal et al., 2007] on the faulty RAM model, in which all but O(1) memory is unreliable. There, if an upper bound delta on the number of corruptions is known in advance, all dictionary operations can be implemented in Theta(log n + delta) amortized time, thus trading resiliency for speed as soon as delta = omega(log n). Our construction does not need to know the value of delta in advance and remains fast and effective even when up to a constant fraction of the available memory is corrupted. Our techniques can be immediately extended to implement other data types (e.g., associative containers and priority queues), which can then be used as a building block in the design of other resilient algorithms. For example, we are able to solve the resilient sorting problem in our model using O(n log n) time.

Cite as

Stefano Leucci, Chih-Hung Liu, and Simon Meierhans. Resilient Dictionaries for Randomly Unreliable Memory. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 70:1-70:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{leucci_et_al:LIPIcs.ESA.2019.70,
  author =	{Leucci, Stefano and Liu, Chih-Hung and Meierhans, Simon},
  title =	{{Resilient Dictionaries for Randomly Unreliable Memory}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{70:1--70:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.70},
  URN =		{urn:nbn:de:0030-drops-111911},
  doi =		{10.4230/LIPIcs.ESA.2019.70},
  annote =	{Keywords: resilient dictionary, unreliable memory, faulty RAM}
}
Document
Empirical Evaluation for Graph Drawing (Dagstuhl Seminar 15052)

Authors: Ulrik Brandes, Irene Finocchi, Martin Nöllenburg, and Aaron Quigley

Published in: Dagstuhl Reports, Volume 5, Issue 1 (2015)


Abstract
This report documents the program and outcomes of Dagstuhl Seminar 15052 "Empirical Evaluation for Graph Drawing" which took place January 25-30, 2015. The goal of the seminar was to advance the state of the art in experimental evaluation within the wider field of graph drawing, both with respect to user studies and algorithmic experimentation.

Cite as

Ulrik Brandes, Irene Finocchi, Martin Nöllenburg, and Aaron Quigley. Empirical Evaluation for Graph Drawing (Dagstuhl Seminar 15052). In Dagstuhl Reports, Volume 5, Issue 1, pp. 243-258, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@Article{brandes_et_al:DagRep.5.1.243,
  author =	{Brandes, Ulrik and Finocchi, Irene and N\"{o}llenburg, Martin and Quigley, Aaron},
  title =	{{Empirical Evaluation for Graph Drawing (Dagstuhl Seminar 15052)}},
  pages =	{243--258},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{1},
  editor =	{Brandes, Ulrik and Finocchi, Irene and N\"{o}llenburg, Martin and Quigley, Aaron},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.1.243},
  URN =		{urn:nbn:de:0030-drops-50414},
  doi =		{10.4230/DagRep.5.1.243},
  annote =	{Keywords: graph drawing, experimental design, algorithm engineering, user studies, empirical evaluation, information visualization}
}
Document
Dynamic programming in faulty memory hierarchies (cache-obliviously)

Authors: Saverio Caminiti, Irene Finocchi, Emanuele G. Fusco, and Francesco Silvestri

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)


Abstract
Random access memories suffer from transient errors that lead the logical state of some bits to be read differently from how they were last written. Due to technological constraints, caches in the memory hierarchy of modern computer platforms appear to be particularly prone to bit flips. Since algorithms implicitly assume data to be stored in reliable memories, they might easily exhibit unpredictable behaviors even in the presence of a small number of faults. In this paper we investigate the design of dynamic programming algorithms in faulty memory hierarchies. Previous works on resilient algorithms considered a one-level faulty memory model and, with respect to dynamic programming, could address only problems with local dependencies. Our improvement upon these works is two-fold: (1) we significantly extend the class of problems that can be solved resiliently via dynamic programming in the presence of faults, settling challenging non-local problems such as all-pairs shortest paths and matrix multiplication; (2) we investigate the connection between resiliency and cache-efficiency, providing cache-oblivious implementations that incur an (almost) optimal number of cache misses. Our approach yields the first resilient algorithms that can tolerate faults at any level of the memory hierarchy, while maintaining cache-efficiency. All our algorithms are correct with high probability and match the running time and cache misses of their standard non-resilient counterparts while tolerating a large (polynomial) number of faults. Our results also extend to Fast Fourier Transform.

Cite as

Saverio Caminiti, Irene Finocchi, Emanuele G. Fusco, and Francesco Silvestri. Dynamic programming in faulty memory hierarchies (cache-obliviously). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 433-444, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{caminiti_et_al:LIPIcs.FSTTCS.2011.433,
  author =	{Caminiti, Saverio and Finocchi, Irene and Fusco, Emanuele G. and Silvestri, Francesco},
  title =	{{Dynamic programming in faulty memory hierarchies (cache-obliviously)}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{433--444},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.433},
  URN =		{urn:nbn:de:0030-drops-33241},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.433},
  annote =	{Keywords: Unreliable memories, fault-tolerant algorithms, dynamic programming, cache-oblivious algorithms, Gaussian elimination paradigm}
}
Document
Local dependency dynamic programming in the presence of memory faults

Authors: Saverio Caminiti, Irene Finocchi, and Emanuele G. Fusco

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


Abstract
We investigate the design of dynamic programming algorithms in unreliable memories, i.e., in the presence of faults that may arbitrarily corrupt memory locations during the algorithm execution. As a main result, we devise a general resilient framework that can be applied to all local dependency dynamic programming problems, where updates to entries in the auxiliary table are determined by the contents of neighboring cells. Consider, as an example, the computation of the edit distance between two strings of length n and m. We prove that, for any arbitrarily small constant epsilon in (0,1] and n >=m, this problem can be solved correctly with high probability in O(nm + alpha delta^{1+epsilon}) worst-case time and O(nm + n delta) space, when up to delta memory faults can be inserted by an adversary with unbounded computational power and alpha <= delta is the actual number of faults occurring during the computation. We also show that an optimal edit sequence can be constructed in additional time O(n delta + alpha delta^{1+epsilon}). It follows that our resilient algorithms match the running time and space usage of the standard non-resilient implementations while tolerating almost linearly-many faults.

Cite as

Saverio Caminiti, Irene Finocchi, and Emanuele G. Fusco. Local dependency dynamic programming in the presence of memory faults. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 45-56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{caminiti_et_al:LIPIcs.STACS.2011.45,
  author =	{Caminiti, Saverio and Finocchi, Irene and Fusco, Emanuele G.},
  title =	{{Local dependency dynamic programming in the presence of memory faults}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{45--56},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.45},
  URN =		{urn:nbn:de:0030-drops-29988},
  doi =		{10.4230/LIPIcs.STACS.2011.45},
  annote =	{Keywords: unreliable memories, fault-tolerant algorithms, local dependency dynamic programming, edit distance}
}
  • Refine by Author
  • 3 Finocchi, Irene
  • 2 Caminiti, Saverio
  • 2 Fusco, Emanuele G.
  • 1 Brandes, Ulrik
  • 1 Leucci, Stefano
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 2 fault-tolerant algorithms
  • 1 Gaussian elimination paradigm
  • 1 Unreliable memories
  • 1 algorithm engineering
  • 1 cache-oblivious algorithms
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2011
  • 1 2015
  • 1 2019

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