Browsing by Author "Woelfel, Philipp"
Now showing 1 - 20 of 22
Results Per Page
Sort Options
- ItemOpen AccessAdaptive Partial Snapshots with Logarithmic Step Complexity(2021-06-06) Bashari, Benyamin; Woelfel, PhilippThe standard single-writer snapshot type allows processes to obtain a consistent snapshot of an array of n memory locations, each of which can be updated by one of n processes. In almost all algorithms, a Scan() operation returns a linearizable snapshot of the entire array. Under realistic assumptions, where hardware registers do not have the capacity to store many array entries, this inherently leads to a step complexity of Ω(n). In this paper, we consider an alternative version of the snapshot type, where a Scan() operation stores a consistent snapshot of all n memory locations, but does not return anything. Instead, a process can later observe the value of any component of that snapshot using a separate Observe() operation. This allows us to implement the type from fetch-and-increment and compare-and-swap objects, such that Scan() operations have constant step complexity and Update() and Observe() operations have step complexity O(logn).
- ItemOpen AccessAn Almost Tight Lower Bound for Abortable Leader Election(2018-07-11) Eghbali, Aryaz; Woelfel, Philipp; Woelfel, Philipp; Cockett, J. Robin B.; Hadzilacos, VassosThis thesis introduces a general definition of abortability for object types with concurrent specifications. The main result discussed here is a lower bound of Ω(log n/ log log n) remote memory references (RMR) of abortable leader election in both cache coherent (CC) and distributed shared memory (DSM) models. Hence, showing a gap in the RMR complexity of abortable and non-abortable leader election, as leader election has O(1) RMR complexity [30]. Further, a small modification to the implementation of name-consensus and compare-and-swap [33] provides abortable name-consensus and abortable compare-and-swap in the CC model, given an abortable or atomic test-and-set object.
- ItemOpen AccessAnalysis of Asynchronous and Synchronous Rumor Spreading Protocols(2016) Nazari, Yasamin; Woelfel, Philipp; Giakkoupis, GeorgeThis thesis focuses on a class of randomized broadcasting algorithms known as rumor spreading algorithms. In these algorithms, initially one node in a network has a rumor, and nodes exchange the rumor with one of their randomly chosen neighbors. In the originally proposed rumor spreading algorithms, nodes take steps in synchronous rounds. More recently, an arguably more realistic asynchronous model was proposed in which nodes take steps independently of each other. In this thesis, we first provide formal definitions for the basic concepts used in the literature. We then formally prove that several known models are equivalent. Next, we present several upper bounds on the running time of the push protocol on general graphs that improve the currently known upper bounds. Finally, we show that in the asynchronous model, the push protocol has twice the running time of the push-pull protocol on regular graphs.
- ItemOpen AccessBipartite Double-Word Compare-and-Swap(2020-11-27) Jafarigiv, Mehrdad; Woelfel, Philipp; Brown, Trevor; Reardon, JoelMulti-word compare-and-swap operations have always been in demand and have applications in several complex distributed data structures [5,10]. These operations are not offered by any modern architectures, so researchers have to implement their own versions of them using the primitives that are available in hardware. In this research, we implement a lock-free linearizable bipartite double-word compare-and-swap operation. This operation can be used on its own as a restricted version of the double-word compare-and-swap operation. However, the most significant feature of our algorithm is that our design has the potential to be expanded to implement an expected wait-free double-word compare-and-swap operation with sub-linear step complexity. To the best of our knowledge, this is the first result of this kind that achieves sub-linear step complexity.
- ItemOpen AccessBounds of Quantum Mixing Processes via Controlled Walks(2020-04-29) Li, Shang; Høyer, Peter; Woelfel, Philipp; Swishchuk, Anatoliy V.; Høyer, PeterQuantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.
- ItemOpen AccessDagger Linear Logic and Categorical Quantum Mechanics(2021-09) Srinivasan, Priyaa Varshinee; Cockett, Robin; Gour, Gilad; Woelfel, Philipp; Bauer, KristineThis thesis develops the categorical proof theory for the non-compact multiplicative dagger linear logic, and investigates its applications to Categorical Quantum Mechanics (CQM). The existing frameworks of CQM are categorical proof theories of compact dagger linear logic, and are motivated by the interpretation of quantum systems in the category of finite dimensional Hilbert spaces. This thesis describes a new non-compact framework called Mixed Unitary Categories which can accommodate infinite dimensional systems, and develops models for the framework. To this end, it builds on linearly distributive categories, and *-autonomous categories which are categorical proof theories of (non-compact) multiplicative linear logic. The proof theory of non-compact dagger linear logic is obtained from the basic setting of an LDC by adding a dagger functor satisfying appropriate coherences to give a dagger LDC. From every (isomix) dagger LDC one can extract a canonical "unitary core" which up to equivalence is the traditional CQM framework of dagger monoidal categories. This leads to the framework of Mixed Unitary Categories (MUCs): every MUC contains a (compact) unitary core which is extended by a (non-compact) isomix dagger LDC. Various models of MUCs based on Finiteness Spaces, Chu spaces, Hopf modules, etc., are developed in this thesis. This thesis also generalizes the key algebraic structures of CQM, such as observables, measurement, and complementarity, to MUC framework. Furthermore, using the MUC framework, this thesis establishes a connection between the complementary observables of quantum mechanics and the exponential modalities of linear logic.
- ItemOpen AccessDynamic Resource Allocation and Pricing: A Randomized Auction Perspective(2017) Zhang, Linquan; Li, Zongpeng; Wu, Kui; Wang, Yingxu; Woelfel, Philipp; Fapojuwo, Abraham OlatunjiAuctions are widely employed to allocate scarce resources among strategic users. Truthfulness is a desired property of auctions, for eliminating falsified bids. The celebrated VCG auction is truthful, yet it becomes computationally infeasible when the underlying winner determination problem is NP-hard. Simply substituting the optimal solutions with approximate solutions makes a VCG auction lose its truthfulness property. In this thesis, we aim to address this challenge by employing a randomized auction framework, which translates a cooperative approximation algorithm into a truthful auction. Four resource allocation problems are carefully studied. We first discuss dynamic resource provisioning in clouds through the auction of virtual machines (VMs). It generalizes the existing literature by introducing combinatorial auctions of heterogeneous VMs, and models dynamic VM provisioning. We then study electricity markets between power grids and microgrids, an emerging paradigm of electric power generation and supply. We address the economic challenges arising from such grid integration, and design a power auction that explicitly handles the Unit Commitment Problem, a key challenge in power grids. Both power markets with grid-to-microgrid and microgrid-to-grid energy sales are studied, with an auction designed for each, under the same randomized auction framework. We next study emergency demand response (EDR) in multi-tenant colocation data centers. EDR in colocation data centers is challenging, due to lack of incentives to reduce energy consumption by tenants who control their servers and are typically on fixed power contracts with the colocation. We propose a new auction mechanism using the framework to enable colocation EDR, which leverages a reverse auction to provide monetary remuneration to tenants according to their energy reduction. We further study the online electricity cost minimization problem at a colocation data center. Electricity billing faced by a data center is nowadays based on both the total volume consumed, and the peak consumption rate. This leads to an interesting new combinatorial optimization structure on the electricity cost optimization problem. Applying the randomized framework, we model and solve the problem through two approaches: the pricing approach and the auction approach.
- ItemOpen AccessAn Efficient Adaptive Partial Snapshot Implementation(2021-10-19) Bashari, Benyamin; Woelfel, Philipp; Woelfel, Philipp; Ruppert, Eric; Jacobson, MichaelIn an asynchronous shared-memory system with n processes, the single-writer snapshot type provides consistent views of an array A of n components, each of which can be updated by one of the processes. Formally, a process p can call Update(v) to write v into A[p], and call Scan() to obtain a view of A. Inherently, under realistic assumptions on the base objects’ size, the specification of this type leads to a lower bound of Ω(n) steps for method Scan(). In some cases, it suffices for a process to take a snapshot of k (1 ≤ k ≤ n) components of A, and thus, taking Ω(n) steps to obtain that snapshot is inefficient when k is small. In this thesis, we provide an implementation of the single-writer adaptive partial snapshot type, which allows a process to take a partial snapshot of k components in O(k log n) steps. We define a new version of Scan() that does not return anything and its behavior is defined in terms of another operation Observe(). An Observe(i) operation by process p returns the value that A[i] had at the point in time of p’s preceding Scan(). We implement a single-writer adaptive partial snapshot object from read-write registers, fetch-and-increment objects, and compare-and-swap objects, such that the step complexity of method Scan() is O(1) and that of methods Update() and Observe() is O(log n).
- ItemOpen AccessEfficient Algorithms for Dynamic Cloud Resource Provisioning(2018-04-20) Zhou, Ruiting; Li, Zongpeng; Woelfel, Philipp; Krishnamurthy, Diwakar; Wu, Kui; Williamson, Carey L.Cloud computing has emerged as a new computing paradigm, with data centers proliferating in today’s Internet. Cloud service providers often adopt static resource provisioning to pack cloud resources to fixed types of virtual machines (VM), failing to address user demands efficiently and precisely. In this thesis, we focus on dynamic cloud resource provisioning, which provides realtime, on-demand access to cloud resources. We propose efficient algorithms to guide resource allocation and workload dispatching in cloud systems. We first study dynamic VM provisioning via an online auction algorithm. We generalize the existing literature by introducing computing jobs with completion deadlines. A cloud user bids for future cloud resources to execute its job. Each bid specifies (a) a resource profile of tailor-made VMs, (b) a utility, reflecting the amount that the user is willing to pay for executing its job, and (c) a soft deadline, specifying the preferred finish time of the job, as well as a penalty function that characterizes the cost of violating the deadline. We propose efficient cloud job auctions that execute in an online fashion, provide truthfulness guarantee, and achieve a good competitive ratio. We then discuss cloud container services, a more recent form of cloud resource provisioning. Compared to traditional VMs, cloud containers are more flexible and lightweight. We exploit this new algorithm design space, and study dynamic cloud container provisioning. We design efficient scheduling algorithms for complex computing jobs that are running on cloud containers. Our offline and online schedulers permit partial execution, allow a job to specify its job deadline, desired cloud containers, and inter-container dependence relations, and achieve near-optimal expected objective values. We further extend our study to cloud container clusters. Enterprise users often create clusters of inter-connected containers to provision complex services. Compared to traditional cloud services, key challenges in container cluster (CC) provisioning lie in the optimal placement of containers while considering inter-container traffic in a CC. The challenge further escalates when CCs are provisioned in an online fashion upon CC request arrivals. We investigate dynamic cloud CC provisioning, and propose an online algorithm to address the above challenges. Our online algorithm achieves computational and economical efficiencies.
- ItemOpen AccessEfficient Auction Mechanisms in the NFV Market(2016) Gu, Sijia; Li, Zongpeng; Woelfel, Philipp; Krishnamurthy, DiwakarNetwork Function Virtualization (NFV) is a new paradigm for providing elastic network functions through flexible virtual network function (VNF) instances executed on industry- standard computing platforms exemplified by cloud datacenters. We design efficient auction mechanisms for two types of NFV market. First, we study the dynamic market mechanism for the transaction of VNF service chains in the NFV market, combining the techniques of primal-dual approximation algorithm de- sign with Myerson’s characterization of truthful mechanisms. Second, we consider the recent Cloud Radio Access Network (C-RAN) paradigm, a canonical use case of NFV. We study auction mechanisms for efficiently sharing C-RAN resources among mobile operators lever- aging randomized rounding, in both offline and online scenarios. The auction mechanisms we design run efficiently in polynomial time, guarantee truthfulness, and achieve near-optimal social welfare. The C-RAN online algorithm achieves a competitive ratio of (1−ε). Extensive simulation studies verify the efficacy of our auction mechanisms.
- ItemOpen AccessEfficient Bounded Timestamping from Standard Synchronization Primitives(2023) Bashari, Benyamin; Jamadi, Ali; Woelfel, PhilippBounded timestamps [9, 19 ] allow a temporal ordering of events in executions of concurrent algorithms. They are a fundamental and well studied building block used in many shared memory algorithms. A concurrent timestamp system keeps track of 𝑚 timestamps, which is usually greater or equal to the number of processes in the system, 𝑛. A process may, at any point, obtain a new timestamp, and later determine a total order of all process’s most recent timestamps. Known timestamp algorithms do not scale well in the number of processes. Getting a new timestamp takes at least a linear number of steps, and a lower bound by Israeli and Li [ 19 ] implies that each timestamp needs to be represented by at least Ω(𝑚) bits. We introduce a slightly different semantics for timestamping, where there is no fixed timestamp value associated with an event. A process can execute operation updateTS() to update its latest timestamp, associating it with the (linearization) point of that operation, and is Earlier (𝑝,𝑞) to determine the temporal order of the latest updateTS() operations executed by processes 𝑝 and 𝑞. Since no static timestamp value is returned by update TS(), the lower bound of Israeli and Li does not apply. We present efficient linearizable and wait-free implementations of these methods using a single bounded fetch-and-add object and 𝑂 (𝑛²) bounded compare-and-swap objects, which are available on standard hardware. The step complexity of each method call is constant, and base objects need only store 𝑂 (log 𝑛) bits.
- ItemOpen AccessEfficient Framework for Quantum Walks and Beyond(2015-12-22) Dohotaru, Catalin; Høyer, Peter; Krovi, Hari; Woelfel, Philipp; Jacobson, Michael J. Jr; Gour, Gilad; Høyer, PeterIn the first part of the thesis we construct a new, simple framework which amplifies to a constant the success probability of any abstract search algorithm. The total query complexity is given by the quantum hitting time of the resulting operator, which we show that it is of the same order as the quantum hitting time of the original algorithm. As a major application of our framework, we show that for any reversible walk $P$ and a single marked state, the quantum walk corresponding to $P$ can find the solution using a number of queries that is quadratically smaller than the classical hitting time of $P$. Our algorithm is more general and simpler to implement than the solution known previously in the literature (Krovi, Magniez, Ozols, and Roland, 2015), which was developed specifically for quantum walks; we also prove that, for the particular case of quantum walks, we can embed their algorithm into our framework, thus simulating it exactly. Finally, we show that we can implement amplitude amplification using our tool. In the second part of the thesis we give a new lower bound in the query model which proves that Grover's algorithm for unordered searching is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same an exact bound. We then turn our attention to non-adaptive algorithms for the same problem of searching an unordered set. In this model, we obtain a lower bound and we give an algorithm which matches the lower bound, thus showing that the lower bound is exactly optimal.
- ItemOpen AccessEfficient Shared Memory Algorithms for Bounding Space(2018-04-26) Aghazadeh, Zahra; Woelfel, Philipp; Higham, Lisa; Raynal, Michel; Yanushkevich, Svetlana; Mohassel, Payman; Li, ZongpengIt is the state of the art that computer systems use multi-core architectures. In order to exploit the benefits of parallelism, multiple processors have to cooperate and concurrently communicate by executing operations on shared objects. It is challenging in shared memory algorithms to deal with the inherent asynchrony of processes. To overcome this difficulty and to achieve high efficiency, algorithm designers often assume unbounded space. This work focuses on designing time-efficient shared memory algorithms while avoiding unbounded space. One example is that of making shared objects writable: Many standard primitives (for instance, compare-and-swap or fetch-and-add) do not provide a Write() operation that unconditionally changes the object's state to the one provided as a parameter. Adding Write() operations without sacrificing efficiency is challenging if space is limited. We provide a space-efficient solution for making synchronization primitives writable with optimal step complexity. A special case of making an object writable is to augment non-resettable objects with Reset() operations. We show how our general transformation can be improved to achieve optimal space implementations of long-lived test-and-set objects with time-efficient Reset() operations. Another example concerns the ABA problem: Even though a process retrieves the same value twice in a row from a shared object, it is still possible that the value of the object has changed multiple times. We investigate the time and space complexity of detecting ABAs in shared memory algorithms for systems with bounded base objects. To that end, we propose a new primitive called an ABA-detecting register, and we give an efficient implementation of this type using asymptotically optimal number of bounded registers. Finally we deal with a more general unbounded space problem: Many applications employ the tagging technique, where shared objects get augmented with additional values, called tags. Unbounded tags are mainly used in those applications, because bounding them is too complicated and error prone. We introduce a new primitive that provides an abstraction for avoiding unbounded tags. Also, we propose optimally time-efficient implementations of this primitive from bounded objects. In addition to straightforward applications that use tags directly, our implementations can also often be used for memory reclamation.
- ItemOpen AccessNew Techniques for Private Function Evaluation(2015-12-04) Sadeghian, SeyedSaeed; Mohassel, Payman; Safavi-Naini, Reyhaneh Alsadat; Høyer, Peter; Woelfel, Philipp; Scheidler, Renate; Butler, KevinIn this thesis, we study the problem of general-purpose private function evaluation (PFE) wherein a single party P1 holds a circuit C, while each Pi for 1<=i<=m holds a private input xi, and the goal is for a subset (or all) of the parties to learn C(x1,…,xm) but nothing else. We pursue the design of PFE with better concrete and/or asymptotic complexity for a variety of settings. We put forth a general framework for designing PFE as the first alternative general approach to universal circuits. In this framework, the task of hiding the circuit topology and securely evaluating its gates are addressed independently through two functionalities we call CTH (Circuit Topology Hiding) and PGE (Private Gate Evaluation). We instantiate our framework using the building blocks of several well-known general MPC constructions, obtaining more efficient PFE than prior work for two-party PFE, multi-party PFE and PFE for arithmetic circuits. Next, we propose the first general framework for designing actively secure PFE, not based on universal circuits. On the theoretical side, our framework yields the first actively secure PFE with linear complexity in the circuit size. On the practical side, we obtain the first actively secure PFE for arithmetic circuits with O(glogg) complexity where g is the circuit size, significantly improving over previous constructions with complexity O(g^5). Despite its inefficiency, we identify various advantages for PFE based on universal circuits. Valiant's construction (STOC 1976) yields universal circuits with the optimal asymptotic complexity, and has been employed in several recent works. But somewhat surprisingly, no implementations of the construction exist. We look back at this construction, and provide a more approachable description. This enables us to provide constant factor improvements and the first implementation. A more accurate comparison made possible through our implementation shows that the improved Valiant's UC performs better than the theoretical estimate, and in fact is almost always smaller than the UC construction of Kolesnikov and Schneider (FC 2008). We also observe, for the first time, that the same construction can be adapted to yield size-optimized universal arithmetic circuits (UAC).
- ItemOpen AccessOptimality and Fairness in Speed Scaling Systems(2017) Elahi, Bibi Maryam; Williamson, Carey; Woelfel, PhilippDynamic speed-scaling has received significant attention in the recent literature as an effective method for balancing between better performance and the associated cost of energy. In particular, the objective of minimizing the linear combination of average response time and energy consumption in single-server systems is extensively studied. Coupled speed-scaling, in which the speed is a function of the number of jobs in the system, is shown to be robust and optimal for minimizing the linear combination of average response-time and energy consumption in a single-server system. However, there are concerns that coupled speed-scaling may create or magnify unfairness. The goal of this thesis is to further investigate the tradeoffs between optimality and fairness in speed-scaling systems. We investigate the autoscaling properties of coupled speed-scaling systems under distributional assumptions about the workload and structural assumptions about the speed scaler. We observe distinct speed-scaling dynamics for PS and SRPT, which sheds light on the tradeoffs between optimality and fairness in coupled speed-scaling systems. In particular, we observe that the cost under M/GI/1 PS with coupled speed-scaling is near-optimal at high load. Furthermore, we investigate the magnitude of unfairness under SRPT. We observe that the compromise in cost optimality is small for PS in comparison to the significant performance degradation for the largest jobs under the optimal policy SRPT. We further investigate the possibility of a robust, fair, and near-optimal policy in speed-scaling systems. We show that the FSP policy is not well-defined in the coupled speed-scaling model. To facilitate the analysis of FSP and other scheduling policies on a level ground, an alternative model called decoupled speed-scaling is proposed and evaluated. With decoupled speed-scaling, FSP dominates PS, and is provably efficient. Simulation results demonstrate a notable performance advantage for FSP, compared to PS. Based on our analysis and evaluation, we conjecture that it is possible to achieve fairness, robustness, and near-optimality with decoupled speed-scaling.
- ItemOpen AccessPerformance Comparison of Randomized and Deterministic Mutual Exclusion Algorithms(2014-09-30) Kahlon, Amandeep; Woelfel, Philipp; Golab, WojciechMutual exclusion is a well known in distributed computing. Mutual exclusion comes into existence when n processes try to access the Critical Section at the same time. It prevents any two processes from accessing the Critical Section simultaneously. Mutual exclusion is a standard building block for shared memory algorithms. This thesis presents the performance comparison of various Randomized and Deterministic mutual exclusion algorithms. The performance of these algorithms is compared in the same environment and using the same platform. To perform these comparison tests, time taken by processes to execute mutual exclusion algorithms is measured in isolation, and in data structures (implemented based on mutual exclusion algorithms). Diff erent test cases have been considered to gain some insight about how diff erent algorithms behave under diff erent levels of contention. These test cases involve various combinations of insertion, deletion and look-up operations. From this comparison tests, we gain some insight about which mutual exclusion algorithms are most resilient to contention. We can use this knowledge while doing concurrent programming. We can choose our mutual exclusion locks based on insertions, deletions and look-ups in the concurrent programming.
- ItemOpen AccessQuantum walk on two-dimensional torus and grid(2018-05-28) Komeili, Mojtaba; Høyer, Peter; Woelfel, Philipp; Swishchuk, Anatoliy V.Let χ be a function that maps the vertices of a graph to zero or one. We want to find a vertex m, called a marked vertex, such that χ(m) = 1. Random walk is an algorithm for finding such a vertex. The measure of complexity for random walk is hitting time. There is a quantum algorithm that finds a marked vertex, and runs in the square root of the extended hitting time. For some configurations of marked vertices on certain graphs, the extended hitting time is asymptotically larger than the hitting time. This might cause the quantum algorithm for finding to be less efficient than a random walk. Two-dimensional torus and grid are canonical examples of such graphs. This thesis is about efficient quantum algorithms for finding a marked vertex on a two-dimensional torus. We prove the convexity of the extended hitting time, and provide a new upper bound on it. We show that, with a probability that is more than a constant, random walk on a torus is localized, and it is restricted to a sub-graph of the torus. From these observations, we introduce two algorithms that find a marked vertex on a torus. The complexity of these algorithms is in the order of the square root of the hitting time, up to logarithmic factors. They both start by finding an estimate to the hitting time. Using that, they estimate the size of a sub-graph that contains a marked vertex with more than a constant probability, and sample such a sub-graph. Our first algorithm finds a marked vertex on this sub-graph by using a quantum algorithm that runs in extended hitting time, and finds a marked vertex with probability at least a constant. Our second algorithm recursively runs the detection algorithm on cuts of the sub-graph, until reaching a constant sized sub-graph that contains a marked vertex. These algorithms are the first quantum algorithms that achieve close-to-quadratic speed-up in quantum walk on a two-dimensional torus, for all configurations of marked vertices.
- ItemOpen AccessRMR-Efficient Randomized Abortable Mutual Exclusion(2012) Pareek, Abhijeet; Woelfel, Philipp
- ItemOpen AccessSampling Using Controlled Quantum Walks(2020-10-26) Bencivenga, Dante; Høyer, Peter; Feder, David; Woelfel, PhilippWe give a new quantum algorithm to sample from probability distributions over graph vertices quadratically faster than the optimal classical algorithm, which uses random walks with stopping rules. Efficient sampling is an important computational task used in simulations based on stochastic processes. This is the first quantum algorithm that achieves a quadratic speed-up for sampling from general probability distributions over graph vertices. Our algorithm generalizes the controlled quantum walk algorithm proposed by Dohotaru and Høyer in 2015. Our main technical innovation is to allow for multiple distinct controlled reflections. This allows us to generate the quantum state analogous to the target probability distribution over vertices. This quantum state, when measured, gives a corresponding classical sample from the target distribution. We also give a second classical algorithm for sampling from probability distributions over graph vertices. This algorithm adds different self-loops to each vertex of the random walk. We show how to construct the quantum analogue of this algorithm. Finally, we show that we can embed this quantum analogue into our controlled quantum walk.
- ItemOpen AccessStrongly Linearizable Implementations of Fundamental Primitives(2019-08-20) Ovens, Sean; Woelfel, Philipp; Woelfel, Philipp; Cockett, J. Robin B.; Hendler, DannyLinearizability is the gold standard of correctness conditions for shared memory algorithms, and historically has been considered the practical equivalent of atomicity. However, it has been shown [1] that replacing atomic objects with linearizable implementations can affect the probability distribution of execution outcomes in randomized algorithms. Thus, linearizable objects are not always suitable replacements for atomic objects. A stricter correctness condition called strong linearizability has been developed and shown to be appropriate for randomized algorithms in a strong adaptive adversary model [1]. We devise several new lock-free strongly linearizable implementations from atomic registers. In particular, we give the first strongly linearizable lock-free snapshot implementation that uses bounded space. This improves on the unbounded space solution of Denysyuk and Woelfel [2]. As a building block, our algorithm uses a lock-free strongly linearizable ABA-detecting register. We obtain this object by modifying the wait-free linearizable ABA-detecting register of Aghazadeh and Woelfel [3], which, as we show, is not strongly linearizable. Aspnes and Herlihy [4] identified a wide class types that have wait-free linearizable implementations from atomic registers. These types require that any pair of operations either commute, or one overwrites the other. Aspnes and Herlihy gave a general wait-free linearizable implementation of such types, employing a wait-free linearizable snapshot object. Replacing that snapshot object with our lock-free strongly linearizable one, we prove that all types in this class have a lock-free strongly linearizable implementation from atomic registers.