@MASTERSTHESIS{Cardoso2009,
  author = {Jorge C. S. Cardoso},
  title = {Probabilistic Estimation of Network Size and Diameter},
  school = {Universidade do Minho},
  year = {2009},
  month = {November},
  abstract = {Determining the size of a network and its diameter are important functions
	
	in distributed systems, as there are a number of algorithms which
	rely on
	
	such parameters, or at least on estimates of those values. Although
	important,
	
	determining the size of a network, in a distributed manner, is not
	
	trivial. Algorithms that do this should be fast, to cope with high
	churn;
	
	fault-tolerant, to cope with link and node failures; and use a small
	number
	
	of messages, in order not to impose a high overhead in network bandwidth.
	
	The Extrema Propagation technique presented in [Baquero et al., 2007]
	
	allows the estimation of the size of a network in a fast, distributed
	and fault
	
	tolerant manner. The technique was studied in a simulation setting
	where
	
	rounds advance synchronously and where there is no message loss.
	
	This work presents two main contributions. The first, is the study
	of the
	
	Extrema Propagation technique under asynchronous rounds and integrated
	
	in the Network Friendly Epidemic Multicast (NeEM) framework. The second,
	
	is the evaluation of a diameter estimation technique associated with
	
	the Extrema Propagation. This study also presents a small enhancement
	
	to the Extrema Propagation in terms of communication cost and points
	out
	
	some other possible enhancements.
	
	Results show that there is a clear trade-off between time and communication
	
	that must be considered when configuring the protocol—a faster
	
	convergence time implies a higher communication cost. Results also
	show
	
	that its possible to reduce the total communication cost by more the
	18%
	
	using a simple approach. The diameter estimation technique is shown
	to
	
	have a relative error of less than 10% even when using a small sample.
	
	The Extrema Propagation technique was partly integrated into the NeEM
	
	framework. Full integration would simply be a matter of feeding the
	estimated
	
	values back into the gossip and overlay layers which could use the
	
	estimated values for a better configuration of the fanout and time-to-live
	
	parameters.},
  owner = {Jorge Cardoso},
  timestamp = {2009.05.05},
  url = {http://jorgecardoso.eu/publications/TeseMScJorgeCardoso.pdf}
}