Brief Announcement: Rumor Spreading with Bounded In-Degree

Sebastian Daum, Fabian Kuhn, Yannic Maus Dept. of Comp. Science, University of Freiburg, Freiburg, Germany daum.sebastian@gmail.com, {kuhn,yannic.maus}@cs.uni-freiburg. de

Introduction, Model & Motivation

Random gossip (push and pull) is one of the most studied protocols for disseminating information in a network, e.g., [START_REF] Demers | Epidemic algorithms for replicated database management[END_REF][START_REF] Karp | Randomized rumor spreading[END_REF]. Classically, in each time unit, every node u is allowed to contact a single random neighbor v. If u knows the data (rumor) to be disseminated, node v learns it (known as push) and if node v knows the rumor, u learns it (known as pull). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be successfully contacted by and thus interact with many neighboring nodes. As an extreme case, consider the behavior of random pull in a star network where a single center node is connected to n -1 leaf nodes. In fact, all recent papers which study the time complexity of the random push-pull protocol critically rely on the fact that a node can be contacted by many nodes in a single round, e.g., [START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF]. However, in order to obtain applicable and scalable protocols, ideally, we would like to not only limit the number of interactions each node initiates, but also the number of interactions each node participates in.

We therefore study a weaker variant of the described random pull algorithm, which we call rpull (stands for restricted pull). In each round, every node can still initiate a connection to one uniformly random neighbor. However, if a single node receives several connection requests, only one of these connections is actually established. We consider two versions of how one of these incoming requests is selected. Assume that in a given round some informed node v receives requests from a set of neighbors R v . In the adversarial rpull protocol, an (adaptive) adversary picks some node u ∈ R v which will then learn the rumor, whereas in the random rpull protocol, we assume that a uniformly random node u ∈ R v learns the rumor (chosen independently for different nodes and rounds). While the choice of which neighbor a node (actively) contacts with a request is under the control of the protocol, it is not necessarily clear how one of the incoming requests in R v is chosen, e.g., it might be determined by the underlying network infrastructure in which case the adversarial model allows to study the worst-case behavior.

Rumor Spreading with Bounded In-Degree

Contributions

Separation of Adversarial and Random Pull: For trees we can show that both forms of rpull are asymptotically as fast as pull plus an additive term in the order of the degree of the node that initially has the rumor. On general graphs we show an exponential separation between adversarial and random rpull. Theorem 1. There is a graph such that for all source nodes, the random rpull protocol informs all nodes of the network in polylogarithmic time, w.h.p., whereas the adversarial rpull algorithm requires time Ω( √ n) to even succeed with a constant probability.

Comparison of Pull and RPull: Let δ and ∆ denote the smallest and largest degrees of a given graph G. In each round of rpull, in expectation, each informed node receives at most ∆/δ requests. Hence, if an uninformed node u sends a request to an informed node, u should receive the rumor with probability at least Ω(δ/∆). Consequently, intuitively, the slowdown of using random rpull instead of the usual pull protocol should not be more than roughly O(∆/δ).

Theorem 2. For every given instance, if the pull algorithm informs all nodes in T rounds with probability p, the random rpull algorithm reaches all nodes in time O T • ∆ δ • log n with probability (1 -o(1))p. The same result holds when comparing random push-pull with random push-rpull1 .

While the statement is intuitive its proof turns out more involved. Formally, we prove a stronger statement and couple the random processes defined by pull and random rpull such that for every start configuration, w.h.p., the set of nodes informed after O ∆ δ • log n rounds of random rpull is a superset of the set of nodes informed in a single pull round. We achieve this by coupling both processes with an intermediate process which is similar to rpull but removes dependencies between nodes which request from the same neighbor. Note that there is no coupling of pull and rpull in the classical sense, i.e., a coupling which does relinquish the w.h.p. term.

Furthermore, we show that for such a round-by-round analysis, our bound is tight. That is, there are configurations where Ω ∆ δ log n random rpull rounds are needed to simulate a single pull round, w.h.p..

A full version of this paper can be found at http://arxiv.org/abs/1506.00828

By push-rpull we denote the combination of rpull with a simultaneous execution of the classic push protocol.


Alex Kogan

Yossi Lev

Brief Announcement: HTM-Assisted Combining

We present HCF, an algorithm that uses hardware transactional memory to combine operations that are conflicting with each other, while allowing other operations to run concurrently.

Introduction

Transactional lock elision (TLE) [START_REF] Rajwar | Speculative lock elision: Enabling highly concurrent multithreaded execution[END_REF] and flat combining (FC) [START_REF] Hendler | Flat combining and the synchronization-parallelism tradeoff[END_REF] were in the focus of recent work on improving concurrency in lock based programs. TLE uses hardware transactional memory (HTM) to execute a critical section speculatively using a hardware transaction while confirming that the lock associated with the critical section is not held. Thus, as long as no thread acquires the lock due to consistent failures of speculative attempts, multiple threads can run the critical section concurrently. FC, on the other hand, is effective when many threads are trying to acquire the lock ; the thread holding the lock (denoted as combiner ) helps threads that are waiting for it by executing operations on their behalf. This approach improves performance not only because of better cache locality, but also because many data structures allow optimizing a sequence of operations either by packing them together into a more compact operation, or via elimination of one operation with another. Therefore, while TLE can significantly improve performance for data structures whose operations rarely conflict with each other (e.g., a binary tree), FC is more beneficial for data structures whose operations are inherently conflicting (e.g., a stack or a queue).

In our work we explore how to combine these two techniques and provide a "best of both words" solution. A trivial solution can use the original FC algorithm if and when threads that use TLE fail to the lock; unfortunately, as we demonstrate, this approach is rarely helpful because it still prevents other threads, that are not waiting for the lock, to execute the critical section. We therefore introduce the HTM-assisted Combining Framework (HCF), that enables multiple (combiner and non-combiner) threads to access the data structure concurrently using HTM. Our algorithm allows multiple threads to act concurrently as combiners for different kinds of operations, and hence is well suited for data structures with operations of different nature. For example, with a double ended queue (deque), we expect operations on one end of the queue to conflict with each other, while operations on opposite ends of the queue are unlikely to conflict. Another example is a priority queue, where we expect all RemoveMin operations to conflict with each other, while Insert operations can still run in parallel with all other operations. With HCF, we can associate the operations on each end of the deque with a different combiner, and with the priority queue, use TLE for Insert operations while concurrently combining RemoveMin operations. Importantly, due to the use of HTM, this is achieved using a simple sequential implementation of the data structure protected by a global lock, without the need to reason about fine-grained synchronization. In particular, the choice of how many combiners to use and which operations to combine can only affect performance, not correctness.

Overview of the HCF Algorithm

With HCF, each operation Op is associated with a publication array, PA(Op), that has at most one thread executing as a combiner for the operations held in PA(Op). Using multiple publication arrays allows concurrent execution of operations that are unlikely to conflict with each other, even if some of them are executed by combiner threads. A thread T executes Op in one of four phases that it attempts one after another until Op is completed. The first OwnerPreAnnounce phase simply tries to execute Op using a hardware transaction (TX). If failed (perhaps multiple times), the second OwnerPostAnnounce phase keeps trying to execute Op using a TX, but only after announcing it in PA(Op), and only as long as the operation is not being helped by a combiner thread. If T does not complete Op in the OwnerPostAnnounce phase, it continues to the CombinerHTM phase, where it becomes a combiner, and tries to execute a subset of operations in PA(Op) (including Op) using one or more TXs. Finally, if all three phases fail to execute Op, T acquires the datastructure lock at the CombinerLock phase, and applies the subset of operations left while holding the lock. The last two phases allow any data-structure specific combining and elimination techniques that can reduce the contention on the main data structure, and help executing operations faster. Critically, like with TLE, any TX run by HCF respects the data structure's lock, testing that it is not held and aborting otherwise.

Performance Overview

We denote by HCF<X,Y,Z> a variant of the HCF framework that executes up to X,Y and Z HTM trials in the OwnerPreAnnounce, OwnerPostAnnounce and CombinerHTM phases, respectively. We note that HCF<0,0,0> that helps all operations in the publication array is equivalent to the original FC algorithm [START_REF] Hendler | Flat combining and the synchronization-parallelism tradeoff[END_REF], and HCF<X,0,0> that helps only the combiner's own operation is equivalent to the TLE algorithm [START_REF] Rajwar | Speculative lock elision: Enabling highly concurrent multithreaded execution[END_REF].

We evaluated a priority queue data structure, implemented as a skip-list, so we can efficiently combine N RemoveMin operations by chopping off the first N elements in the list. Using the HCF framework, we let RemoveMin and Insert operations to use separate publication arrays. For RemoveMin operations, we used a HCF<0,0,10> variant, as we expect them all to conflict with each other, and they can be efficiently combined. For Insert, we experimented with either TLE (HCF<10,0,0>), HCF<5,0,5>, or HCF<2,3,5> variants.

Throughput results are presented in Figure 1. As expected, when running only RemoveMin operations, our HCF algorithm achieves results that are competitive with those of FC. TLE, on the other hand, performs poorly as all the operations conflict with each other. Even the simple TLE+FC solution, that uses the FC algorithm when TLE fails to the lock, does not provide any benefit. On the other hand, when running only Insert operations, FC performs poorly while TLE is doing pretty well, but is still outperformed by our HCF variants. This is because with HCF, conflicting operations serialize among themselves at the CombinerHTM phase, but can run concurrently with other non-conflicting operations. The biggest advantage of HCF, however, is evident in the 50%-50% operation mix experiment, where the variants that use two different configurations of HCF for Insert and RemoveMin outperforms all other mechanisms (including the simple TLE+FC variant) by a large margin. This demonstrates one of the most important benefits of our algorithm: the ability to easily apply different combining policies in parallel for different operations executed on the same data structure.

Fig. 1 :

 1 Fig. 1: Skip-lists-based priority queue throughput results. Experiments were done on an Intel Haswell (Core i7-4770) 4-core hyper-threaded machine running at 3.40GHz and powered by Oracle Linux 7.


Leqi Zhu
email: lezhu@cs.toronto.edu

Brief Announcement: Tight Space Bounds for Memoryless Anonymous Consensus

Introduction. Tight Θ(n 2 ) bounds are known for the total step complexity of randomized algorithms for n-process consensus from registers [START_REF] Attiya | Tight bounds for asynchronous randomized consensus[END_REF]. However, there is a large gap between the best known space lower bound of Ω( √ n) registers [START_REF] Fich | On the space complexity of randomized synchronization[END_REF] and the Θ(n) space complexity of the best existing algorithms. We prove matching upper and lower bounds of n for the space complexity of nondeterministic solo-terminating consensus in a restricted computational model. Specifically, we consider an asynchronous system with n anonymous processes, which communicate through an m-component multi-writer snapshot. Each process alternately performs SCAN and UPDATE. The location and value of each UPDATE can depend only on the result of the preceding SCAN by the same process. The only exception is the first UPDATE by each process, which can also depend on its input. We call algorithms designed for this model memoryless.

Lower Bound. Let C be any configuration of an n-process memoryless anonymous consensus algorithm. A process is free in C if it has already taken at least one step and is poised to perform a SCAN in C. Since processes are anonymous and memoryless, an adversary can cause any two free processes in C to behave identically if they both see the same result on their next SCAN. We say C is solo v-deciding for free processes if there is a solo execution by a free process starting from C that decides v. We say C is (P, q)-bivalent if P is a set of processes covering distinct components and q / ∈ P is a process covering a component such that Cβ P is solo v-deciding for free processes and Cβ q is solo v-deciding for free processes, for some v ∈ {0, 1}, where β q is an UPDATE by q and β P consists of one UPDATE by each process in P .

Given a (Z ∪{p}, q)-bivalent configuration C, consider the longest prefix α of q's solo terminating execution α from C such that Cα β Z∪{p} is solo v-deciding for free processes. The next step δ by q in α after α must be an UPDATE to a component not covered by Z ∪ {p}. Running p from Cα β P until it is about to perform an UPDATE yields a ({p}, q)-bivalent configuration C . Since C is also ({q}, p)-bivalent, the same argument implies that there is an execution from C in which q takes at least two steps, such that the resulting configuration C is ({q}, p)-bivalent and every process in Z is free. Note that at least |Z|+2 different components were updated in the execution from C to C (via δ and β Z∪{p} ).

I would like to thank my advisor, Dr. Faith Ellen, and David Solymosi. This work was supported by the Natural Sciences and Engineering Council of Canada.

We show that, if C is ({p}, q)-bivalent and Z is a set of free processes in C, there is an execution γ from C in which p and q take at least two steps, such that Cγ is (Z ∪{p}, q)-bivalent. The proof is by induction on |Z|. The base case, when Z = ∅, holds by the previous paragraph. Fix any Z ⊂ Z with |Z | = |Z| -1. By induction, there is an execution γ 1 in which p and q take at least two steps, such that Cγ 1 is (Z ∪ {p}, q)-bivalent. By the preceding paragraph, there is an execution γ 2 from Cγ 1 in which at least |Z | + 2 components have been updated and p and q have taken at least 2 steps, such that Cγ 1 γ 2 is ({p}, q)-bivalent and each process in Z is free in Cγ 1 γ 2 . By induction, there execution γ 3 such that Cγ 1 γ 2 γ 3 is (Z ∪ {p}, q)-bivalent. Among the components updated in γ 2 γ 3 , there is at least one component j which is not covered by Z ∪ {p} in Cγ 1 γ 2 γ 3 . Let z ∈ Z ∪ {p, q} be the last process to UPDATE component j prior to Cγ 1 γ 2 γ 3 , and let σ be the SCAN by z before this UPDATE. Note that every process in Z is free immediately before σ . Modifying the execution γ 1 γ 2 γ 3 to let the remaining free process in Z -Z perform its SCAN immediately after σ gives a (Z ∪ {p}, q)-bivalent configuration.

To obtain the lower bound, construct a ({p}, q)-bivalent configuration having a set Z of n-2 free processes. Apply the previous argument to get a (Z ∪{p}, q)bivalent configuration. Running q until it is about to UPDATE a component not covered by Z ∪ {p} gives a configuration with n components covered. This proof method, which uses induction on the number of free processes to build larger coverings, seems applicable in the general case. In fact, we recently used this method to give a different, much simpler proof of the Ω( √ n) lower bound in [START_REF] Fich | On the space complexity of randomized synchronization[END_REF].

Upper Bound. We describe an n-process memoryless anonymous obstructionfree consensus algorithm using an n-component multi-writer snapshot, matching the lower bound. The algorithm can also be made randomized wait-free by [START_REF] Giakkoupis | An O( √ n) space bound for obstruction-free leader election[END_REF]. Intuitively, 0 and 1 are competing to complete laps. If v gets a substantial lead on v, then v is decided. Initially, each component contains (0, 0). If a process with input x sees this initial state in a SCAN, it updates component 1 with (x, x). Otherwise, it determines the laps, 0 and 1 , of 0 and 1 by finding the largest values in the first and second entries of the components returned by its SCAN. If some component is not ( 0 , 1 ), then it updates the first such component with ( 0 , 1 ). So, suppose all components are the same. If value v is ahead of value v by at least 2 laps, for some v ∈ {0, 1}, then it decides v. If not, it increments the larger of 0 and 1 (breaking ties in favour of 0 ) and updates component 1 with ( 0 , 1 ). This is repeated until the process decides.


Brief Announcement: Faster Data Structures in

Transactional Memory using Three Paths

Trevor Brown

University of Toronto, Toronto, ON M5S 3G4, Canada

With the introduction of Intel's restricted hardware transactional memory (HTM) in commodity hardware, the transactional memory abstraction has finally become practical to use. Transactional memory allows a programmer to easily implement safe concurrent code by specifying that certain blocks of code should be executed atomically. However, Intel's HTM implementation does not offer any progress guarantees. Even in a single threaded system, a transaction can repeatedly fail for complex (and often undocumented) reasons. Consequently, any code that uses HTM must also provide a non-transactional fallback path to be executed if a transaction fails. Since the primary goal of HTM is to simplify the task of writing concurrent code, a typical fallback path simply acquires a global lock, and then runs the same code as the transaction. This is essentially transactional lock elision (TLE). Changes made by a process on the fallback path are not atomic, so transactions that run concurrently with a process on the fallback path may see inconsistent state. Thus, at the beginning of each transaction, a process reads the state of the global lock and aborts the transaction if it is held.

Despite its widespread use, there are many problems with this fallback path. If transactions abort infrequently, then processes rarely execute on the fallback path. However, once one process begins executing on the fallback path, all concurrent transactions will abort, and processes on the fast path will cascade onto the fallback path. This has been called the lemming effect [START_REF] Dice | Early experience with a commercial hardware transactional memory implementation[END_REF], from the myth that lemmings will leap from cliffs in large numbers (in our case, leaping down to the fallback path).

One simple way to mitigate the lemming effect is to retry aborted transactions a few times, waiting between retries for the fallback path to become empty. For some common workloads (e.g., range queries and updates on an ordered set implemented with a binary search tree), some operation is nearly always on the fallback path, so concurrency is very limited and performance is poor. Thus, waiting for the fallback path to become empty is not always a good solution.

A more sophisticated solution is to design transactions so they can commit even if processes are executing on the fallback path. One way to do this is to start with a handcrafted fallback path that uses fine-grained synchronization, and obtain a fast path by wrapping each operation in a transaction (and then optimizing the resulting sequential code). This technique was also explored in concurrent work by Spear et al. [START_REF] Liu | Transactional acceleration of concurrent data structures[END_REF]. To support concurrency between the two paths, the fast path must read and update the meta-data used by the fallback path to synchronize processes. (For example, lock-free algorithms often maintain a record associated with each update operation, so that one process can help complete another process' operation.) Unfortunately, the overhead of manipulating meta-data on the fast path can eliminate much or all of the performance benefit of HTM.

To overcome this, we introduce a novel approach for obtaining faster algorithms by using three execution paths: an HTM-based fast path, an HTM-based middle path and a non-transactional fallback path. Our approach eliminates the lemming effect without imposing any overhead on the fast path. Each operation begins on the fast path, and moves to the middle path after it retries F times. An operation on the middle path moves to the fallback path after retrying M times on the middle path. The fast path does not manipulate any synchronization meta-data used by the fallback path, so operations on the fast path and fallback path cannot run concurrently. Thus, whenever an operation is on the fallback path, all operations on the fast path move to the middle path. The middle path manipulates the synchronization meta-data used by the fallback path, so operations on the middle path and fallback path can run concurrently. Operations on the middle path can also run concurrently with operations on the fast path. The lemming effect does not occur, since an operation does not have to move to the fallback path simply because another operation is on the fallback path. Since processes on the fast path do not run concurrently with processes on the fallback path, the fallback path does not impose any overhead on the fast path (regardless of how it operates).

Comprehensive experiments compared the performance of several two-and threepath algorithms, with lock-based and lockfree fallback paths and many different retry strategies, over a variety of randomized workloads. The graphs on the right show some results from a binary search tree microbenchmark on a 36-core Intel system. In the workload with 2% range queries, TLE succumbs to the lemming effect and performs very poorly. These results suggest that three-path algorithms can be used to obtain the full performance benefit of HTM while robustly avoiding the lemming effect.

This work was supported by the National Science and Engineering Research Council of Canada. I extend my thanks to my advisor Faith Ellen for her helpful comments and guidance in shaping this work. Some of the experiments were performed while at Oracle Labs.