Search Results

Documents authored by Wei, Yuanhao

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.41
Brief Announcement: Survey of Persistent Memory Correctness Conditions

Authors: Naama Ben-David, Michal Friedman, and Yuanhao Wei

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

Abstract
In this brief paper, we survey existing correctness definitions for concurrent persistent programs.
Cite as

Naama Ben-David, Michal Friedman, and Yuanhao Wei. Brief Announcement: Survey of Persistent Memory Correctness Conditions. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 41:1-41:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.DISC.2022.41,
  author =	{Ben-David, Naama and Friedman, Michal and Wei, Yuanhao},
  title =	{{Brief Announcement: Survey of Persistent Memory Correctness Conditions}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{41:1--41:4},
  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.41},
  URN =		{urn:nbn:de:0030-drops-172328},
  doi =		{10.4230/LIPIcs.DISC.2022.41},
  annote =	{Keywords: Persistence, NVRAM, Correctness, Concurrency}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.12
Space and Time Bounded Multiversion Garbage Collection

Authors: Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei

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

Abstract
We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique takes only O(1) time on average to reclaim each version and maintains only a constant factor more versions than needed (plus an additive term). It is designed for multiversion schemes using version lists, which are the most common. Our approach uses two components that are of independent interest. First, we define a novel range-tracking data structure which stores a set of old versions and efficiently finds those that are no longer needed. We provide a wait-free implementation in which all operations take amortized constant time. Second, we represent version lists using a new lock-free doubly-linked list algorithm that supports efficient (amortized constant time) removals given a pointer to any node in the list. These two components naturally fit together to solve the multiversion garbage collection problem - the range-tracker identifies which versions to remove and our list algorithm can then be used to remove them from their version lists. We apply our garbage collection technique to generate end-to-end time and space bounds for the multiversioning system of Wei et al. (PPoPP 2021).
Cite as

Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei. Space and Time Bounded Multiversion Garbage Collection. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.DISC.2021.12,
  author =	{Ben-David, Naama and Blelloch, Guy E. and Fatourou, Panagiota and Ruppert, Eric and Sun, Yihan and Wei, Yuanhao},
  title =	{{Space and Time Bounded Multiversion Garbage Collection}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{12:1--12: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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.12},
  URN =		{urn:nbn:de:0030-drops-148143},
  doi =		{10.4230/LIPIcs.DISC.2021.12},
  annote =	{Keywords: Lock-free, data structures, memory management, snapshot, version lists}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.5
LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS

Authors: Guy E. Blelloch and Yuanhao Wei

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

Abstract
When designing concurrent algorithms, Load-Link/Store-Conditional (LL/SC) is a very useful primitive since it avoids ABA problems. The full semantics of LL/SC are not supported in hardware by any modern architecture, so there has been a significant amount of work on simulations of LL/SC using CAS. However, all previous algorithms that are constant time either use unbounded sequence numbers (and thus base objects of unbounded size), or require Ω(MP) space to implement M LL/SC objects for P processes. We present the first constant time implementation of LL/SC from bounded-sized CAS objects using only constant space overhead per LL/SC variable. In particular, our implementation uses Θ(M+kP²) space, where k is the number of outstanding LL operations per process, and only requires pointer-width CAS operations. In most algorithms that use LL/SC, k is a small constant which reduces our additive space overhead to Θ(P²). Our algorithm can also be extended to implement L word LL/SC objects in Θ(L) time for LL and SC, O(1) time for VL, and Θ((M+kP²)L) space. To achieve these bounds, our main technical contribution is implementing a new primitive called Single-Writer Copy which takes a pointer to a word sized memory location and atomically copies its contents into another object. The restriction is that only one process is allowed to write/copy into the destination object at a time. The ability to read from one memory location and write to another atomically, and in constant-time, is very powerful and we believe this primitive will be useful in designing other algorithms.
Cite as

Guy E. Blelloch and Yuanhao Wei. LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blelloch_et_al:LIPIcs.DISC.2020.5,
  author =	{Blelloch, Guy E. and Wei, Yuanhao},
  title =	{{LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{5:1--5:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.5},
  URN =		{urn:nbn:de:0030-drops-130831},
  doi =		{10.4230/LIPIcs.DISC.2020.5},
  annote =	{Keywords: LL/SC, Atomic Copy, CAS, Constant Time}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.51
Brief Announcement: Concurrent Fixed-Size Allocation and Free in Constant Time

Authors: Guy E. Blelloch and Yuanhao Wei

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

Abstract
We describe an algorithm for supporting allocation and free for fixed-sized blocks, for p asynchronous processors, with O(1) worst-case time per operation, Θ(p²) additive space overhead, and using only single-word read, write, and CAS. While many algorithms rely on having constant-time fixed-size allocate and free, we present the first implementation of these two operations that is constant time with reasonable space overhead.
Cite as

Guy E. Blelloch and Yuanhao Wei. Brief Announcement: Concurrent Fixed-Size Allocation and Free in Constant Time. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blelloch_et_al:LIPIcs.DISC.2020.51,
  author =	{Blelloch, Guy E. and Wei, Yuanhao},
  title =	{{Brief Announcement: Concurrent Fixed-Size Allocation and Free in Constant Time}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{51:1--51: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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.51},
  URN =		{urn:nbn:de:0030-drops-131291},
  doi =		{10.4230/LIPIcs.DISC.2020.51},
  annote =	{Keywords: malloc, free, fixed-size, concurrent, constant time}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.84
Short Proofs Are Hard to Find

Authors: Ian Mertz, Toniann Pitassi, and Yuanhao Wei

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We obtain a streamlined proof of an important result by Alekhnovich and Razborov [Michael Alekhnovich and Alexander A. Razborov, 2008], showing that it is hard to automatize both tree-like and general Resolution. Under a different assumption than [Michael Alekhnovich and Alexander A. Razborov, 2008], our simplified proof gives improved bounds: we show under ETH that these proof systems are not automatizable in time n^f(n), whenever f(n) = o(log^{1/7 - epsilon} log n) for any epsilon > 0. Previously non-automatizability was only known for f(n) = O(1). Our proof also extends fairly straightforwardly to prove similar hardness results for PCR and Res(r).
Cite as

Ian Mertz, Toniann Pitassi, and Yuanhao Wei. Short Proofs Are Hard to Find. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mertz_et_al:LIPIcs.ICALP.2019.84,
  author =	{Mertz, Ian and Pitassi, Toniann and Wei, Yuanhao},
  title =	{{Short Proofs Are Hard to Find}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{84:1--84:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.84},
  URN =		{urn:nbn:de:0030-drops-106605},
  doi =		{10.4230/LIPIcs.ICALP.2019.84},
  annote =	{Keywords: automatizability, Resolution, SAT solvers, proof complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.32
Step Optimal Implementations of Large Single-Writer Registers

Authors: Tian Ze Chen and Yuanhao Wei

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
We present two wait-free algorithms for simulating an l-bit single-writer register from k-bit single-writer registers, for any k >= 1. Our first algorithm has big-theta(l/k) step complexity for both Read and Write and uses big-theta (4^(l-k)) registers. An interesting feature of the algorithm is that Read operations do not write to shared variables. Our second algorithm has big-theta (l/k + (log n)/k) step complexity for both Read and Write, where n is the number of readers, but uses only big-theta (nl/k + n(log n)/k) registers. Combining both algorithms gives an implementation with big-theta (l/k) step complexity using big-theta (nl/k) space for any 1 <= k < l. We also prove that any implementation with big-O (l/k) step complexity for Read requires big-omega (l/k) step complexity for Write. Since reading l-bits requires at least ceiling(l/k) reads of k-bit registers, our lower bound shows that our implementation is step optimal.
Cite as

Tian Ze Chen and Yuanhao Wei. Step Optimal Implementations of Large Single-Writer Registers. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.OPODIS.2016.32,
  author =	{Chen, Tian Ze and Wei, Yuanhao},
  title =	{{Step Optimal Implementations of Large Single-Writer Registers}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.32},
  URN =		{urn:nbn:de:0030-drops-71010},
  doi =		{10.4230/LIPIcs.OPODIS.2016.32},
  annote =	{Keywords: atomic register, regular register, wait-free implementation, single writer, optimal}
}
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact