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

IEEE 11th Annual Computing and Communication Workshop and Conference (CCWC)

作者： Hovhannisyan, Narek Amer Univ Armenia Comp & Informat Sci Yerevan Armenia

ISBN: (纸本)9781665414906

Efficient data representation and secure communication are both crucial problems in the modern world. Those problems are both actual in the distributed context as well. In this article we focus on forest decomposition of graphs in distributed networks in order to impact those two problems. Currently, there are several existing algorithms that decompose generic or restricted graph instances with both bounded degree or arboricity into edge-disjoint forests with sublogarithmic running time. We propose a modification of an algorithm that was already devised before, such that it is possible to implement the algorithm and conduct an experiment over simulated graph instances from different graph families. Finally, we compare achieved experimental results with theoretical estimates. We also discuss the application of the algorithm for solving the problem of efficient graph representation and secure data communication in distributed networks. More specifically, the impact of the algorithm on implementing an implicit representation of graphs, overcoming man-in-the-middle attacks and implementing efficient load balancing of networks.

关键词： forest decomposition arboricity distributed algorithms implicit graphs

来源：评论

学校读者我要写书评

暂无评论

Scaling Equi-Joins 22

Scaling Equi-Joins

引用

International Conference on Management of Data (SIGMOD)

作者： Metwally, Ahmed Uber Inc Sunnyvale CA 94086 USA

ISBN: (纸本)9781450392495

This paper proposes Adaptive-Multistage-Join (AM-Join) for scalable and fast equi-joins in distributed shared-nothing architectures. AM-Join utilizes (a) Tree-Join, a novel algorithm that scales well when the joined tables share hot keys, and (b) Broadcast-Join, the fastest-known when joining keys that are hot in only one table. Unlike the state-of-the-art algorithms, AM-Join (a) holistically solves the join-key skew problem by achieving load balancing throughout the join execution, and (b) supports all outer-join variants without record deduplication or custom table partitioning. For the best AM-Join outer-join performance, we propose Index-Broadcast-Join (IB-Join) for Small-Large outer-joins, where one table fits in memory and the other is orders of magnitude larger. IB-Join improves on the state-of-the-art outer-join algorithms. The proposed algorithms can be adopted in any shared-nothing architecture. We implemented a MapReduce version using Spark. Our evaluation shows the proposed algorithms execute significantly faster and scale to more skewed and orders-of-magnitude bigger tables when compared to the state-of-the-art algorithms.

关键词： Big Data Data skew distributed algorithms Load balancing

来源：评论

学校读者我要写书评

暂无评论

distributed VARIABLE SAMPLE-SIZE GRADIENT-RESPONSE AND BEST-RESPONSE SCHEMES FOR STOCHASTIC NASH EQUILIBRIUM PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第2期32卷 573-603页

作者： Lei, Jinlong Shanbhag, Uday, V Tongji Univ Dept Control Sci & Engn Shanghai 200092 Peoples R China Penn State Univ Dept Ind & Mfg Engn University Pk PA 16803 USA

This paper considers an n-player stochastic Nash equilibrium problem (NEP) in which the ith player minimizes a composite objective f(i)(.,x-i) + r(i)(.), where f(i) is an expectation-valued smooth function, x-i, is a tuple of rival decisions, and r, is a nonsmooth convex function with an efficient prox-evaluation. In this context, we make the following contributions. (I) Under suitable monotonicity assumptions on the pseudogradient map, we derive optimal rate statements and oracle complexity bounds for the proposed variable sample-size proximal stochastic gradient-response (VS-PGR) scheme when the sample-size increases at a geometric rate. If the sample-size increases at a polynomial rate with degree v > 0, the mean-squared error of the iterates decays at a corresponding polynomial rate;in particular, we prove that the iteration and oracle complexities to obtain an epsilon-Nash equilibrium (epsilon-NE) are O(1/epsilon(1/v)) and O(1/epsilon(1+1/v)), respectively. When the sample-size is held constant, the iterates converge geometrically to a neighborhood of the Nash equilibrium in an expected-value sense. (II) We then overlay VS-PGR with a consensus phase with a view towards developing distributed protocols for aggregative stochastic NEPs. In the resulting d-VS-PGR scheme, when the sample-size at each iteration grows at a geometric rate while the communication rounds per iteration grow at the rate of k + 1, computing an epsilon-NE requires similar iteration and oracle complexities to VS-PGR with a communication complexity of O(1/epsilon(1+1/v))). Notably, (I) and (II) rely on weaker oracle assumptions in that the conditionally unbiasedness assumption is relaxed while the bound on the conditional second moment may be state-dependent. (III) Under a suitable contractive property associated with the proximal best-response (BR) map, we design a variable sample-size proximal BR (VS-PBR) scheme, where each player solves a sample-average BR problem. When the sample-size incr

关键词： stochastic Nash equilibrium problems distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

On the non-resiliency of subsequence reduced resilient consensus in multiagent networks

引用

EUROPEAN JOURNAL OF CONTROL 2024年 80卷

作者： Khalyavin, Leon Abbas, Waseem Imperial Coll London London SW7 2AZ England Univ Texas Dallas Richardson TX 75080 USA

This paper studies resilient distributed consensus in networks lacking the structural robustness necessary for achieving consensus in the presence of misbehaving agents. Existing resilient consensus solutions, including widely adapted weighted mean subsequence reduced (WMSR) resilient consensus algorithm, present robustness conditions guaranteeing consensus among normal agents. However, when the graph is less robust than required, they only inform that agents fail to achieve consensus and do not evaluate the network performance comprehensively in such non-ideal scenarios. To address this limitation, we analyze the performance of resilient consensus in non-ideal situations by introducing the concept of non-convergent nodes. These nodes/agents cannot achieve consensus with any arbitrary agent due to the presence of misbehaving agents in the network. This notion enables ordering graphs that lack required robustness and facilitates the assessment of partial performance. Additionally, we demonstrate that among graphs with the same level of robustness (measured by their ( r, s)-robustness), the number of non-convergent nodes varies significantly, indicating differing degrees of non-resilience. We also present numerical evaluation of results. Our approach quantifies the network performance under sub-optimal robustness conditions and offers a comprehensive resilience perspective.

关键词： Resilient consensus Multiagent networks Graph robustness distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Mutual visibility of luminous robots despite angular inaccuracy

引用

THEORETICAL COMPUTER SCIENCE 2024年 1011卷

作者： Pramanick, Subhajit Jana, Saswata Bhattacharya, Adri Mandal, Partha Sarathi Indian Inst Technol Guwahati Dept Math Gauhati 781039 Assam India

We initiate the study of the Mutual Visibility problem using N opaque luminous point robots that have inaccurate movements. Each robot operates in Look-Compute-Move cycles and has a persistent light attached to it to have a weak form of communication between robots using a constant number of colors. The inaccuracy for a robot r is an angular deviation from its target point T to a point T ' such that the angle t TrT ' < 90 degrees . The problem becomes unsolvable if this angle is >= 90 degrees . From any initial configuration of the robots on the Euclidean plane, the problem aims to arrange the robots in a configuration such that any two robots are visible to each other. We assume that the robots agree on one coordinate axis. We present two collision-free algorithms, a 2 color algorithm (which is optimal in the number of colors used) for semi-synchronous setting and a 3 color algorithm for asynchronous setting, both of which run in O ( N ) epochs. We also study the problem in the presence of mobile faulty robots. A robot can exhibit both mobility failure and angular inaccuracies in its movement. We present a fault-tolerant algorithm that aims to bring the robots in a configuration where no three non-faulty robots are collinear, and no faulty robot lies between two non-faulty robots. This algorithm uses 10 colors and takes O ( N ) epochs under asynchronous settings.

关键词： distributed algorithms Mobile robots Angular inaccuracy Mobility failure Luminous robots Mutual visibility

来源：评论

学校读者我要写书评

暂无评论

distributed control of battery energy storage systems in distribution networks for voltage regulation at transmission-distribution network interconnection points

引用

CONTROL ENGINEERING PRACTICE 2022年第0期119卷 104988-104988页

作者： Zhao, Tianqiao Parisio, Alessandra Milanovic, Jovica V. Univ Manchester Dept Elect & Elect Engn Manchester M13 9PL England

This paper describes a control framework that enables distributed battery energy storage systems (BESS) connected to distribution networks (DNs) to track voltage setpoints requested by the transmission system operator (TSO) at specific interconnection points in an optimal and coordinated manner. The control design is based on an optimisation problem whose objective is to minimise the real-time voltage-tracking mismatch while satisfying local physical network constraints. A novel agent-based control scheme adopting an online convex optimisation (OCO) framework is developed and solved in a distributed fashion to guarantee the solution's scalability and the service provision within the required time. The BESS agents under the proposed control framework automatically adapt to the time-varying network conditions so as to track the required voltage setpoints whilst fulfilling the technical operating requirements of the local network. The designed OCO-based framework addresses the existing conflict between the accuracy and optimality of the solution and the communication and computational efficiency. The convergence to the optimal solution is demonstrated. Several case studies are performed to corroborate the analytical results and assess the performance of the proposed approach.

关键词： distributed algorithms Online convex optimisation Energy storage systems Voltage control Distribution networks

来源：评论

学校读者我要写书评

暂无评论

Parallel and distributed paradigms for community detection in social networks: A methodological review

引用

EXPERT SYSTEMS WITH APPLICATIONS 2022年第0期187卷 115956-115956页

作者： Naik, Debadatta Ramesh, Dharavath Gandomi, Amir H. Gorojanam, Naveen Babu Indian Inst Technol Indian Sch Mines Dept Comp Sci & Engn Dhanbad Bihar India Univ Technol Sydney Dept Engn & Informat Technol Ultimo NSW Australia

Community detection in social networks is the process of identifying the cohesive groups of similar nodes. Detection of these groups can be helpful in many applications, such as finding networks of protein interaction in biological networks, finding the users of similar mind for ads and suggestions, finding a shared research field in collaborative networks, analyzing public health, future link prediction in social networks, analyzing criminology, and many more. However, with the increase in the number of profiles and content shared on social media platforms, the analysis is often time-consuming and exhaustive. In order to speed up and optimize the community detection process, parallel processing and Shared/distributed memory techniques are widely used. Despite community detection has widespread use in social networks, no attempt has ever been made to compile and systematically discuss research efforts on the emerging subject of identifying parallel and distributed methods for community detection in social networks. Most of the surveys described the serial algorithms used for community detection. Our survey work comes under the scope of new design techniques, exciting or novel applications, components or standards, and applications of an educational, transactional, and co-operational nature. This paper accommodates and presents a systematic literature review with state-of-the-art research on the application of parallel processing and Shared/distributed techniques to determine communities for social network analysis. Advanced search strategy has been performed on several digital libraries for extracting several studies for the review. The systematic search landed in finding 3220 studies, among which 65 relevant studies are selected after conducting various screening phases for further review. The application of parallel computing, shared memory, and distributed memory on the existing community detection methodologies have been discussed thoroughly. More specifically,

关键词： Social Networks Community Detection Parallel algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model 22

Brief Announcement: Near Optimal Bounds for Replacement Path...

引用

ACM Symposium on Principles of distributed Computing (PODC)

作者： Manoharan, Vignesh Ramachandran, Vijaya Univ Texas Austin Austin TX 78712 USA

ISBN: (纸本)9781450392624

We present round complexity results in the CONGEST model for Replacement Paths (RPaths), Minimum Weight Cycle (MWC), and All Nodes Shortest Cycles (ANSC). We study these fundamental problems in both directed and undirected graphs, weighted and unweighted. Many of our results are optimal to within a polylog factor: For an.. -node graph.. we establish near linear lower and upper bounds for RPaths if.. is directed andweighted, and forMWC and ANSC if.. is weighted, directed or undirected;near root n lower and upper bounds for undirected weighted RPaths;and Theta(D) bound for undirected unweighted RPaths. We also present lower and upper bounds for approximation: a (2 - ( 1/g))-approximation algorithm for undirected unweighted MWC that runs in O-similar to (root n +D) rounds, improving on the previous best bound of O-similar to (root ng +D) rounds, where.. is the MWC length, and a ( 1 +epsilon)-approximation algorithm for directed weighted RPaths and (2 +epsilon)-approximation for weighted undirected MWC, for any constant epsilon > 0, that beat the round complexity lower bound for an exact solution.

关键词： distributed algorithms CONGEST lower bounds replacement paths minimum weight cycle

来源：评论

学校读者我要写书评

暂无评论

Building Regular Formations with Establishing/Preserving Information Connectivity by Multi-Agent Robotic Teams 22

Building Regular Formations with Establishing/Preserving Inf...

引用

22nd International Conference on Control, Automation and Systems (ICCAS)

作者： Matveev, Alexey S. Konovalov, Petr A. Kapitonov, Alexander A. Shepeljavyi, A., I St Petersburg State Univ Math & Mech Fac St Petersburg 198504 Russia Sirius Univ Math Robot Sci Div Sirius City Krasnodar Regio Russia ITMO Univ Fac Control Syst & Robot St Petersburg 197101 Russia

ISBN: (纸本)9788993215243

We consider a team of identical agents that are unaware of the team size, cannot discern between the peers or play distinct roles, and should be driven a common control rule, which is to be individually run at any of them. Every agent has access to the relative state of any peer that lies within a finite "visibility range" if nobody "obscures the view" to the peer. Computationally inexpensive distributed algorithms are presented for solution of the following problems: distribution of the agents into nodes of a uniform grid with a given step without gaps and multiple occupancy of nodes;reaching consensus on a quantity of interest (QoI);even self-distribution between two given values of QoI. These algorithms are illustrated by using them as building blocks for control laws that ensure first, dense sweep coverage of corridor environments by planar robotic swarms and second, autonomously building a virtual antenna array in 3D by mobile devices. The proposed algorithms are justified by mathematically rigorous global convergence results;their performance is confirmed by computer simulation tests.

关键词： Multiagent systems generalized consensus coordination distributed algorithms stability analysis

来源：评论

学校读者我要写书评

暂无评论

BigMEC: Scalable Service Migration for Mobile Edge Computing 7

BigMEC: Scalable Service Migration for Mobile Edge Computing

引用

IEEE/ACM 7th Symposium on Edge Computing (SEC)

作者： Brandherm, Florian Gedeon, Julien Abboud, Osama Muehlhaeuser, Max Tech Univ Darmstadt Telecooperat Lab Darmstadt Germany Huawei Technol Munich Germany

ISBN: (纸本)9781665486118

The proximity of Mobile Edge Computing offers the potential for offloading low latency closed-loop applications from mobile devices. However, to repair decreases in quality of service (QoS), e.g., resulting from user mobility, the placement of service instances must be continually updated - essential for mission critical applications that cannot tolerate decreased QoS, for example virtual reality or networked control systems. This paper presents BigMEC, a decentralized service placement algorithm that achieves scalable, fast, and high-quality placements by making local service migration decisions immediately when a drop in QoS is detected. The algorithm relies on reinforcement learning to adapt to unknown scenarios and to approximate long-term optimal placement updates by taking future transition costs into account. BigMEC limits each decentralized migration decision to nearby edge sites. Thus, decision computation times are independent of the number of nodes in the network and well below 10ms in our experimental setup. Our ablation study validates that, using its scalable approach to decentralized resource conflict resolution, BigMEC quickly approaches optimal placement with increasing local view size, and that it can reliably learn to approximate long-term optimal migration decisions, given only a black-box optimization objective.

关键词： mobile edge computing service migration reinforcement learning distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：