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

38th acm symposium on principles of distributed computing (PODC)

作者： Gelles, Ran Kalai, Yael Tauman Ramnarayan, Govind Bar Ilan Univ Ramat Gan Israel Microsoft Res Redmond WA USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781450362177

In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel. We provide efficient, constant rate schemes that successfully conduct any computation with high probability as long as the adversary corrupts at most epsilon/m fraction of the total communication, where m is the number of links in the network and epsilon is a small constant. This scheme assumes an oblivious adversary which is independent of the parties' inputs and randomness. We can remove this assumption and resist a worst-case adversary at the price of being resilient to epsilon/m log m errors. While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.

关键词： interactive coding distributed algorithms error correcting codes

来源：评论

学校读者我要写书评

暂无评论

Simulating heterogeneous models on multi-core platforms using Julia's computing language parallel potential 20

Simulating heterogeneous models on multi-core platforms usin...

引用

proceedings of the IEEE/acm 24th International symposium on distributed Simulation and Real Time Applications

作者： Sergey Suslov Michael Schiek Markus Robens Christian Grewing Stefan van Waasen ZEA-2 - Electronic Systems Germany

This paper addresses the questions of high-level system modelling using heterogeneous multi-tool modelling environment on parallel multi-core processing systems for simulation acceleration. The modelling technique has been applied for high-level validation of a high-precision Indoor Positioning System for Motion Analysis (IPS-MA) developed in the Central Institute Electronic Systems (ZEA-2) of the Research Center Juelich GmbH. The heterogeneous modelling environment has been built using an implementation-level model designed in Matlab Simulink, a verification model for describing the system environment using Modelica language, and Julia language for automatic generation of binding modelling environment and parallelizing the simulation of the overall model. The approach showed a good flexibility in system description and verification in the multi-instrument modelling environment and a good performance gain due to simulation parallelism.

关键词： modelica Julia computing language high level system modelling parallelized simulation distributed simulation functional verification

来源：评论

学校读者我要写书评

暂无评论

Asynchronous Arbitrary Pattern Formation: the effects of a rigorous approach

引用

distributed computing 2019年第2期32卷 91-132页

作者： Cicerone, Serafino Di Stefano, Gabriele Navarra, Alfredo Univ Aquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy Univ Perugia Dept Math & Comp Sci Via Vanvitelli 1 I-06123 Perugia Italy

Given any multiset F of points in the Euclidean plane and a set R of robots such that |R|=|F|, the Arbitrary Pattern Formation (APF) problem asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections, uniform scalings. Initially, each robot occupies a distinct position. When active, a robot operates in standard Look-Compute-Move cycles. Robots are asynchronous, oblivious, anonymous, silent and execute the same distributed algorithm. So far, the problem has been mainly addressed by assuming chirality, that is robots share a common left-right orientation. We are interested in removing such a restriction. While working on the subject, we faced several issues that required close attention. We deeply investigated how such difficulties were overcome in the literature, revealing that crucial arguments for the correctness proof of the existing algorithms have been neglected. The systematic lack of rigorous arguments with respect to necessary conditions required for providing correctness proofs deeply affects the validity as well as the relevance of strategies proposed in the literature. Here we design a new deterministic distributed algorithm that fully characterizes APF showing its equivalence with the well-known Leader Election problem in the asynchronous model without chirality. Our approach is characterized by the use of logical predicates in order to formally describe our algorithm as well as its correctness. In addition to the relevance of our achievements, our techniques might help in revising previous results. In fact, it comes out that well-established results like (Fujinaga et al. in SIAM J Comput 44(3):740-785, 2015), more recent approaches like (Bramas and Tixeuil, in: proceedings of the 35th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC), 2016;Bramas and Tixeuil, in: proceedings of the 18th interna

关键词： distributed algorithms Mobile robots Asynchrony Pattern formation

来源：评论

学校读者我要写书评

暂无评论

AgileWatts: An Energy-Efficient CPU Core Idle-State Architecture for Latency-Sensitive Server Applications 22

AgileWatts: An Energy-Efficient CPU Core Idle-State Architec...

引用

proceedings of the 55th Annual IEEE/acm International symposium on Microarchitecture

作者： Jawad Haj Yahya Haris Volos Davide B. Bartolini Georgia Antoniou Jeremie S. Kim Zhe Wang Kleovoulos Kalaitzidis Tom Rollet Zhirui Chen Ye Geng Onur Mutlu Yiannakis Sazeides Rivos Inc Mountain View California United States Computer Architecture Laboratory Department of Computer Science University of Cyprus Computing Systems Lab Huawei Zurich Research Center Department of Information Technology and Electrical Engineering ETH Zurich Switzerland

ISBN: (纸本)9781665462723

User-facing applications running in modern datacenters exhibit irregular request patterns and are implemented using a multitude of services with tight latency requirements (30--250μs). These characteristics render existing energy-conserving techniques ineffective when processors are idle due to the long transition time (order of 100μs) from a deep CPU core idle power state (C-state). While prior works propose management techniques to mitigate this inefficiency, we tackle it at its root with AgileWatts (AW): a new deep CPU core C-state architecture optimized for datacenter server processors targeting latency-sensitive *** drastically reduces the transition latency from deep CPU core idle power states while retaining most of their power savings based on three key ideas. First, AW eliminates the latency (several microseconds) of saving/restoring the core context when powering-off/-on the core in a deep idle state by i) implementing medium-grained power-gates, carefully distributed across the CPU core, and ii) retaining context in the power-ungated domain. Second, AW eliminates the flush latency (several tens of microseconds) of the L1/L2 caches when entering a deep idle state by keeping L1/L2 content power-ungated. A small control logic also remains ungated to serve cache coherence traffic. AW implements cache sleep-mode and leakage reduction for the power-ungated domain by lowering a core's voltage to the minimum operational level. Third, using a state-of-the-art power efficient all-digital phase-locked loop (ADPLL) clock generator, AW keeps the PLL active and locked during the idle state, cutting microseconds of wake-up latency at negligible power *** evaluation with an accurate industrial-grade simulator calibrated against an Intel Skylake server shows that AW reduces the energy consumption of Memcached by up to 71% (35% on average) with <1% end-to-end performance degradation. We observe similar trends for other evaluated services (MySQL and Kafka).

关键词：

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of distributed Splitting Problems 19

On the Complexity of Distributed Splitting Problems

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Bamberger, Philipp Ghaffari, Mohsen Kuhn, Fabian Maus, Yannic Uitto, Jara Univ Freiburg Freiburg Germany Swiss Fed Inst Technol Zurich Switzerland Technion Haifa Israel

ISBN: (纸本)9781450362177

One of the fundamental open problems in the area of distributed graph algorithms is whether randomization is needed for efficient symmetry breaking. While there are poly logn-time randomized algorithms for all the classic symmetry breaking problems, for many of them, the best deterministic algorithms are almost exponentially slower. The following basic local splitting problem, which is known as weak splitting, takes a central role in this context: Each node of a graph G = (V, E) has to be colored red or blue such that each node of sufficiently large degree has at least one neighbor of each color. Ghaffari, Kuhn, and Maus [STOC '17] showed that this seemingly simple problem is complete w.r.t. the above fundamental open question in the following sense: If there is an efficient poly logn-time determinstic distributed algorithm for weak splitting, then there is such an algorithm for all locally checkable graph problems for which an efficient randomized algorithm exists. We investigate the distributed complexity of weak splitting and some closely related problems and we in particular obtain the following results: center dot We obtain efficient algorithms for special cases of weak splitting in nearly regular graphs. We show that if delta = Omega(log n) and Delta are the minimum and maximum degrees of G, weak splitting can be solved deterministically in time O(Delta/delta center dot poly(log n)). Further, if delta = Omega(log log n) and Delta <= 2(epsilon delta), the time complexity is O(Delta/delta center dot poly(log log n)). center dot We prove that the following two related problems are also complete in the same sense: (I) Color the nodes of a graph with C <= poly log n colors such that each node with a sufficiently large polylogarithmic degree has at least 2 log n different colors among its neighbors, and (II) Color the nodes with a large constant number of colors so that for each node of a sufficiently large at least logarithmic degree d(v), the number of neighbors o

关键词： distributed graph algorithms weak splitting LOCAL Model distributed symmetry breaking randomness

来源：评论

学校读者我要写书评

暂无评论

Strongly Linearizable Implementations of Snapshots and Other Types 19

Strongly Linearizable Implementations of Snapshots and Other...

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Ovens, Sean Woelfel, Philipp Univ Calgary Calgary AB Canada

ISBN: (纸本)9781450362177

Linearizability is the gold standard of correctness conditions for shared memory algorithms, and historically has been considered the practical equivalent of atomicity. However, it has been shown [16] that replacing atomic objects with linearizable implementations can affect the probability distribution of execution outcomes in randomized algorithms. Thus, linearizable objects are not always suitable replacements for atomic objects. A stricter correctness condition called strong linearizability has been developed and shown to be appropriate for randomized algorithms in a strong adaptive adversary model [16]. We devise several new lock-free strongly linearizable implementations from atomic registers. In particular, we give the first strongly linearizable lock-free snapshot implementation that uses bounded space. This improves on the unbounded space solution of Denysyuk and Woelfel [14]. As a building block, our algorithm uses a lock-free strongly linearizable ABA-detecting register. We obtain this object by modifying the wait-free linearizable ABA-detecting register of Aghazadeh and Woelfel [5], which, as we show, is not strongly linearizable. Aspnes and Herlihy [8] identified a wide class of types that have wait-free linearizable implementations. These types require that any pair of operations either commute, or one overwrites the other. Aspnes and Herlihy gave a general wait-free linearizable implementation of such types, employing an atomic snapshot object. We show that this implementation is strongly linearizable, proving that all types in this class have a lock-free strongly linearizable implementation from atomic registers.

关键词： distributed algorithms shared memory strong linearizability snapshots ABA lock-freedom

来源：评论

学校读者我要写书评

暂无评论

Collision avoidance proposal in a MEC based VANET environment 20

Collision avoidance proposal in a MEC based VANET environmen...

引用

proceedings of the IEEE/acm 24th International symposium on distributed Simulation and Real Time Applications

作者： Nicolas Nevigato Mauro Tropea Floriano De Rango University of Calabria Rende Italy

Mobile Edge computing (MEC) is a new network paradigm that allows resource management and IT services at the edge of a communication network and, so, closer to the devices guaranteeing low latency and high bandwidth requirements. This characteristic makes MEC paradigm suitable for critical communication services used in collaboration with container-based virtualization and with 5G networks. In this paper, an implementation of a collision avoidance system based on MEC in a VANET environment is proposed. This system makes use of cloud and edge computing and it is able to switch communication from edge to cloud server and vice versa when possible, trying to guarantee the required constraints and balancing the communication among the servers avoiding of overloading edge layer. The simulation results have proved how, in some cases, the MEC-5G combination is the best solution for avoiding collisions in a VANET environment.

关键词： collision avoidance mobile edge computing (MEC) 5G VANET

来源：评论

学校读者我要写书评

暂无评论

Digital twins at the edge to track mobility for MaaS applications 20

Digital twins at the edge to track mobility for MaaS applica...

引用

proceedings of the IEEE/acm 24th International symposium on distributed Simulation and Real Time Applications

作者： Claudia Campolo Giacomo Genovese Antonella Molinaro Bruno Pizzimenti University "Mediterranea" of Reggio Calabria Italy

The research into wireless communication and mobile computing is called to formulate novel smart mobility solutions to improve the quality of a citizen's life in smart cities. In such a context, in this paper we elaborate on the role of technologies like multi-access edge computing (MEC), Internet of Things (IoT) messaging protocols, such as Constrained Application Protocol (CoAP) and Message Queue Telemetry Transport (MQTT), and virtualization (i.e., digital twins) in the design of a framework enabling the collection and processing of data about the mobility of commuters and public transport vehicles. Such data have the purpose to feed mobility monitoring and transport planning solutions. A Proof-of-Concept (PoC) is developed to validate the framework under realistic experimental settings. Results in terms of efficiency and effectiveness of the considered messaging protocols are reported.

关键词： multi-access edge computing digital twin MQTT OMA LwM2M MaaS CoAP

来源：评论

学校读者我要写书评

暂无评论

A novel deep reinforcement learning based service migration model for mobile edge computing 20

A novel deep reinforcement learning based service migration ...

引用

proceedings of the IEEE/acm 24th International symposium on distributed Simulation and Real Time Applications

作者： Sung Woon Park Azzedine Boukerche Shichao Guan University of Ottawa Ottawa Canada

Cloud computing has emerged as a foundation of smart environments by encapsulating and virtualizing the underlying design and implementation details. Concerning the inherent latency and deployment issues, Mobile Edge computing seeks to migrate services in the vicinity of mobile users. However, the current migration-based studies lack the consideration of migration cost, transaction cost, and energy consumption on the system-level with discussion on the impact of personalized user mobility. In this paper, we implement an enhanced service migration model to address user proximity issues. We formalize the migration cost, transaction cost, energy consumption related to the migration process. We model the service migration issue as a complex optimization problem and adapt Deep Reinforcement Learning to approximate the optimal policy. We compare the performance of the proposed model with the recent Q-learning method and other baselines. The results demonstrate that the proposed model can estimate the optimal policy with complicated computation requirements.

关键词： service migration migration cost deep reinforcement learning mobile edge computing energy consumption

来源：评论

学校读者我要写书评

暂无评论

Secure distributed computing Made (Nearly) Optimal 19

Secure Distributed Computing Made (Nearly) Optimal

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Parter, Merav Yogev, Eylon Weizmann Inst Sci Rehovot Israel Technion Haifa Israel

ISBN: (纸本)9781450362177

In this paper, we study secure distributed algorithms that are nearly optimal, with respect to running time, for the given input graph G. Roughly speaking, an algorithm is secure if the nodes learn only their final output while gaining no information on the input (or output) of other nodes. A graph theoretic framework for secure distributed computation was recently introduced by the authors (SODA 2019). This framework is quite general and it is based on a new combinatorial structure called private neighborhood trees: a collection of n trees T (u(1)), ... , T (u(n)) such that each tree T (u(i)) spans the neighbors of ui without going through ui. Intuitively, each tree T (u(i)) allows all neighbors of ui to exchange a secret that is hidden from ui. The efficiency of the framework depends on two key parameters of these trees: their depth and the amount of overlap. In a (d, c)-private neighborhood trees each tree T (u(i)) has depth O(d) and each edge e is an element of G appears in at most O(c) different trees. An existentially optimal construction of private neighborhood trees with d = O(Delta center dot D) and c = (O) over tilde (D) was1 presented therein. We make two key contributions: Universally Optimal Private Trees: We show a combinatorial construction of nearly (universally) optimal (d, c)-private neighborhood trees with d + c = (O) over tilde (OPT(G)) for any input graph G. Perhaps surprisingly, we show that OPT(G) is equal to the best depth possible for these trees even without the congestion constraint. We also present efficient distributed constructions of these private trees. Optimal Secure Computation: Using the optimal constructions above, we get a secure compiler for distributed algorithms where the overhead for each round is (O) over tilde (poly(Delta) center dot OPT(G)). As our second key contribution, we design an optimal compiler with an overhead of merely (O) over tilde (OPT(G)) per round for a class of "simple" algorithms. This class includes many

关键词： distributed algorithms multi-party computation private neighborhood trees secure computation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：