Space Efficient Processor Identity Protocol

Shang-Hua TengInf. Process. Lett 1990 · OpenReview

Abstract

In this paper, a space efficient probabilistic protocol is presented for the Processor Identity Problem—an essential problem in distributed computation and asynchronous parallel computation. The new protocol uses only O(n log2 n) bits, which improves the previous known protocol, due to Lipton and Park, which uses O(n2) bits. The new protocol is very simple, fully distributed, and symmetric, and has no assumption on the initial contents of the elements in the shared memory. Moreover, it is very fast in theory and in practice. This provides a very practical and important primitive for distributed systems and asynchronous parallel systems.
BibTeX
@inproceedings{teng1990space,
  author = {Shang-Hua Teng},
  title = {{Space Efficient Processor Identity Protocol}},
  booktitle = {Inf. Process. Lett},
  year = {1990},
  url = {https://openreview.net/forum?id=pgYXC6WTrs},
}

Loading related content...

Figure