Memory and communication efficient algorithm for decentralized counting of nodes in networks

Area of Science:

• Computer Science
• Distributed Systems
• Graph Theory

Background:

• Distributed graph algorithms face theoretical limitations for tasks like node counting.
• Existing solutions include stochastic and basic deterministic methods for graph size estimation.
• Real-world applications in robotics and sensor networks require efficient distributed graph analysis.

Purpose of the Study:

• To present a novel deterministic and distributed algorithm for connected graph size calculation.
• To enable every node in a graph to determine the total number of nodes in finite time.
• To offer an efficient alternative to existing graph size estimation methods.

Main Methods:

• The algorithm employs iterative information aggregation within local hubs.
• Information is subsequently broadcast throughout the entire connected graph.
• A prerequisite is providing an upper bound on the graph size.

Main Results:

• The proposed algorithm allows deterministic distributed node counting.
• It demonstrates improved average efficiency in node memory and communication costs compared to prior deterministic methods.
• Average-case time complexity is comparable or superior to existing algorithms.

Conclusions:

• The developed algorithm provides an efficient solution for distributed node counting in connected graphs.
• It offers broader applicability to other distributed problems like summation and quorum sensing.
• This method advances distributed graph theory with practical implications for various systems.