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

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

作者： Hendler, Danny Khattabi, Adnane Milani, Alessia Travers, Corentin Ben Gurion Univ Negev Beer Sheva Israel Univ Bordeaux LaBRI Bordeaux France Bordeaux INP LaBRI Bordeaux France

ISBN: (纸本)9781665445139

Relaxing the sequential specification of shared objects has been proposed as a promising approach to obtain implementations with better complexity. In this paper, we study the step complexity of relaxed variants of two common shared objects: max registers and counters. In particular, we consider the k-multiplicative-accurate max register and the k-multiplicative-accurate counter, where read operations are allowed to err by a multiplicative factor of k (for some k is an element of N). More accurately, reads are allowed to return an approximate value x of the maximum value v previously written to the max register, or of the number v of increments previously applied to the counter, respectively, such that v/k <= x <= v.k. We provide upper and lower bounds on the complexity of implementing these objects in a wait-free manner in the shared memory model.

关键词： distributed computing distributed algorithms shared memory fault tolerance concurrent data structures relaxed specifications

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks 21

Brief Announcement: Wake Up and Join Me! An Energy-Efficient...

引用

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

作者： Dani, Varsha Gupta, Aayush Hayes, Thomas P. Pettie, Seth Ronin Inst Montclair NJ 07043 USA Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA Univ Michigan Dept EECS Ann Arbor MI 48109 USA

ISBN: (纸本)9781450385480

We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology. We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is O(log(2) n), and the time complexity is O(Delta log(n)). Here n is any upper bound on the number of nodes, and Delta is any upper bound on the maximum degree;n and Delta are parameters of our algorithm that we assume are known a priori to all the processors. We note that there exist families of graphs for which our bounds on energy cost and time complexity are simultaneously optimal up to polylog factors, so any significant improvement would need additional assumptions about the network topology. We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of eventual node failure. Here, a key goal is to minimize the maximum load, defined as the number of nodes assigned to a single node. We present an efficient decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog(n) factor bigger that the optimum.

关键词： distributed algorithms Energy-Aware Computation Radio Networks Maximal Matching Sensor Networks

来源：评论

学校读者我要写书评

暂无评论

Polylogarithmic-Time Deterministic Network Decomposition and distributed Derandomization 2020

Polylogarithmic-Time Deterministic Network Decomposition and...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Rozhon, Vaclav Ghaffari, Mohsen Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450369794

We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated 2(O(root log n))-time algorithm of Panconesi and Srinivasan [STOC'92] and settles a central and long-standing question in distributed graph algorithms. It also leads to the first polylogarithmictime deterministic distributed algorithms for numerous other problems, hence resolving several well-known and decades-old open problems, including Linial's question about the deterministic complexity of maximal independent set [FOCS'87;SICOMP'92]-which had been called the most outstanding problem in the area. The main implication is a more general distributed derandomization theorem: Put together with the results of Ghaffari, Kuhn, and Maus [STOC'17] and Ghaffari, Harris, and Kuhn [FOCS'18], our network decomposition implies that P-RLOCAL = P-LOCAL. That is, for any problem whose solution can be checked deterministically in polylogarithmic-time, any polylogarithmic-time randomized algorithm can be derandomized to a polylogarithmic-time deterministic algorithm. Informally, for the standard first-order interpretation of efficiency as polylogarithmic-time, distributed algorithms do not need randomness for efficiency. By known connections, our result leads also to substantially faster randomized distributed algorithms for a number of well-studied problems including (Delta + 1)-coloring, maximal independent set, and Lovasz Local Lemma, as well as massively parallel algorithms for (Delta + 1)-coloring.

关键词： network decomposition distributed algorithms derandomization

来源：评论

学校读者我要写书评

暂无评论

NEAR-OPTIMAL APPROXIMATE SHORTEST PATHS AND TRANSSHIPMENT IN distributed AND STREAMING MODELS

引用

SIAM JOURNAL ON COMPUTING 2021年第3期50卷 815-856页

作者： Becker, Ruben Forster, Sebastian Karrenbauer, Andreas Lenzen, Christoph Gran Sasso Sci Inst Laquila Italy Univ Salzburg Dept Comp Sci Salzburg Austria Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany

We present a method for solving the transshipment problem-also known as uncapacitated minimum cost flow-up to a multiplicative error of 1+ epsilon in undirected graphs with nonnegative edge weights using a tailored gradient descent algorithm. Using \widetilde (O) over tilde (.) to hide polylogarithmic factors in n (the number of nodes in the graph), our gradient descent algorithm takes \widetilde (O) over tilde(epsilon(-2)) iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of polylog n. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a randomized rounding scheme, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve upon prior works by obtaining the following results: (1) Broadcast CONGEST model: (1 + epsilon)-approximate SSSP using (O) over tilde((root n + D)epsilon(-3)) rounds, where D is the (hop) diameter of the network. (2) Broadcast Congested Clique model: (1 + epsilon)-approximate transshipment and SSSP using \widetilde (O) over tilde(epsilon(-2)) rounds. (3) Multipass Streaming model: (1 + epsilon)-approximate transshipment and SSSP using \widetilde (O) over tilde (n) space and \widetilde (O) over tilde(epsilon(-2)) passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction;computing a spanner is sufficient with our method. The above bounds assume nonnegative edge weights that are polynomially bounded in n;for general nonnegative weights, there is an additional multiplicative overhead equal to the logarithm of the maximum ratio between nonzero weights. Our algorithms can also handle asymmetric costs for traversing edges in opposite directions. In this case, we obtain an additional multiplicative dependence of the maximum ratio between the two costs on so

关键词： shortest paths gradient descent distributed algorithms streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Contention Resolution with Predictions 21

Contention Resolution with Predictions

引用

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

作者： Gilbert, Seth Newport, Calvin Vaidya, Nitin Weaver, Alex Natl Univ Singapore Singapore Singapore Georgetown Univ Washington DC 20057 USA

ISBN: (纸本)9781450385480

In this paper, we consider contention resolution algorithms that are augmented with predictions about the network. We begin by studying the natural setup in which the algorithm is provided a distribution defined over the possible network sizes that predicts the likelihood of each size occurring. The goal is to leverage the predictive power of this distribution to improve on worst-case time complexity bounds. Using a novel connection between contention resolution and information theory, we prove lower bounds on the expected time complexity with respect to the Shannon entropy of the corresponding network size random variable, for both the collision detection and no collision detection assumptions. We then analyze upper bounds for these settings, assuming now that the distribution provided as input might differ from the actual distribution generating network sizes. We express their performance with respect to both entropy and the statistical divergence between the two distributions-allowing us to quantify the cost of poor predictions. Finally, we turn our attention to the related perfect advice setting, parameterized with a length b >= 0, in which all active processes in a given execution are provided the best possible b bits of information about their network. We provide tight bounds on the speed-up possible with respect to b for deterministic and randomized algorithms, with and without collision detection. These bounds provide a fundamental limit on the maximum power that can be provided by any predictive model with a bounded output size.

关键词： distributed algorithms contention resolution

来源：评论

学校读者我要写书评

暂无评论

An energy saving approach: Understanding microservices as multidimensional entities in p2p networks 21

An energy saving approach: Understanding microservices as mu...

引用

36th Annual ACM Symposium on Applied Computing (SAC)

作者： Valera, Hernan Humberto Alvarez Dalmau, Marc Roose, Philippe Larracoechea, Jorge Herzog, Christina Univ Pau E2S UPPA Anglet France EFFICIT SAS Mauzac France

ISBN: (纸本)9781450381048

With the use of microservices, many software solutions have been improved in terms of scalability, response efficiency, ease of load balancing among others. However, it is still a challenge to dynamically deploy them according to devices' heterogeneity and energy consumption concerns, while maintaining a defined QoS. Centralized and decentralized approaches that manage microservices deployment have the traditional pros and cons long discussed over time. While the former offer greater control over distributed application components, the latter offers frugal network negotiations, no system-wide crashes, privacy, among others. This work focuses on identifying "ideal" host candidates for microservices' execution in a decentralized network, applying run-time scheduling operations (migration or duplication) to reduce energy consumption. To do this, we created a scheduling algorithm using MAAN (a P2P approach) to interpret a decentralized network as a multidimensional resource (capacity-demand) space, which supports range queries in a logarithmic quantity of hops. In this way, a node that runs a set of microservices is able to 1) map them in terms of their execution requirements (i.e. CPU frequency, RAM capacity, Network rate and disk speed) 2) Select an ideal microservice to be moved or duplicated, 3) find ideal node(s) that meet all those requirements in an optimal computational complexity and 4) negotiate the movement or duplication of the selected microservice, by analyzing energy consumption and QoS criteria.

关键词： distributed algorithms power consumption energy consumption P2P microservices cloud computing

来源：评论

学校读者我要写书评

暂无评论

IMPROVED STEP-SIZE SCHEDULES FOR NOISY GRADIENT METHODS

IMPROVED STEP-SIZE SCHEDULES FOR NOISY GRADIENT METHODS

引用

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Khirirat, Sarit Wang, Xiaoyu Magnusson, Sindri Johansson, Mikael KTH Royal Inst Technol Stockholm Sweden Stockholm Univ Stockholm Sweden

ISBN: (纸本)9781728176055

Noise is inherited in many optimization methods such as stochastic gradient methods, zeroth-order methods and compressed gradient methods. For such methods to converge toward a global optimum, it is intuitive to use large step-sizes in the initial iterations when the noise is typically small compared to the algorithm-steps, and reduce the step-sizes as the algorithm progresses. This intuition has been confirmed in theory and practice for stochastic gradient methods, but similar results are lacking for other methods using approximate gradients. This paper shows that the diminishing step-size strategies can indeed be applied for a broad class of noisy gradient methods. Unlike previous works, our analysis framework shows that such step-size schedules enable these methods to enjoy an optimal O(1/k) rate. We exemplify our results on zeroth-order methods and stochastic compression methods. Our experiments validate fast convergence of these methods with the step decay schedules.

关键词： Optimization machine learning distributed algorithms zeroth-order algorithms quantization

来源：评论

学校读者我要写书评

暂无评论

FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems 40

FIFO and Atomic broadcast algorithms with bounded message si...

引用

40th International Symposium on Reliable distributed Systems (SRDS)

作者： Johnen, Colette Arantes, Luciana Sens, Pierre INRIA Paris LIP6 UMR 7606 Paris France Univ Bordeaux LaBRI UMR 5800 Bordeaux France Sorbonne Univ LIP6 INRIA CNRS Paris France

ISBN: (纸本)9781665438193

FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and have been mostly implemented on top of unreliable static networks. In this article, we propose a round-based FIFO broadcast algorithm with both termination detection and bounded message size for dynamic networks with recurrent connectivity (Class TCR of Time-varying Graph formalism [1]). Initially, processes only know the number of processes N in the system and their identifier. Due to the dynamics of the network links, messages can be lost. Since no unbounded timestamp is used to identify a message, its size is bounded to 2N + O(log(N)) + msgSize bits where msgSize is the bound size in bits of the broadcast data. We also present a FIFO atomic broadcast algorithm for dynamic networks with recurrent connectivity that uses the proposed FIFO broadcast and deliver primitives. This algorithm provides causal total order broadcast primitives.

关键词： Theory of computation distributed algorithms dynamic graphs communication primitive FIFO Broadcast Causal Broadcast Atomic Broadcast total order Broadcast bounded message size

来源：评论

学校读者我要写书评

暂无评论

Caching Heterogeneous Size Content in Small Cell Networks with CoMP Joint Transmissions

Caching Heterogeneous Size Content in Small Cell Networks wi...

引用

IEEE Global Communications Conference (GLOBECOM)

作者： Ricardo, Guilherme Iecker L. Neglia, Giovanni Spyropoulos, Thrasyvoulos EURECOM Biot France Univ Cote dAzur INRIA Nice France

ISBN: (纸本)9781728181042

In SG and beyond network architectures, operators and content providers base their content distribution strategies on small cell networks. On top of such networks, edge caching and Coordinated Multi-Point (CoMP) Joint Transmissions are used to improve performance. Online solutions for average delay minimization problem have been studied in the related literature, although only under the strong assumption that files have equal sizes. In this paper we aim to fill this gap and propose an online caching policy, qLRU-HS, that takes into account heterogeneous sizes and asymptotically converges to the optimal cache allocation under the Independent Reference Model. Our experiments confirm such convergence in practice and reveal that qLRU-HS outperforms other state-of-the-art solutions.

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

来源：评论

学校读者我要写书评

暂无评论

CoCoS: Fast and Accurate distributed Triangle Counting in Graph Streams

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2021年第3期15卷 38-38页

作者： Shin, Kijung Lee, Euiwoong Oh, Jinoh Hammoud, Mohammad Faloutsos, Christos Korea Adv Inst Sci & Technol 291 Daehak Ro Daejeon 34141 South Korea Univ Michigan 500 S State St Ann Arbor MI 48109 USA Carnegie Mellon Univ 5000 Forbes Ave Pittsburgh PA 15213 USA Carnegie Mellon Univ Qatar Doha 24866 Qatar

Given a graph stream, how can we estimate the number of triangles in it using multiple machines with limited storage? Specifically, how should edges be processed and sampled across the machines for rapid and accurate estimation? The count of triangles (i.e., cliques of size three) has proven useful in numerous applications, including anomaly detection, community detection, and link recommendation. For triangle counting in large and dynamic graphs, recent work has focused largely on streaming algorithms and distributed algorithms but little on their combinations for "the best of both worlds." In this work, we propose CoCoS, a fast and accurate distributed streaming algorithm for estimating the counts of global triangles (i.e., all triangles) and local triangles incident to each node. Making one pass over the input stream, CoCoS carefully processes and stores the edges across multiple machines so that the redundant use of computational and storage resources is minimized. Compared to baselines, CoCoS is: (a) accurate: giving up to 39x smaller estimation error;(b) fast: up to 10.4x faster, scaling linearly with the size of the input stream;and (c) theoretically sound: yielding unbiased estimates.

关键词： Graph stream triangle counting sampling streaming algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：