FAST GOSSIPING WITH SHORT UNRELIABLE MESSAGES

Each of n nodes of a communication network has a piece of information (gossip) which should be made known to all other nodes. Gossiping is d one by sending letters. In a unit of time each node can either send on e letter to a neighbor or receive one such letter, containing one goss ip currently known to the sender. Letters reach their destinations wit h constant probability 0 < q < 1, independently of one another. For a large class of networks, including rings, grids, hypercubes and comple te graphs, we construct gossip schemes working in linear time and succ essfully performing gossiping with probability converging to 1, as the number of nodes grows.