Talks & Seminars
Slicing Posets with Applications to Distributed Computing and Combinatorics
Prof. Vijay K. Garg, IIT, Kanpur, and Univ. of Texas, Austin
Date & Time: December 9, 2002 11:00
Venue: CSE Seminar Room
Detecting a fault in execution of a distributed system requires finding a consistent global state of the computation that satisfies certain predicate (e.g. violation of mutual exclusion). Detecting a global predicate even in 2-CNF form is an NP-complete problem. We develop a computation slicing technique for reducing the size of the computation and hence the number of global states to be analyzed for detecting a predicate. Informally, a slice of a distributed computation with respect to a global predicate is the smallest computation that contains all the consistent cuts of the original computation that satisfy the predicate. We prove that slice exists for all global predicates and provide efficient algorithms to compute slices for several useful classes of predicates. Slicing can also be applied to solve problems in combinatorics. A combinatorial problem usually requires enumerating, counting or ascertaining existence of structures that satisfy a given property $B$. We cast the combinatorial problem as a distributed computation such that there is a bijection between combinatorial structures satisfying $B$ and the global states that satisfy a property equivalent to $B$. We then apply results in slicing a computation with respect to a predicate to obtain a small representation of only those global states that satisfy $B$. This gives us an efficient algorithm to enumerate, count or detect structures that satisfy $B$ when the total set of structures is large but the set of structures satisfying $B$ is small. We illustrate our techniques by analyzing problems in integer partitions, set families, and set of permutations.
Speaker Profile:
Prof. Vijay K. Garg received his Bachelor of Technology degree in computer science from the Indian Institute of Technology, Kanpur in 1984 and the M.S. and Ph.D. degrees in electrical engineering and computer science from the University of California at Berkeley in 1985 and 1988, respectively. He is a professor in the Department of Electrical and Computer Engineering and the director of the Parallel and Distributed Systems Laboratory at the University of Texas, Austin. He is currently visiting IIT Kanpur as N. Rama Rao Chair Professor (Visiting) in the Computer Science and Engineering Department. His research interests are in the areas of distributed systems and discrete event systems. He is the author of the book "Elements of Distributed Computing" (Wiley&Sons, 2002).
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback