All posts tagged: network theory

Achieving consensus in networks with disturbances

The problem of finding a consensus in a group of people occurs in many social contexts. In a similar way, distributed algorithms for consensus play an important role in networked computing and communication systems if centralized decision making is difficult or impossible. Each entity in such a system processes only local information obtained from its neighbors and ideally performs only simple computations. Despite this simplicity, the process of consensus building should be robust against different types of disturbance, such as faulty entities, noise, and communication errors. A research team with members from Klagenfurt and Genoa has now analyzed the robustness of a special class of consensus algorithms, namely binary consensus, in which all entities must eventually agree on one out of two possible values. The motivation for their study is as follows: Some binary consensus algorithms that work well in noiseless and error-free networks—such as the well-known Gacs-Kurdyumov-Levin algorithm—show convergence problems in networks with disturbances. In turn, some other algorithms that are inferior in noiseless and error-free networks may actually improve their performance with the …

Probabilistic flooding in stochastic networks

Crisostomo, Schilcher, Bettstetter and Barros investigate probabilistic information dissemination in stochastic networks. The following problem is studied: A source node intends to deliver a message to all other network nodes using probabilistic flooding, i.e., each node forwards a received message to all its neighbors with a forwarding probability ϖ. Question is: which minimum ϖ-value needs to be met by each node to ensure receipt of the flooded message by all nodes with high probability? Their forthcoming article in the journal Computer Networks presents a generic approach to this problem in arbitrary networks and then focuses on Erdős Rényi graphs (ERGs) and random geometric graphs (RGGs). An exact solution is given for ERGs. An asymptotic expression is given for RGGs, which is shown to be an approximation for networks with high node density. In both cases, unreliable links are taken into account. Download article: