Record Details

Tight bounds on parallel list marking

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Tight bounds on parallel list marking
 
Creator BHATT, SN
BILARDI, G
HERLEY, KT
PUCCI, G
RANADE, A
 
Subject computation
list marking
list ranking
linked structures
shared-memory machines
parallel algorithms
randomized algorithms
lower bounds
 
Description The list marking problem involves marking the nodes of an L-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 Omega(min{l, n/p}) randomized lower bound for l-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 Theta(min {l, l/p + root(n/p) log n }) bound for randomized algorithms. Therefore, in the latter case, randomization yields a better performance for a wide range of parameter values. (C) 1998
 
Publisher ACADEMIC PRESS INC
 
Date 2011-07-12T13:14:15Z
2011-12-26T12:48:54Z
2011-12-27T05:34:25Z
2011-07-12T13:14:15Z
2011-12-26T12:48:54Z
2011-12-27T05:34:25Z
1998
 
Type Article
 
Identifier JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 51(2), 75-88
0743-7315
http://dx.doi.org/10.1006/jpdc.1998.1447
http://dspace.library.iitb.ac.in/xmlui/handle/10054/3335
http://hdl.handle.net/10054/3335
 
Language en