5 Search Results for "Scott, Michael L."


Document
Fast Nonblocking Persistence for Concurrent Data Structures

Authors: Wentao Cai, Haosen Wen, Vladimir Maksimovski, Mingzhe Du, Rafaello Sanna, Shreif Abdallah, and Michael L. Scott

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)


Abstract
We present a fully lock-free variant of our recent Montage system for persistent data structures. The variant, nbMontage, adds persistence to almost any nonblocking concurrent structure without introducing significant overhead or blocking of any kind. Like its predecessor, nbMontage is buffered durably linearizable: it guarantees that the state recovered in the wake of a crash will represent a consistent prefix of pre-crash execution. Unlike its predecessor, nbMontage ensures wait-free progress of the persistence frontier, thereby bounding the number of recent updates that may be lost on a crash, and allowing a thread to force an update of the frontier (i.e., to perform a sync operation) without the risk of blocking. As an extra benefit, the helping mechanism employed by our wait-free sync significantly reduces its latency. Performance results for nonblocking queues, skip lists, trees, and hash tables rival custom data structures in the literature - dramatically faster than achieved with prior general-purpose systems, and generally within 50% of equivalent non-persistent structures placed in DRAM.

Cite as

Wentao Cai, Haosen Wen, Vladimir Maksimovski, Mingzhe Du, Rafaello Sanna, Shreif Abdallah, and Michael L. Scott. Fast Nonblocking Persistence for Concurrent Data Structures. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.DISC.2021.14,
  author =	{Cai, Wentao and Wen, Haosen and Maksimovski, Vladimir and Du, Mingzhe and Sanna, Rafaello and Abdallah, Shreif and Scott, Michael L.},
  title =	{{Fast Nonblocking Persistence for Concurrent Data Structures}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.14},
  URN =		{urn:nbn:de:0030-drops-148169},
  doi =		{10.4230/LIPIcs.DISC.2021.14},
  annote =	{Keywords: Persistent Memory, Nonblocking Progress, Buffered Durable Linearizability}
}
Document
Brief Announcement
Brief Announcement: Building Fast Recoverable Persistent Data Structures with Montage

Authors: Haosen Wen, Wentao Cai, Mingzhe Du, Benjamin Valpey, and Michael L. Scott

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)


Abstract
The recent emergence of fast, dense, nonvolatile main memory suggests that certain long-lived data structures might remain in their natural, pointer-rich format across program runs and hardware reboots. Operations on such structures must be instrumented with explicit write-back and fence instructions to ensure consistency in the wake of a crash. Techniques to minimize the cost of this instrumentation are an active topic of current research. We present what we believe to be the first general-purpose approach to building buffered durably linearizable persistent data structures, and a system, Montage, to support that approach. Montage is built on top of the Ralloc nonblocking persistent allocator. It employs a slow-ticking epoch clock, and ensures that no operation appears to span an epoch boundary. If a crash occurs in epoch e, all work performed in epochs e and e-1 is lost, but all work from prior epochs is preserved. We describe the implementation of Montage, argue its correctness, and report on experiments confirming excellent performance for operations on queues, sets/mappings, and general graphs.

Cite as

Haosen Wen, Wentao Cai, Mingzhe Du, Benjamin Valpey, and Michael L. Scott. Brief Announcement: Building Fast Recoverable Persistent Data Structures with Montage. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{wen_et_al:LIPIcs.DISC.2020.52,
  author =	{Wen, Haosen and Cai, Wentao and Du, Mingzhe and Valpey, Benjamin and Scott, Michael L.},
  title =	{{Brief Announcement: Building Fast Recoverable Persistent Data Structures with Montage}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{52:1--52:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.52},
  URN =		{urn:nbn:de:0030-drops-131304},
  doi =		{10.4230/LIPIcs.DISC.2020.52},
  annote =	{Keywords: Durable linearizability, consistency, persistence, fault tolerance}
}
Document
Typically-Correct Derandomization for Small Time and Space

Authors: William M. Hoza

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
Suppose a language L can be decided by a bounded-error randomized algorithm that runs in space S and time n * poly(S). We give a randomized algorithm for L that still runs in space O(S) and time n * poly(S) that uses only O(S) random bits; our algorithm has a low failure probability on all but a negligible fraction of inputs of each length. As an immediate corollary, there is a deterministic algorithm for L that runs in space O(S) and succeeds on all but a negligible fraction of inputs of each length. We also give several other complexity-theoretic applications of our technique.

Cite as

William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{hoza:LIPIcs.CCC.2019.9,
  author =	{Hoza, William M.},
  title =	{{Typically-Correct Derandomization for Small Time and Space}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{9:1--9:39},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.9},
  URN =		{urn:nbn:de:0030-drops-108317},
  doi =		{10.4230/LIPIcs.CCC.2019.9},
  annote =	{Keywords: Derandomization, pseudorandomness, space complexity}
}
Document
Dalí: A Periodically Persistent Hash Map

Authors: Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey III, Dhruva R. Chakrabarti, and Michael L. Scott

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)


Abstract
Technology trends suggest that byte-addressable nonvolatile memory (NVM) will supplant many uses of DRAM over the coming decade, raising the prospect of inexpensive recovery from power failures and similar faults. Ensuring the consistency of persistent state remains nontrivial, however, in the presence of volatile caches; cached values can "leak" back to persistent memory in arbitrary order. To ensure consistency, existing persistent memory algorithms use expensive, explicit write-back instructions to force each value back to memory before performing a dependent write, thereby incurring significant run-time overhead. To reduce this overhead, we present a new design paradigm that we call periodic persistence. In a periodically persistent data structure, updates are made "in place," but can safely leak back to memory in any order, because only those updates that are known to be valid will be heeded during recovery. To guarantee forward progress, we periodically force a write-back of all dirty data in the cache, ensuring that all "sufficiently old" updates have indeed become persistent, at which point they become semantically visible to the recovery process. As an example of periodic persistence, we present a transactional hash map, Dalí, together with an informal proof of safety (buffered durable linearizability). Experiments with a prototype implementation suggest that periodic persistence can offer substantially better performance than either file-based or incrementally persistent (per-access write-back) alternatives.

Cite as

Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey III, Dhruva R. Chakrabarti, and Michael L. Scott. Dalí: A Periodically Persistent Hash Map. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{nawab_et_al:LIPIcs.DISC.2017.37,
  author =	{Nawab, Faisal and Izraelevitz, Joseph and Kelly, Terence and Morrey III, Charles B. and Chakrabarti, Dhruva R. and Scott, Michael L.},
  title =	{{Dal{\'\i}: A Periodically Persistent Hash Map}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.37},
  URN =		{urn:nbn:de:0030-drops-80148},
  doi =		{10.4230/LIPIcs.DISC.2017.37},
  annote =	{Keywords: data structure, nonvolatile memory, durable linearizability}
}
Document
Concurrent Computing in the Many-core Era (Dagstuhl Seminar 15021)

Authors: Michael Philippsen, Pascal Felber, Michael L. Scott, and J. Eliot B. Moss

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


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15021 "Concurrent computing in the many-core era". This seminar is a successor to Dagstuhl Seminars 08241 "Transactional memory: From implementation to application" and 12161 "Abstractions for scalable multicore computing", respectively held in June 2008 and in April 2012. The current seminar built on the previous seminars by notably (1) broadening the scope to concurrency beyond transactional memory and shared-memory multicores abstractions, (2) focusing on the new challenges and potential uses of emerging hardware support for synchronization extensions, and (3) considering the increasing complexity resulting from the explosion in heterogeneity.

Cite as

Michael Philippsen, Pascal Felber, Michael L. Scott, and J. Eliot B. Moss. Concurrent Computing in the Many-core Era (Dagstuhl Seminar 15021). In Dagstuhl Reports, Volume 5, Issue 1, pp. 1-56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@Article{philippsen_et_al:DagRep.5.1.1,
  author =	{Philippsen, Michael and Felber, Pascal and Scott, Michael L. and Moss, J. Eliot B.},
  title =	{{Concurrent Computing in the Many-core Era (Dagstuhl Seminar 15021)}},
  pages =	{1--56},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{1},
  editor =	{Philippsen, Michael and Felber, Pascal and Scott, Michael L. and Moss, J. Eliot B.},
  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.1},
  URN =		{urn:nbn:de:0030-drops-50105},
  doi =		{10.4230/DagRep.5.1.1},
  annote =	{Keywords: Multi-/many-core processors, Concurrent Programming, Synchronization, Transactional Memory, Programming Languages, Compilation}
}
  • Refine by Author
  • 4 Scott, Michael L.
  • 2 Cai, Wentao
  • 2 Du, Mingzhe
  • 2 Wen, Haosen
  • 1 Abdallah, Shreif
  • Show More...

  • Refine by Classification
  • 2 Computer systems organization → Reliability
  • 2 Computing methodologies → Concurrent algorithms
  • 2 Theory of computation → Parallel computing models
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Probabilistic computation
  • Show More...

  • Refine by Keyword
  • 1 Buffered Durable Linearizability
  • 1 Compilation
  • 1 Concurrent Programming
  • 1 Derandomization
  • 1 Durable linearizability
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2015
  • 1 2017
  • 1 2019
  • 1 2020
  • 1 2021

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