2016/03/17 by Maitri Chakraborty, Chakraborty, Maitri, Alessia Milani +3
Computer Science · Engineering · #68W15 #Advanced Memory and Neural Computing #Age of Information Optimization #Caching and Content Delivery #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC #msc:68W15
paper · pdf · doi:10.48550/arxiv.1603.05459
arxiv created 2016/03/17 · openalex publication_date 2016/03/17 · arxiv updated 2016/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Anonymous Dynamic Networks is a harsh computational environment due to changing topology and lack of identifiers. Computing the size of the network, a problem known as Counting, is particularly challenging because messages received cannot be tagged to a specific sender. Previous works on Counting in Anonymous Dynamic Networks do not provide enough guarantees to be used in practice. Indeed, they either compute only an upper bound on the network size that may be as bad as exponential, or guarantee only double-exponential running time, or do not terminate, or guarantee only eventual termination without running-time guarantees. Faster experimental protocols do not guarantee the correct count. Recently, we presented the first Counting protocol that computes the exact count with exponential running-time guarantees. The protocol requires the presence of one leader node and knowledge of any upper bound Delta on the maximum number of neighbors that any node will ever have. In the present work, we complement the latter theoretical study evaluating the performance of such protocol in practice. We tested a variety of network topologies that may appear in practice, including extremal cases such as trees, paths, and continuously changing topologies. We also tested networks that temporarily are not connected. Our simulations showed that the protocol is polynomial for all the inputs tested, paving the way to use it in practical applications where topology changes are predictable. The simulations also provided insight on the impact of topology changes on information dissemination. To the best of our knowledge, this is the first experimental study that shows the possibility of computing the exact count in polynomial time in a variety of Anonymous Dynamic Networks that are worse than expected in practice.