9505551 Hakimi Effective communication in networks is emerging as a critical factor in improving the performance of distributed systems including multiprocessor computers and computer networks. Research in this project will focus on three classes of problems: 1) the design of effective sequential and parallel algorithms for certain common communication functions in networks, such as all-to-all broadcast or "gossiping"; 2) the study of gossiping in a faulty environment and its application to the problem of automatic identification of the faulty units; and 3) the investigation of gossiping in wireless (radio) networks and the channel assignment problem in cellular telephone systems. Work will also include extending the PI's previous work on effective information dissemination in networks with emphasis on devising efficient approximation algorithms for known difficult problems and extending work on distributed gossiping algorithms in a faulty environment to make it applicable to automatic identification of intermittently faulty units in a network. The principal investigator will also study problems in wireless networks and cellular systems using generalizations of graph coloring problems. ***
