List ranking

In parallel algorithms, the list ranking problem involves determining the position, or rank, of each item in a linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As Anderson & Miller (1990) wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.

History

The list ranking problem was posed by

• Anderson, Richard J.; Miller, Gary L. (1990), "A simple randomized parallel algorithm for list-ranking", Information Processing Letters, 33 (5): 269–273,
  doi:10.1016/0020-0190(90)90196-5
  .
• Cole, Richard;
  doi:10.1016/0890-5401(89)90036-9
  .
• S2CID 7231609
  .
• S2CID 17475781
  .
• Wyllie, J. C. (1979), The Complexity of Parallel Computation, Ph.D. thesis, Department of Computer Science, Cornell University.