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

ACM TRANSACTIONS ON algorithms 2021年第4期17卷 30-30页

作者： Abboud, Amir Censor-Hillel, Keren Khoury, Seri Paz, Ami Weizmann Inst Sci Dept Comp Sci & Appl Math Fac Math & Comp Sci 234 Herzl St IL-7610001 Rehovot Israel Technion Dept Comp Sci Taub Bldg IL-3200003 Haifa Israel Univ Calif Berkeley EECS 253 Cory Hall Berkeley CA 94720 USA Univ Vienna Fac Comp Sci Wahringer Str 29 A-1090 Vienna Austria

This article proves strong lower bounds for distributed computing in the congest model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing careful sparse graph constructions with small cuts extends known techniques to show a near-linear lower bound for computing the diameter, a result previously known only for dense graphs. Moreover, the sparseness of the construction plays a crucial role in applying it to approximations of various distance computation problems, drastically improving over what can be obtained when using dense graphs. Second, small cuts are essential for proving super-linear lower bounds, none of which were known prior to this work. In fact, they allow us to show near-quadratic lower bounds for several problems, such as exact minimum vertex cover or maximum independent set, as well as for coloring a graph with its chromatic number. Such strong lower bounds are not limited to NP-hard problems, as given by two simple graph problems in P, which are shown to require a quadratic and near-quadratic number of rounds. All of the above are optimal up to logarithmic factors. In addition, in this context, the complexity of the all-pairs-shortest-paths problem is discussed. Finally, it is shown that graph constructions for congest lower bounds translate to lower bounds for the semi-streaming model, despite being very different in its nature.

关键词： Lower bounds distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Atomic Appends in Asynchronous Byzantine distributed Ledgers

Atomic Appends in Asynchronous Byzantine Distributed Ledgers

引用

European Dependable Computing Conference (EDCC)

作者： Vicent Cholvi Antonio Fernandez Anta Chryssis Georgiou Nicolas Nicolaou Michel Raynal Universitat Jaume I Spain IMDEA Networks Institute Madrid Spain University of Cyprus Cyprus Algolysis Ltd Cyprus IRISA France & PolyU Hong Kong

The following topics are dealt with: security of data; formal specification; safety-critical software; risk analysis; fault tolerant computing; genetic algorithms; finite state machines; automata theory; distributed p... 详细信息

ISBN: (数字)9781728189369

ISBN: (纸本)9781728189376

关键词： Servers distributed ledger Fabrics Computer crashes Blockchain distributed algorithms Consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Ordered and delayed adversaries and how to work against them on a shared channel

引用

distributed COMPUTING 2019年第5期32卷 379-403页

作者： Klonowski, Marek Kowalski, Dariusz R. Mirek, Jaroslaw Wroclaw Univ Sci & Technol Fac Fundamental Problem Technol Wybrzeze Wyspianskiego 27 PL-50370 Wroclaw Poland Univ Liverpool Dept Comp Sci Ashton BldgAshton St Liverpool L69 3BX Merseyside England

An execution of a distributed algorithm is often seen as a game between the algorithm and a conceptual adversary causing specific distractions to the computation. In this work we define a class of ordered adaptive adversaries, which cause distractions-in particular crashes-online according to some partial order of the participating stations, which is fixed by the adversary before the execution. We distinguish: Linearly-Ordered adversary, restricted by some pre-defined linear order of (potentially) crashing stations;Anti-Chain-Ordered adversary, previously known as the Weakly-Adaptive adversary, which is restricted by some pre-defined set of crash-prone stations (it can be seen as an ordered adversary with the order being an anti-chain, i.e., a collection of incomparable elements, consisting of these stations);k-Thick-Ordered adversary restricted by partial orders of stations with a maximum anti-chain of size k. We initiate a study of how they affect performance of algorithms. For this purpose, we focus on the well-known Do-All problem of performing t tasks by p synchronous crash-prone stations communicating on a shared channel. The channel restricts communication by the fact that no message is delivered to the operational stations if more than one station transmits at the same time. The question addressed in this work is how the ordered adversaries controlling crashes of stations influence work performance, defined as the total number of available processor steps during the whole execution and introduced by Kanellakis and Shvartsman (Distrib Comput 5(4):201-217, 1992) in the context of Write-All algorithms. The first presented algorithm solves the Do-All problem with work O proved in Chlebus et al. (Distrib Comput 18(6):435-451, 2006). Another algorithm is developed against the Weakly-Adaptive adversary. Work done by this algorithm is O(t+pt+pminp/(p-f),tlogp), which is close to the lower bound omega(t+pt+pminp/(p-f),t) proved in [11] and answers the open questions

关键词： Performing tasks Do-All Shared channel Multiple-access channel Ordered adversaries Delayed adversaries Crash failures distributed algorithms Randomized algorithms Work complexity Time complexity Transmission energy complexity

来源：评论

学校读者我要写书评

暂无评论

CSDGP: cluster switched data gathering protocol for mobile wireless sensor networks

引用

IET COMMUNICATIONS 2019年第18期13卷 2973-2985页

作者： Karunanithy, Kalaivanan Velusamy, Bhanumathi Anna Univ Reg Campus Dept ECE Coimbatore 641046 Tamil Nadu India

Nowadays, most of the research focuses on the distributed algorithm to form the clusters in wireless sensor networks, in which the sensor nodes act autonomously to self-configure themselves with the help of the local information. However, the issues in such distributed mechanisms are (i) how to assign the time division multiple access (TDMA) schedule to collect the data from the cluster member (CM), (ii) how to distribute and balance the overall energy consumption of the cluster heads (CHs) under the circumstance of node's mobility. To overcome these problems, a cluster switched data gathering protocol (CSDGP) is proposed which ensures a uniform distribution of CHs by utilising a waiting time-based CH selection and an effective cluster switch based TDMA scheduling mechanism. The salient feature observed in the proposed CSDGP is that the migrated node has a chance to transmit the sensed data to the CH, whenever the CH has a free time slot. From the simulation results, it is proved that CSDGP provides a good performance under three different scenarios in comparison with existing protocols in terms of average energy consumption, average end-to-end delay, packet delivery ratio, and control overhead.

关键词： protocols wireless sensor networks mobile radio time division multiple access distributed algorithms telecommunication scheduling CSDGP mobile wireless sensor networks distributed algorithm sensor nodes local information distributed mechanisms time division multiple access schedule cluster heads cluster switched data gathering protocol uniform distribution waiting time-based CH selection effective cluster switch TDMA scheduling mechanism free time slot energy consumption node mobility end-to-end delay packet delivery ratio control overhead

来源：评论

学校读者我要写书评

暂无评论

Gradient-Consensus Method for distributed Optimization in Directed Multi-Agent Networks

Gradient-Consensus Method for Distributed Optimization in Di...

引用

American Control Conference

作者： Vivek Khatana Govind Saraswat Sourav Patel Murti V. Salapaka department of Electrical and Computer Engineering University of Minnesota Minneapolis USA

ISBN: (数字)9781538682661

ISBN: (纸本)9781538682678

In this article, a distributed optimization problem for minimizing a sum, Σ_i = 1~n, f_i, of convex objective functions, f_i, on directed graph topologies is addressed. Here each function f i is a function of n variables, private to agent i which defines the agent's objective. These f i 's are assumed to be Lipschitz-differentiable convex functions. For solving this optimization problem, we develop a novel distributed algorithm, which we term as the gradient-consensus method. The gradient-consensus scheme uses a finite-time terminated consensus protocol called ρ-consensus, which allows each local estimate to be ρ-close to each other at every iteration. The parameter ρ is a fixed constant independent of the network size and topology. It is shown that the estimate of the optimal solution at any local agent i converges geometrically to the optimal solution within an O(ρ) neighborhood, where ρ can be chosen to be arbitrarily small.

关键词： distributed optimization distributed gradient descent multi-agent networks finite-time consensus NETWORKING AGENT optimal solution Mentoring distributed algorithms Distribute Convex function

来源：评论

学校读者我要写书评

暂无评论

A self-managing volatile key scheme for wireless sensor networks

引用

JOURNAL OF AMBIENT INTELLIGENCE AND HUMANIZED COMPUTING 2019年第9期10卷 3349-3364页

作者： Laouid, Abdelkader Dahmani, Abdelnasser Hassen, Hani Ragab Bounceur, Ahcene Euler, Reinhardt Lalem, Farid Tari, Abdelkamel Univ Bejaia Dept Comp Sci LIMED Lab Bejaia Algeria Univ Bretagne Occidentale Lab STICC UMR CNRS 6285 20 Ave Victor Le Gorgeu F-29238 Brest France Heriot Watt Univ Sch Math & Comp Sci Edinburgh Midlothian Scotland Univ Ctr Tamanrasset Tamanrasset Algeria Univ Echahid Hamma Lakhdar POB 789 El Oued 39000 Algeria

The last decade has seen major advances in Wireless Sensor Networks (WSN). The limited amount of resources in WSNs is the main challenge for securing them. Indeed, sensors are inherently small devices with limited embedded storage, processor and battery capacity. The situation is even worse when attackers, with virtually unlimited amount of resources, have direct physical access to sensors. Cryptographic keys are used for authentication, authorization, confidentiality, data integrity, as well as many other security services. Several proposals have been made for key management in WSNs. In this paper, we review some notable key management schemes and propose a new one. The originality of our work lies in two main facts: first, we do not place a master key on all sensors before deploying them as several other proposals did, but we rather place the master key in a subset of sensors;second, the master keys are volatile, i.e., sensors use the master key to bootstrap the system and they delete them shortly after that. Our extensive simulations have shown the efficiency of our approach.

关键词： Key management Wireless sensor networks Secure connectivity coverage Network scalability distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

PD-DESYNC: Practical and Deterministic Desynchronization in Wireless Sensor Networks

引用

KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS 2019年第8期13卷 3880-3899页

作者： Hyun, Sang-Hyun Kim, Geon Yang, Dongmin SOFTITECH Co Ltd Daejeon South Korea Chonbuk Natl Univ Grad Sch Arch & Records Management Jeonju Si Jeollabuk Do South Korea

Distributive desynchronization algorithms based on pulse-coupled oscillator (PCO) models have been proposed for achieving collision-free wireless transmissions. These algorithms do not depend on a global clock or infrastructure overheads. Moreover, they gradually converge to fair time-division multiple access (TDMA) scheduling by broadcasting a periodic pulse signal (called a 'firing') and adjusting the next firing time based on firings from other nodes. The time required to achieve constant spacing between phase neighbors is estimated in a closed form or via stochastic modeling. However, because these algorithms cannot guarantee the completion of desynchronization in a short and bounded timeframe, they are not practical. Motivated by the limitations of these methods, we propose a practical solution called PD-DESYNC that provides a short and deterministic convergence time using a flag firing to indicate the beginning of a cycle. We demonstrate that the proposed method guarantees the completion of desynchronization within three cycles, regardless of the number of nodes. Through extensive simulations and experiments, we confirm that PD-DESYNC not only outperforms other algorithms in terms of convergence time but also is a practical solution.

关键词： Desynchronization distributed algorithms Wireless MAC protocol Time division multiple access Wireless Sensor Networks

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Mobile Sink Aided Data Collection From Dedicated and Virtual Aggregation Nodes in Energy Harvesting Wireless Sensor Networks

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING

引用

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING 2019年第4期3卷 1058-1071页

作者： Tao, Lei Zhang, Xin Ming Liang, Weifa Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230027 Peoples R China Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China Australian Natl Univ Res Sch Comp Sci Canberra ACT 2601 Australia

We study the mobile data collection problem in an energy harvesting wireless sensor network (EH-WSN), where sensor nodes are densely deployed in a monitoring area and a mobile sink (MS) travels around the area to collect sensory data from the sensors. In order to optimize the network performance while achieving perpetual network operation, we propose efficient algorithms to dynamically schedule the MS for collecting data from sensors with different data generation rates. Specifically, in this paper, we propose an optimization framework that consists of three stages. We first deal with the reliable, stable, and energy neutral energy assignment for sensors. We then find a closed trajectory for the MS for sensory data collection that covers as many as aggregation nodes, and devise a decentralized algorithm to determine the data generation rate of each sensor and the data flow rate of each link to optimize the network performance. We also develop a fast heuristic algorithm for the problem. We finally evaluate the performance of the proposed algorithms through numerical experiments. The simulation results demonstrate that the proposed algorithms are efficient.

关键词： distributed algorithms energy harvesting wireless sensor networks network utility mobile data collection path planning

来源：评论

学校读者我要写书评

暂无评论

VRDD: vehicular relevance-based data dissemination in a vehicular ad hoc network

引用

IET INTELLIGENT TRANSPORT SYSTEMS 2019年第12期13卷 1792-1803页

作者： Chowdhury, Debanjan Roy Jain, Vinod Kumar PDPM Indian Inst Informat Technol Design & Mfg Ja Dept Comp Sci & Engn Dumna Airport RdPO Khamaria Jabalpur Madhya Pradesh India

Safety message (SM) dissemination in vehicular ad hoc network needs to be fast as it allows vehicles to become alert and avoid adverse situations. An SM usually gets disseminated within a topology by multi-hop broadcast technique. Existing protocols have proposed various controlled flooding mechanisms to address the issues of broadcast storm and network partition. However, no work has been done to take care the direction of message dissemination. In a real scenario, all vehicles within an area of interest (AOI) are not equally affected by an emergency incident. The vehicles of the road where the incident happened, or the vehicles of roads which are connected to incident location by nearby junctions, are most affected and hence are more relevant to receive the SM as fast as possible. Hence, this study proposes a novel method to predict the relevance of vehicles using a distributed algorithm and heuristically tries to disseminate SM toward the relevant vehicles. The authors have compared their work with three state of-the-art algorithms and found that vehicular relevance-based data dissemination is compatible with the existing algorithms on the metrics of packet loss and dissemination delay, but clearly leading in the metric of relevant dissemination.

关键词： vehicular ad hoc networks protocols broadcasting telecommunication network topology distributed algorithms vehicular relevance-based data dissemination relevant dissemination vehicular ad hoc network safety message dissemination multihop broadcast techniques controlled rebroadcast mechanisms controlled rebroadcast mechanisms protocols packet loss dissemination delay distributed algorithm emergency incident

来源：评论

学校读者我要写书评

暂无评论

Packet Efficient Implementation of the Omega Failure Detector

引用

THEORY OF COMPUTING SYSTEMS 2019年第2期63卷 237-260页

作者： Bramas, Quentin Foreback, Dianne Nesterenko, Mikhail Tixeuil, Sebastien Univ Strasbourg Strasbourg France Kent State Univ Kent OH 44242 USA Sorbonne Univ UPMC Paris France IUF Paris France

We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an Omega Failure Detector implementation. To motivate the study, we prove the existence and sustainability of a leader is exponentially more probable in a multi-hop than in a single-hop implementation. An implementation is: message efficient if all but finitely many messages are sent by a single process;packet efficient if it is message efficient and the number of packets used to transmit all but finitely many messages is proportional to the number of processes in the system;super packet efficient if it is message efficient and the number of channels used to transmit all but finitely many packets is proportional to the number of processes in the system. We prove that a super packet efficient implementation of Omega is impossible. We establish necessary conditions for the existence of a packet efficient implementation of Omega and present an algorithm that implements Omega under these conditions.

关键词： Failure detectors Fault tolerance Consensus distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：