Tight bounds on parallel list marking

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-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 location of the head of the list is initially known. Under the assumption that memory 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. In the case where list cells are tagged in a way that differentiates them from other cells, we establish a tight (Formula presented) bound for randomized algorithms.

Original languageEnglish
Title of host publicationEURO-PAR 1995 Parallel Processing - 1st International EURO-PAR Conference, Proceedings
EditorsSeif Haridi, Khayri Ali, Peter Magnusson
Pages231-242
Number of pages12
DOIs
StatePublished - 1995
Event1st International EURO-PAR Conference on Parallel Processing, EURO-PAR 1995 - Stockholm, Sweden
Duration: 29 Aug 199531 Aug 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume966
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference1st International EURO-PAR Conference on Parallel Processing, EURO-PAR 1995
Country/TerritorySweden
CityStockholm
Period29/08/9531/08/95

Fingerprint

Dive into the research topics of 'Tight bounds on parallel list marking'. Together they form a unique fingerprint.

Cite this