Prof. Teofilo F. Gonzalez

Department of Computer Science
University of California, Santa Barbara, USA
teo@cs.ucsb.edu

Title: Message Dissemination Under the Multicasting Communication Mode

Abstract

We discuss algorithms, complexity issues, and applications for message dissemination problems under the multicasting communication mode. These problems arise while executing in a parallel or distributed computing environment iterative methods for solving scientific computation applications, dynamic programming procedures, sparse matrix multiplication, etc. Our message communication problems also arise when disseminating information over ad-hoc wireless networks.

Given a communication environment and a set of messages that need to be exchanged, the message dissemination problem is to find a schedule to transmit all the messages in the least total number of communication rounds. Generating an optimal communication schedule (with the least total number of communication rounds) for message dissemination problems over a wide range of communication environments is an NP-hard problem. To cope with intractability efficient message dissemination approximation algorithms have been developed for different types of communication environments and message communication patterns (the communications that must take place). The communication environment consists of the communication network (the direct communications allowed for each processor), primitive operations (the basic communication operations allowed by the system), and the communication model (possible operations during each communication round or step).

Our goal is to present scattered research results developed during the last decade to establish that the multicasting (one-to-many) communication environment is a powerful communication primitive that allows for solutions that are considerable better than those achievable under the telephone (or one-to-one) communication environment. The multicasting communication environment has been available for quite some time in parallel computing systems. We also establish that, within the multicasting communication mode, forwarding plays an important role by allowing solutions that are considerable better than when restricting to direct communications, even when the communication load is balanced and the network is complete (all possible bidirectional links are present). We show that off-line communication scheduling allows for considerably better solutions over on-line scheduling. However, on-line scheduling provides added flexibility and it is applicable to a larger set of scenarios.

Biographical Sketch

Professor Gonzalez was born in Monterrey, Mexico. He was one of the first handful of students to received a computer science undergraduate degree in Mexico (ITESM 1972). He received his Ph.D. degree from the University of Minnesota (1975). He has been member of the faculty at OU, Penn State, and UT Dallas, and has spent sabbatical leave at the ITESM (Monterrey, Mexico) and U. Utrecht (the Netherlands). Since 1984 he has been professor of computer science at UCSB.

Professor Gonzalez's main research contributions include the development of algorithms for scheduling, computational geometry, computer-aided design, and message dissemination (under the multicasting communication mode) problems. Dr. Gonzalez has also developed exact and approximation algorithms for graph problems, code minimization, map compression, generalized dictionaries, statistical tests, page fault minimization, etc.

His research contributions for the open shop scheduling problem are seminal as they started a research area that is now as important as the more traditional ones. He was one of the first researchers that developed the first set of computationally interesting algorithms for preemptive scheduling problems. He developed a best possible clustering algorithm that has found applications in many research areas. He was one of a small group researchers that made the first set of contributions to the area of approximation algorithms. One of his main research contributions include the first set of in-approximability results. Professor Gonzalez edited the Handbook on Approximation Algorithms and Metaheuristics (May 2007). This handbook is the first one in the area, and includes contributions from top researchers from all over the world.

His work has been published in the top journals in computer science and operations research. He also has numerous publications in research books and conference proceedings. Professor Gonzalez has served as program committee chair for several conferences, and editor (and guest editor) of several publications. He has received three teaching awards at UCSB and has served as a program evaluator for ABET.