Search Results

Documents authored by Chan, David Yu Cheng

Found 2 Possible Name Variants:

Chan, David Yu Cheng

Document
DOI: 10.4230/LIPIcs.DISC.2024.7
A Fully Concurrent Adaptive Snapshot Object for RMWable Shared-Memory

Authors: Benyamin Bashari, David Yu Cheng Chan, and Philipp Woelfel

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
An adaptive RMWable snapshot object maintains an array A[0..m-1] of m readable shared memory objects that support an arbitrary set of read-modify-write (RMW) operations, in addition to Read(). Each array entry A[i] can be accessed by any process using an operation Invoke(i,op), which simply applies a supported RMW operation op to A[i] and returns the response of op. In addition, processes can record the state of the array by calling Click(). While Click() does not return anything, a process p can call Observe(i) to determine the value of A[i] at the point of p’s latest Click(). Recently, Jayanti, Jayanti, and Jayanti [Prasad Jayanti et al., 2024] presented an RMWable adaptive snapshot object, where all operations have constant step complexity. Their algorithm is single-scanner, meaning that Click() operations cannot be executed concurrently. We present the first fully concurrent RMWable adaptive snapshot object, where all operations can be executed concurrently, assuming the the system provides atomic Fetch-And-Increment and Compare-And-Swap operations. Click() and Invoke() operations have constant step complexity, and Observe() has step complexity O(log n). The total number of base objects needed is O(mnlog n).
Cite as

Benyamin Bashari, David Yu Cheng Chan, and Philipp Woelfel. A Fully Concurrent Adaptive Snapshot Object for RMWable Shared-Memory. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bashari_et_al:LIPIcs.DISC.2024.7,
  author =	{Bashari, Benyamin and Chan, David Yu Cheng and Woelfel, Philipp},
  title =	{{A Fully Concurrent Adaptive Snapshot Object for RMWable Shared-Memory}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.7},
  URN =		{urn:nbn:de:0030-drops-212342},
  doi =		{10.4230/LIPIcs.DISC.2024.7},
  annote =	{Keywords: Shared memory, snapshot, camera object, RMW, distributed computing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.12
On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects

Authors: David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg

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

Abstract
We first prove that there are uncountably many objects with distinct computational powers. More precisely, we show that there is an uncountable set of objects such that for any two of them, at least one cannot be implemented from the other (and registers) in a wait-free manner. We then strengthen this result by showing that there are uncountably many linearizable objects with distinct computational powers. To do so, we prove that for all positive integers n and k, there is a linearizable object that is computationally equivalent to the k-set agreement task among n processes. To the best of our knowledge, these are the first linearizable objects proven to be computationally equivalent to set agreement tasks.
Cite as

David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.DISC.2017.12,
  author =	{Chan, David Yu Cheng and Hadzilacos, Vassos and Toueg, Sam},
  title =	{{On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{12:1--12:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.12},
  URN =		{urn:nbn:de:0030-drops-79973},
  doi =		{10.4230/LIPIcs.DISC.2017.12},
  annote =	{Keywords: Set Agreement, Asynchronous System, Shared Memory}
}

Yu, Changyuan

Document
DOI: 10.4230/LIPIcs.STACS.2008.1314
An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

Authors: Pinyan Lu and Changyuan Yu

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We study the scheduling problem on unrelated machines in the mechanism design setting. This problem was proposed and studied in the seminal paper (Nisan and Ronen 1999), where they gave a $1.75$-approximation randomized truthful mechanism for the case of two machines. We improve this result by a $1.6737$-approximation randomized truthful mechanism. We also generalize our result to a $0.8368m$-approximation mechanism for task scheduling with $m$ machines, which improve the previous best upper bound of $0.875m( Mu'alem and Schapira 2007)
Cite as

Pinyan Lu and Changyuan Yu. An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 527-538, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.STACS.2008.1314,
  author =	{Lu, Pinyan and Yu, Changyuan},
  title =	{{An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{527--538},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1314},
  URN =		{urn:nbn:de:0030-drops-13146},
  doi =		{10.4230/LIPIcs.STACS.2008.1314},
  annote =	{Keywords: Truthful mechanism, scheduling}
}
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 About DROPS Imprint Privacy Contact