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

40th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Elkin, Michael Matar, Shaked Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9781450385480

Near-additive (aka (1 + epsilon, beta)-) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related problems in distributed, streaming and dynamic settings. Known constructions of near-additive emulators enable one to trade between their sparsity (i.e., number of edges) and the additive stretch beta. Specifically, for any pair of parameters epsilon > 0, kappa = 1, 2, ..., one can have a (1 + epsilon, beta)-emulator with O(n(1+1/kappa)) edges, with beta = (log kappa/epsilon)(log kappa). At their sparsest, these emulators employ c . n edges, for some constant c >= 2. We tighten this bound, and show that in fact precisely n(1+1/kappa )edges suffice. In particular, our emulators can be ultra-sparse, i.e., we can have an emulator with n + o(n) edges and beta (log log n/epsilon)(log log n (1+o(1))).( ) We also devise a distributed deterministic algorithm in the CONG EST model that builds these emulators in low polynomial time (i.e., in O(n(rho)) time, for an arbitrarily small constant parameter time, for an arbitrarily small constant parameter rho > 0). Finally, we also improve the state-of-the-art distributed deterministic CONGEST-model construction of (1 + epsilon, beta)-spanners devised in the PODC'19 paper [13]. Specifically, the spanners of [13] have O(beta . n(1+1/kappa)) edges, i.e., at their sparsest they employ O(log log n/epsilon) (log log n). n edges. In this paper, we devise an efficient distributed deterministic CONGEST-model algorithm that builds such spanners with O(n(1+1/kappa)) edges for kappa = O (log n/log((3) )n). K = 0 At their sparsest, these spanners employ only O(n. log log n) edges.

关键词： Emulators Deterministic distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Time and Communication Complexity of Leader Election in Anonymous Networks 41

Time and Communication Complexity of Leader Election in Anon...

引用

41st IEEE International Conference on distributed Computing Systems (ICDCS)

作者： Kowalski, Dariusz R. Mosteiro, Miguel A. Augusta Univ Augusta GA 30912 USA SWPS Univ Warsaw Poland Pace Univ New York NY 10038 USA

ISBN: (纸本)9781665445139

We study the problem of randomized Leader Election in synchronous distributed networks with indistinguishable nodes. We consider algorithms that work on networks of arbitrary topology in two settings, depending on whether the size of the network, i.e., the number of nodes n, is known or not. In the former setting, we present a new Leader Election protocol that improves over previous work by lowering message complexity and making it close to a lower bound by a factor in 0 (\/t, \/.7I)), where (I) is the conductance and is the mixing time of the network graph. We then show that lacking the network size no Leader Election algorithm can guarantee that the election is final with constant probability, even with unbounded communication. Hence, we further classify the problem as Leader Election (the classic one, requiring knowledge of n as is our first protocol) or Revocable Leader Election, and present a new polynomial time and message complexity Revocable Leader Election algorithm in the setting without knowledge of network size. We analyze time and message complexity of our protocols in the CONGEST model of communication.

关键词： Leader Election Anonymous Networks Ad -hoc Networks distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique 2021

A Deterministic Algorithm for the MST Problem in Constant Ro...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Nowicki, Krzysztof Univ Copenhagen Copenhagen Denmark Univ Wroclaw Wroclaw Poland

ISBN: (纸本)9781450380539

In this paper we show that the Minimum Spanning Tree problem (MST) can be solved deterministically in O(1) rounds of the Congested Clique model. In the Congested Clique model there are n players that perform computation in synchronous rounds. Each round consist of a phase of local computation and a phase of communication, in which each pair of players is allowed to exchange O(log n) bit messages. The studies of this model began with the MST problem: in the paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05] that defines the Congested Clique model the authors give a deterministic O(log log n) round algorithm that improved over a trivial O(log n) round adaptation of Boravka's algorithm. There was a sequence of gradual improvements to this result: an O(log log log n) round algorithm by Hegeman, Pandurangan, Pemmaraju, Sardeshmukh, and Scquizzato [PODC'15], an O(log* n) round algorithm by Ghaffari and Parter, [PODC'16] and an O(1) round algorithm by Jurdzinski and Nowicki, [SODA'18], but all those algorithms were randomized. Therefore, the question about the existence of any deterministic o(log log n) round algorithms for the Minimum Spanning Tree problem remains open since the seminal paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05]. Our result resolves this question and establishes that O(1) rounds is enough to solve the MST problem in the Congested CI iq ue model, even if we are not allowed to use any randomness. Furthermore, the amount of communication needed by the algorithm makes it applicable to a variant of the M PC model using machines with local memory of size O(n).

关键词： Minimum Spanning Tree MST Deterministic algorithms Graph algorithms distributed algorithms Congested Clique Parallel algorithms Massively Parallel algorithms MapReduce

来源：评论

学校读者我要写书评

暂无评论

distributed scheduling method for multiple workflows with parallelism prediction and DAG prioritizing for time constrained cloud applications

引用

COMPUTER NETWORKS 2021年 201卷 108560-108560页

作者： Davami, Fatemeh Adabi, Sahar Rezaee, Ali Rahmani, Amir Masoud Islamic Azad Univ North Tehran Branch Dept Comp Engn Tehran Iran Islamic Azad Univ Sci & Res Branch Dept Comp Engn Tehran Iran Natl Yunlin Univ Sci & Technol Future Technol Res Ctr 123 Univ RdSect 3 Touliu 64002 Yunlin Taiwan

Fog computing is an emerging popular paradigm that extends the availability of resources to the network's edge in order to improve the quality metrics of existing Cloud-based applications. However, scheduling workflow applications with time-constraints are complex regarding the count of resources, physical topology of clusters, and the structure of the task graph of the workflows. Adding Fog resources to the intricate problem space of Cloud-based scheduling needs even more time-consuming and complicated algorithms. In this paper, a multi-criteria Mamdani fuzzy algorithm is proposed to analyze the workflow graphs with the assistance of a LongShort Term Memory neural network parallelism prediction module. The group-based priority assignment schema performed by the fuzzy inference system assigns a priority value to workflows to indicate the relative precedence of requests. distributed schedulers then send the workflows to target sites according to their current workloads. The whole process is performed in a decentralized manner to prevent any bottlenecks. We have used an extensive software simulation study to compare the proposed algorithm in real workloads with two recent and notable algorithms. The simulation results confirm the proposed algorithm's superiority in fulfilling time-constraints, resource utilization, and overall application scheduling success rate.

关键词： Multiple workflows scheduling Cloud Fog computing distributed algorithms Long-short term memory FIS

来源：评论

学校读者我要写书评

暂无评论

VisibleSim: A behavioral simulation framework for lattice modular robots

引用

ROBOTICS AND AUTONOMOUS SYSTEMS 2022年第0期147卷 103913-103913页

作者： Thalamy, Pierre Piranda, Benoit Naz, Andre Bourgeois, Julien Univ Bourgogne Franche Comte CNRS FEMTO ST Inst 1 Cours Leproice Ringuet F-25200 Montbeliard France Univ Bourgogne Franche Comte UBFC CNRS FEMTO ST Inst Montbeliard France

Simulation is one of the most important tools for robotics research, as it serves several crucial purposes such as prototyping, learning, avoiding dispensable hardware costs, or studying future systems that cannot be fabricated yet. Large scale self-reconfiguring modular robotic systems are an instance of such systems. Yet, current modular robotic simulators are overwhelmingly physics-based, which are good for real-world simulation but can be superfluous and sacrifice scalability when studying such systems through a behavioral lens. This paper introduces VisibleSim, an open-source behavioral simulator for lattice-based modular robots that uses discrete-event simulation. We describe the principles behind the simulator and introduce its features and usage from a user standpoint. VisibleSim has unique features like extensibility, versatility, and flexibility, it can also be used as a powerful visualization tool and has already a proven track record with several modular robotic architectures. We present a stress test composed of, ultimately, 32 million simulated robots, a new record in the field of modular robotic simulation. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Discrete-event simulator Modular robotic systems Programmable matter distributed algorithms Robotic simulation

来源：评论

学校读者我要写书评

暂无评论

Efficient CRDT Synchronization at Scale using a Causal Multicast over a Virtual Hypercube Overlay 22

Efficient CRDT Synchronization at Scale using a Causal Multi...

引用

Proceedings of the 11th Latin-American Symposium on Dependable Computing

作者： Leonardo de Freitas Galesky Luiz Antonio Rodrigues Western Parana State University – UNIOESTE 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.

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

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal Scheduling in the Congested Clique 28th

Near-Optimal Scheduling in the Congested Clique

引用

28th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Censor-Hillel, Keren Maus, Yannic Polosukhin, Volodymyr Technion Haifa Israel

ISBN: (纸本)9783030795269;9783030795276

This paper provides three nearly-optimal algorithms for scheduling t jobs in the CLIQUE model. First, we present a deterministic scheduling algorithm that runs in O(GlobalCongestion + dilation) rounds for jobs that are sufficiently efficient in terms of their memory. The dilation is the maximum round complexity of any of the given jobs, and the GlobalCongestion is the total number of messages in all jobs divided by the per-round bandwidth of n(2) of the CLIQUE model. Both are inherent lower bounds for any scheduling algorithm. Then, we present a randomized scheduling algorithm which runs t jobs in O(GlobalCongestion + dilation . log n + t) rounds and only requires that inputs and outputs do not exceed O(n log n) bits per node, which is met by, e.g., almost all graph problems. Lastly, we adjust the random-delay-based scheduling algorithm [Ghaffari, PODC'15] from the CONGEST model and obtain an algorithm that schedules any t jobs in O(t/n + LocalCongestion + dilation . log n) rounds, where the LocalCongestion relates to the congestion at a single node of the CLIQUE. We compare this algorithm to the previous approaches and show their benefit. We schedule the set of jobs on-the-fly, without a priori knowledge of its parameters or the communication patterns of the jobs. In light of the inherent lower bounds, all of our algorithms are nearly-optimal. We exemplify the power of our algorithms by analyzing the message complexity of the state-of-the-art MIS protocol [Ghaffari, Gouleakis, Konrad, Mitrovic and Rubinfeld, PODC'18], and we show that we can solve t instances of MIS in O(t+ log *** n) rounds, that is, in O(1) amortized time, for t >= log log Delta log n.

关键词： distributed algorithms Congested clique Scheduling Maximal independent set

来源：评论

学校读者我要写书评

暂无评论

Reduced-communication parallel dynamic mode decomposition

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2022年第0期61卷

作者： Maryada, K. R. Norris, S. E. Univ Auckland Dept Mech Engn Auckland New Zealand

A new reduced-communication parallel algorithm for deterministic dynamic mode decomposition of large datasets on distributed memory architectures is presented, which has notable savings in computational and communication costs. The parallel algorithm relies on horizontal-slicing and parallel Tall and Skinny QR factorisation to compress the high-dimensional snapshot data. The compressed snapshot data is used to construct the Koopman operator using an embarrassingly parallel approach, resulting in only one communication step for the entire parallel algorithm. The computation of the orthonormal matrix during the parallel QR factorisation is avoided for time-series data, leading to significant savings in computational costs. Numerical tests on highfidelity computational fluid dynamics data show that the current algorithm is up to 2.5 times faster than existing parallel approaches without sacrificing accuracy.

关键词： distributed algorithms Domain decomposition Parallel dynamic mode decomposition Modal reduction

来源：评论

学校读者我要写书评

暂无评论

Domain Compression and its Application to Randomness-Optimal distributed Goodness-of-Fit 33

Domain Compression and its Application to Randomness-Optimal...

引用

33rd Conference on Learning Theory (COLT)

作者： Acharya, Jayadev Canonne, Clement L. Han, Yanjun Sun, Ziteng Tyagi, Himanshu Cornell Univ Ithaca NY USA IBM Res Almaden CA USA Stanford Univ Stanford CA 94305 USA IISc Bangalore Bangalore Karnataka India

We study goodness-of-fit of discrete distributions in the distributed setting, where samples are divided between multiple users who can only release a limited amount of information about their samples due to various information constraints. Recently, a subset of the authors showed that having access to a common random seed (i.e., shared randomness) leads to a significant reduction in the sample complexity of this problem. In this work, we provide a complete understanding of the interplay between the amount of shared randomness available, the stringency of information constraints, and the sample complexity of the testing problem by characterizing a tight trade-off between these three parameters. We provide a general distributed goodness-of-fit protocol that as a function of the amount of shared randomness interpolates smoothly between the private- and public-coin sample complexities. We complement our upper bound with a general framework to prove lower bounds on the sample complexity of this testing problems under limited shared randomness. Finally, we instantiate our bounds for the two archetypal information constraints of communication and local privacy, and show that our sample complexity bounds are optimal as a function of all the parameters of the problem, including the amount of shared randomness. A key component of our upper bounds is a new primitive of domain compression, a tool that allows us to map distributions to a much smaller domain size while preserving their pairwise distances, using a limited amount of randomness.

关键词： Hypothesis testing goodness-of-fit distributed algorithms discrete distributions randomness dimensionality reduction communication constraints privacy

来源：评论

学校读者我要写书评

暂无评论

LSF-Join: Locality Sensitive Filtering for distributed All-Pairs Set Similarity Under Skew 20

LSF-Join: Locality Sensitive Filtering for Distributed All-P...

引用

29th Web Conference (WWW)

作者： Rashtchian, Cyrus Sharma, Aneesh Woodruff, David P. UCSD La Jolla CA 92093 USA Google Stanford CA USA CMU Pittsburgh PA USA

ISBN: (纸本)9781450370233

All-pairs set similarity is a widely used data mining task, even for large and high-dimensional datasets. Traditionally, similarity search has focused on discovering very similar pairs, for which a variety of efficient algorithms are known. However, recent work has highlighted the importance of discovering pairs of sets with relatively small intersection sizes. For example, in a recommender system, two users may be alike even though their interests only overlap on a small percentage of items. In such systems, it is also common that some dimensions are highly-skewed, because they are very popular. Together, these two properties render previous approaches infeasible for large input sizes. To address this problem, we present a new distributed algorithm, LSF-Join, for approximate all-pairs set similarity. The core of our algorithm is a randomized selection procedure based on Locality Sensitive Filtering. In particular, our method deviates from prior approximate algorithms, which are based on Locality Sensitive Hashing. Theoretically, we show that LSF-Join efficiently finds most close pairs, even for small similarity thresholds and for skewed input sets. We prove guarantees on the communication, work, and maximum load of LSF-Join, and we also experimentally demonstrate its accuracy on multiple graphs.

关键词： similarity search distributed algorithms social networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：