Graph connectivity analysis is one of the primary ways to analyze the topological structure of social networks. Graph biconnectivity decompositions are of particular interest due to how they identify cut vertices and ...
详细信息
ISBN:
(数字)9781665497473
ISBN:
(纸本)9781665497480
Graph connectivity analysis is one of the primary ways to analyze the topological structure of social networks. Graph biconnectivity decompositions are of particular interest due to how they identify cut vertices and cut edges in a network. We present the first, to our knowledge, implementation of a distributed-memory parallel biconnectivity algorithm. As part of our algorithm, we also require the computation of least common ancestors (LCAs) of non-tree edge endpoints in a BFS tree. As such, we also propose a novel distributed algorithm for the LCA problem. Using our implementations, we observe up to a 14.8× speedup from 1 to 128 MPI ranks for computing a biconnectivity decomposition.
This demonstration showcases distributed algorithms for configuration control in multi-robot systems. These algorithms include examples of gradient communication, clustering and dispersion, group motion, and network c...
详细信息
This demonstration showcases distributed algorithms for configuration control in multi-robot systems. These algorithms include examples of gradient communication, clustering and dispersion, group motion, and network characterization. The algorithms are demonstrated on a swarm of 15 mobile robots.
It has been found that the sensor nodes dissipate a significant proportion of their energy in redundant sensing and idle listening. The former occurs when multiple sensor nodes perform their sensing activity in the sa...
详细信息
It has been found that the sensor nodes dissipate a significant proportion of their energy in redundant sensing and idle listening. The former occurs when multiple sensor nodes perform their sensing activity in the same region. The latter occurs when sensor nodes have their radios switched on awaiting incoming communication from other sensor nodes, but none is received since no sensor node is wanting to communicate with it. Researchers have proposed putting the sensors and/or the radios of sensor nodes to sleep (switch them off) so as to conserve energy. The task of scheduling when the sensors and/or radios need to be in sleep/active mode is referred to as sleep scheduling. Sensor sleeping may result in interesting events being missed by the network or may lead to a lower quality of data being sensed. Radio sleeping may lead to communication delays in the network. In this work we propose several distributed algorithms to perform sensor and radio sleep scheduling in wireless sensor networks while trying to minimize its negative impact
Previously, we developed the broadcast incremental power (BIP) algorithm (Wieselthier, J.E. et al., Proc. IEEE INFOCOM 2000, p.585-94, 2000; Mobile Networks and Applications (MONET), vol.7, no.6, 2002), which is a cen...
详细信息
Previously, we developed the broadcast incremental power (BIP) algorithm (Wieselthier, J.E. et al., Proc. IEEE INFOCOM 2000, p.585-94, 2000; Mobile Networks and Applications (MONET), vol.7, no.6, 2002), which is a centralized heuristic for energy-efficient broadcasting of source-initiated session-based traffic in wireless networks. This algorithm, which exploits the characteristics of the wireless channel, was shown to perform better than adaptations of conventional algorithms that were originally developed for wired networks. However, as a consequence of its centralized nature, it is "expensive" in terms of both communication and computation requirements. We now develop two distributed versions of BIP, and compare their performance to that of centralized BIP and to an algorithm based on the minimum-cost spanning tree formulation.
This paper introduces the concept of low-congestion shortcuts for (near-)planar networks, and demonstrates their power by using them to obtain near-optimal distributed algorithms for problems such as Minimum Spanning ...
详细信息
ISBN:
(纸本)9781611974331
This paper introduces the concept of low-congestion shortcuts for (near-)planar networks, and demonstrates their power by using them to obtain near-optimal distributed algorithms for problems such as Minimum Spanning Tree (MST) or Minimum Cut, in planar networks. Consider a graph G = (V, E) and a partitioning of V into subsets of nodes S_1, ..., S_N, each inducing a connected subgraph G[S_i]. We define an α-congestion shortcut with dilation β to be a set of subgraphs H_1, ..., H_N {is contained in} G, one for each subset S_i, such that 1. For each i ∈ [1, N], the diameter of the subgraph G[S_i] + H_i is at most β. 2. For each edge e ∈ E, the number of subgraphs G[S_i] + H_i containing e is at most α. We prove that any partition of a D-diameter planar graph into individually-connected parts admits an O(D log D)-congestion shortcut with dilation O(DlogD), and we also present a distributed construction of it in O(D) rounds. We moreover prove these parameters to be near-optimal;i.e., there are instances in which, unavoidably, max{α, β} = Ω(D (log D)/(log log D)). Finally, we use low-congestion shortcuts, and their efficient distributed construction, to derive O(D)-round distributed algorithms for MST and Min-Cut, in planar networks. This complexity nearly matches the trivial lower bound of Ω(D). We remark that this is the first result bypassing the well-known Ω(D+{the square root of}n) existential lower bound of general graphs (see Peleg and Rubinovich [FOCS'99];Elkin [STOC'04];and Das Sarma et al. [STOC'11]) in a family of graphs of interest.
This paper presents a family of discrete-time distributed algorithms that enable nodes in an undirected, connected network to solve, in a fully decentralized fashion, a system of modular congruences whose residues and...
详细信息
ISBN:
(数字)9781538682661
ISBN:
(纸本)9781538682678
This paper presents a family of discrete-time distributed algorithms that enable nodes in an undirected, connected network to solve, in a fully decentralized fashion, a system of modular congruences whose residues and pairwise coprime moduli are locally known to the nodes. We show that each algorithm in the family is able to determine, in finite time, the congruence class of solutions whose existence and uniqueness is guaranteed by the Chinese remainder theorem. We also describe and analyze three specific algorithms from the family called Synchronous Updating (SU), Pairwise Equalizing (PE), and Groupwise Equalizing (GE), relating the convergence rate of SU to the network diameter and those of PE and GE to their asynchronous update patterns. Finally, we provide simulation results that illustrate their effectiveness.
A class of novel interconnection topologies called the generalized Fibonacci cubes is presented. The generalized Fibonacci cubes include the hypercubes, the recently proposed Fibonacci cubes (W.-J. Hsu, Proc. Int. Con...
详细信息
A class of novel interconnection topologies called the generalized Fibonacci cubes is presented. The generalized Fibonacci cubes include the hypercubes, the recently proposed Fibonacci cubes (W.-J. Hsu, Proc. Int. Conf. on Parallel Processing, p.1722-3 (1991)), and some other asymmetric interconnection topologies bridging between the two mentioned above. The generalized Fibonacci cubes can serve as a framework for studying degraded hypercubes due to faulty nodes or links. Previously known algorithms for hypercubes do not generalize to this class of interconnection topologies. The authors present distributed routing and broadcasting algorithms that can be applied to all members of this class of interconnection topologies. It is shown that their distributed routing algorithm always finds a shortest and deadlock-free path. The broadcasting algorithms are designed and evaluated based on both the all-port and the 1-port communication models. The all-port broadcasting algorithm is provably optimal in terms of minimizing routing steps. An upper bound for the 1-port broadcasting algorithm is determined, which is shown to be optimal for certain cases.< >
When designing distributed algorithms for application overlay networks, it is usually assumed that the overlay nodes are cooperative to collectively achieve optimal global performance properties. However, this assumpt...
详细信息
When designing distributed algorithms for application overlay networks, it is usually assumed that the overlay nodes are cooperative to collectively achieve optimal global performance properties. However, this assumption does not hold in reality, as nodes generally tend to be noncooperative and always attempt to maximize their gains by optimizing their strategies. With such an assumption, we present extensive theoretical analysis to gain insights from a game theoretic perspective, with respect to the behavior of nodes and the equilibrium of the system. The main idea in our analysis is to design appropriate payoff functions, so that the equilibrium of the system may achieve the optimal properties that we desire. Driven by the per-node goal of maximizing gains, such payoff functions naturally lead to distributed algorithms that lead to the desired favorable properties of overlay networks.
A distributed sampling strategy for multiple (N) agents is considered that minimizes the sample complexity and regret of acquiring the best subset of size N among total K ≥ N channels in a cognitive radio access setu...
详细信息
ISBN:
(数字)9783903176201
ISBN:
(纸本)9781728130859
A distributed sampling strategy for multiple (N) agents is considered that minimizes the sample complexity and regret of acquiring the best subset of size N among total K ≥ N channels in a cognitive radio access setup. Agents cannot directly communicate with each other, and no central coordination is possible. Each agent can transmit on one channel at a time, and if multiple agents transmit on the same channel at the same time, a collision occurs, and no agent gets any information about the channel gain or how many other agents transmitted on the same channel. If no collision occurs, the agent observes a reward (or gain) sample drawn from an underlying distribution associated with the channel. An algorithm to minimize the sample complexity and regret is proposed. One important property of our algorithm that distinguishes it from the prior work (that do not assume knowledge of N) is that it requires no information about the difference of the means of the channel gains of the K channels. Our approach results in fewer collisions with improved regret performance compared to the state-of-the-art algorithms. We validate our theoretical guarantees with experiments.
暂无评论