Parallel Algorithms based on Predicate Detection
Cullen Trust Endowed Professor
The University of Texas at Austin
COM2 Level 2
MR3, COM2-02-26
Abstract:
We present a method to design parallel algorithms for the combinatorial optimization problems based on predicate detection.
Our method solves and generalizes many classical combinatorial optimization problems including the stable marriage problem, the shortest path problem and the market clearing price problem.
These problems are cast as searching for an element that satisfies an appropriate predicate in a distributive lattice.
Moreover, our method solves generalizations of all these problems --- namely finding the optimal solution satisfying additional constraints called lattice-linear predicates.
For stable marriage problems, an example of such a constraint is that Peter's regret is less than that of Paul.
Our algorithm, called Lattice-Linear Predicate Detection (LLP) can be implemented in parallel with without any locks or compare-and-set instructions. It just assumes atomicity of reads and writes.
The method is applicable to many other problems including the Housing Market Allocation problem, various dynamic programming problems, and the minimum spanning tree problem.
Bio:
Vijay Garg is a Cullen Trust Endowed Professor in the Department of Electrical & Computer Engineering at The University of Texas at Austin.
He received his Ph.D. in Computer Science at the University of California at Berkeley and B. Tech. in computer science at IIT, Kanpur.
His research interests are in parallel and distributed computing, discrete event systems and lattice theory.
He is the author of "Elements of Distributed Computing" (Wiley, 2002), "Introduction to Lattice Theory with
Computer Science Applications" (Wiley, 2015), and "Modeling and Control of Logical Discrete Event Systems" (Springer, 2012).