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

Conic Formation in Presence of Faulty Robots 1

16th International Symposium on algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)

作者： Pattanayak, Debasish Foerster, Klaus-Tycho Mandal, Partha Sarathi Schmid, Stefan IIT Guwahati Dept Math Gauhati India Univ Vienna Fac Comp Sci Vienna Austria

ISBN: (数字)9783030624019

ISBN: (纸本)9783030624002;9783030624019

Pattern formation is one of the most fundamental problems in distributed computing, which has recently received much attention. In this paper, we initiate the study of distributed pattern formation in situations when some robots can be faulty. In particular, we consider the well-established look-compute-move model with oblivious, anonymous robots. We first present lower bounds and show that any deterministic algorithm takes at least two rounds to form simple patterns in the presence of faulty robots. We then present distributed algorithms for our problem which match this bound, for conic sections: in at most two rounds, robots form lines, circles and parabola tolerating f = 2, 3 and 4 faults, respectively. For f = 5, the target patterns are parabola, hyperbola and ellipse. We show that the resulting pattern includes the f faulty robots in the pattern of n robots, where n >= 2f + 1, and that f < n < 2f + 1 robots cannot form such patterns. We conclude by discussing several relaxations and extensions.

关键词： distributed algorithms Pattern formation Conic formation Fault tolerance Oblivious mobile robots

来源：评论

学校读者我要写书评

暂无评论

Parallel State Machine Replication from Generalized Consensus 39

Parallel State Machine Replication from Generalized Consensu...

引用

39th International Symposium on Reliable distributed Systems (SRDS)

作者： Ceolin Junior, Tarcisio Dotti, Fernando Pedone, Fernando Pontificia Univ Catolica Rio Grande do Sul Escola Politecn Porto Alegre RS Brazil Univ Fed Santa Maria Santa Maria RS Brazil Univ Svizzera Italiana Lugano Switzerland

ISBN: (纸本)9781728176260

State machine replication (SMR) is a established approach to building fault-tolerant services. In search for high SMR throughput, approaches that exploit semantic information in the ordering and execution of commands have emerged. Generalized consensus and parallel state machine replication are two representative examples, respectively. Although both approaches have been proved effective in isolation, no study in the literature has considered their integration. In this paper, we investigate the integration of generalized consensus and parallel SMR. We derive algorithms to parallelize the execution of commands based on the ordering of commands provided by consensus. As a prototype, we extended Egalitarian Paxos and conducted many experiments varying conflict rates, command computational costs, and number of cores at replicas. Compared to Egalitarian Paxos, the integrated approach (a) results in important throughput gains, as command independency and computational cost increase, and (b) converges to the same performance with high conflict rates or reduced number of cores.

关键词： State Machine Replication Generalized Consensus distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A scalable graph generation algorithm to sample over a given shell distribution 34

A scalable graph generation algorithm to sample over a given...

引用

34th IEEE International Parallel and distributed Processing Symposium (IPDPS)

作者： Ozkaya, M. Yusuf Balin, M. Fatih Pinar, Ali Catalyurek, Umit, V Georgia Inst Technol Sch Computat Sci & Engn Atlanta GA 30332 USA Sandia Natl Labs Livermore CA USA

ISBN: (纸本)9781728174457

Graphs are commonly used to model the relationships between various entities. These graphs can be enormously large and thus, scalable graph analysis has been the subject of many research efforts. To enable scalable analytics, many researchers have focused on generating realistic graphs that support controlled experiments for understanding how algorithms perform under changing graph features. Significant progress has been made on scalable graph generation which preserve some important graph properties (e.g., degree distribution, clustering coefficients). In this paper, we study how to sample a graph from the space of graphs with a given shell distribution. Shell distribution is related to the k-core, which is the largest subgraph where each vertex is connected to at least k other vertices. A k-shell is the subset of vertices that are in k-core but not (k + 1)-core, and the shell distribution comprises the sizes of these shells. Core decompositions are widely used to extract information from graphs and to assist other computations. We present a scalable shared and distributed memory graph generator that, given a shell decomposition, generates a random graph that conforms to it. Our extensive experimental results show the efficiency and scalability of our methods. Our algorithm generates 2(33) vertices and 2(37) edges in less than 50 seconds on 384 cores.(1)

关键词： graph generation scalable graph algorithms distributed algorithms shared memory

来源：评论

学校读者我要写书评

暂无评论

distributed convergence to Nash equilibria in network and average aggregative games

引用

AUTOMATICA 2020年 117卷 108959-108959页

作者： Parise, Francesca Grammatico, Sergio Gentile, Basilio Lygeros, John MIT Lab Informat & Decis Syst Cambridge MA 02139 USA Delft Univ Technol Delft Ctr Syst & Control Delft Netherlands Circuit Mind Ltd London England Swiss Fed Inst Technol Automat Control Lab Zurich Switzerland

We consider network aggregative games where each player minimizes a cost function that depends on its own strategy and on a convex combination of the strategies of its neighbors. As a first contribution, we propose a class of distributed algorithms that can be used to steer the strategies of the rational agents to a Nash equilibrium configuration, with guaranteed convergence under different sufficient conditions depending on the cost functions and on the network. A distinctive feature of the proposed class of algorithms is that agents use optimal responses instead of gradient type of strategy updates. As a second contribution, we show that the algorithm suggested for network aggregative games can also be used to recover a Nash equilibrium of average aggregative games (i.e., games where each agent is affected by the average of the strategies of the whole population) in a distributed fashion, that is, without requiring a central coordinator. We apply our theoretical results to multi-dimensional, convex-constrained opinion dynamics and to demand-response schemes for energy management. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Deterministic aggregative games Best response dynamics distributed algorithms Multi-agent systems

来源：评论

学校读者我要写书评

暂无评论

Fast Byzantine Gathering with Visibility in Graphs 1

引用

16th International Symposium on algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)

作者： Miller, Avery Saha, Ullash Univ Manitoba Winnipeg MB Canada

ISBN: (数字)9783030624019

ISBN: (纸本)9783030624002;9783030624019

We consider the gathering task by a team of m synchronous mobile robots in a graph of n nodes. Each robot has an identifier (ID) and runs its own deterministic algorithm, i.e., there is no centralized coordinator. We consider a particularly challenging scenario: there are f Byzantine robots in the team that can behave arbitrarily, and even have the ability to change their IDs to any value at any time. There is no way to distinguish these robots from non-faulty robots, other than perhaps observing strange or unexpected behaviour. The goal of the gathering task is to eventually have all non-faulty robots located at the same node in the same round. It is known that no algorithm can solve this task unless there at least f + 1 non-faulty robots in the team. In this paper, we design an algorithm that runs in polynomial time with respect to n and m that matches this bound, i.e., it works in a team that has exactly f + 1 non-faulty robots. In our model, we have equipped the robots with sensors that enable each robot to see the subgraph (including robots) within some distance H of its current node. We prove that the gathering task is solvable if this visibility range H is at least the radius of the graph, and not solvable if H is any fixed constant.

关键词： Robot gathering Byzantine faults Visibility Graphs distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Local Medium Access 20

Efficient Local Medium Access

引用

32nd ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Garncarek, Pawel Jurdzinski, Tomasz Kowalski, Dariusz R. Univ Wroclaw Wroclaw Poland Augusta Univ Augusta GA USA SWPS Univ Warsaw Poland

ISBN: (纸本)9781450369350

Shah, Shin and Tetali [25] initiated the study of queuing systems on the medium access channel with arbitrary interference graph. The graph models dependencies between the channel members - any two connected by an edge are dependent. This problem could be also re-stated as a query system with dependent elements or local scheduling of dependent packets/jobs. In short, if two dependent units, also called stations, want to transmit (or be in the same query, or do jobs in parallel), there is a conflict and none of them succeeds. The problem is particularly challenging, if the units need to make their decisions locally, without any coordination. Prior the paper by Shah, Shin and Tetali [FOCS 2011], the main focus was on the clique graph - even in this simple topology, many problems related to stability remain open. While the solution by Shah, Shin and Tetali [FOCS 2011] is semi-local, as nodes make use of information about interfering neighbors in the graph, we provide the first purely local stable algorithms. In particular, in our algorithms stations make their decision whether to transmit or not based only on looking at their local queues. Based only on this feature, and without using a priori knowledge of topology, we design an algorithm that allows all stations for implicit transferring information to and from all other stations. We use it as a tool for developing universally stable algorithms for the problem of queuing messages - i.e., guaranteeing bounded queues when, on average, less than one independent set is injected per round. The first one is stable in adversarial (worst-case) sense, the second one - in stochastic sense (average-case). We also prove optimality of our algorithm in adversarial sense: no algorithm can be stable against injections with rate rho = 1 (when, on average, one independent set is injected per round). Moreover, for the class of non-adaptive protocols, we show that it is not possible to achieve stability for any injection rate omega (1/lo

关键词： local queuing shared channel multiple-access channel adversarial packet arrivals stability distributed algorithms deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed OPF Algorithm for System-Level Control of Active Multi-Terminal DC Distribution Grids

引用

IEEE ACCESS 2020年 8卷 136638-136654页

作者： Korompili, Asimenia Pandis, Petros Monti, Antonello Rhein Westfal TH Aachen EON Energy Res Ctr Inst Automat Complex Power Syst D-52074 Aachen Germany

This paper presents a distributed optimal power flow (OPF) algorithm for the system-level control of multi-terminal DC (MTDC) distribution grids with distributed energy resources (DER). At each control period, the algorithm updates the nominal voltage and power set-points of the DER-interfacing converters, which operate according to active network management (ANM) concepts. To achieve this, the OPF problem, in its nodal formulation, includes power dispatch strategies for diverse DER according to their technical characteristics, which change during the system operation. This multi-objective OPF-for-ANM problem is solved by distributed control units (DCUs) according to the distributed algorithm for the alternating direction method of multipliers (ADMM). All DCUs have identical roles in the distributed control structure and thus the distributed OPF-for-ANM algorithm is highly modular. Simulation results in different IEEE standard systems and various scenarios demonstrate that the algorithm is fast and scalable, irrespective of the number and location of integrated DER, as well as the operating condition of the system. The convergence speed of the algorithm is analysed considering the computation and communication time needed for its execution. The online application in a computers cluster demonstrates the fast execution of the developed algorithm in a physically-distributed implementation. Through the proposed OPF-for-ANM algorithm, the system-level control can dispatch fast diverse DER in different coordination approaches in a distributed manner.

关键词： distributed algorithms Decentralized control Voltage control Load flow Communication networks distributed control power system control DC-DC converters optimisation methods distributed power generation energy resources

来源：评论

学校读者我要写书评

暂无评论

Fast and Parallelizable Ranking with Outliers from Pairwise Comparisons

Fast and Parallelizable Ranking with Outliers from Pairwise ...

引用

European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD)

作者： Im, Sungjin Qaem, Mahshid Montazer Univ Calif EECS 5200 N Lake Rd Merced CA 95343 USA

ISBN: (纸本)9783030461508;9783030461492

In this paper, we initiate the study of the problem of ordering objects from their pairwise comparison results when allowed to discard up to a certain number of objects as outliers. More specifically, we seek to find an ordering under the popular Kendall tau distance measure, i.e., minimizing the number of pairwise comparison results that are inconsistent with the ordering, with some outliers removed. The presence of outliers challenges the assumption that a global consistent ordering exists and obscures the measure. This problem does not admit a polynomial time algorithm unless NP. BPP, and therefore, we develop approximation algorithms with provable guarantees for all inputs. Our algorithms have running time and memory usage that are almost linear in the input size. Further, they are readily adaptable to run on massively parallel platforms such as MapReduce or Spark.

关键词： Rank aggregation Outliers Approximation distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving Billion-Scale Knapsack Problems 20

Solving Billion-Scale Knapsack Problems

引用

29th World Wide Web Conference (WWW)

作者： Zhang, Xingwen Qi, Feng Hua, Zhigang Yang, Shuang Ant Financial Serv Grp San Mateo CA 94402 USA

ISBN: (纸本)9781450370233

Knapsack problems (KPs) are common in industry, but solving KPs is known to be NP-hard and has been tractable only at a relatively small scale. This paper examines KPs in a slightly generalized form and shows that they can be solved nearly optimally at scale via distributed algorithms. The proposed approach can be implemented fairly easily with off-the-shelf distributed computing frameworks (e.g. MPI, Hadoop, Spark). As an example, our implementation leads to one of the most efficient KP solvers known to date - capable to solve KPs at an unprecedented scale (e.g., KPs with 1 billion decision variables and 1 billion constraints can be solved within 1 hour). The system has been deployed to production and called on a daily basis, yielding significant business impacts at Ant Financial.

关键词： Knapsack Problems Large-scale Optimization distributed algorithms MapReduce Dual Descent Synchronous Coordinate Descent

来源：评论

学校读者我要写书评

暂无评论

Caching Policies for Delay Minimization in Small Cell Networks with Joint Transmissions

Caching Policies for Delay Minimization in Small Cell Networ...

引用

IEEE International Conference on Communications (IEEE ICC) / Workshop on NOMA for 5G and Beyond

作者： Ricardo, Guilherme Neglia, Giovanni Spyropoulos, Thrasyvoulos Univ Cote dAzur INRIA Sophia Antipolis France EURECOM Commun Syst Dept Sophia Antipolis France

ISBN: (纸本)9781728150895

In 5G and beyond network architectures, operators and content providers base their content distribution strategies on Heterogeneous Networks, where macro and small(er) cells are combined to offer better Quality of Service (QoS) to wireless users. On top of such networks, edge caching and Coordinated Multi-Point (CoMP) transmissions are used to further improve performance. The problem of optimally utilizing the cache space in dense and heterogeneous cell networks has been extensively studied under the name of "FemtoCaching." However, related literature usually assumes relatively simple physical layer (PHY) setups and known or stationary content popularity. In this paper, we address these issues by proposing a class of fully distributed and dynamic caching algorithms that take advantage of CoMP capabilities towards minimizing PHY-aware metrics, such as end-to-end (E2E) delay. Our policies outperform existing dynamic solutions that are PHY-unaware, under both synthetic and real (non-stationary) request processes, and converge to efficient centralized solutions, in static setups.

关键词： Edge caching joint transmission CoMP heterogeneous cellular networks distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：