@inproceedings{5508d7ba8e7a41a9a855c563fb8b5371,
title = "Tight bounds on parallel list marking",
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.",
author = "Bhatt, {Sandeep N.} and Gianfranco Bilardi and Herley, {Kieran T.} and Geppino Pucci and Ranade, {Abhiram G.}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1995.; 1st International EURO-PAR Conference on Parallel Processing, EURO-PAR 1995 ; Conference date: 29-08-1995 Through 31-08-1995",
year = "1995",
doi = "10.1007/bfb0020468",
language = "English",
isbn = "9783540602477",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "231--242",
editor = "Seif Haridi and Khayri Ali and Peter Magnusson",
booktitle = "EURO-PAR 1995 Parallel Processing - 1st International EURO-PAR Conference, Proceedings",
}