Naming symmetric processes using shared variables

Summary Implementations of inter-process communication and synchronization in distributed systems usually rely on the existence of unique ids for the processes. We consider the problem of generating such ids for identical processes in a shared-variable system. A randomized protocol that assigns distinct ids to the processes within an expected polynomial number of rounds using a polynomial number of boolean atomic variables is presented. Ömer Eeciolu obtained his Ph.D. degree in mathematics from the University of California, San Diego in 1984. At present he is an Associate Professor in the Computer Science department of the University of California, Santa Barbara, where he has been on the faculty since 1985. His principal areas of research are parallel algorithms, bijective and enumerative combinatorics, and combinatorial algorithms. His current interest in parallel algorithms involve approximation and numerical techniques on distributed memory systems while his combinatorial interests center around computational geometry, bijective methods, and ranking algorithms for combinatorial structures. Ambuj K. Singh is an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara. He received a Ph.D. in Computer Science from the University of Texas at Austin in 1989, an M.S. in Computer Science from Iowa State University in 1984, and a B. Tech. from the Indian Institute of Technology at Kharagpur in 1982. His research interests are in the areas of adaptive resource allocation, concurrent program development, and distributed shared memory.Work supported in part by NSF grants CCR-9008628 and CCR-9223094