Design and Implementation of Parallel Algorithms.

摘要

Greg Plaxton 1989B won the best paper award at SPAA for his recent work on three related problems, each highly fundamental: (1) Load balancing: given a distribution of tasks to processors, move the task tokens so each processor has an equal number of tasks; (2) Selection: Given n items and k between 1 and n, find the kth item in sorted order; and (3) Sorting: given n items distributed equally among p processors, sort the items.