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

11th Latin-American Symposium on Dependable Computing (LADC)

作者： Galesky, Leonardo de Freitas Rodrigues, Luiz Antonio Western Parana State Univ UNIOESTE Cascavel Parana Brazil

ISBN: (纸本)9781450397377

This paper presents a work in progress that intends to evaluate the use of a virtual hypercube topology as a partial replication protocol for a data store based on Conflict-free Replicated Data Types (CRDT). CRDTs can ensure consistency in a deterministic and conflict-free manner. This project presents a review of recent solutions for the replication of CRDTs, and proposes the input data and the test environment for evaluation. Currently, we are focused on building a prototype based on the VCube-PS pub-sub protocol. Various load and network distributions will be later evaluated using the Grid5000 testbed. The results will be compared with other replication protocols proposed in recent research to determine the feasibility of the proposed specification in terms of latency, scalability, and fault tolerance.

关键词： Conflict-Free Replication Data Types VCube multicast distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 6055-6070页

作者： Zhang, Xinwei Hong, Mingyi Dhople, Sairaj Yin, Wotao Liu, Yang Univ Minnesota Minneapolis MN 55455 USA Univ Calif Los Angeles Los Angeles CA 90095 USA Tsinghua Univ Inst AI Ind Res Beijing 100084 Peoples R China

Federated Learning (FL) is popular for communication-efficient learning from distributed data. To utilize data at different clients without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a computation then aggregation model, in which multiple local updates are performed using local data before aggregation. These algorithms fail to work when faced with practical challenges, e.g., the local data being non-identically independently distributed. In this paper, we first characterize the behavior of the FedAvg algorithm, and show that without strong and unrealistic assumptions on the problem structure, it can behave erratically. Aiming at designing FL algorithms that are provably fast and require as few assumptions as possible, we propose a new algorithm design strategy from the primal-dual optimization perspective. Our strategy yields algorithms that can deal with non-convex objective functions, achieves the best possible optimization and communication complexity (in a well-defined sense), and accommodates full-batch and mini-batch local computation models. Importantly, the proposed algorithms are communication efficient, in that the communication effort can be reduced when the level of heterogeneity among the local data also reduces. In the extreme case where the local data becomes homogeneous, only O(1) communication is required among the agents. To the best of our knowledge, this is the first algorithmic framework for FL that achieves all the above properties.

关键词： Signal processing algorithms Protocols Complexity theory Servers Computational modeling Data models distributed databases distributed algorithms machine learning algorithms federated learning data heterogeneity convergence analysis

来源：评论

学校读者我要写书评

暂无评论

Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study

引用

IEEE ACCESS 2021年 9卷 147855-147873页

作者： Cicerone, Serafino Univ LAquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy

Concerning the coordination of autonomous mobile robots, the main focus has been on the important class of Pattern Formation problems, where the robots are required to arrange themselves to form a given geometric shape. This class of problems has been extensively studied in the continuous environment (e.g., the Euclidean plane), whereas few results exist when robots move in a discretization of the plane, like infinite grids. In this environment, to form any pattern, the problem of breaking symmetries emerges. Breaking the symmetry by moving some leader robot is not a straightforward task due to the movement restrictions as all the adjacent nodes of the leader may be occupied. It may even happen that before obtaining the requested asymmetric configuration, most of the robots must be moved. Due to the asynchrony of robots, this fact greatly increases the difficulty of the problem. We assume very weak robots moving on any regular tessellation graph as a discretization of the Euclidean plane, and we devise an algorithm Abreak able to solve the Symmetry Breaking problem on both the square and triangular grids. It is important to note that Abreak is proposed so that it can be used as a module for solving more general problems. As a case study, we use Abreak to deal with the Line Formation problem, where n >= 3 robots must arrange themselves to occupy n contiguous vertices along a grid line. In this respect, we first provide an algorithm A(LF)(-) able to partially solve this problem (it works with configurations in which it is not necessary to break symmetries), and then we show how Abreak and A(LF) can be combined to form A(LF.) We provide a complete characterization of the solvability of the Line Formation problem on the considered topologies by showing that A(LF) solves the problem in each configuration where this is possible.

关键词： distributed algorithms mobile robots asynchrony pattern formation symmetry grid graphs

来源：评论

学校读者我要写书评

暂无评论

Low-Latency Data Aggregation Scheduling for Cognitive Radio Networks With Non-Predetermined Structure

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2021年第7期20卷 2412-2426页

作者： Chen, Quan Cai, Zhipeng Cheng, Lianglun Gao, Hong Guangdong Univ Technol Sch Comp Guangzhou 510006 Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Harbin Inst Technol Sch Comp Sci & Technol Harbin 150001 Peoples R China

Data aggregation is a fundamental yet popular operation in wireless networks where the sink needs to obtain the combined information of the whole network. However, the problem of minimum latency aggregation scheduling (MLAS) is not well studied in cognitive radio networks. Few studies have addressed this issue and most previous aggregation methods all assume that a fixed-structure based aggregation tree is constructed in advance, which may result in the selection of a node with limited spectrum opportunities as the parent by many nodes and by extension results in a large latency. Thus, the MLAS problem in cognitive radio networks (MLAS-CR) without the above limitation is investigated in this paper. First, the MLAS-CR problem with primary social behaviors where the activity of primary users can be predicted is studied. To make full use of the limited spectrum opportunities, we integrate the construction of the aggregation tree, and the computation of a conflict-free schedule simultaneously, without any predetermined structures. Second, the MLAS-CR problem without the above assumption is also investigated. To reduce the latency, a two-way aggregation scheduling method is proposed to adaptively choose the parent with only current channel information. To further reduce the latency, we also introduce a new data aggregation mode for CRN, i.e., Data Aggregation Scheduling in The Dark, to utilize the spectrum opportunities of scheduled nodes. Finally, the theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of latency.

关键词： Data aggregation Cognitive radio Interference Schedules Processor scheduling Scheduling distributed algorithms Data aggregation low latency conflict-free scheduling cognitive radio networks (CRNs)

来源：评论

学校读者我要写书评

暂无评论

Workspace Partitioning and Topology Discovery algorithms for Heterogeneous Multiagent Networks

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2021年第1期8卷 354-366页

作者： Bakolas, Efstathios Univ Texas Austin Dept Aerosp Engn & Engn Mech Austin TX 78712 USA

In this article, we consider a class of workspace partitioning problems that arise in the context of area coverage for spatially distributed heterogeneous multiagent networks. It is assumed that each agent has certain directions of motion or directions for sensing that are preferable to others. These preferences are measured by means of convex and anisotropic (direction-dependent) quadratic proximity metrics, which can be different for each agent. These proximity metrics induce Voronoi-like partitions of the network's workspace, whose cells may not always be convex (or even connected) sets but are necessarily contained in a priori known ellipsoids. The main contributions of this article are as follows: 1) a distributed algorithm for the computation of a Voronoi-like partition of the workspace of a heterogeneous multiagent network and 2) a systematic process to discover the network topology induced by the latter partition. The distributed implementation of the proposed algorithms is enabled by the utilization of a hypothetical agent which determines when the performance of each agent is acceptable. Numerical simulations that illustrate the efficacy of the proposed algorithms are also presented.

关键词： distributed algorithms geometric methods networks of autonomous agents sensor networks

来源：评论

学校读者我要写书评

暂无评论

Exploration of dynamic tori by multiple agents

引用

THEORETICAL COMPUTER SCIENCE 2021年 850卷 202-220页

作者： Gotoh, Tsuyoshi Sudo, Yuichi Ooshita, Fukuhito Kakugawa, Hirotsugu Masuzawa, Toshimitsu Osaka Univ 1-5 Yamadaoka Suita Osaka Japan Nara Inst Sci & Technol 8916-5 Takayamacho Nara 6300192 Japan Ryukyus Univ 1-5 Setaooecho Otsu Shiga 5202123 Japan

Mobile agents (agents) are objects which can migrate autonomously in a distributed system and execute actions at visited nodes. One of the most fundamental problems of agents is exploration, which requires that each node should be visited by at least one agent. For a long time, researchers focus on exploration of static networks while exploration of dynamic networks has been studied recently. In this paper, we consider exploration of a dynamic torus under some constraints on the dynamics (or topology changes). An n x m torus (3 <= n <= m) is considered as a collection of n row rings and m column rings. The constraint on the dynamics is that each ring should be 1-interval connected, which allows at most one link to be missing at any time in each ring. For the n x m dynamic torus, we propose exploration algorithms with and without the link presence detection. With the link presence detection, an agent can detect which incident links are missing (if some link is missing) before determining its next move. On the other hand, without the link presence detection, an agent has to determine its next move without knowing which incident links are missing, which makes the agent stay on the same node when it tries to move through a missing link. The main contribution of this paper is to clarify the necessary and sufficient number of agents to explore an n x m dynamic torus with and without the link presence detection. Specifically, it is proven that, without the link presence detection, n + 1 agents are necessary and sufficient to explore the n x m dynamic torus. It also proven that, with the link presence detection, [n/2] + 1 agents are necessary and sufficient when n not equal 4 and, [n/2] + 2 (i.e., four) agents are necessary and sufficient when n = 4 to explore the n x m dynamic torus. With respect to the time complexity, we propose asymptotically time-optimal algorithms with and without the link presence detection. (c) 2020 Elsevier B.V. All rights reserved.

关键词： distributed algorithms Dynamic networks Mobile agents Exploration Link presence detection

来源：评论

学校读者我要写书评

暂无评论

Caching Policies for Delay Minimization in Small Cell Networks With Coordinated Multi-Point Joint Transmissions

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2021年第3期29卷 1105-1115页

作者： Ricardo, Guilherme Iecker Tuholukova, Alina Neglia, Giovanni Spyropoulos, Thrasyvoulos EURECOM F-06904 Biot Sophia Antipolis France Univ Cote Azur INRIA F-06902 Sophia Antipolis France

In 5G and beyond network architectures, operators and content providers base their content distribution strategies on Heterogeneous Networks, where macro and small cells are combined to offer better Quality of Service to wireless users. On top of such networks, edge caching and Coordinated Multi-Point (CoMP) joint transmissions are used to further improve performance. In this paper, we address the average delay minimization problem by first formulating it as a static optimization problem. Even though the problem is NP-hard we are able to solve it via an efficient algorithm that guarantees a 1/2-approximation ratio. We then proceed to propose two fully distributed and dynamic caching policies for the same problem. The first one asymptotically converges to the static optimal solution under the Independent Reference Model (IRM). The second one provides better results in practice under real (non-stationary) request processes. Our online policies outperform existing dynamic solutions that are PHY-unaware.

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

来源：评论

学校读者我要写书评

暂无评论

The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots

引用

THEORETICAL COMPUTER SCIENCE 2021年 852卷 29-40页

作者： Li, Shouwei Heide, Friedhelm Meyer auf der Podlipyan, Pavel Paderborn Univ Heinz Nixdorf Inst Furstenallee 11 D-33102 Paderborn Germany Paderborn Univ Dept Comp Sci Furstenallee 11 D-33102 Paderborn Germany

In this paper, we reconsider the well-known discrete, round-based Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita [2] for gathering n autonomous mobile robots with limited viewing range in the plane. Remarquably, this algorithm exploits the fact that during its execution, many collisions of robots occur. Such collisions are interpreted as a success because it is assumed that such collided robots behave the same from now on. This is acceptable under the assumption that each robot is represented by a single point. Otherwise, collisions should be avoided. In this paper, we consider a continuous Go-To-The-Center algorithm in which the robots continuously observe the positions of their neighbors and adapt their speed (assuming a speed limit) and direction. Our first results are time bounds of O(n(2)) for gathering in two dimensions Euclidean space, and O(n) for the one dimension. Our main contribution is the introduction and evaluation of a continuous algorithm which performs Go-To-The-Center considering only the neighbors of a robot with respect to the Gabriel subgraph of the visibility graph, i.e. Go-To-The-Gabriel-Center algorithm. We show that this modification still correctly executes gathering in one and two dimensions, with the same time bounds as above. Simulations exhibit a severe difference of the behavior of the Go-To-The-Center and the Go-To-The-Gabriel-Center algorithms: Whereas lots of collisions occur during a run of the Go-To-The-Center algorithm, typically only one, namely the final collision occurs during a run of the Go-To-The-Gabriel-Center algorithm. We can prove this "collisionless property" of the Go-To-The-Gabriel-Center algorithm for one dimension. In two-dimensional Euclidean space, we conjecture that the "collisionless property" holds for almost every initial configuration. We support our conjecture with measurements obtained from the simulation where robots execute both continuous Go-To-The-Center and Go-To-The-Gabriel-Center alg

关键词： Local algorithms distributed algorithms Collisionless gathering Mobile robots Multiagent system

来源：评论

学校读者我要写书评

暂无评论

Gradual Federated Learning With Simulated Annealing

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 6299-6313页

作者： Luong Trung Nguyen Shim, Byonghyo Seoul Natl Univ Inst New Media & Commun Seoul 08826 South Korea Seoul Natl Univ Dept Elect & Comp Engn Seoul 08826 South Korea

Federated averaging (FedAvg) is a popular federated learning (FL) technique that updates the global model by averaging local models and then transmits the updated global model to devices for their local model update. One main limitation of FedAvg is that the average-based global model is not necessarily better than local models in the early stage of the training process so that FedAvg might diverge in realistic scenarios, especially when the data is non-identically distributed across devices and the number of data samples varies significantly from device to device. In this paper, we propose a new FL technique based on simulated annealing. The key idea of the proposed technique, henceforth referred to as simulated annealing-based FL (SAFL), is to allow a device to choose its local model when the global model is immature. Specifically, by exploiting the simulated annealing strategy, we make each device choose its local model with high probability in early iterations when the global model is immature. From extensive numerical experiments using various benchmark datasets, we demonstrate that SAFL outperforms the conventional FedAvg technique in terms of the convergence speed and the classification accuracy.

关键词： Servers Data models Numerical models Predictive models Computational modeling Simulated annealing Signal processing algorithms Client-server systems distributed algorithms federated learning machine learning

来源：评论

学校读者我要写书评

暂无评论

Competitive Age of Information in Dynamic IoT Networks

引用

IEEE INTERNET OF THINGS JOURNAL 2021年第20期8卷 15160-15169页

作者： Yu, Dongxiao Zou, Yifei Xu, Minghui Xu, Yicheng Zhang, Yong Gong, Bei Xing, Xiaoshuang Shandong Univ Inst Intelligent Comp Sch Comp Sci & Technol Qingdao 266237 Peoples R China Shandong Univ Sch Comp Sci & Technol Qingdao 266237 Peoples R China George Washington Univ Dept Comp Sci Washington DC 20052 USA Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Beijing Univ Technol Fac Informat Technol Beijing 100124 Peoples R China Changshu Inst Technol Dept Comp Sci & Engn Suzhou 215500 Peoples R China

In the past decades, Dynamic Internet of Things (D-IoT) networks have played a conspicuously more important role in many real-life areas, including disaster relief, environment monitoring, public safety, and so on, to rapidly collect information from the environment and help people to make the decision. Meanwhile, due to the widespread implementation of dynamic IoT networks, there exists an enormous demand on designing suitable models and efficient algorithms for fundamental operations in dynamic IoT networks, to achieve the high throughput and reliable low-latency communication demands in 6G networks. In this article, we first present a general dynamic model to comprehensively depict most of the dynamic phenomena in IoT networks. Then, based on the proposed dynamic model, a distributed scheduling algorithm is proposed to competitively optimize the Age-of-Information (AoI) problem in the context of a D-IoT network. We say our scheduling algorithm is competitive: the throughput of the base station approximates the optimal solution with constant competitive ratio;and, the latency for a packet received by the base station is only constant times larger than the optimal latency. Rigorous theoretical analysis and extensive simulations are presented to verify the high throughput and reliable low-latency communications in our proposed algorithm.

关键词： Base stations Heuristic algorithms Interference Dynamic scheduling Scheduling algorithms Wireless communication Throughput Age-of-Information (AoI) scheduling distributed algorithms dynamic IoT networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：