TIME AND COST TRADE-OFFS IN GOSSIPING

Each of n processors has a value which should be transmitted to all ot her processors. This fundamental communication task is called gossipin g. In a unit of time every processor can communicate with at most one other processor and during such a transmission each member of a commun icating pair learns all values currently known to the other. Two impor tant criteria of efficiency of a gossiping algorithm are its running t ime and the total number of transmissions. Another measure of quality of a gossiping algorithm is the total number of links used for transmi ssions. This is the minimum cost of a network which can support the go ssiping algorithm. We establish trade-offs between the time T of gossi ping and the number C of transmissions and between the time of gossipi ng and the number L of links used by the algorithm. For a given T we c onstruct gossiping algorithms working in time T, with parameters C and L close to optimal.