Model-Based Iterative Reconstruction (MBIR) methods for X-ray CT provide improved image quality compared to conventional techniques like filtered backprojection (FBP), but their computational burden is undesirably hig...
详细信息
ISBN:
(纸本)9781538693308
Model-Based Iterative Reconstruction (MBIR) methods for X-ray CT provide improved image quality compared to conventional techniques like filtered backprojection (FBP), but their computational burden is undesirably high. distributed algorithms have the potential to significantly reduce reconstruction time, but the communication overhead of existing methods has been a considerable bottleneck. This paper proposes a distributed algorithm called Block-Axial Checkerboarding (BAC) that utilizes the special structure found in helical CT geometry to reduce inter-node communication. Preliminary results using a simulated 3D helical CT scan suggest that the proposed algorithm has the potential to reduce reconstruction time in multi-node systems, depending on the balance between compute speed and communication bandwidth.
This paper proposes a discrete-time, distributed algorithm for multi-agent networks to achieve the minimum l(1)-norm solution to a group of linear equations known to possess a family of solutions. We assume each agent...
详细信息
This paper proposes a discrete-time, distributed algorithm for multi-agent networks to achieve the minimum l(1)-norm solution to a group of linear equations known to possess a family of solutions. We assume each agent in the network knows only one equation and can communicate with only its neighbors. The algorithm is developed based on a combination of the projection-consensus idea and the sub-gradient descent method. Given the underlying network graph to be directed and strongly connected, we prove that the algorithm enables all agents to achieve a common minimum l(1) -norm solution. The major difficulty to be dealt with is the non-smooth nature of the norm and the lack of strict convexity of the associated relevant performance index. Copyright (C) 2020 The Authors.
Traffic jams on the motorways due to accidents or other emergencies have proven difficult to resolve. The time it takes for the cars to line up and move out of the jam on their own accord is usually rather long. This ...
详细信息
Traffic jams on the motorways due to accidents or other emergencies have proven difficult to resolve. The time it takes for the cars to line up and move out of the jam on their own accord is usually rather long. This article presents a system named ETMRTCM, which effectively centralized traffic coordination as a solution for overcoming transitory bottlenecks on multi-lane motorways. At initially, warning alerts regarding the traffic congestion happened depending on Vehicle to Vehicle communications. Then, automobiles start negotiating with their neighbors to figure out the best structure (platoon leader, distance gap, speed, and the number of vehicles) for formulating platoons. As a result, cars can move through the congestion more efficiently. After that, the platoon leaders give orders to the troops to switch lanes if there is an open space in the road adjacent to the one in which they are. The trial findings show that our method may shorten the wait time for the last few cars passing through the congested region by up to 22%. The suggested process also efficiently shortens wait times for vehicles entering the crowded zone while keeping things even for those leaving it.
We study smoothed analysis of distributed graph algorithms, focusing on the fundamental minimum spanning tree (MST) problem. With the goal of studying the time complexity of distributed MST as a function of the "...
详细信息
ISBN:
(纸本)9781450377515
We study smoothed analysis of distributed graph algorithms, focusing on the fundamental minimum spanning tree (MST) problem. With the goal of studying the time complexity of distributed MST as a function of the "perturbation" of the input graph, we posit a smoothing model that is parameterized by a smoothing parameter 0 <= epsilon(n) <= 1 which controls the amount of random edges that can be added to an input graph G per round. Informally, epsilon(n) is the probability (typically a small function of n, e.g., n(-1/4)) that a random edge can be added to a node per round. The added random edges, once they are added, can be used (only) for communication. We show upper and lower bounds on the time complexity of distributed MST in the above smoothing model. We present a distributed algorithm that, with high probability,(1) computes an MST and runs in (O) over tilde (min{1/root epsilon(n)2(O(root log n)), D + root n}) rounds(2) where epsilon is the smoothing parameter, D is the network diameter and n is the network size. To complement our upper bound, we also show a lower bound of (Omega) over tilde (min{1/root epsilon(n), D + root n}). We note that the upper and lower bounds essentially match except for a multiplicative 2(O(root log n)) polylog(n) factor. Our work can be considered as a first step in understanding the smoothed complexity of distributed graph algorithms.
The edge connectivity of a network is the minimum number of edges whose removal disconnect the network. The edge connectivity determines the minimum number of edge-disjoint paths between all nodes. Hence finding the e...
详细信息
ISBN:
(纸本)9783903176317
The edge connectivity of a network is the minimum number of edges whose removal disconnect the network. The edge connectivity determines the minimum number of edge-disjoint paths between all nodes. Hence finding the edge connectivity can reveal useful information about reliability, alternative paths and bottlenecks. In this paper, we propose a cost-effective distributed algorithm that finds a lower bound for the edge connectivity of a network via finding at most c depth-first-search trees, where c is the edge connectivity. The proposed algorithm is asynchronous and does not need any synchronization between the nodes. In the proposed algorithm, the root node starts a distributed depth-first-search algorithm, and the nodes select next node in the tree based on their available edges to maximize the total number of established trees. The simulation results show that the proposed algorithm finds the edge connectivity with an average of 48% accuracy ratio.
Recently, distributed algorithms for power system state estimation have attracted significant attention. Along with such advantages as decomposition, parallelization of the original problem and absence of a central co...
详细信息
Recently, distributed algorithms for power system state estimation have attracted significant attention. Along with such advantages as decomposition, parallelization of the original problem and absence of a central computation unit, distributed state estimation may also serve for local information privacy reasons since the only information to be transferred is the boundary states of neighboring areas. In this paper, we propose some novel approaches for speeding up the ADMM-based distributed state estimation algorithms by utilizing some recent results in optimization theory. We also thoroughly analyze the theoretical and practical performance, concluding that accelerated approach outperforms the existing ones. The theoretical considerations are verified through the experiments on a scalable example. Copyright (C) 2020 The Authors.
We study the distributed average consensus problem in multi-agent systems with directed communication links that are subject to quantized information flow. The goal of distributed average consensus is for the agents, ...
详细信息
We study the distributed average consensus problem in multi-agent systems with directed communication links that are subject to quantized information flow. The goal of distributed average consensus is for the agents, each associated with some initial value, to obtain the average (or some value close to the average) of these initial values. In this paper, we present and analyze a distributed averaging algorithm which operates exclusively with quantized values (specifically, the information stored, processed and exchanged between neighboring agents is subject to deterministic uniform quantization) and relies on event-driven updates (e.g., to reduce energy consumption, communication bandwidth, network congestion, and/or processor usage). We characterize the properties of the proposed distributed averaging protocol and show that its execution, on any time-invariant and strongly connected digraph, will allow all agents to reach, in finite time, a common consensus value that is equal to the quantized average. We conclude with comparisons against existing quantized average consensus algorithms that illustrate the performance and potential advantages of the proposed algorithm. Copyright (C) 2020 The Authors.
Age of Information (AoI) is an emerging concept to model information freshness from the perspective of destinations of information deliveries. Serving as a metric to characterize the data delivery timeliness, the peak...
详细信息
ISBN:
(纸本)9781728198293
Age of Information (AoI) is an emerging concept to model information freshness from the perspective of destinations of information deliveries. Serving as a metric to characterize the data delivery timeliness, the peak age indicates the maximum value of the AoI prior to a data packet reception. In this paper, we present a distributed scheduling algorithm for peak age optimization in a wireless network where a number of sensor nodes attempt to deliver their sensed data to a data collector over a wireless channel. In particular, each sensor node accesses the channel for data delivery independently according to an adaptively tuned transmission probability. The beauty of our algorithm lies in that, even with neither centralized infrastructure nor coordinations among the sensor nodes, our algorithm asymptotically approximates the optimal solution by only a constant factor. We perform solid theoretical analysis and extensive simulations to verify the efficacy of our algorithm. To the best of our knowledge, it is the first fully distributed scheduling algorithm for AoI optimization in wireless networks.
In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfigur...
详细信息
ISBN:
(纸本)9781450375825
In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a global reconfiguration from a given initial network G(s). to a target network G(f). from a family of networks having some good properties, like small diameter. To formally capture costs associated with creating and maintaining connections, we define three reasonable edge-complexity measures: the total edge activations, the maximum activated edges per round, and the maximum activated degree of a node. We give (poly)log(n) time algorithms for the general task of transforming any G(s) into a G(f) of diameter (poly)log(n), while minimizing the edge-complexity. There is a natural trade-off between time and edge complexity. Our main lower bound shows that Omega(n) total edge activations and O(n/log n) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of Theta( log n) rounds. On the positive side, we give three distributed algorithms for our general task. The first runs in O( log n) time, with at most 2n active edges per round, a total of O(n log n) edge activations, a maximum degree n - 1, and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter O( log n) and uses O (n) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(n) then we can achieve a running time of o (log(2) n). This novel model of distributed computation and reconfiguration in actively dynamic networks and the proposed measures of the edge complexity of distributed algorithms, may open new avenues for research in the algorithmic theory of dynamic networks.
There is a recent exciting line of work in distributed graph algorithms in the CONGEST model that exploit expanders. All these algorithms so far are based on two tools: expander decomposition and expander routing. An ...
详细信息
ISBN:
(纸本)9781728196213
There is a recent exciting line of work in distributed graph algorithms in the CONGEST model that exploit expanders. All these algorithms so far are based on two tools: expander decomposition and expander routing. An (epsilon, phi)expander decomposition removes epsilon-fraction of the edges so that the remaining connected components have conductance at least phi, i.e., they are phi-expanders, and expander routing allows each vertex v in a phi-expander to very quickly exchange deg(v) messages with any other vertices, not just its local neighbors. In this paper, we give the first efficient deterministic distributed algorithms for both tools. We show that an (epsilon, phi)-expander decomposition can be deterministically computed in poly(epsilon(-1))n(o(1)) rounds for phi = poly(epsilon)n(-o(1)), and that expander routing can be performed deterministically in poly(phi(-1))n(o(1)) rounds. Both results match previous bounds of randomized algorithms by [Chang and Saranurak, PODC 2019] and [Ghaffari, Kuhn, and Su, PODC 2017] up to subpolynomial factors. Consequently, we derandomize existing distributed algorithms that exploit expanders. We show that a minimum spanning tree on n(-o(1))-expanders can be constructed deterministically in n(o(1)) rounds, and triangle detection and enumeration on general graphs can be solved deterministically in O(n(0.58)) and n(2/3+o(1)) rounds, respectively. Using similar techniques, we also give the first polylogarithmic-round randomized algorithm for constructing an (epsilon, phi)-expander decomposition in poly(epsilon(-1), log n) rounds for phi = 1/poly(epsilon(-1), log n). This algorithm is faster than the previous algorithm by [Chang and Saranurak, PODC 2019] in all regimes of parameters. The previous algorithm needs n(Omega(1)) rounds for any phi >= 1/poly log n.
暂无评论