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

Efficient bounded timestamping from standard synchronization primitives

distributed computing 2025年 1-39页

作者： Bashari, Benyamin Jamadi, Ali Woelfel, Philipp Univ Calgary Comp Sci 2500 Univ Dr Calgary AB T2N 1N4 Canada

Bounded timestamping systems (Israeli and Li in proceedings of the 28th annual IEEE symposium on Foundations of Computer Science (FOCS), pp 371-382, 1987;Dolev and Shavit in SIAM J Comput 26 (2):418-455, 1997) allow a temporal ordering of events in executions of concurrent algorithms. They are a fundamental and well-studied building block used in many shared-memory algorithms (Haldar and Vit & aacute;nyi in J acm, 49 (1):101-126, 2002;Afek et al. in acm Trans Program Lang Syst 16:939-953, 1994;Abrahamson in proceedings of the 7th acm symposium on principles of distributed computing.(PODC), pp 291-302, 1988;Bashari and Woelfel in proceedings of the 40th acm symposium on principles of distributed computing.(PODC), pp 545-555, 2021). A concurrent bounded timestamping system keeps track of m timestamps, which is usually greater or equal to the number of processes in the system, n. A process may, at any point, obtain a new timestamp, and later determine a total order of all process's most recent timestamps. Known bounded timestamping algorithms (Dolev and Shavit in SIAM J Comput 26(2):418-455, 1997;Dwork and Waarts in J acm 46(5):633-666, 1999;Dwork et al. in SIAM J Comput 28(5):1848-1874, 1999;Gawlick et al. in Theory of computing.and systems (ISTCS), pp 171-183, 1992;Israeli and Pinhasov in distributed algorithms, pp 95-109, 1992;Haldar and Vit & aacute;nyi in J acm 49(1):101-126, 2002) do not scale well in the number of processes as getting a new timestamp takes at least Omega(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (n)$$\end{document} steps. Moreover, a lower bound by Israeli and Li (proceedings of the 28th annual IEEE symposium on foundations of computer science (FOCS), pp 371-382, 1987) implies that timestamps need to be represented by Omega(m)\documentclass[12pt]{minim

关键词： Timestamping Shared memory Concurrency distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Know Your Audience: Communication model and computability in anonymous networks 24

Brief Announcement: Know Your Audience: Communication model ...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing. PODC 2024

作者： Charron-Bost, Bernadette Lambein-Monette, Patrick CNRS Di Ens École Normale Supérieure Paris France Unaffiliated Paris France

ISBN: (纸本)9798400706684

In distributed computing. questions of computability are exquisitely sensitive to minute details of the model assumptions, and there is no universally agreed upon model of network computing. Here, we study which functions are computable by deterministic and anonymous agents in either static or dynamic networks. We consider various communication assumptions common in the literature, and in each case we strive to characterize the set of computable functions, organizing existing results as well as offering new ones, alongside new proofs which bring new understanding of this computability landscape. © 2024 Copyright is held by the owner/author(s). Publication rights licensed to acm.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

COMPSO: Optimizing Gradient Compression for distributed Training with second-Order Optimizers 25

COMPSO: Optimizing Gradient Compression for Distributed Trai...

引用

30th symposium on principles and Practice of Parallel Programming

作者： Sun, Baixi Liu, Weijin Pauloski, J. Gregory Tian, Jiannan Jia, Jinda Wang, Daoce Zhang, Boyuan Zheng, Mingkai Di, Sheng Jin, Sian Zhang, Zhao Yu, Xiaodong Iskra, Kamil A. Beckman, Pete Tan, Guangming Tao, Dingwen Indiana Univ Bloomington IN USA Stevens Inst Technol Hoboken NJ USA Univ Chicago Chicago IL USA Rutgers State Univ New Brunswick NJ USA Argonne Natl Lab Lemont IL USA Temple Univ Philadelphia PA USA Northwestern Univ Evanston IL USA Univ Chinese Acad Sci Beijing Peoples R China

ISBN: (纸本)9798400714436

second-order optimization methods have been developed to enhance convergence and generalization in deep neural network (DNN) training compared to first-order methods like Stochastic Gradient Descent (SGD). However, these methods face challenges in distributed settings due to high communication overhead. Gradient compression, a technique commonly used to accelerate communication for first-order approaches, often results in low communication reduction ratios, decreased model accuracy, and/or high compression overhead when applied to second-order methods. To address these limitations, we introduce a novel gradient compression method for second-order optimizers called COMPSO. This method effectively reduces communication costs while preserving the advantages of second-order optimization. COMPSO employs stochastic rounding to maintain accuracy and filters out minor gradients to improve compression ratios. Additionally, we develop GPU optimizations to minimize compression overhead and performance modeling to ensure end-to-end performance gains across various systems. Evaluation of COMPSO on different DNN models shows that it achieves a compression ratio of 22.1x, reduces communication time by 14.2x, and improves overall performance by 1.9x, all without any drop in model accuracy.

关键词： Deep learning distributed training second-order optimization K-FAC data compression

来源：评论

学校读者我要写书评

暂无评论

PODC 2024 - proceedings of the 2024 acm symposium on principles of distributed computing

PODC 2024 - Proceedings of the 2024 ACM Symposium on Princip...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing. PODC 2024

ISBN: (纸本)9798400706684

The proceedings contain 62 papers. The topics discussed include: determining recoverable consensus numbers;history-independent concurrent objects;MemSnap: a fast adaptive snapshot algorithm for RMWable shared-memory;brief announcement: randomized consensus: common coins are not the holy grail!;game dynamics and equilibrium computation in the population protocol model;brief announcement: optimally encoding information in chemical reaction networks;polylogarithmic time algorithms for shortest path forests in programmable matter;majority consensus thresholds in competitive Lotka-Volterra populations;brief announcement: self-stabilizing mis computation in the beeping model;brief announcement: on the limits of information spread by memory-less agents;and system optimizations for enabling training of extreme long sequence transformer models.

关键词：

来源：评论

学校读者我要写书评

暂无评论

OsirisBFT: Say No to Task Replication for Scalable Byzantine Fault Tolerant Analytics 24

OsirisBFT: Say No to Task Replication for Scalable Byzantine...

引用

29th acm SIGPLAN annual symposium on principles and Practice of Parallel Programming (PPoPP)

作者： Jamshidi, Kasra Vora, Keval Simon Fraser Univ Sch Comp Sci Burnaby BC Canada

ISBN: (纸本)9798400704352

We present a verification-based Byzantine Fault Tolerant processing system, called OsirisBFT, for distributed taskparallel applications. OsirisBFT treats computation tasks differently from state update tasks, allowing the application to scale independently from number of expected failures. OsirisBFT captures application-specific verification semantics via generic verification operators and employs lightweight verification strategies with little coordination during graceful execution. Evaluation across multiple applications and workloads shows that OsirisBFT delivers high processing throughput and scalability compared to replicated processing. Importantly, the scalable nature of OsirisBFT enables it to reduce the performance gap compared to baseline with no fault tolerance by simply scaling out.

关键词： distributed computing Byzantine Fault Tolerance Data Processing Systems Resilient Systems.

来源：评论

学校读者我要写书评

暂无评论

All Byzantine Agreement Problems Are Expensive 24

All Byzantine Agreement Problems Are Expensive

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing. PODC 2024

作者： Civit, Pierre Gilbert, Seth Guerraoui, Rachid Komatovic, Jovan Paramonov, Anton Vidigueira, Manuel Lausanne Switzerland Nus Singapore Singapore Singapore

ISBN: (纸本)9798400706684

Byzantine agreement, arguably the most fundamental problem in distributed computing. operates among n processes, out of which t 2) exchanged messages in the worst case. Since then, it remained unknown whether the quadratic lower bound extends to all variants of Byzantine agreement. This paper answers the question in the affirmative, closing this long-standing open problem. Namely, we prove that any non-trivial agreement problem requires ω(t2) messages to be exchanged in the worst case. To prove the general lower bound, we determine the weakest Byzantine agreement problem and show, via a novel indistinguishability argument, that it incurs ω(t2) exchanged messages even in the general omission model. © 2024 Association for computing.Machinery. All rights reserved.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Colorless Tasks and Extension-Based Proofs 38

Brief Announcement: Colorless Tasks and Extension-Based Proo...

引用

38th International symposium on distributed computing. DISC 2024

作者： Shi, Yusong Liu, Weidong Department of Computer Science and Technology Tsinghua University Beijing China Zhongguancun Laboratory Beijing China

ISBN: (纸本)9783959773522

The concept of extension-based proofs models the idea of a valency argument, which is widely used in distributed computing. Extension-based proofs are limited in power: it has been shown that there is no extension-based proof of the impossibility of a wait-free protocol for (n, k)-set agreement among n > k ≥ 2 processes. There are only a few tasks that have been proven to have no extension-based proof of the impossibility, since the techniques in these works are closely related to the specific task. We give a necessary and sufficient condition for colorless tasks to have no extension-based proofs of the impossibility of wait-free protocols in the NIIS model. We introduce a general adversarial strategy decoupled from any concrete task specification. In this strategy, some properties of the chromatic subdivision that is widely used in distributed computing.are proved. © Yusong Shi and Weidong Liu.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Helios: Efficient distributed Dynamic Graph Sampling for Online GNN Inference 25

Helios: Efficient Distributed Dynamic Graph Sampling for Onl...

引用

30th symposium on principles and Practice of Parallel Programming

作者： Sun, Jie Shi, Zuocheng Su, Li Shen, Wenting Wang, Zeke Li, Yong Yu, Wenyuan Lin, Wei Wu, Fei He, Bingsheng Zhou, Jingren Zhejiang Univ Hangzhou Peoples R China Alibaba Grp Hangzhou Peoples R China Zhejiang Univ Shanghai Inst Adv Study Hangzhou Peoples R China Natl Univ Singapore Singapore Singapore

ISBN: (纸本)9798400714436

Online GNN inference has been widely explored by applications such as online recommendation and financial fraud detection systems, where even minor delays can result in significant financial impact. Real-time dynamic graph sampling enables online GNN inference to reflect the latest graph updates in real-world graphs. However, online GNN inference typically demands millisecond-level latency Service Level Objectives (SLOs) as its performance guarantees, which poses great challenges for existing dynamic graph sampling approaches based on graph databases. The issues mainly arise from two aspects: long tail latency due to imbalanced data-dependent sampling and large communication overhead incurred by distributed sampling. To address these issues, we propose Helios, an efficient distributed dynamic graph sampling service to meet the stringent latency SLOs. The key ideas of Helios are 1) pre-sampling the dynamic graph in an event-driven approach, and 2) maintaining a query-aware sample cache to build the complete K-hop sampling results locally for inference requests. Experiments on multiple datasets show that Helios achieves up to 67x higher serving throughput and up to 32x lower P99 query latency compared to baselines.

关键词： Graph Neural Network distributed System Online Inference

来源：评论

学校读者我要写书评

暂无评论

PPoPP 2025 - proceedings of the 2025 30th acm SIGPLAN annual symposium on principles and Practice of Parallel Programming

PPoPP 2025 - Proceedings of the 2025 30th ACM SIGPLAN Annual...

引用

30th acm SIGPLAN annual symposium on principles and Practice of Parallel Programming, PPoPP 2025

ISBN: (纸本)9798400714436

The proceedings contain 49 papers. The topics discussed include: Semi-StructMG: a fast and scalable semi-structured algebraic multigrid;LibRTS: a spatial indexing library by ray tracing;high-performance visual semantics compression for AI-driven science;COMPSO: optimizing gradient compression for distributed training with second-order optimizers;TurboFFT: co-designed high-performance and fault-tolerant fast Fourier transform on GPUs;Helios: efficient distributed dynamic graph sampling for online GNN inference;triangle counting on tensor cores;AC-Cache: a memory-efficient caching system for small objects via exploiting access correlations;magneto: accelerating parallel structures in DNNsvia co-optimization of operators;and FlashSparse: minimizing computation redundancy for fast sparse matrix multiplications on tensor cores.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Adaptive Parallel Training for Graph Neural Networks 25

Adaptive Parallel Training for Graph Neural Networks

引用

30th symposium on principles and Practice of Parallel Programming

作者： Ma, Kaihao Liu, Renjie Yan, Xiao Cai, Zhenkun Song, Xiang Wang, Minjie Li, Yichao Cheng, James Chinese Univ Hong Kong Hong Kong Peoples R China Southern Univ Sci & Technol Shenzhen Peoples R China Ctr Perceptual & Interact Intelligence Hong Kong Peoples R China Amazon Seattle WA USA AWS Shanghai AI Lab Shanghai Peoples R China

ISBN: (纸本)9798400714436

There are several strategies to parallelize graph neural network (GNN) training over multiple GPUs. We observe that there is no consistent winner (i.e., with the shortest running time), and the optimal strategy depends on the graph dataset, GNN model, training algorithm, and hardware configurations. As such, we design the APT system to automatically select efficient parallelization strategies for GNN training tasks. To this end, we analyze the trade-offs of the strategies and design simple yet effective cost models to compare their execution time and facilitate strategy selection. Moreover, we also propose a general abstraction of the strategies, which allows to implement a unified execution engine that can be configured to run different strategies. Our experiments show that APT usually chooses the optimal or a close to optimal strategy, and the training time can be reduced by over 2x compared with always using a single strategy. APT is open-source at https://***/kaihaoma/APT.

关键词： Graph Neural Networks distributed and Parallel Training Network Communication

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：