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

IEEE 35th International Conference on Data Engineering (ICDE)

作者： Sun, Shixuan Che, Yulin Wang, Lipeng Luo, Qiong Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China

ISBN: (纸本)9781538674741

Subgraph enumeration finds all subgraphs in an unlabeled graph that are isomorphic to another unlabeled graph. Existing depth-first search (DFS) based algorithms work on a single machine, but they are slow on large graphs due to the large search space. In contrast, distributed algorithms on clusters adopt a parallel breadth-first search (BFS) and improve the performance at the cost of large amounts of hardware resources, since the BFS approach incurs expensive data transfer and space cost due to the exponential number of intermediate results. In this paper, we develop an efficient parallel subgraph enumeration algorithm for a single machine, named LIGHT. Our algorithm reduces redundant computation in DFS by deferring the materialization of pattern vertices until necessary and converting the candidate set computation into finding a minimum set cover. Moreover, we parallelize our algorithm with both SIMD (Single-Instruction-Multiple-Data) instructions and SMT (Simultaneous Multi-Threading) technologies in modern CPUs. Our experimental results show that LIGHT running on a single machine outperforms existing single-machine DFS algorithms by more than three orders of magnitude, and is up to two orders of magnitude faster than the state-of-the-art distributed algorithms running on 12 machines. Additionally, LIGHT completed all test cases, whereas the existing algorithms fail in some cases due to either running out of time or running out of available hardware resources.

关键词： distributed algorithms Parallel processing Clustering algorithms Hardware Computational modeling Conferences Data engineering

来源：评论

学校读者我要写书评

暂无评论

Silent Self-Stabilizing Scheme for Spanning-Tree-like Constructions 19

Silent Self-Stabilizing Scheme for Spanning-Tree-like Constr...

引用

20th International Conference on distributed Computing and Networking (ICDCN)

作者： Devismes, Stephane Ilcinkas, David Johnen, Colette Univ Grenoble Alpes CNRS Grenoble INP VERIMAGInst Engn Grenoble France CNRS Talence France Univ Bordeaux LaBRI UMR 5800 Talence France Univ Bordeaux LaBRI UMR 5800 CNRS Talence France

ISBN: (纸本)9781450360944

In this paper, we propose a general scheme, called Algorithm STlC, to compute spanning-tree-like data structures on arbitrary networks. STlC is self-stabilizing and silent and, despite its generality, is also efficient. It is written in the locally shared memory model with composite atomicity assuming the distributed unfair daemon, the weakest scheduling assumption of the model. Its stabilization time is in O(n(maxCC)) rounds, where n(maxCC) is the maximum number of processes in a connected component. We also exhibit polynomial upper bounds on its stabilization time in steps and process moves holding for large classes of instantiations of Algorithm STlC. We illustrate the versatility of our approach by proposing several such instantiations that efficiently solve classical problems such as leader election, as well as, unconstrained and shortest-path spanning tree constructions.

关键词： distributed algorithms self-stabilization spanning tree leader election spanning forest

来源：评论

学校读者我要写书评

暂无评论

FORGIVE & FORGET Self-Stabilizing Swarms in Spite of Byzantine Robots 7

FORGIVE & FORGET Self-Stabilizing Swarms in Spite of Byzanti...

引用

7th International Symposium on Computing and Networking (CANDAR)

作者： Ashkenazi, Yotam Dolev, Shlomi Kamei, Sayaka Ooshita, Fukuhito Wada, Koichi Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Hiroshima Univ Grad Sch Engn Dept Informat Engn Grad Hiroshima Japan Nara Inst Sci & Technol Grad Sch Sci & Technol Nara Japan Hosei Univ Fac Sci & Engn Dept Appl Informat Tokyo Japan

ISBN: (纸本)9781728152684

In this paper, we consider the case in which a swarm of robots collaborates in a mission, where a few of the robots behave maliciously. These malicious Byzantine robots may be temporally or constantly controlled by an adversary. The scope is synchronized full information robot operations, where a robot that does not follow the program/policy of the swarm is immediately identified and can be remembered as Byzantine. As robots may be suspected of being Byzantine due to benign temporal malfunctions, it is imperative to forgive and forget, otherwise, a robot cannot assume collaborative actions with any other robot in the swarm. Still, remembering for a while may facilitate a policy of surrounding, isolating and freezing the movement of the misbehaving robots, by several robots, allowing the rest to perform the swarm task with no intervention. We demonstrate the need to periodically forgive and forget to realize swarm several tasks including patrolling/cleaning in the presence of possible Byzantine robots. The policy for achieving the task consists of blocking the movement of the Byzantine robot(s) by some of the robots, while the rest patrol/clean the plane. We present and use self-stabilizing (non-two faced) Byzantine pulse and clock synchronizations that are of independent interest.

关键词： Byzantine robots self-stabilizing algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Partitioned Big-Data Optimization via Asynchronous Dual Decomposition

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2018年第4期5卷 1910-1919页

作者： Notarnicola, Ivano Carli, Ruggero Notarstefano, Giuseppe Univ Salento Dept Engn I-73100 Lecce Italy Univ Padua Dept Informat Engn I-35131 Padua Italy

In this paper, we consider a novel partitioned framework for distributed optimization in peer-to-peer networks. In several important applications, the agents of a network have to solve an optimization problem with two key features: i) the dimension of the decision variable depends on the network size, and ii) cost function and constraints have a sparsity structure related to the communication graph. For this class of problems, a straightforward application of existing consensus methods would show two inefficiencies: poor scalability and redundancy of shared information. We propose an asynchronous distributed algorithm, based on dual decomposition and coordinate methods, to solve partitioned optimization problems. We show that by exploiting the problem structure, the solution can be partitioned among the nodes, so that each node just stores a local copy of a portion of the decision variable (rather than a copy of the entire decision vector) and solves a small-scale local problem.

关键词： Asynchronous algorithms big-data optimization distributed algorithms distributed optimization optimization methods

来源：评论

学校读者我要写书评

暂无评论

Proportional Fair RAT Aggregation in HetNets 31

Proportional Fair RAT Aggregation in HetNets

引用

31st International Teletraffic Congress (ITC)

作者： Aryafar, Ehsan Keshavarz-Haddad, Alireza Joe-Wong, Carlee Portland State Univ Portland OR 97207 USA Shiraz Univ Shiraz Iran Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9780988304574

Heterogeneity in wireless network architectures (i.e., the coexistence of 3G, LTE, 5G, WiFi, etc.) has become a key component of current and future generation cellular networks. Simultaneous aggregation of each client's traffic across multiple such radio access technologies (RATs) / base stations (BSs) can significantly increase the system throughput, and has become an important feature of cellular standards on multi-RAT integration. distributed algorithms that can realize the full potential of this aggregation are thus of great importance to operators. In this paper, we study the problem of resource allocation for multi-RAT traffic aggregation in HetNets (heterogeneous networks). Our goal is to ensure that the resources at each BS are allocated so that the aggregate throughput achieved by each client across its RATs satisfies a proportional fairness (PF) criterion. In particular, we provide a simple distributed algorithm for resource allocation at each BS that extends the PF allocation algorithm for a single BS. Despite its simplicity and lack of coordination across the BSs, we show that our algorithm converges to the desired PF solution and provide (tight) bounds on its convergence speed. We also study the characteristics of the optimal solution and use its properties to prove the optimality of our algorithm's outcomes.

关键词： Resource management Throughput Radio access technologies Long Term Evolution Wireless fidelity Convergence distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Controllers Seeking AC Optimal Power Flow Solutions Using ADMM

引用

IEEE TRANSACTIONS ON SMART GRID 2018年第5期9卷 4525-4537页

作者： Zhang, Yijian Hong, Mingyi Dall'Anese, Emiliano Dhople, Sairaj V. Xu, Zi Iowa State Univ Dept Ind & Mfg Syst Engn Ames IA 50011 USA Natl Renewable Energy Lab Golden CO 80401 USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA Shanghai Univ Dept Math Shanghai 200444 Peoples R China

This paper focuses on power distribution systems with inverter-interfaced renewable energy sources (RESs), and develops a distributed control framework to steer the RES output powers to solutions of ac optimal power flow (OPF) problems. The design of the distributed control algorithm is based on suitable linear approximation of the ac power-flow equations, and leverages the so-called alternating direction method of multipliers (ADMM). Convergence of the RES-inverter output powers to solutions of the approximate ac OPF problem is established under suitable conditions on the mismatches between the commanded setpoints and actual RES output powers. Overall, since the proposed scheme can be cast as an ADMM with inexact primal and dual updates, the convergence results can be applied to more general distributed optimization settings.

关键词： ADMM distribution systems distributed algorithms optimal power flow renewable energy sources

来源：评论

学校读者我要写书评

暂无评论

FMAP: A platform for the development of distributed multi-agent planning systems

引用

KNOWLEDGE-BASED SYSTEMS 2018年 145卷 166-168页

作者： Torreno, Alejandro Sapena, Oscar Onaindia, Eva Univ Politecn Valencia Camino de Vera S-N Valencia 46010 Spain

The development of cooperative Multi-Agent Planning (MAP) solvers in a distributed context encompasses the design and implementation of decentralized algorithms that make use of multi-agent communication protocols. In this paper, we present FMAP, a platform aimed at developing distributed MAP solvers such as MAP-POP, FMAP and MH-FMAP, among others. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Multi-agent planning distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Data Mining algorithms Parallelization in Logic Programming Framework for Execution in Cluster 19th

Data Mining Algorithms Parallelization in Logic Programming ...

引用

19th International Conference on Next Generation Teletraffic and Wired/Wireless Advanced Networks and Systems (NEW2AN) / 12th Conference on the Internet of Things and Smart Spaces ruSMART (Are You Smart)

作者： Malov, Aleksey Rodionov, Sergey Shorov, Andrey St Petersburg Electrotech Univ LETI St Petersburg Russia

This article describes an approach to parallelizing of data mining algorithms in logical programming framework, for distributed data processing in cluster. As an example Naive Bayes algorithm implementation in Prolog ... 详细信息

ISBN: (纸本)9783030308599;9783030308582

关键词： Parallel algorithms distributed algorithms Data mining distributed data mining MapReduce Logical programming

来源：评论

学校读者我要写书评

暂无评论

Towards the Locality of Vizing's Theorem 2019

Towards the Locality of Vizing's Theorem

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Su, Hsin-Hao Vu, Hoa T. Boston Coll Chestnut Hill MA 02167 USA

ISBN: (纸本)9781450367059

Vizing showed that it suffices to color the edges of a simple graph using Delta + 1 colors, where Delta is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithm is known for obtaining such coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Delta + (Theta) over tilde(root Delta))-edge-coloring algorithm that runs in polylog( n) rounds by Chang et al. [SODA 2018] and the deterministic (Delta + polylog(n))-edge-coloring algorithm that runs in poly(Delta, log n) rounds by Ghaffari et al. [STOC 2018]. We present two distributed edge-coloring algorithms that run in poly(Delta, log n) rounds. The first algorithm, with randomization, uses only Delta + 2 colors. The second algorithm is a deterministic algorithm that uses Delta + O(log n/log log n) colors. Our approach is to reduce the distributed edge-coloring problem into an online and restricted version of balls-into-bins problem. If l is the maximum load of the bins, our algorithm uses Delta + 2l - 1 colors. We show how to achieve l = 1 with randomization and l = O(log n/log log n) without randomization.

关键词： distributed algorithms edge coloring randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Random Gossip Processes in Smartphone Peer-to-Peer Networks 15

Random Gossip Processes in Smartphone Peer-to-Peer Networks

引用

15th Annual International Conference on distributed Computing in Sensor Systems (DCOSS)

作者： Newport, Calvin Weaver, Alex Georgetown Univ Washington DC 20057 USA

ISBN: (纸本)9781728105703

In this paper, we study random gossip processes in communication models that describe the peer-to-peer networking functionality included in standard smartphone operating systems. These processes are well-understood in standard peer-to-peer network models, but little is known about their behavior in models that abstract the smartphone peer-to-peer setting. With this in mind, we begin by studying a simple random gossip process in the synchronous mobile telephone model (the most common abstraction used to study smartphone peer-to-peer systems). We prove that the simple process is actually more efficient than the best-known gossip algorithm in the mobile telephone model, which required complicated coordination among the nodes in the network. We then introduce a novel variation of the mobile telephone model that removes the synchronized round assumption, shrinking the gap between theory and practice. We prove that simple random gossip processes still converge in this setting and that information spreading still improves along with graph connectivity.

关键词： gossip distributed algorithms peer-to-peer networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：