Uzi Vishkin - Parallel Algorithms

Parallel Algorithms

In the field of parallel algorithms, Uzi Vishkin co-authored the paper Shiloach & Vishkin (1982b) that contributed the work-time (WT) (sometimes called work-depth) framework for conceptualizing and describing parallel algorithms. The WT framework was adopted as the basic presentation framework in the parallel algorithms books JaJa (1992) and Keller, Kessler & Traeff (2001), as well as in the class notes Vishkin (2009). In the WT framework, a parallel algorithm is first described in terms of parallel rounds. For each round, the operations to be performed are characterized, but several issues can be suppressed. For example, the number of operations at each round need not be clear, processors need not be mentioned and any information that may help with the assignment of processors to jobs need not be accounted for. Second, the suppressed information is provided. The inclusion of the suppressed information is, in fact, guided by the proof of a scheduling theorem due to Brent (1974). The WT framework is useful since while it can greatly simplify the initial description of a parallel algorithm, inserting the details suppressed by that initial description is often not very difficult. Similarly, first casting an algorithm in the WT framework can be very helpful for programming it in XMTC. Vishkin (2011) explains the simple connection between the WT framework and the more rudimentary ICE abstraction noted above.

In the field of parallel and distributed algorithms, one of the seminal papers co-authored by Uzi Vishkin is Cole & Vishkin (1986). This work introduced an efficient parallel technique for graph coloring. The Cole–Vishkin algorithm finds a vertex colouring in an n-cycle in O(log* n) synchronous communication rounds. This algorithm is nowadays presented in many textbooks, including Introduction to Algorithms by Cormen et al., and it forms the basis of many other distributed algorithms for graph colouring.

Other contributions by Uzi Vishkin and various co-authors include parallel algorithms for list ranking, lowest common ancestor, spanning trees, and biconnected components.