Selective families, superimposed codes, and broadcasting on unknown radio networks

摘要: Selective families, a weaker variant of superimposed codes [KS64, F92, 197, CR96], have been recently used to design Deterministic Distributed Broadcast (DDB) protocols for unknown radio networks (a network is said be when the nodes know nothing about but their own label) [CGGPR00, CGOR00].We first provide general almost tight lower bound on size selective families. Then, by reverting families - DDB connection, we exploit our construct family “hard” (i.e. directed graphs). These yield an O(n log D) completion time that superlinear (in n network) even very small maximum eccentricity D network, while all previous bounds (e.g. O(D n) [CGGPR00]) are only linear.On other hand, upper in independently and in-degree d network. We introduce broadcast technique exploits new way. combining optimal with technique, obtain O(Dd log3n) prove = O(n/D). This exponentially improves over best known [CGR00) D, O(polylogn). Furthermore, comparing deterministic randomized one [BGI87] new, rather surprising insight into real gap between protocols. It turns out this exponential (as discovered [BGI87]), has large O(na), some constant > O).We then look at multibroadcast problem networks. A similar connection (single) also holds multibroadcast. fact combine available literature [EFF85, HS87, I97, CHI99]. yields protocol having O(Dd2 log3n). Finally, order determine limits generalize (and improve) [CR96] codes.