Document

**Published in:** LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Strong linearizability is a correctness condition conceived to address the inadequacies of linearzability when using implemented objects in randomized algorithms. Due to its newfound nature, not many strongly linearizable implementations of data structures are known. In particular, very little is known about what can be achieved in terms of strong linearizability with strong primitives that are available in modern systems, such as the compare-and-swap (CAS) operation.
This paper kick-starts the research into filling this gap. We show that Harris’s linked list and Michael and Scott’s queue, two well-known lock-free, linearizable data structures, are not strongly linearizable. In addition, we give modifications to these data structures to make them strongly linearizable while maintaining lock-freedom. The algorithms we describe are the first instances of non-trivial, strongly linearizable data structures of their type not derived by a universal construction.

Steven Munsu Hwang and Philipp Woelfel. Strongly Linearizable Linked List and Queue. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hwang_et_al:LIPIcs.OPODIS.2021.28, author = {Hwang, Steven Munsu and Woelfel, Philipp}, title = {{Strongly Linearizable Linked List and Queue}}, booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)}, pages = {28:1--28:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-219-8}, ISSN = {1868-8969}, year = {2022}, volume = {217}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.28}, URN = {urn:nbn:de:0030-drops-158030}, doi = {10.4230/LIPIcs.OPODIS.2021.28}, annote = {Keywords: Strong linearizability, compare-and-swap, linked list, queue, lock-freedom} }

Document

**Published in:** LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Many shared memory algorithms have to deal with the problem of determining whether the value of a shared object has changed in between two successive accesses of that object by a process when the responses from both are the same. Motivated by this problem, we define the signal detection problem, which can be studied on a purely combinatorial level. Consider a system with n+1 processes consisting of n readers and one signaller. The processes communicate through a shared blackboard that can store a value from a domain of size m. Processes are scheduled by an adversary. When scheduled, a process reads the blackboard, modifies its contents arbitrarily, and, provided it is a reader, returns a Boolean value. A reader must return true if the signaller has taken a step since the reader’s preceding step; otherwise it must return false.
Intuitively, in a system with n processes, signal detection should require at least n bits of shared information, i.e., m >= 2^n. But a proof of this conjecture remains elusive. We prove a lower bound of m >= n^2, as well as a tight lower bound of m >= 2^n for two restricted versions of the problem, where the processes are oblivious or where the signaller always resets the blackboard to the same fixed value. We also consider a one-shot version of the problem, where each reader takes at most two steps. In this case, we prove that it is necessary and sufficient that the blackboard can store m=n+1 values.

Faith Ellen, Rati Gelashvili, Philipp Woelfel, and Leqi Zhu. Space Lower Bounds for the Signal Detection Problem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ellen_et_al:LIPIcs.STACS.2019.26, author = {Ellen, Faith and Gelashvili, Rati and Woelfel, Philipp and Zhu, Leqi}, title = {{Space Lower Bounds for the Signal Detection Problem}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {26:1--26:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.26}, URN = {urn:nbn:de:0030-drops-102654}, doi = {10.4230/LIPIcs.STACS.2019.26}, annote = {Keywords: Signal detection, ABA problem, space complexity, lower bound} }

Document

**Published in:** LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Many fundamental problems in shared-memory distributed computing, including mutual exclusion [James E. Burns and Nancy A. Lynch, 1993], consensus [Leqi Zhu, 2016], and implementations of many sequential objects [Prasad Jayanti et al., 2000], are known to require linear space in the worst case. However, these lower bounds all work by constructing particular executions for any given algorithm that may be both very long and very improbable. The significance of these bounds is justified by an assumption that any space that is used in some execution must be allocated for all executions. This assumption is not consistent with the storage allocation mechanisms of actual practical systems.
We consider the consequences of adopting a per-execution approach to space complexity, where an object only counts toward the space complexity of an execution if it is used in that execution. This allows us to show that many known randomized algorithms for fundamental problems in shared-memory distributed computing have expected space complexity much lower than the worst-case lower bounds, and that many algorithms that are adaptive in time complexity can also be made adaptive in space complexity.
For the specific problem of mutual exclusion, we develop a new algorithm that illustrates an apparent trade-off between low expected space complexity and low expected RMR complexity. Whether this trade-off is necessary is an open problem.
For some applications, it may be helpful to pay only for objects that are updated, as opposed to those that are merely read. We give a data structure that requires no space to represent objects that are not updated at the cost of a small overhead on those that are.

James Aspnes, Bernhard Haeupler, Alexander Tong, and Philipp Woelfel. Allocate-On-Use Space Complexity of Shared-Memory Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.DISC.2018.8, author = {Aspnes, James and Haeupler, Bernhard and Tong, Alexander and Woelfel, Philipp}, title = {{Allocate-On-Use Space Complexity of Shared-Memory Algorithms}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {8:1--8:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.8}, URN = {urn:nbn:de:0030-drops-97974}, doi = {10.4230/LIPIcs.DISC.2018.8}, annote = {Keywords: Space complexity, memory allocation, mutual exclusion} }

Document

**Published in:** LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

We prove a lower bound of Omega(log n/log log n) for the remote memory reference (RMR) complexity of abortable test-and-set (leader election) in the cache-coherent (CC) and the distributed shared memory (DSM) model. This separates the complexities of abortable and non-abortable test-and-set, as the latter has constant RMR complexity [Wojciech Golab et al., 2010].
Golab, Hendler, Hadzilacos and Woelfel [Wojciech M. Golab et al., 2012] showed that compare-and-swap can be implemented from registers and test-and-set objects with constant RMR complexity. We observe that a small modification to that implementation is abortable, provided that the used test-and-set objects are atomic (or abortable). As a consequence, using existing efficient randomized wait-free implementations of test-and-set [George Giakkoupis and Philipp Woelfel, 2012], we obtain randomized abortable compare-and-swap objects with almost constant (O(log^* n)) RMR complexity.

Aryaz Eghbali and Philipp Woelfel. An Almost Tight RMR Lower Bound for Abortable Test-And-Set. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eghbali_et_al:LIPIcs.DISC.2018.21, author = {Eghbali, Aryaz and Woelfel, Philipp}, title = {{An Almost Tight RMR Lower Bound for Abortable Test-And-Set}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {21:1--21:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.21}, URN = {urn:nbn:de:0030-drops-98103}, doi = {10.4230/LIPIcs.DISC.2018.21}, annote = {Keywords: Abortability, Test-And-Set, Leader Election, Compare-and-Swap, RMR Complexity, Lower Bound} }

Document

**Published in:** LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Recently, Aspnes and Ruppert (DISC 2016) defined the following simple random experiment to determine the impact of concurrency on the performance of binary search trees: n randomly permuted keys arrive one at a time. When a new key arrives, it is first placed into a buffer of size c. Whenever the buffer is full, or when all keys have arrived, an adversary chooses one key from the buffer and inserts it into the binary search tree.
The ability of the adversary to choose the next key to insert among c buffered keys, models a distributed system, where up to c processes try to insert keys concurrently. Aspnes and Ruppert showed that the expected average depth of nodes in the resulting tree is O(log(n) + c) for a comparison-based adversary, which can only take the relative order of arrived keys into account. We generalize and strengthen this result. In particular, we allow an adversary that knows the actual values of all keys that have arrived, and show that the resulting expected average node depth is D_{avg}(n) + O(c), where D_{avg}(n) = 2ln(n) - Theta(1) is the expected average node depth of a random tree obtained in the standard unbuffered version of this experiment. Extending the bound by Aspnes and Ruppert to this stronger adversary model answers one of their open questions.

George Giakkoupis and Philipp Woelfel. An Improved Bound for Random Binary Search Trees with Concurrent Insertions. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{giakkoupis_et_al:LIPIcs.STACS.2018.37, author = {Giakkoupis, George and Woelfel, Philipp}, title = {{An Improved Bound for Random Binary Search Trees with Concurrent Insertions}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {37:1--37:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.37}, URN = {urn:nbn:de:0030-drops-85108}, doi = {10.4230/LIPIcs.STACS.2018.37}, annote = {Keywords: random binary search tree, buffer, average depth, concurrent data structures} }

Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

We consider the classical rumor spreading problem, where a piece of information must be disseminated from a single node to all n nodes of a given network. We devise two simple push-based protocols, in which nodes choose the neighbor they send the information to in each round using pairwise independent hash functions, or a pseudo-random generator, respectively. For several well-studied topologies our algorithms use exponentially fewer random bits than previous protocols. For example, in complete graphs, expanders, and random graphs only a polylogarithmic number of random bits are needed in total to spread the rumor in O(log n) rounds with high probability.
Previous explicit algorithms require Omega(n) random bits to achieve the same round complexity. For complete graphs, the amount of randomness used by our hashing-based algorithm is within an O(log n)-factor of the theoretical minimum determined by [Giakkoupis and Woelfel, 2011].

George Giakkoupis, Thomas Sauerwald, He Sun, and Philipp Woelfel. Low Randomness Rumor Spreading via Hashing. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 314-325, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{giakkoupis_et_al:LIPIcs.STACS.2012.314, author = {Giakkoupis, George and Sauerwald, Thomas and Sun, He and Woelfel, Philipp}, title = {{Low Randomness Rumor Spreading via Hashing}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {314--325}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.314}, URN = {urn:nbn:de:0030-drops-34417}, doi = {10.4230/LIPIcs.STACS.2012.314}, annote = {Keywords: Parallel and Distributed Computing, Randomness, Rumor Spreading} }

Document

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

We analyze a simple random process in which a token is moved in the
interval $A={0,dots,n$: Fix a probability distribution $mu$
over ${1,dots,n$. Initially, the token is placed in a random
position in $A$. In round $t$, a random value $d$ is chosen
according to $mu$. If the token is in position $ageq d$, then it
is moved to position $a-d$. Otherwise it stays put. Let $T$ be
the number of rounds until the token reaches position 0. We show
tight bounds for the expectation of $T$ for the optimal
distribution $mu$. More precisely, we show that
$min_mu{E_mu(T)=Thetaleft((log n)^2
ight)$. For the
proof, a novel potential function argument is introduced. The
research is motivated by the problem of approximating the minimum
of a continuous function over $[0,1]$ with a ``blind'' optimization
strategy.

Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, and Philipp Woelfel. Tight Bounds for Blind Search on the Integers. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 241-252, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{dietzfelbinger_et_al:LIPIcs.STACS.2008.1348, author = {Dietzfelbinger, Martin and Rowe, Jonathan E. and Wegener, Ingo and Woelfel, Philipp}, title = {{Tight Bounds for Blind Search on the Integers}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {241--252}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1348}, URN = {urn:nbn:de:0030-drops-13486}, doi = {10.4230/LIPIcs.STACS.2008.1348}, annote = {Keywords: } }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail