distributed multi-broadcast in unknown radio networks
One of the most frequent tasks in multi-hop synchronous radio networks is the multi-broadcast operation: it consists in performing r independent message broadcasts through a network of n nodes. We investigate the case in which messages have logarithmic bounded size and the nodes have no knowledge of the topology (i.e. unknown networks ). Let D and c be the maximum eccentricity and the congestion of the network, respectively. First, we prove an &OHgr;( c +( D + c /log c ) log n ) lower bound on the number of time-slots required to complete a multi-broadcast operation by any deterministic distributed protocol. Secondly, we prove an &OHgr;( c +( c /log c )log n + D log( n / D )) lower bound for randomized distributed protocols. An important consequence is that perfect pipeline is not achievable for both deterministic and randomized protocols. Finally, for any constant &agr; > 0, we provide an O (( D + c ) d 2 log (2+&agr;) n ) deterministic upper bound for the same task where d is the maximum in-degree of the network. Our (non-constructive) deterministic distributed protocol is thus almost optimal when d = O (polylog n ) and it can be converted into an efficiently constructible one having O (( D + c ) d 2 log (3+&agr;) n ) completion time.
distributed broadcast radio network network task synchronization message case log size knowledge topologies congestion lower bound timing completeness randomization pipeline optimality