检索结果-内蒙古大学图书馆

Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and graph computation Problems

ALGORITHMS 2025年第1期18卷 26-26页

作者： Kshemkalyani, Ajay D. Misra, Anshuman Univ Illinois Dept Comp Sci Chicago IL 60607 USA Purdue Univ Ft Wayne Dept Comp Sci Ft Wayne IN 46805 USA

This paper considers the solvability of several fundamental problems in asynchronous message-passing distributed systems in the presence of Byzantine processes using distributed algorithms. These problems are the following: mutual exclusion, global snapshot recording, termination detection, deadlock detection, predicate detection, causal ordering, spanning tree construction, minimum spanning tree construction, all-all shortest paths computation, and maximal independent set computation. In a distributed algorithm, each process has access only to its local variables and incident edge parameters. We show the impossibility of solving these fundamental problems by proving that they require a solution to the causality determination problem which has been shown to be unsolvable in asynchronous message-passing distributed systems.

关键词： Byzantine fault-tolerance "happened before" relation causality state observation synchronization graph computation distributed system asynchronous message-passing

来源：评论

学校读者我要写书评

暂无评论

graph computation based Power Flow for Large-Scale AC/DC System

Graph Computation based Power Flow for Large-Scale AC/DC Sys...

引用

International Conference on Power System Technology (POWERCON)

作者： Feng, Wei Yuan, Chen Dai, Renchang Liu, Guangyi Li, Fangxing GEIRINA Knoxville TN 37996 USA Univ Tennessee Knoxville TN 37996 USA GEIRINA San Jose CA 95143 USA

ISBN: (纸本)9781538664612

In this paper, a graph computation based power flow algorithm is introduced to solve large-scale AC/DC hybrid systems with multi LCC (Line Commuter Converter) based DC grids. The proposed approach is to improve the computational efficiency of constructing related matrices and getting power flow results without changing the conventional sequential iteration method. The hybrid system is modeled as a graph of vertices and edges with info of topology and parameters, thus local computation could be done independently for like formulating mismatch vectors of Delta P, Delta Q, Delta theta, Delta V and matrices of B', B '', only with parameters on its linked edges and adjacent vertices. Then by taking advantages of hierarchical parallel computing, the FDPF (fast decoupled power flow) of AC system, calculation of DC grids and mismatch comparing for each iteration of the sequential method could be done parallelly. This method is implemented on a graph database platform, and tested on IEEE 300-Bus, modified South Carolina 500-Bus system and a Chinese system to verify the accuracy and time-saving performance.

关键词： graph computation Large scale AC/DC systems Sequential Iteration

来源：评论

学校读者我要写书评

暂无评论

graph computation and Its Applications in Smart Grid 6

Graph Computation and Its Applications in Smart Grid

引用

IEEE 6th International Congress on Big Data (BigData Congress)

作者： Liu, Guangyi Liu, Kewen Shi, Di Zhu, Wendong Wang, Zhiwei Chen, Xi GEIRI North Amer Inc Santa Clara CA 95054 USA GEIRI Beijing 100192 Peoples R China

ISBN: (纸本)9781538619964

Smart grid is an important platform for the exploitation of renewable energy resources and maintaining/improving the reliability of power grid. Challenges have been identified during the construction of smart grid, which calls for novel simulation, computation and data management technologies. For example, as the size of power systems continue to increase, new computational tools are needed to co-simulate the transmission and distribution networks;new data processing and analytical technologies are required to handle big data in power systems;new database technologies are required to manage huge amounts of equipment, etc. To handle these challenges, a graph computation based framework is proposed. Initial investigation of this framework shows that graph computation is a promising technology for solving many of the challenges that arise during the development of smart grid.

关键词： graph data model graph computation Big data analytics Power flow algorithm Smart grid

来源：评论

学校读者我要写书评

暂无评论

A communication-reduced and computation-balanced framework for fast graph computation

引用

Frontiers of Computer Science 2018年第5期12卷 887-907页

作者： Yongli CHENG Fang WANG Hong JIANG Yu HUA Dan FENG Lingling ZHANG Jun ZHOU College of Mathematics and Computer Science FuZhou University Fuzhou 350116 China Wuhan National Laboratory for Optoelectronics School of Computer Science and Technology Huazhong University of Science and Technology Wuhan 430074 China Shenzhen Huazhong University of Science and Technology Research Institute Shenzhen 518300 China Department of Computer Science & Engineering University of Texas at Arlington Arlington TX 76019 USA

The bulk synchronous parallel （BSP） model is very user friendly for coding and debugging parallel graph algorithms. However, existing BSP-based distributed graphprocessing frameworks, such as Pregel, GPS and Giraph, routinely suffer from high communication costs. These high communication costs mainly stem from the fine-grained message-passing communication model. In order to address this problem, we propose a new computation model with low communication costs, called LCC-BSE We use this model to design and implement a high-performance distributed graphprocessing framework called LCC-graph. This framework eliminates high communication costs in existing distributed graph-processing frameworks. Moreover, LCC-graph also balances the computation workloads among all compute nodes by optimizing graph partitioning, significantly reducing the computation time for each superstep. Evaluation of LCC-graph on a 32-node cluster, driven by real-world graph datasets, shows that it significantly outperforms existing distributed graph-processing frameworks in terms of runtime, particularly when the system is supported by a highbandwidth network. For example, LCC-graph achieves an order of magnitude performance improvement over GPS and graphLab.

关键词： graph computation communication decrease computation balance

来源：评论

学校读者我要写书评

暂无评论

Using High-Bandwidth Networks Efficiently for Fast graph computation

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2019年第5期30卷 1170-1183页

作者： Cheng, Yongli Jiang, Hong Wang, Fang Hua, Yu Feng, Dan Guo, Wenzhong Wu, Yunxiang Fuzhou Univ Coll Math & Comp Sci Fuzhou 350016 Fujian Peoples R China Univ Texas Arlington Dept Comp Sci & Engn Arlington TX 76019 USA Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan Natl Lab Optoelect Wuhan 430074 Hubei Peoples R China

Nowadays, high-bandwidth networks are more easily accessible than ever before. However, existing distributed graph-processing frameworks, such as GPS, fail to efficiently utilize the additional bandwidth capacity in these networks for higher performance, due to their inefficient computation and communication models, leading to very long waiting times experienced by users for the graph-computing results. The root cause lies in the fact that the computation and communication models of these frameworks generate, send and receive messages so slowly that only a small fraction of the available network bandwidth is utilized. In this paper, we propose a high-performance distributed graph-processing framework, called BlitzG, to address this problem. This framework fully exploits the available network bandwidth capacity for fast graph processing. Our approach aims at significant reduction in (i) the computation workload of each vertex for fast message generation by using a new slimmed-down vertex-centric computation model and (ii) the average message overhead for fast message delivery by designing a light-weight message-centric communication model. Evaluation on a 40Gbps Ethernet, driven by real-world graph datasets, shows that BlitzG outperforms GPS by up to 27x with an average of 20.7x.

关键词： graph computation high-bandwidth networks high performance computation model communication model

来源：评论

学校读者我要写书评

暂无评论

VENUS: A System for Streamlined graph computation on a Single PC

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2016年第8期28卷 2230-2245页

作者： Liu, Qin Cheng, Jiefeng Li, Zhenguo Lui, John C. S. Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China Huawei Noahs Ark Lab Hong Kong Hong Kong Peoples R China

Recent studies show that disk-based graph computation systems on just a single PC can be as highly competitive as cluster-based systems on large-scale problems. Inspired by this remarkable progress, we develop VENUS, a disk-based graph computation system which is able to handle billion-scale graphs efficiently on a commodity PC. VENUS adopts a novel computing architecture that features vertex-centric "streamlined" processing-the graph is sequentially loaded and an update function is executed for each vertex in parallel on the fly. VENUS deliberately avoids loading batch edge data by separating read-only structure data from mutable vertex data on disk, and minimizes random IOs by caching vertex data in the main memory whenever possible. The streamlined processing is realized with efficient sequential scan over massive structure data and fast feeding the update function for a large number of vertices. Extensive evaluation on large real-world and synthetic graphs has demonstrated the efficiency of VENUS. For example, to run the PageRank algorithm on a Twitter graph of 42 million vertices and 1.4 billion edges, Spark needs 8.1 minutes with 50 machines and graphChi spends 13 minutes using high-speed SSD, while VENUS only takes 5 minutes on one machine with an ordinary hard disk.

关键词： graph computation disk-based computing vertex-centric streamlined processing

来源：评论

学校读者我要写书评

暂无评论

A highly cost-effective task scheduling strategy for very large graph computation

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2018年 89卷 698-712页

作者： Cheng, Yongli Wang, Fang Jiang, Hong Hua, Yu Feng, Dan Wu, Yunxiang Zhu, Tingwei Guo, Wenzhong Fuzhou Univ Coll Math & Comp Sci Fuzhou Fujian Peoples R China Huazhong Univ Sci & Technol Sch Comp Wuhan Hubei Peoples R China Univ Texas Arlington Dept Comp Sci & Engn Arlington TX 76019 USA Min Educ Key Lab Spatial Data Min & Info Sharing Fuzhou Fujian Peoples R China Fuzhou Univ Fujian Prov Key Lab Network Comp & Intelligent In Fuzhou Fujian Peoples R China

Existing distributed graph-processing frameworks, e.g., Pregel, GPS and Giraph, handle large-scale graphs in the memory of clusters built of commodity compute nodes for better scalability and performance. While capable of scaling out according to the size of graphs up to thousands of compute nodes, for graphs beyond a certain size, these frameworks would usually require investments of machines that are either beyond the financial capability of or unprofitable for most small and medium-sized organizations, making the deployment of their large-scale graph-computing jobs difficult if not impossible. At the other end of the spectrum of graph-processing frameworks research, the single-node disk-based graph-computing frameworks, such as graphChi and XStream, handle large-scale graphs on just one commodity computer, leading to high efficiency in the use of hardware but at the cost of low user performance and limited scalability. Motivated by this dichotomy, in this paper we propose a pipeline-based task scheduling strategy with high cost-effectiveness. We use this scheduling strategy to design and implement a distributed disk-based graph-processing framework, called DD-graph, that can process very large graphs with trillions of edges on a small cluster while achieving the high performance of existing distributed in-memory graph-processing frameworks. The evaluation of DD-graph prototype, driven by very large graph datasets, shows that it saves 73% of GPS' hardware costs while running 1.34x faster than GPS. (C) 2018 Elsevier B.V. All rights reserved.

关键词： graph computation Cost-effectiveness Very large graphs

来源：评论

学校读者我要写书评

暂无评论

PAGE: A Partition Aware Engine for Parallel graph computation

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2015年第2期27卷 518-530页

作者： Shao, Yingxia Cui, Bin Ma, Lin Peking Univ Sch EECS Key Lab High Confidence Software Technol MOE Beijing Peoples R China

graph partition quality affects the overall performance of parallel graph computation systems. The quality of a graph partition is measured by the balance factor and edge cut ratio. A balanced graph partition with small edge cut ratio is generally preferred since it reduces the expensive network communication cost. However, according to an empirical study on Giraph, the performance over well partitioned graph might be even two times worse than simple random partitions. This is because these systems only optimize for the simple partition strategies and cannot efficiently handle the increasing workload of local message processing when a high quality graph partition is used. In this paper, we propose a novel partition aware graph computation engine named PAGE, which equips a new message processor and a dynamic concurrency control model. The new message processor concurrently processes local and remote messages in a unified way. The dynamic model adaptively adjusts the concurrency of the processor based on the online statistics. The experimental evaluation demonstrates the superiority of PAGE over the graph partitions with various qualities.

关键词： graph computation graph partition message processing

来源：评论

学校读者我要写书评

暂无评论

PowerLyra: Differentiated graph computation and Partitioning on Skewed graphs

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2018年第3期5卷 13.1-13.39页

作者： Chen, Rong Shi, Jiaxin Chen, Yanzhe Zang, Binyu Guan, Haibing Chen, Haibo Shanghai Jiao Tong Univ Inst Parallel & Distributed Syst 800 Dongchuan Rd Shanghai 200240 Peoples R China

Natural graphs with skewed distributions raise unique challenges to distributed graph computation and partitioning. Existing graph-parallel systems usually use a "one-size-fits-all" design that uniformly processes all vertices, which either suffer from notable load imbalance and high contention for high-degree vertices (e.g., Pregel and graphLab) or incur high communication cost and memory consumption even for low-degree vertices (e.g., Powergraph and graphX). In this article, we argue that skewed distributions in natural graphs also necessitate differentiated processing on high-degree and low-degree vertices. We then introduce PowerLyra, a new distributed graph processing system that embraces the best of both worlds of existing graph-parallel systems. Specifically, PowerLyra uses centralized computation for low-degree vertices to avoid frequent communications and distributes the computation for high-degree vertices to balance workloads. PowerLyra further provides an efficient hybrid graph partitioning algorithm (i.e., hybrid-cut) that combines edge-cut (for low-degree vertices) and vertex-cut (for high-degree vertices) with heuristics. To improve cache locality of inter-node graph accesses, PowerLyra further provides a locality-conscious data layout optimization. PowerLyra is implemented based on the latest graphLab and can seamlessly support various graph algorithms running in both synchronous and asynchronous execution modes. A detailed evaluation on three clusters using various graph-analytics andMLDM (Machine Learning and DataMining) applications shows that PowerLyra outperforms Powergraph by up to 5.53X (from 1.24X) and 3.26X (from 1.49X) for real-world and synthetic graphs, respectively, and is much faster than other systems like graphX and Giraph, yet with much less memory consumption. A porting of hybrid-cut to graphX further confirms the efficiency and generality of PowerLyra.

关键词： graph computation graph partitioning power-law degree distribution skewed graph locality-conscious data layout

来源：评论

学校读者我要写书评

暂无评论

A graph computation based Sequential Power Flow Calculation for Large-Scale AC/DC Systems

A Graph Computation based Sequential Power Flow Calculation ...

引用

IEEE-Power-and-Energy-Society General Meeting (PESGM)

作者： Feng, Wei Wu, Jingjin Yuan, Chen Liu, Guangyi Dai, Renchang Shi, Qingxin Li, Fangxing GEIRI North Amer Inc Santa Clara CA 95134 USA Univ Tennessee Dept Elect Engn & Comp Sci Knoxville TN USA

ISBN: (纸本)9781728119816

This paper proposes a graph computation based sequential power flow calculation method for Line Commutated Converter (LCC) based large-scale AC/DC systems to achieve a high computing performance. Based on the graph theory, the complex AC/DC system is first converted to a graph model and stored in a graph database. Then, the hybrid system is divided into several isolated areas with graph partition algorithm by decoupling AC and DC networks. Thus, the power flow analysis can be executed in parallel for each independent area with the new selected slack buses. Furthermore, for each area, the node-based parallel computing (NPC) and hierarchical parallel computing (HPC) used in graph computation are employed to speed up fast decoupled power flow (FDPF). Comprehensive case studies on the IEEE 300-bus, polished South Carolina 12,000-bus system and a China 11,119-bus system are performed to demonstrate the accuracy and efficiency of the proposed method.

关键词： graph computation sequential method AC/DC system parallel computing graph partition

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：