✦ LIBER ✦

Optimal parallel randomized renaming

✍ Scribed by Martin Farach; S. Muthukrishnan

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 388 KB
Volume: 61
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(96)00182-2

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the Renaming Problem, a basic processing step in string algorithms, for which we give a simultaneously work and time optimal Las Vegas type PRAM algorithm. The Renaming Problem is closely related to the Multiset Sorting Problem.

📜 SIMILAR VOLUMES

Optimal parallel processing of random ta

Optimal parallel processing of random task graphs

✍ Zhen Liu; Rhonda Righter 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 180 KB

We consider scheduling of tasks of parallel programs on multiprocessor systems where tasks have precedence relations and synchronization points. The task graph structures are random variables in the sense that successors to a task do not become known until the task is executed. Thus, as is often the

Parallel randomized load balancing

✍ Micah Adler; Soumen Chakrabarti; Michael Mitzenmacher; Lars Rasmussen 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 313 KB

It is well known that after placing n balls independently and uniformly at ## Ž . random into n bins, the fullest bin holds ⌰ log nrlog log n balls with high probability. More recently, Azar et al. analyzed the following process: randomly choose d bins for each ball, and then place the balls, one

IMCO Renamed

📂 Article 📅 1981 🏛 Springer 🌐 English ⚖ 196 KB

Interdab renamed

📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 132 KB

Waukesha renames facility

📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 160 KB

Parallel heap: An optimal parallel prior

Parallel heap: An optimal parallel priority queue

✍ Narsingh Deo; Sushil Prasad 📂 Article 📅 1992 🏛 Springer US 🌐 English ⚖ 619 KB

We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the p