Search

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n , and loose if m > n. In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O (log n) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = (1 + ϵ) ⋅ n and constant ϵ , they achieve a step complexity of O (log log n). In this paper we consider tight as well as loose renaming and introduce randomized algorithms that achieve their tasks with high probability. The model assumed is the asynchronous shared-memory model against an adaptive adversary. Our algorithm for loose renaming maps n processes to a name space of size m = (1 + 2 ∕ (log n) ℓ) ⋅ n = (1 + o (1)) ⋅ n performing O (ℓ ⋅ (log log n) 2) test-and-set operations. In the case of tight renaming, we present a protocol that assigns n processes to n names with step complexity O (log n) , but without the overhead and impracticality of the AKS network. This algorithm utilizes modern hardware features in form of a counting device which is also described in the paper. This device may have the potential to speed up other distributed algorithms as well. • Tight and loose renaming in the shared-memory model. • Loose renaming with (1+o(1)) * n names in poly-double-logarithmic number of steps. • Tight renaming algorithm simpler and more practical than existing one. • Tight renaming relies on new HW register with potential benefits in other areas. [ABSTRACT FROM AUTHOR]

Asynchronous stochastic algorithms with variance reduction techniques have been empirically shown to be useful for many large-scale machine learning problems. By making a parallel optimization algorithm asynchronous, one can reduce the synchronization cost and improve the practical efficiency. Recently, the stochastic recursive gradient algorithm has shown superior theoretical performance; however, it is not scalable enough in the current big data era. To make it more practical, we propose a class of asynchronous stochastic recursive gradient methods and analyze them in the shared memory model. The analysis results show that our asynchronous algorithms can linearly converge to the solution in the strongly convex case and complete the iteration faster. In addition, we analyze the "price of asynchrony" and give the sufficient conditions required for linear speedup. To the best of our knowledge, our speedup conditions match the optimal bounds of asynchronous stochastic algorithms known thus far. Finally, we demonstrate our theoretical analyses from a practical implementation on a multicore machine. [ABSTRACT FROM AUTHOR]

We present a new shared memory model, SF shared memory model. In this model, the actions of each node are partitioned into slow actions and fast actions. By contrast, the traditional shared memory model only includes fast actions. Intuitively, slow actions can utilize slightly stale state information to execute successfully. However, fast actions require that the state information they use is most recent. We show that the use of slow actions can substantially benefit in improving performance of programs from the shared memory model to WAC model that has been designed for sensor networks. To illustrate this, we use three protocols concerning problems that need to be solved in sensor networks. We show that under various message loss probabilities, densities, etc., slow actions can improve the performance substantially, since slow actions reduce the performance penalty of fast actions under heavy message loss environments. Moreover, the effectiveness of the slow action increases when there is a higher probability of message loss. [ABSTRACT FROM AUTHOR]