In our talk we are concerned with distributed graph algorithms, where a synchronous, message-passing network without shared memory is to compute a function of its own topology. In such distributed network the cost of sending a message between two nodes is proportional to their distance. Since sending messages to far-away nodes is expensive, it is desirable that computation be based only on information available locally. This locality constraint can be quite severe when one is to compute a global function of input data that are spread across the network, and represents a challenge from the point of view of algorithmic design. This communication problem is completely neglected in the popular PRAM model. There, the existence of a shared memory which can be accessed in unit time allows fast collection and dissemination of data among the processors. Once this assumption is removed and the cost of communication is taken into consideration, several computational problems which were easily solvable suddenly become hard or unsolvable efficiently, especially if one is seeking deterministic solutions. Here we focus our attention on computing maximal matchings and f-matchings, as well as on graph coloring problems.

WHERE: TEC 205