کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431770 688625 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Node discovery in networks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Node discovery in networks
چکیده انگلیسی

This paper abstracts the problem of network nodes discovering one another in a network of unknown size using all-to-all gossip. The problem is studied in terms of evolving directed graphs where each vertex represents a participating node and each edge represents one node’s knowledge about another. Ideally, such a graph has diameter one, i.e., each node knows all others. Nodes share their knowledge by sending gossip messages. Gossip among the nodes allows them to discover one another, decreasing the diameter of the graph. Here this problem is considered in several synchronous settings under different assumptions about the ability of the participating nodes to communicate. Specifically, the following aspects of communication are considered: (1) the ability of the nodes to multicast gossip messages, and (2) the size of the messages. The results describe the lower and upper bounds on the number of synchronous rounds required for the participants to discover each other. A particular question of interest is: if the network size is unknown, how does a node know that it has discovered all other nodes? Given a weakly-connected graph describing the initial knowledge of the nodes, every node in our algorithm can stop the discovery process knowing that there are no unknown nodes—this is done without any prior knowledge of the total number of nodes participating in the computation.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 69, Issue 4, April 2009, Pages 337–348
نویسندگان
, , ,