We present randomized wait-free lock implementations that are simple and time- and space-efficient. One of them uses only three shared variables and has expected step complexity O(κ log2 κ), where κ is the maximum point contention. The other ones have optimal expected step complexity O(κ), but require O(log n) space, where n is the number of processes in the system. All of our algorithms can be easily implemented on standard hardware that supports compare-and-swap and fetch-and-increment/decrement operations.

At STOC 2021, Giakkoupis, Giv, and Woelfel [10], presented an efficient randomized implementation of Double Compare-And-Swap (DCAS) from Compare-And-Swap (CAS) objects. DCAS is a useful and fundamental synchronization primitive for shared memory systems, which, contrary to CAS, is not available in hardware. The DCAS algorithm has O(log n) expected amortized step complexity against an oblivious adversary, where n is the number of processes in the system. The bottleneck of this algorithm is a building block, introduced in the same paper: A repeated choice (RC) object, which allows processes to propose values, and later agree on (and "lock in") one of the proposed values, which is roughly uniformly distributed among the "recently" proposed ones. The object can then be unlocked, and the process be repeated.

We present an efficient strongly linearizable implementation of the load-linked/store-conditional (LL/SC) primitive from compare-and-swap (CAS) objects. Our algorithm has constant step complexity, and uses a bounded number of CAS objects and registers that can each store O(log n) bits, where n is the number of processes. All previously known wait-free LL/SC algorithms are either not strongly linearizable, or they use objects of unbounded size.

Bounded timestamps [10, 20] 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 m timestamps, which is usually greater or equal to the number of processes in the system, n. 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 [20] implies that each timestamp needs to be represented by at least Ω(m) bits.

We present tradeoffs between RMR complexity and memory word size for recoverable mutual exclusion (RME) algorithms using arbitrary synchronization primitives. Assuming that each memory location stores w bits, we show that n-process mutual exclusion has an RMR complexity of at least Ω (min{logw n, log n/log log n}) on the DSM and the CC model. For w = (log n)Ω(1), our lower bound asymptotically matches an upper bound by Katzan and Morrison [19], whose RME mutual exclusion algorithm employs w-bit fetch-and-add operations. Our lower bound is the first one that does not restrict the type of atomic operations that can be executed on a memory location.

The Edsger W. Dijkstra Prize in Distributed Computing is awarded for outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributed computing have been evident for at least a decade. It is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). The prize is presented annually, with the presentation taking place alternately at PODC and DISC.

The 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).

We present a tight RMR complexity lower bound for the recoverable mutual exclusion (RME) problem, defined by Golab and Ramaraju [9]. In particular, we show that any n-process RME algorithm using only atomic read, write, fetch-and-store, fetch-and-increment, and compare-and-swap operations, has an RMR complexity of Ω(log n/log log n) on the CC and DSM model. This lower bound covers all realistic synchronization primitives that have been used in RME algorithms and matches the best upper bounds of algorithms employing swap objects (e.g.,[6,7,11]).

Double Compare-And-Swap (DCAS) is a tremendously useful synchronization primitive, which is also notoriously difficult to implement efficiently from objects that are provided by hardware. We present a randomized implementation of DCAS with O(logn) expected amortized step complexity against the oblivious adversary, where n is the number of processes in the system. This is the only algorithm to-date that achieves sub-linear step complexity. We achieve that by first implementing two novel algorithms as building blocks. One is a mechanism that allows processes to repeatedly agree on a random value among multiple proposed ones, and the other one is a restricted bipartite version of DCAS.

Abstract 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 ≥ 2n. But a proof of this conjecture remains elusive. For the general case, we prove a lower bound of m ≥ n2. For restricted versions of the problem, where the processes are oblivious or where the signaller must write a fixed sequence of values, we prove a tight lower bound of m ≥ 2n. We also consider a version of the problem where each reader takes at most two steps. In this case, we prove that m = n + 1 blackboard values are necessary and sufficient.

Motivated by advances in non-volatile memory technology, recent research in mutual exclusion has focused on algorithms for a shared memory model, in which failed processes can recover from crashes. Golab and Ramaraju [9] defined the recoverable mutual exclusion problem, where a process may crash during a mutual exclusion protocol. Upon crashing a process's local memory is erased, and it starts a recovery procedure. The contents of the shared memory survives process failures.

The notion of an anonymous shared memory, introduced by Taubenfeld in PODC 2017, considers that processes use different names for the same memory location. As an example, a location name A used by a process p and a location name B ≠ A used by another process q can correspond to the very same memory location X, and similarly for the names B used by p and A used by q which may (or may not) correspond to the same memory location Y ≠ X. In this context, the PODC paper presented a 2-process symmetric deadlock-free mutual exclusion (mutex) algorithm and a necessary condition on the size m of the anonymous memory for the existence of such an n-process algorithm. This condition states that m must be belongs to M(n) {1} where M(n)= {m: ∀ ℓ: (1) < ℓ ≤ n: gcd(ℓ,m)=1). Symmetric means here that,process identities define a specific data type which allows a process to check only if two identities are equal or not.

Linearizability 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 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[16].

Randomization has become an invaluable tool to overcome some of the problems associated with asynchrony and faultiness. Allowing processors to use random bits helps to break symmetry, and to reduce the likelihood of undesirable schedules. As a consequence, randomized techniques can lead to simpler and more efficient algorithms, and sometimes to solutions of otherwise unsolvable computational problems. However, the design and the analysis of randomized shared memory algorithms remains challenging. This talk will give an overview of recent progress towards developing a theory of randomized shared memory algorithms.

Herlihy's consensus hierarchy ranks the power of various synchronization primitives for solving consensus in a model where asynchronous processes communicate through shared memory and fail by halting. This paper revisits the consensus hierarchy in a model with crash-recovery failures, where the specification of consensus, called \emph{recoverable consensus} in this paper, is weakened by allowing non-terminating executions when a process fails infinitely often. Two variations of this model are considered: independent failures, and simultaneous (i.e., system-wide) failures. Several results are proved in this model: (i) We prove that any primitive at level two of Herlihy's hierarchy remains at level two if simultaneous crash-recovery failures are introduced. This is accomplished by transforming (one instance of) any 2-process conventional consensus algorithm to a 2-process recoverable consensus algorithm. (ii) For any $n > 1$ and $f > 0$, we show how to use $f+1$ instances of any conventional $n$-process consensus algorithm and $Θ(f + n)$ read/write registers to solve $n$-process recoverable consensus when crash-recovery failures are independent, assuming that every execution contains at most $f$ such failures. (iii) Next, we prove for any $f > 0$ that any 2-process recoverable consensus algorithm that uses TAS and read/writer registers requires at least $f+1$ TAS objects, assuming that crash-recovery failures are independent and every execution contains at most $f$ such failures. (iv) Lastly, we generalize and strengthen (iii) by proving that any universal construction of $n$-process recoverable consensus from a type $T$ with consensus number $n$ and read/write registers requires at least $f+1$ base objects of type $T$ in executions with up to $f$ failures.

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.

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.

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.

We present an abortable mutual exclusion algorithm for the cache-coherent (CC) model with atomic registers and CAS objects. The algorithm has constant expected amortized RMR complexity in the oblivious adversary model and is deterministically deadlock-free. This is the first abortable mutual exclusion algorithm that achieves o(\log n/\log\log n) RMR complexity.

Linearizability [5] of a concurrent object ensures that operations on that object appear to execute atomically. It is well known that linearizable implementations are composable: in an algorithm designed to work with atomic objects, replacing any atomic object with a linearizable implementation preserves the correctness of the original algorithm. However, replacing atomic objects with linearizable ones in a randomized algorithm can break the original probabilistic guarantees [3]. With an adaptive adversary, this problem is solved by using strongly linearizable [3] objects in the composition. How about with an oblivious adversary.

In standard randomized (push-pull) rumor spreading, nodes communicate in synchronized rounds. In each round every node contacts a random neighbor in order to exchange the rumor (i.e., either push the rumor to its neighbor or pull it from the neighbor). A natural asynchronous variant of this algorithm is one where each node has an independent Poisson clock with rate 1, and every node contacts a random neighbor whenever its clock ticks. This asynchronous variant is arguably a more realistic model in various settings, including message broadcasting in communication networks, and information dissemination in social networks. In this paper we study how asynchrony affects the rumor spreading time, that is, the time before a rumor originated at a single node spreads to all nodes in the graph. Our first result states that the asynchronous push-pull rumor spreading time is asymptotically bounded by the standard synchronous time. Precisely, we show that for any graph G on n-nodes, where the synchronous push-pull protocol informs all nodes within T(G) rounds with high probability, the asynchronous protocol needs at most time O(T(G)+log n) to inform all nodes with high probability. On the other hand, we show that the expected synchronous push-pull rumor spreading time is bounded by O(√ n) times the expected asynchronous time. These results improve upon the bounds for both directions shown recently by Acan et al. (PODC 2015). An interesting implication of our first result is that in regular graphs, the weaker push-only variant of synchronous rumor spreading has the same asymptotic performance as the synchronous push-pull algorithm.

We investigate the time and space complexity of detecting and preventing ABAs in shared memory algorithms for systems with n processes and bounded base objects. To that end, we define ABA-detecting registers, which are similar to normal read/write registers, except that they allow a process q to detect with a read operation, whether some process wrote the register since q's last read. ABA-detecting registers can be implemented trivially from a single unbounded register, but we show that they have a high complexity if base objects are bounded: An obstruction-free implementation of an ABA-detecting single bit register cannot be implemented from fewer than n-1 bounded registers. Moreover, bounded CAS objects (or more generally, conditional read-modify-write primitives) offer little help to implement ABA-detecting single bit registers: We prove a linear time-space tradeoff for such implementations. We show that the same time-space tradeoff holds for implementations of single bit LL/SC primitives from bounded writable CAS objects. This proves that the implementations of LL/SC/VL by Anderson and Moir (1995) as well as Jayanti and Petrovic (2003) are optimal. We complement our lower bounds with tight upper bounds: We give an implementation of ABA-detecting registers from n+1 bounded registers, which has step complexity O(1). We also show that (bounded) LL/SC/VL can be implemented from a single bounded CAS object and with O(n) step complexity. Both upper bounds are asymptotically optimal with respect to their time-space product.

Out-of-order execution of instructions is a common optimization technique for multicores and multiprocessors, which is governed by the memory model of the architecture. Relatively strong memory models, like TSO (supported by x86 and AMD), only allow reads to bypass earlier writes, while other models, like RMO (supported by ARM, POWER and Alpha) and PSO (supported by older SPARC), also allow the reordering of writes to different locations. These reorderings can be prevented by the use of costly fence instructions.

The test-and-set object is a fundamental synchronization primitive for shared memory systems. This paper addresses the number of registers (supporting atomic reads and writes) required to implement a one-shot test-and-set object in the standard asynchronous shared memory model with n processes. The best lower bound is log n - 1 [12,21] for obstruction-free and deadlock-free implementations, and recently a deterministic obstruction-free implementation using O(√ n) registers was presented [11].

In this paper we settle an open question by determining the remote memory reference (RMR) complexity of randomized mutual exclusion, on the distributed shared memory model (DSM) with atomic registers, in a weak but natural (and stronger than oblivious) adversary model. In particular, we present a mutual exclusion algorithm that has constant expected amortized RMR complexity and is deterministically deadlock free. Prior to this work, no randomized algorithm with o(log n/log log n) RMR complexity was known for the DSM model. Our algorithm is fairly simple, and compares favorably with one by Bender and Gilbert (FOCS 2011) for the CC model, which has expected amortized RMR complexity O(log2log n) and provides only probabilistic deadlock freedom.

In speed scaling systems, the execution speed of a processor can be adjusted dynamically under operating system control to provide tradeoffs between response time, fairness, and energy consumption. In this paper, we propose and evaluate an approach called envelope-based turbo charging, applied in conjunction with Fair Sojourn Protocol (FSP) scheduling and job-count-based speed scaling. This approach restores the strict dominance of FSP over Processor Sharing (PS) in speed scaling systems, and preserves fairness. We evaluate our new approach using analysis and simulation. The simulation results show that Turbocharged FSP (T-FSP) outperforms PS in response time, and often in energy consumption as well. Furthermore, the energy consumption of T-FSP is typically within 15% of optimal.

We devise a technique for augmenting shared objects in the standard n-process shared memory model with a linearizable Write{} operation, using bounded space and optimal worst-case step complexity. We provide a transformation of any shared object SW supporting only sequential Write{} operations into an object $W$ that supports concurrent Write{} operations. This transformation requires O(n2) SW objects and O(n2) O(log n)-bit registers, and each method (including Write{}) has, up to a constant additive term, the same time complexity as the corresponding method on object $SW$. Our implementation is deterministic, wait-free, and uses only shared registers (supporting atomic read and write operations). To the best of our knowledge, similarly efficient general constructions are not known even if stronger primitives such as CAS or LL/SC are available.

We consider Kleinberg's celebrated small world graph model [12, 13], in which a D-dimensional grid {0, …, n – 1}D is augmented with a constant number of additional unidirectional edges leaving each node. These long range edges are determined at random according to a probability distribution (the augmenting distribution), which is the same for each node. Kleinberg suggested using the inverse D-th power distribution, in which node v is the long range contact of node u with a probability proportional to ‖u – v‖1 –D. He showed that such an augmenting distribution allows to route a message efficiently in the resulting random graph: The greedy algorithm, where in each intermediate node the message travels over a link that brings the message closest to the target w.r.t. the Manhattan distance, finds a path of expected length O((logn)2) between any two nodes. In this paper we prove that greedy routing does not perform asymptotically better for any uniform and isotropic augmenting distribution, i. e., the probability that node u has a particular long range contact v is independent of the labels of u and v and only a function of ‖u – v‖ 1. In particular, we show that for such graphs the expected greedy routing time between two arbitrary nodes s and t is Ω((log ‖s – t‖1)2). This lower bound proves and strengthens a conjecture by Aspnes, Diamadi, and Shah [1]. In order to obtain the result, we introduce a novel proof technique: We define a so-called budget game, in which a token travels over a game board, from one end to the other, while the player manages a “probability budget”. In each round, the player “bets” part of her remaining probability budget on step sizes. A step size is chosen at random according to a probability distribution of the player's bet. The token then makes progress as determined by the chosen step size, while some of the player's bet is removed from her probability budget. We prove a tight lower bound for such a budget game, and then obtain a lower bound for greedy routing in the D-dimensional grid by a reduction.

This article is concerned with the problem of implementing an unbounded timestamp object from multiwriter atomic registers, in an asynchronous distributed system of n processes with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen et al. [2008] showed that √ n /2 − O (1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processes can repeatedly get timestamps). We improve this existing lower bound in two ways. First we establish a lower bound of n /6 − 1 registers for the obstruction-free long-lived timestamp problem. Previous such linear lower bounds were only known for constrained versions of the timestamp problem. This bound is asymptotically tight; Ellen et al. [2008] constructed a wait-free algorithm that uses n − 1 registers. Second we show that √2 n − log n − O (1) registers are required for any obstruction-free implementation of one-shot timestamp systems (meaning each process can get a timestamp at most once). We show that this bound is also asymptotically tight by providing a wait-free one-shot timestamp system that uses at most ⌈2√ n ⌉ registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems.

We present a new technique for reclaiming memory in concurrent shared memory algorithms with n asynchronous processes. Our methodology can be applied in the same settings as hazard pointers [10], but provides better worst-case guarantees: For the same tasks for which hazard pointers have expected constant amortized complexity, our technique guarantees constant time in the worst-case.

Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. In this paper, we consider the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We give a non-adaptive algorithm with O( log log n ) (individual) step complexity, where n is a known upper bound on contention, and an adaptive algorithm with step complexity O((log log k)2 ), where k is the actual contention in the execution. We also present a variant of the adaptive algorithm which requires O( k log log k ) total process steps. All upper bounds hold with high probability against a strong adaptive adversary.

We study the time and space complexity of randomized Test-And-Set (TAS) implementations from atomic read/write registers in asynchronous shared memory models with n processes. We present an adaptive TAS algorithm with an expected (individual) step complexity of O(log* k), for contention k, against the oblivious adversary, improving a previous (non-adaptive) upper bound of O(log log n) (Alistarh and Aspnes, 2011). We also present a modified version of the adaptive RatRace TAS algorithm (Alistarh et al., 2010), which improves the space complexity from O(n3) to O(n), while maintaining logarithmic expected step complexity against the adaptive adversary. We complement this upper bound with an Ω(log n) lower bound on the space complexity of any TAS algorithm that has the nondeterministic solo-termination property (which is a weaker progress condition than wait-freedom). No non-trivial lower bounds on the space requirements of TAS were known prior to this work.

The Cache Coherent (CC) and the Distributed Shared Memory (DSM) models are standard shared memory models, and the Remote Memory Reference (RMR) complexity is considered to accurately predict the actual performance of mutual exclusion algorithms in shared memory systems. In [12] we prove a tight lower bound for the RMR complexity of deadlock-free randomized mutual exclusion algorithms in both the CC and the DSM model with an adaptive adversary. Our lower bound establishes that an adaptive adversary can schedule n processes in such a way that each enters the critical section once, and the total number of RMRs is Ω(n log n/log log n) in expectation. This matches an upper bound of Hendler and Woelfel [14].

Herlihy and Wing [11] established that the set of possible outcomes of a shared memory distributed algorithm remains unchanged when atomic objects are replaced by their linearizable implementations. Since then, linearizability has been the correctness condition of choice for distributed algorithm designers. In 2011, however, Golab, Higham and Woelfel [9] showed that, if an algorithm employs randomization, then the probability distribution over the set of possible outcomes can differ between the atomic and implemented versions. They also proved that a stronger condition, called strong linearizability, is necessary and sufficient to guarantee the same probability distributions for these two cases when the randomized algorithm is under the control of an adaptive adversary. Therefore, we are motivated to construct strongly linearizable implementations of common distributed objects whenever possible. In this paper we prove

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].

The Cache Coherent (CC) and the Distributed Shared Memory (DSM) models are standard shared memory models, and the Remote Memory Reference (RMR) complexity is considered to accurately predict the actual performance of mutual exclusion algorithms in shared memory systems. In this paper we prove a tight lower bound for the RMR complexity of deadlock-free randomized mutual exclusion algorithms in both the CC and the DSM model with atomic registers and compare & swap objects and an adaptive adversary. Our lower bound establishes that an adaptive adversary can schedule n processes in such a way that each enters the critical section once, and the total number of RMRs is Ω(n log n/log log n) in expectation. This matches an upper bound of Hendler and Woelfel (2011).

This paper is concerned with the problem of implementing an unbounded timestamp object from multi-writer atomic registers, in an asynchronous distributed system of n processors with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen, Fatourou and Ruppert [7] showed that √n/2-O(1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processors can repeatedly get timestamps).

We investigate the randomness requirements of the classical rumor spreading problem on fully connected graphs with n vertices. In the standard random protocol, where each node that knows the rumor sends it to a randomly chosen neighbor in every round, each node needs O((log n)2) random bits in order to spread the rumor in O(log n) rounds with high probability (w.h.p.). For the simple quasirandom rumor spreading protocol proposed by Doerr, Friedrich, and Sauerwald (2008), [log n] random bits per node are sufficient. A lower bound by Doerr and Fouz (2009) shows that this is asymptotically tight for a slightly more general class of protocols, the so-called gate-model. In this paper, we consider general rumor spreading protocols. We provide a simple push-protocol that requires only a total of O(n log log n) random bits (i.e., on average O(log log n) bits per node) in order to spread the rumor in O(log n) rounds w.h.p. We also investigate the theoretical minimal randomness requirements of efficient rumor spreading. We prove the existence of a (non-uniform) push-protocol for which a total of 2 log n + log log n + o(log log n) random bits suffice to spread the rumor in log n + ln n + O(1) rounds with probability 1 − o(1). This is contrasted by a simple time-randomness tradeoff for the class of all rumor spreading protocols, according to which any protocol that uses log n − log log n − ω(1) random bits requires ω(log n) rounds to spread the rumor.

Linearizability is the gold standard among algorithm designers for deducing the correctness of a distributed algorithm using implemented shared objects from the correctness of the corresponding algorithm using atomic versions of the same objects. We show that linearizability does not suffice for this purpose when processes can exploit randomization, and we discuss the existence of alternative correctness conditions. This paper makes the following contributions: 1. Various examples demonstrate that using well-known linearizable implementations of objects (e.g., snapshots) in place of atomic objects can change the probability distribution of the outcomes that the adversary is able to generate. In some cases, an oblivious adversary can create a probability distribution of outcomes for an algorithm with implemented, linearizable objects, that not even a strong adversary can generate for the same algorithm with atomic objects. 2. A new correctness condition for shared object implementations, called strong inearizability, is defined. We prove that a strong adversary (i.e., one that sees the outcome of each coin flip immediately) gains no additional power when atomic objects are replaced by strongly linearizable implementations. In general, no strictly weaker correctness condition suffices to ensure this. We also show that strong linearizability is a local and composable property. 3. In contrast to the situation for the strong adversary, for a natural weaker adversary (one that cannot see a process' coin flip until its next operation on a shared object) we prove that there is no correspondingly general correctness condition. Specifically, any linearizable implementation of counters called terminating. from atomic registers and load-linked/store-conditional objects, that satisfies a natural locality property, necessarily gives the weak adversary more power than it has with atomic counters.

Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. A mutual exclusion algorithm is adaptive to point contention, if its RMR complexity is a function of the maximum number of processes concurrently executing their entry, critical, or exit section.

The leader election problem is a fundamental coordination problem. We present leader election algorithms for multiprocessor systems where processes communicate by reading and writing shared memory asynchronously and do not fail. In particular, we consider the cache-coherent (CC) and distributed shared memory (DSM) models of such systems. We present leader election algorithms that perform a constant number of remote memory references (RMRs) in the worst case. Our algorithms use splitter-like objects [J. Anderson and M. Moir, Sci. Comput. Programming, 25 (1995), pp. 1–39; H. Attiya and A. Fouren, Theory Comput. Syst., 31 (2001), pp. 642–664] in a novel way, by organizing active processes into teams that share work. As there is an $\Omega(\log n)$ lower bound on the RMR complexity of mutual exclusion for n processes using reads and writes only [H. Attiya, D. Hendler, and W. Woelfel, in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2008, pp. 217–226], our result separates the mutual exclusion and leader election problems in terms of RMR complexity in both the CC and DSM models. Our result also implies that any algorithm using reads, writes, and one-time test-and-set objects can be simulated by an algorithm using reads and writes with only a constant blowup of the RMR complexity; proving this is easy in the CC model but presents subtle challenges in the DSM model, as we explain later. Anderson, Herman, and Kim raise the question of whether conditional primitives such as test-and-set and compare-and-swap can be used, along with reads and writes, to solve mutual exclusion with better worst-case RMR complexity than is possible using reads and writes only [Distributed Computing, 16 (2003), pp. 75–110]. We provide a negative answer to this question in the case of implementing one-time test-and-set.

Motivated by Kleinberg's Small World Graph model and packet routing strategies in peer-to-peer networks, greedy routing algorithms on augmented networks have been investigated thoroughly. We prove tight lower bounds for one- and two-sided greedy routing on augmented rings.

Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. A recent proof [9] established an Ω(log N) lower bound on the number of RMRs incurred by processes as they enter and exit the critical section, matching an upper bound by Yang and Anderson [18]. Both these bounds apply for algorithms that only use read and write operations. The lower bound of [9] only holds for deterministic algorithms, however; the question of whether randomized mutual exclusion algorithms, using reads and writes only, can achieve sub-logarithmic expected RMR complexity remained open. This paper answers this question in the affirmative.

We consider augmented ring-based networks with vertices 0,...,n-1, where each vertex is connected to its left and right neighbor and possibly to some further vertices (called long range contacts). The outgoing edges of a vertex v are obtained by choosing a subset D of {1,2,...n-1}, with 1, n-1 in D, at random according to a probability distribution mu on all such D and then for each i in D connecting v to (v+i) mod n by a unidirectional link. The choices for different v are done independently and uniformly in the sense that the same distribution mu is used for all v. The expected number of long range contacts is l=E(|D|)-2. Motivated by Kleinberg's (2000) Small World Graph model and packet routing strategies for peer-to-peer networks, the greedy routing algorithm on augmented rings, where a packet sitting in a node v is routed to the neighbor of v closest to the destination of the package, has been investigated thoroughly, both for the "one-sided case", where packets can travel only in one direction, and the "two-sided case", where there is no such restriction. In this paper, for both the one-sided and the two-sided case and for an arbitrary distribution mu, we prove a lower bound of Omega((log n)2/l) on the expected number of hops that are needed by the greedy strategy to route a package between two randomly chosen vertices on the ring. This bound is tight for Ω(1)≤l=O(log n).

We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary and Gray representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using Gray code does so in O((log n)2) steps. A (1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O((log n)2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Ω((log n)2) holds regardless of the choice of mutation distribution. Finally, we show that it is not possible for a black box algorithms to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).

We investigate the remote memory references (RMRs) complexity of deterministic processes that communicate by reading and writing shared memory in asynchronous cache-coherent and distributed shared-memory multiprocessors.

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.

We investigate the remote memory references (RMRs) complexity of deterministic processes that communicate by reading and writing shared memory in asynchronous cache-coherent and distributed shared-memory multiprocessors. We define a class of algorithms that we call order encoding. By applying information-theoretic arguments, we prove that every order encoding algorithm, shared by n processes, has an execution that incurs Ω(n log n) RMRs. From this we derive the same lower bound for the mutual exclusion, bounded counter and store/collect synchronization problems. The bounds we obtain for these problems are tight. It follows from the results of [10] that our lower bounds hold also for algorithms that can use comparison primitives and load-linked/store-conditional in addition to reads and writes. Our mutual exclusion lower bound proves a longstanding conjecture of Anderson and Kim.

We consider asynchronous multiprocessors where processes communicate only by reading or writing shared memory. We show how to implement consensus, all comparison primitives (such as CAS and TAS), and load-linked/store-conditional using only a constant number of remote memory references (RMRs), in both the cache-coherent and the distributed-shared-memory models of such multiprocessors. Our implementations are blocking, rather than wait-free: they ensure progress provided all processes that invoke the implemented primitive are live.

It is well known that the hardest bit of integer multiplication is the middle bit, i.e., MUL n−1,n . This paper contains several new results on its complexity. First, the size s of randomized read-k branching programs, or, equivalently, their space (log s) is investigated. A randomized algorithm for MUL n−1,n with $$k = {\mathcal{O}}(\hbox{log}\, n)$$ (implying time $${\mathcal{O}}(n\, \hbox{log}\, n))$$ , space $${\mathcal{O}}(\hbox{log}\, n)$$ and error probability n −c for arbitrarily chosen constants c is presented. Second, the size of general branching programs and formulas is investigated. Applying Nechiporuk’s technique, lower bounds of $$\Omega (n^{3/2}/ \hbox{log}\, n)$$ and Ω (n 3/2), respectively, are obtained. Moreover, by bounding the number of subfunctions of MUL n−1,n , it is proven that Nechiporuk’s technique cannot provide larger lower bounds than $${\mathcal{O}}(n^{5/3}/ \hbox{log}\, n)$$ and $${\mathcal{O}}(n^{5/3})$$ , respectively.

The leader election problem is a fundamental distributed coordination problem. We present leader election algorithms for the cache-coherent (CC) and distributed shared memory (DSM) models using reads and writes only, for which the number of remote memory references (RMRs) is constant in the worst case.The algorithms use splitter-like objects [6, 8] in a novel way for the efficient partitioning of processes into disjoint sets that share work. As there is an Ω(log n/log log n) lower bound on the RMR complexity of mutual exclusion for n processes using reads and writes only [4], our result separates the mutual exclusion and leader election problems in terms of RMR complexity in both the CC and DSM models.Our result also implies that any algorithm using reads, writes and one-time test-and-set objects can be simulated by an algorithm using reads and writes with only a constant blowup of the RMR complexity. Anderson, Herman and Kim raise the question of whether conditional primitives such as test-and-set and compare-and-swap are stronger than read and write for the implementation of local-spin mutual exclusion [3]. We provide a negative answer to this question, at least for one-time test-and-set.

We describe a simple randomized construction for generating pairs of hash functions h1,h2 from a universe U to ranges V = [m] = (0,1,...,m-1) and W = [m] so that for every key set S ⊆ U with n = |S| ≤ m/(1 + ε) the (random) bipartite (multi)graph with node set V ∪ W and edge set (h1(x),h2(x))| x ∈ S exhibits a structure that is essentially random. The construction combines d-wise independent classes for d a relatively small constant with the well-known technique of random offsets. While keeping the space needed to store the description of h1 and h2 at O(nζ), for ζ < 1 fixed arbitrarily, we obtain a much smaller (constant) evaluation time than previous constructions of this kind, which involved Siegel's high-performance hash classes. The main new technique is the combined analysis of the graph structure and the inner structure of the hash functions, as well as a new way of looking at the cycle structure of random (multi)graphs. The construction may be applied to improve on Pagh and Rodler's "cuckoo hashing" (2001), to obtain a simpler and faster alternative to a recent construction of Ostlin and Pagh (2002/03) for simulating uniform hashing on a key set S, and to the simulation of shared memory on distributed memory machines. We also describe a novel way of implementing (approximate) d-wise independent hashing without using polynomials.

We prove exponential size lower bounds for nondeterministic and randomized read-k BPs as well as a time-space tradeoff lower bound for unrestricted, deterministic multi-way BPs computing the middle bit of integer multiplication. The lower bound for randomized read-k BPs is superpolynomial as long as the error probability is superpolynomially small. For polynomially small error, we have a polynomial upper bound on the size of approximating read once BPs for this function. The lower bounds follow from a more general result for the graphs of universal hash classes that is applicable to the graphs of arithmetic functions such as integer multiplication, convolution, and finite field multiplication.

Branching programs (BPs) are a well-established computation and representation model for Boolean functions. Although exponential lower bounds for restricted BPs such as read-once branching programs (BP1s) have been known for a long time, the proof of lower bounds for important selected functions is sometimes difficult. Especially the complexity of fundamental functions such as integer multiplication in different BP models is interesting. In (Bolling and Woelfel, 2001), the first strongly exponential lower bound of /spl Omega/(2/sup n/4/) has been proven for the complexity of integer multiplication in the deterministic BP1 model. Here, we consider two well-studied BP models which generalize BP1s by allowing a limited amount of nondeterminism and multiple variable tests, respectively. More precisely, we prove a lower bound of /spl Omega/(2/sup n/(7k)/) for the complexity of integer multiplication in the (V, k)-BP model. As a corollary, we obtain that integer multiplication cannot be represented in polynomial size by nondeterministic BP1s, if the number of nondeterministic nodes is bounded by log n - log log n - /spl omega/ (1). Furthermore, we show that any (1, +k)-BP representing integer multiplication has a size of /spl Omega/(2[n/48(k+1)]). This is not polynomial for k = o(n/log n).

Branching programs (BPs) are a well-established computation and representation model for Boolean functions. Especially read-once branching programs (BP1s) have been studied intensively. Exponential lower bounds on the BP1 complexity of explicit functions have been known for a long time. Nevertheless, the proof of exponential lower bounds on the read-once branching program size of selected functions is sometimes difficult. Motivated by the applications the BP1 complexity of fundamental functions is of interest. It took quite a long time until Ponzio [16, 17] was able to prove a bound of 2^{Ω(\sqrt{n})} for integer multiplication. Combining results and methods for universal hashing with lower bound techniques for BP1s a lower bound of Ω(2^{n/4}) on the size of BP1s for integer multiplication is presented in this paper.