CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Worst-case bounds for blind broadcasting in small-degree networks

Peter Damaschke (Institutionen för datavetenskap, Algoritmer)
8th International Colloquium on Structural Information and Communication Complexity SIROCCO'2001 (Proceedings in Informatics, Carleton Scientific) Vol. 11 (2001), p. 105-115.
[Konferensbidrag, refereegranskat]

Blind broadcasting is the task of delivering a message from a source to all the n nodes in a network, where nodes are not aware of the network topology. We derive upper and lower bounds for the worst-case broadcast time, in terms of size n and depth d of the network (i.e. eccentricity of the source). Provided that the degree of nodes is bounded by a small constant, these results improve upon the general upper bound of 2n-d. For degree up to 5 we get tight bounds.

Nyckelord: broadcasting, one-port model, unknown topology, small degree, full synchronization

Denna post skapades 2006-09-25. Senast ändrad 2015-02-11.
CPL Pubid: 1971


Institutioner (Chalmers)

Institutionen för datavetenskap, Algoritmer (2002-2004)


Information Technology

Chalmers infrastruktur