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

Resilient Synchronization of Pulse-Coupled Oscillators under Stealthy Attacks

IFAC-PapersOnLine 2021年第14期54卷 424-429页

作者： Yugo Iori Hideaki Ishii Department of Computer Science Tokyo Institute of Technology Yokohama 226-8502 Japan

This paper studies a clock synchronization problem for wireless sensor networks employing pulse-based communication when some of the nodes are faulty or even adversarial. The objective is to design resilient distributed algorithms for the nonfaulty nodes to keep the influence of the malicious nodes minimal and to arrive at synchronization in a safe manner. Compared with conventional approaches, our algorithm is more capable in the sense that it is applicable to networks taking noncomplete graph structures, and moreover it is deterministic. Our method extends the class of mean subsequence reduced (MSR) algorithms from the area of multi-agent consensus. First, we provide a simple detection method to find malicious nodes that transmit pulses irregularly. Then, we demonstrate that in the presence of adversaries capable to avoid being detected, the normal nodes can reach synchronization by ignoring suspicious pulses. We illustrate the effectiveness of our result by a numerical example.

关键词： Resilient Synchronization distributed algorithms Fault Detection

来源：评论

学校读者我要写书评

暂无评论

Efficient Dispersion of Mobile Robots on Dynamic Graphs 40

Efficient Dispersion of Mobile Robots on Dynamic Graphs

引用

40th IEEE International Conference on distributed Computing Systems (ICDCS)

作者： Kshemkalyani, Ajay D. Molla, Anisur Rahaman Sharma, Gokarna Univ Illinois Chicago IL 60607 USA Indian Stat Inst Kolkata India Kent State Univ Kent OH 44242 USA

ISBN: (纸本)9781728170022

The dispersion problem on graphs asks k <= n robots placed initially arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a distinct node of the graph. This problem is of significant interest due to its relationship to other fundamental robot coordination problems, such as exploration, scattering, load balancing, and relocation of self-driving electric cars (robots) to recharge stations (nodes). The objective is to simultaneously minimize (or provide trade-off between) two fundamental performance metrics: (i) time to achieve dispersion and (ii) memory requirement at each robot. This problem has been relatively well-studied on static graphs. In this paper, we investigate it for the very first time on dynamic graphs. Particularly, we show that, even with unlimited memory at each robot and 1-neighborhood knowledge, dispersion is impossible to solve on dynamic graphs in the local communication model, where a robot can only communicate with other robots that are present at the same node. We then show that, even with unlimited memory at each robot but without 1-neighborhood knowledge, dispersion is impossible to solve in the global communication model, where a robot can communicate with any other robot in the graph possibly at different nodes. We then consider the global communication model with 1-neighborhood knowledge and establish a tight bound of Theta(k) on the time complexity of solving dispersion in any n-node arbitrary anonymous dynamic graph with Theta(log k) bits memory at each robot. Finally, we extend the fault-free algorithm to solve dispersion for (crash) faulty robots under the global model with 1-neighborhood knowledge.

关键词： Mobile robots Dispersion Dynamic graphs distributed algorithms Runtime Memory Crash faults

来源：评论

学校读者我要写书评

暂无评论

Discovering Evolving Temporal Information: Theory and Application to Clinical Databases

引用

SN Computer Science 2020年第3期1卷 1-30页

作者： Sala, Pietro Combi, Carlo Mantovani, Matteo Rizzi, Romeo Department of Computer Science University of Verona Verona Italy

Functional dependencies (FDs) allow us to represent database constraints, corresponding to requirements as “patients having the same symptoms undergo the same medical tests.” Some research efforts have focused on extending such dependencies to consider also temporal constraints such as “patients having the same symptoms undergo in the next period the same medical tests.” Temporal functional dependencies are able to represent such kind of temporal constraints in relational databases. Another extension for FDs allows one to represent approximate functional dependencies (AFDs), as “patients with the same symptomsgenerallyundergo the same medical tests.” It enables data to deviate from the defined constraints according to a user-defined percentage. Approximate temporal functional dependencies (ATFDs) merge the concepts of temporal functional dependency and of approximate functional dependency. Among the different kinds of ATFD, the Approximate Pure Temporally Evolving Functional Dependencies (APE-FDs for short) allow one to detect patterns on the evolution of data in the database and to discover dependencies as “For most patients with the same initial diagnosis, the same medical test is prescribed after the occurrence of same symptom.” Mining ATFDs from large databases may be computationally expensive. In this paper, we focus on APE-FDs and prove that, unfortunately, verifying a single APE-FD over a given database instance is in general NP-complete. In order to cope with this problem, we propose a framework for mining complex APE-FDs in real-world data collections. In the framework, we designed and applied sound and advanced model-checking techniques. To prove the feasibility of our proposal, we used real-world databases from two medical domains (namely, psychiatry and pharmacovigilance) and tested the running prototype we developed on such databases. © 2020, The Author(s).

关键词： Complexity distributed algorithms Pharmacovigilance Psychiatric case register Temporal data mining Temporal databases Temporal functional dependencies

来源：评论

学校读者我要写书评

暂无评论

Dispersion of Mobile Robots in the Global Communication Model 20

Dispersion of Mobile Robots in the Global Communication Mode...

引用

21st International Conference on distributed Computing and Networking (ICDCN)

作者： Kshemkalyani, Ajay D. Molla, Anisur Rahaman Sharma, Gokarna Univ Illinois Chicago IL 60607 USA Indian Stat Inst Kolkata 700108 India Kent State Univ Kent OH 44240 USA

ISBN: (纸本)9781450377515

The dispersion problem on graphs asks k <= n robots placed initially arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a distinct node of the graph. This problem is of significant interest due to its relationship to other fundamental robot coordination problems, such as exploration, scattering, load balancing, and relocation of self-driven electric cars (robots) to recharge stations (nodes). In this paper, we consider dispersion in the global communication model where a robot can communicate with any other robot in the graph (but the graph is unknown to robots). We provide three novel deterministic algorithms, two for arbitrary graphs and one for arbitrary trees, in a synchronous setting where all robots perform their actions in every time step. For arbitrary graphs, our first algorithm is based on a DFS traversal and guarantees O(min(m, k Delta)) steps runtime using circle minus(log(max(k, Delta))) bits at each robot, where m is the number of edges and Lambda is the maximum degree of the graph. The second algorithm for arbitrary graphs is based on a BFS traversal and guarantees O(max(D, k)Delta(D + Delta)) steps runtime using O(max(D, Delta log k)) bits at each robot, where D is the diameter of the graph. The algorithm for arbitrary trees is also based on a BFS travesal and guarantees O(D max(D, k)) steps runtime using O(max(D, Delta log k)) bits at each robot. Our results are significant improvements compared to the existing results established in the local communication model where a robot can communication only with other robots present at the same node.

关键词： Multi-agent systems Mobile robots Dispersion Collective exploration Scattering Uniform deployment Load balancing distributed algorithms Time and memory complexity

来源：评论

学校读者我要写书评

暂无评论

Scalable distributed reachability query processing in multi-labeled networks

引用

DATA & KNOWLEDGE ENGINEERING 2020年 130卷 101854-101854页

作者： Gacem, Amina Papadopoulos, Apostolos N. Boukhalfa, Kamel Ecole Natl Super Informat Algiers Algeria Aristotle Univ Thessaloniki Sch Informat Thessaloniki Greece Univ Sci & Technol Houari Boumediene Algiers Algeria

Testing reachability in a graph gains substantial interest as an important operation in network analysis and graph mining. In its simplest form, a reachability query is defined by a pair of nodes (u, v) and a graph G, and detects if there is a path from u to v. This paper addresses a specific case of reachability on multi-labeled distributed graphs, where the query is parameterized by a set of source nodes S, a set of target nodes T and a set of constraints C on the edge labels. We conduct a performance evaluation on both synthetic and real-world datasets, using multiple instances of Neo4j servers (as workers) running simultaneously. The results show that the number of workers, the network density and the number of cross-edges have a significant impact on the overall performance. Moreover, we observe that the proposed approach is scalable and can be used to solve label-constrained distributed set reachability queries in multi-labeled networks.

关键词： Graph mining Reachability queries distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient and Robust Top-k algorithms for Big Data IoT

Efficient and Robust Top-k Algorithms for Big Data IoT

引用

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

作者： Yang, Ruifan Zhou, Zheng Tseng, Lewis Alogaily, Moayad Boukerche, Azzedine Cornell Univ Ithaca NY 14850 USA Boston Coll Boston MA USA Al Ain Univ Al Ain U Arab Emirates Univ Ottawa Ottawa ON Canada

ISBN: (纸本)9781728150895

Top-k considers as a technique to retrieve, from a hypothetically big data set, only the k (k >= 1) best (most relevant/important) candidates. Top-k query processing is a decisive necessity in various collaborative environments that comprise big data such as the Internet of Things (IoT) networks. Particularly, efficient top-k processing in large-scale distributed systems has shown a positively noticeable effect on their performance. This paper considers the distributed approximate top-k processing algorithms dedicated to the IoT-based networks and improve the accuracy of algorithms introduced previously. We then propose a safety-based fault-tolerance notation and contribute to improving a known algorithm in terms of accuracy. Our algorithms have been evaluated using simulation and real-world data and show superiority over conventional methods.

关键词： IoT Top-K query fault-tolerance distributed algorithms approximate query

来源：评论

学校读者我要写书评

暂无评论

Effect of nearest neighbors on convergence rate of periodic gossip algorithms in WSNs 9

Effect of nearest neighbors on convergence rate of periodic ...

引用

IEEE 9th International Conference on Communication Systems and Network Technologies (CSNT)

作者： Dhuli, Sateeshkrishna Singh, Y. N. Ranjan, Priya SRM Univ Dept ECE Amaravati AP India IIT Kanpur Dept EE Kanpur Uttar Pradesh India

ISBN: (纸本)9781728149769

distributed algorithms are extremely useful in wireless sensor network to compute the global statistics using local computations. Periodic gossip algorithm is a distributed consensus algorithm, where neighbouring nodes gossip at every time instant. Convergence rate of periodic gossip algorithms determines the time sensor nodes will take to reach consensus. In this paper, we model the WSN as a r-nearest neighbour network and study the effect of nearest neighbours on convergence rate of the gossip algorithms. The 'r' in nearest neighbour network models the node transmission radius and overhead in wireless sensor networks (WSN). We consider the both even and odd number of nodes and observe the convergence rate drastically increasing with the increase in the number of nearest neighbours until the network is fully connected.

关键词： Wireless Sensor Networks Periodic Gossip algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster Deterministic All Pairs Shortest Paths in CONGEST Model 20

Faster Deterministic All Pairs Shortest Paths in CONGEST Mod...

引用

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

作者： Agarwal, Udit Ramachandran, Vijaya Univ Texas Austin Austin TX 78712 USA

ISBN: (纸本)9781450369350

We present a new deterministic algorithm for distributed weighted all pairs shortest paths (APSP) in both undirected and directed graphs. Our algorithm runs in (O) over tilde (n(4/3)) rounds in the Congest models on graphs with arbitrary edge weights, and it improves on the previous (O) over tilde (n(3/2)) bound of Agarwal et al. [3]. The main components of our new algorithm are a new faster technique for constructing blocker set deterministically and a new pipelined method for deterministically propagating distance values from source nodes to the blocker set nodes in the network. Both of these techniques have potential applications to other distributed algorithms. Our new deterministic algorithm for computing blocker set adapts the NC approximate hypergraph set cover algorithm in [5] to the distributed construction of a blocker set. It follows the two-step process of first designing a randomized algorithm that uses only pairwise independence, and then derandomizes this algorithm using a sample space of linear size. This algorithm runs in almost the same number of rounds as the initial step in our APSP algorithm that computes h-hops shortest paths. This result significantly improves on the deterministic blocker set algorithms in [1, 3] by removing an additional n center dot vertical bar Q vertical bar term in the round bound, where Q is the blocker set. The other new component in our APSP algorithm is a deterministic pipelined approach to propagate distance values from source nodes to blocker nodes. We use a simple natural round-robin method for this step, and we show using a suitable progress measure that it achieve the (O) over tilde (n(4/3)) bound on the number of rounds. It appears that the standard deterministic methods for efficiently broadcasting multiple values, and for sending or receiving messages using the routing schedule in an undirected APSP algorithm [13, 16] do not apply to this setting.

关键词： distributed algorithms Shortest Paths Blocker Set

来源：评论

学校读者我要写书评

暂无评论

On Grid Partitioning in AC Optimal Power Flow 10

On Grid Partitioning in AC Optimal Power Flow

引用

10th IEEE PES Innovative Smart Grid Technologies Europe (ISGT-Europe) - Smart Grids - Key Enablers of a Green Power System

作者： Murray, Alexander Kyesswa, Michael Schmurr, Philipp Cakmak, Hueseyin Hagenmeyer, Veit Karlsruhe Inst Technol Karlsruhe Germany

ISBN: (纸本)9781728171005

The AC optimal power flow problem is known to be highly non-convex and scale very poorly with respect to the number of lines and buses. One possible solution is to subdivide and parallelize the problem through distributed optimization. However, the question of how to optimally partition a power grid for use in distributed optimization remains open in the literature. To this end, we compare the graph partitioners KaFFPa and METIS as well as two spectral clustering methods to the standard IEEE 9, 14, 30, 39, 57, 118, 300 bus models. The distributed algorithm ALADIN is used to solve the partitioned OPF problems. For larger grids, KaFFPa yields the best results on average.

关键词： distributed algorithms Partitioning algorithms Power grids Mathematical programming

来源：评论

学校读者我要写书评

暂无评论

In-database connected component analysis 36

In-database connected component analysis

引用

IEEE 36th International Conference on Data Engineering (ICDE)

作者： Bogeholz, Harald Brand, Michael Todor, Radu-Alexandru Monash Univ Fac Informat Technol Melbourne Vic Australia Otzma Analyt Pty Ltd Melbourne Vic Australia UBS Zurich Switzerland

ISBN: (纸本)9781728129037

We describe a Big Data-practical, SQL-implementable algorithm for efficiently determining connected components for graph data stored in a Massively Parallel Processing (MPP) relational database. The algorithm described is a linear-space, randomised algorithm, always terminating with the correct answer but subject to a stochastic running time, such that for any epsilon > 0 and any input graph G = < V, E > the algorithm terminates after O(log vertical bar V vertical bar) SQL queries with probability of at least 1 - epsilon, which we show empirically to translate to a quasi-linear runtime in practice.

关键词： Big Data data science relational databases SQL distributed databases distributed algorithms graph theory blockchain

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：