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

proceedings of the 43rd acm symposium on principles of distributed computing

作者： Nicola Santoro School of Computer Science Carleton University Ottawa Canada

ISBN: (纸本)9798400706684

distributed computing has been concerned with the topics of faults and failures from its very beginning (before PODC was born). The consensus problem was at the forefront of the research efforts, and an extensive body of literature on the subject was developed very quickly (e.g., [5, 6, 11, 20]). The beautiful proof of the impossibility of consensus under asynchrony [7] put to rest the unsuccessful attempts to prove otherwise, and gave an even stronger impetus to the focus on synchronous *** paper Time is not a Healer [16], which we shall denote by {T¬H}, was concerned with the problem of agreement in synchronous systems where failures have mostly a transient and ubiquitous nature; that is, faults can occur anywhere in the system and, following a failure, normal functioning can resume after a finite (although unpredictable) time. These type of dynamic failures, however, could not be handled by the traditional failure models developed for the consensus and related *** the significance and novelty of the scientific and technical contributions of {T¬H}, including the model, the proof technique, and the unexpected results. Incidentally, while known for its results on omissions, {T¬H} contains also tight bounds on corruptions, additions, and the Byzantine combination of all. While known for its impossibility results, it has tight possibility results, which hold in situations for which the traditional models indicate impossibility. Over the decades, triggered by these results, an extensive literature has been developed (e.g., [3, 4, 8, 9, 13, 15, 19, 21]).The relatively recent developments in communication technology and advent of new virtual systems (e.g., wireless mobile networks, social networks) have driven the research in distributed computing to investigate problems (including consensus) in dynamic networks (e.g., [2, 10, 12]); this has inevitably brought to light the immediate connection between such networks and the ones subject to dynamic omiss

关键词： theory of distributed computation synchronous systems dynamic faults agreement dynamic networks

来源：评论

学校读者我要写书评

暂无评论

Synthesizing optimal collective algorithms 21

Synthesizing optimal collective algorithms

引用

26th acm SIGPLAN symposium on principles and Practice of Parallel Programming, PPoPP 2021

作者： Cai, Zixian Liu, Zhengyang Maleki, Saeed Musuvathi, Madanlal Mytkowicz, Todd Nelson, Jacob Saarikivi, Olli Research School of Computer Science Australian National University Canberra ACT Australia School of Computing University of Utah Salt Lake CityUT United States Microsoft Research RedmondWA United States

ISBN: (纸本)9781450382946

Collective communication algorithms are an important component of distributed computation. Indeed, in the case of deep-learning, collective communication is the Amdahl's bottleneck of data-parallel training. This paper introduces SCCL (for Synthesized Collective Communication Library), a systematic approach to synthesizing collective communication algorithms that are explicitly tailored to a particular hardware topology. SCCL synthesizes algorithms along the Pareto-frontier spanning from latency-optimal to bandwidth-optimal implementations of a collective. The paper demonstrates how to encode the synthesis problem as a quantifier-free SMT formula which can be discharged to a theorem prover. We show how our carefully built encoding enables SCCL to scale. We synthesize novel latency and bandwidth optimal algorithms not seen in the literature on two popular hardware topologies. We also show how SCCL efficiently lowers algorithms to implementations on two hardware architectures (NVIDIA and AMD) and demonstrate competitive performance with hand optimized collective communication libraries. © 2021 acm.

关键词： Bandwidth

来源：评论

学校读者我要写书评

暂无评论

Almost Universally Optimal distributed Laplacian Solvers via Low-Congestion Shortcuts 36

Almost Universally Optimal Distributed Laplacian Solvers via...

引用

36th International symposium on distributed computing, DISC 2022

作者： Anagnostides, Ioannis Lenzen, Christoph Haeupler, Bernhard Zuzic, Goran Gouleakis, Themis Carnegie Mellon University PittsburghPA United States CISPA Helmholtz Center for Information Security Saarbrücken Germany ETH Zürich Switzerland National University of Singapore Singapore

ISBN: (纸本)9783959772556

In this paper, we refine the (almost) existentially optimal distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved after no(1)SQ(G) log(1/Ε) rounds, where Ε is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires (Equation presented)(SQ(G)) rounds, even for a crude solution with Ε ≤ 1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D · no(1) log(1/Ε) rounds, where D is the hop-diameter of the network;as well as no(1) log(1/Ε)-round algorithms for the case of SQ(G) ≤ no(1), which holds for most networks of interest. Conditioned on improvements in state-of-the-art constructions of low-congestion shortcuts, the CONGEST results will match the Supported-CONGEST ones. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity no(1) log(1/Ε). The unifying thread of these results, and our main technical contribution, is the study of a novel ρ-congested generalization of the standard part-wise aggregation problem. We develop near-optimal algorithms for this primitive in the Supported-CONGEST model, almost-optimal algorithms in (standard) CONGEST (with the additional overhead due to standard barriers), as well as a simple algorithm for bounded-treewidth graphs with a quadratic dependence on the congestion ρ. This primitive can be readily used to accelerate the Lap

关键词： Topology

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Rise and Shine Efficiently! The Complexity of Adversarial Wake-up 25

Brief Announcement: Rise and Shine Efficiently! The Complexi...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Peter Robinson Ming Ming Tan Augusta University Augusta USA

ISBN: (纸本)9798400718854

We study the wake-up problem in distributed networks, where an adversary awakens a subset of nodes at arbitrary times, and the goal is to wake up all other nodes as quickly as possible by sending only few messages. We prove the following lower bounds:• We first consider the setting where each node receives advice from an oracle who can observe the entire network, but does not know which nodes are awake initially. More specifically, we consider the KT0 LOCAL model with advice, where the nodes have no prior knowledge of their neighbors. We prove that any randomized algorithm must send [EQUATION] messages if nodes receive only O (β) bits of advice on average.• For the KT1 assumption, where each node knows its neighbors' IDs from the start, we show that any (k + 1)-time algorithm requires Ω(n1+1/k) messages. Our result is the first super-linear (in n) lower bound, for a problem that does not require individual nodes to learn a large amount of information about the network topology, which may be of independent interest. This applies even to the synchronous KT1 LOCAL model, where the computation is structured into rounds and messages can be of unbounded *** complement our lower bound results, we present several new algorithms:• We give an asynchronous KT1 LOCAL algorithm that solves the wake-up problem with a time and message complexity of O (n log n) with high probability.• We introduce the notion of awake distance ρawk, which is upper-bounded by the network diameter, and present a synchronous KT1 LOCAL algorithm that takes O (ρawk) rounds and sends [EQUATION] messages with high probability.• We give deterministic advising schemes in the asynchronous KT0 CONGEST model (with advice). In particular, we obtain an O(ρawk log2 n)-time advising scheme that sends O(n log2 n) messages, while requiring O(log2 n) bits of advice per node.

关键词： distributed wake-up

来源：评论

学校读者我要写书评

暂无评论

Fast distributed approximation for TAP and 2-edge-connectivity

引用

distributed computing 2020年第2期33卷 145-168页

作者： Censor-Hillel, Keren Dory, Michal Technion Dept Comp Sci Haifa Israel

The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that T boolean OR Aug is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JaJa (SIAM J Comput 10(2):270-283, 1981). Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov (acm Trans Algorithms 12(2):23, 2016). Recent breakthroughs give an approximation of 1.458 for unweighted TAP (Grandoni et al. in: proceedings of the 50th annual acm SIGACT symposium on theory of computing (STOC 2018), 2018), and approximations better than 2 for bounded weights (Adjiashvili in: proceedings of the twenty-eighth annual acm-SIAM symposium on discrete algorithms (SODA), 2017;Fiorini et al. in: proceedings of the twenty-ninth annual acm-SIAM symposium on discrete algorithms (SODA 2018), New Orleans, LA, USA, 2018. 10.1137/1.9781611975031.53). In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O(h) rounds, where h is the height of T. When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in O(D+root nlog*n) rounds, where n is the number of vertices and D is the diameter of G. Immediate consequences of our results are an O(D)-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an O(h(MST)+root nlog*n)-round 3-approximation algorithm for the weighted case, where h(MST) is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2.

关键词： distributed graph algorithms Approximation algorithms distributed network design Connectivity augmentation

来源：评论

学校读者我要写书评

暂无评论

Integrating Parallel and distributed computing in Early computing Classes 2023

Integrating Parallel and Distributed Computing in Early Comp...

引用

proceedings of the 54th acm Technical symposium on Computer Science Education V. 2

作者： Sheikh Ghafoor Charles Weems Alan Sussman Ramachandran Vaidyanathan Sushil Prasad Tennessee Tech University Cookeville TN USA University of Massachusetts Amherst MA USA University of Maryland College Park MD USA Louisiana State University Baton Rouge LA USA University of Texas at San Antonio San Antonio TX USA

ISBN: (纸本)9781450394338

Parallel and distributed computing (PDC) has become pervasive in all aspects of computing, and thus it is essential that students include parallelism and distribution in the computational thinking that they apply to problem solving, from the very beginning. Computer science education is still teaching to a 20th century model of algorithmic problem solving. Sequence, branch, and loop are taught in our early courses as the only organizing principles needed for algorithms, and we invest considerable time in showing how best to sequentially process large volumes of data. All computing devices that students use currently have multiple cores as well as a GPU in many cases. Most of their favorite applications use multiple cores and numbers of distributed processors. Often concurrency offers simpler solutions than sequential approaches. Industry is desperate for software engineers who think naturally in terms of exploiting these capabilities, rather than seeing them as an exotic upper-level topic that gets layered over a sequential solution. However, we are still teaching students to solve problems using sequential thinking. In this workshop we overview key PDC concepts and provide examples of how they may naturally be incorporated in early computing classes. We will introduce plugged and unplugged curriculum modules that have been successfully integrated in existing computing classes at multiple institutions. We will highlight the upcoming summer training workshop, for which we have funding to support attendance, as well as other CDER (Center for Parallel and distributed computing Curriculum Development and Educational Resources) activities.

关键词： hpc education pdc education shared memory parallel programming computing education early computing class

来源：评论

学校读者我要写书评

暂无评论

TwinVisor: Hardware-isolated Confidential Virtual Machines for ARM 21

TwinVisor: Hardware-isolated Confidential Virtual Machines f...

引用

28th acm symposium on Operating Systems principles (SOSP)

作者： Li, Dingji Mi, Zeyu Xia, Yubin Zang, Binyu Chen, Haibo Guan, Haibing Shanghai Jiao Tong Univ Inst Parallel & Distributed Syst Shanghai Peoples R China Shanghai Jiao Tong Univ AI Inst MoE Key Lab Artificial Intelligence Shanghai Peoples R China Minist Educ Engn Res Ctr Domain Specif Operating Syst Beijing Peoples R China Shanghai Jiao Tong Univ Shanghai Key Lab Scalable Comp & Syst Shanghai Peoples R China

ISBN: (纸本)9781450387095

Confidential VM, which offers an isolated execution environment for cloud tenants with limited trust in the cloud provider, has recently been deployed in major clouds such as AWS and Azure. However, while ARM has become increasingly popular in cloud data centers, existing confidential VM designs mainly leverage specialized x86 hardware extensions (e.g., AMD SEV and Intel TDX) to isolate VMs upon a shared hypervisor. This paper proposes TwinVisor, the first system that enables the hardware-enforced isolation of confidential VMs on ARM platforms. TwinVisor takes advantage of the mature ARMTrustZone to run two isolated hypervisors, one in the secure world (called S-visor in this paper) and the other in the normal world (called N-visor), to support normal VMs and confidential VMs respectively. Instead of building a new S-visor from scratch, our design decouples protection from resource management, and reuses most functionalities of a full-fledged N-visor to minimize the size of S-visor. We have built two prototypes of TwinVisor: one on an official ARM simulator with S-EL2 enabled to validate functional correctness and the other on an ARM development board to evaluate performance. The S-visor comprises 5.8K LoCs while the N-visor introduces 906 LoC changes to KVM. According to our evaluation, TwinVisor can run unmodified VM images as confidential VMs while incurring less than 5% performance overhead for various real-world workloads on SMP VMs.

关键词： Cloud computing Virtualization Confidential computing ARM TrustZone

来源：评论

学校读者我要写书评

暂无评论

Smartphones as a Platform for Hands-On Internet of Things Education 2023

Smartphones as a Platform for Hands-On Internet of Things Ed...

引用

proceedings of the 54th acm Technical symposium on Computer Science Education V. 2

作者： Devin Jean Ákos Lédeczi Vanderbilt University Nashville TN USA

ISBN: (纸本)9781450394338

While some high school courses like AP Computer Science principles cover topics such as the internet, they do not typically include hands-on activities on the Internet of Things (IoT) and related concepts like distributed computing. Notable reasons include the complexity of programming distributed systems and the cost of supplying classrooms with the necessary hardware. However, most students already have access to a smartphone or other mobile device, which contains all the necessary hardware to introduce these topics through highly engaging interactive projects. We introduce an open-source mobile app called PhoneIoT that allows students to remotely access their devices and query live sensor data or manipulate the app's customizable interactive display. Unlike other tools such as App Inventor, PhoneIoT is not an app-creation tool; instead, we take a distributed approach, with students' code running on their computers and remotely accessing the phone. This makes it possible to have multiple student programs connect to a single device, or one program connect to multiple devices, creating a truly distributed application. To target broad audiences, PhoneIoT supports simple programming interfaces in both block-based form through NetsBlox (a networking-oriented fork of Snap!) and text form through PyBlox (a Python library). This demonstration will include the basic information needed to install and use PhoneIoT, an interactive walkthrough of a compelling NetsBlox project that students could complete on their first day using PhoneIoT, and finally some interesting projects implemented in Python.

关键词： distributed computing internet of things block-based languages mobile devices remote sensing

来源：评论

学校读者我要写书评

暂无评论

2021 principles of distributed computing Doctoral Dissertation Award

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the Annual acm symposium on principles of distributed computing 2021年 III-IV页

作者： Aguilera, Marcos K. Attiya, Hagit Cachin, Christian Panconesi, Alessandro VMWare Palo Alto United States Technion Haifa Israel University of Bern Switzerland Sapienza University of Rome Rome Italy

来源：评论

学校读者我要写书评

暂无评论

SnuRHAC: A Runtime for Heterogeneous Accelerator Clusters with CUDA Unified Memory 21

SnuRHAC: A Runtime for Heterogeneous Accelerator Clusters wi...

引用

30th International symposium on High-Performance Parallel and distributed computing (HPDC)

作者： Jung, Jaehoon Park, Daeyoung Jo, Gangwon Park, Jungho Lee, Jaejin Seoul Natl Univ Dept Comp Sci & Engn Seoul South Korea Moreh Inc Seoul South Korea

ISBN: (纸本)9781450382175

This paper proposes a framework called SnuRHAC, which provides an illusion of a single GPU for the multiple GPUs in a cluster. Under SnuRHAC, a CUDA program designed to use a single GPU can utilize multiple GPUs in a cluster without any source code modification. SnuRHAC automatically distributes workload to multiple GPUs in a cluster and manages data across the nodes. To manage data efficiently, SnuRHAC extends CUDA Unified Memory and exploits its page fault mechanism. We also propose two prefetching techniques to fully exploit UM and to maximize performance. Static prefetching allows SnuRHAC to prefetch data by statically analyzing CUDA kernels. Dynamic prefetching complements static prefetching. SnuRHAC enforces an application to run on a single GPU if it is not suitable for multiple GPUs. We evaluate the performance of SnuRHAC using 18 benchmark applications from various sources. The evaluation result shows that while SnuRHAC significantly improves ease-of-programming, it shows scalable performance for the cluster environment depending on the application characteristics.

关键词： Heterogeneous computing Single device image GPU CUDA Unified Memory Runtime system Device driver

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：