Tight Bounds on Parallel List Marking

Sandeep N. Bhatt, Gianfranco Bilardi, Kieran T. Herley, Geppino Pucci, Abhiram Ranade

Research output: Contribution to journalArticlepeer-review

Abstract

The list marking problem involves marking the nodes of an ℓ-node linked list stored in the memory of a (p,n)-PRAM, when only the position of the head of the list is initially known, while the remaining list nodes are stored in arbitrary memory locations. Under the assumption that cells containing list nodes bear no distinctive tags distinguishing them from other cells, we establish anΩ(min{ℓ,n/p}) randomized lower bound for ℓ-node lists and present a deterministic algorithm whose running time is within a logarithmic additive term of this bound. Such a result implies that randomization cannot be exploited in any significant way in this setting. For the case where list cells are tagged in a way that differentiates them from other cells, the above lower bound still applies to deterministic algorithms, while we establish a tightΘ(min{ℓ,ℓ/p+(n/p)logn})bound for randomized algorithms. Therefore, in the latter case, randomization yields a better performance for a wide range of parameter values.

Original languageEnglish
Pages (from-to)75-88
Number of pages14
JournalJournal of Parallel and Distributed Computing
Volume51
Issue number2
DOIs
StatePublished - 15 Jun 1998

Keywords

  • List marking; list ranking; linked structures; shared-memory machines; parallel algorithms; randomized algorithms; lower bounds

Fingerprint

Dive into the research topics of 'Tight Bounds on Parallel List Marking'. Together they form a unique fingerprint.

Cite this