Parallel Computing (TOPC)


Search Issue
enter search term and/or author name


ACM Transactions on Parallel Computing (TOPC), Volume 5 Issue 1, July 2018

Section: Special Issue on SPAA 2016

Introduction to the Special Issue for SPAA 2016
Seth Gilbert
Article No.: 1
DOI: 10.1145/3230677

Better Bounds for Coalescing-Branching Random Walks
Michael Mitzenmacher, Rajmohan Rajaraman, Scott Roche
Article No.: 2
DOI: 10.1145/3209688

Coalescing-branching random walks, or cobra walks for short, are a natural variant of random walks on graphs that can model the spread of disease through contacts or the spread of information in networks. In a k-cobra walk, at each...

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity
Mingmou Liu, Xiaoyin Pan, Yitong Yin
Article No.: 3
DOI: 10.1145/3209884

We study the complexity of parallel data structures for approximate nearest neighbor search in d-dimensional Hamming space {0,1}d. A classic model for static data structures is the cell-probe model [27]....

Fast Distributed Algorithms for Connectivity and MST in Large Graphs
Gopal Pandurangan, Peter Robinson, Michele Scquizzato
Article No.: 4
DOI: 10.1145/3209689

Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where k≥2...

Robust and Probabilistic Failure-Aware Placement
Madhukar Korupolu, Rajmohan Rajaraman
Article No.: 5
DOI: 10.1145/3210367

Motivated by the growing complexity and heterogeneity of modern data centers, and the prevalence of commodity component failures, this article studies the failure-aware placement problem of placing tasks of a parallel job on machines in the...

Lock-Free Transactional Transformation for Linked Data Structures
Deli Zhang, Pierre Laborde, Lance Lebanoff, Damian Dechev
Article No.: 6
DOI: 10.1145/3209690

Nonblocking data structures allow scalable and thread-safe access to shared data. They provide individual operations that appear to execute atomically. However, it is often desirable to execute multiple operations atomically in a transactional...