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

54th Annual acm SIGACT symposium on Theory of computing (STOC)

作者： Parter, Merav Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9781450392648

We (nearly) settle the time complexity for computing vertex faulttolerant (VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFT spanners are sparse subgraphs that preserve distance information, up to a small multiplicative stretch, in the presence of vertex failures. These structures were introduced by [Chechik et al., STOC 2009] and have received a lot of attention since then. Recent work provided algorithms for computing VFT spanners with optimal sparsity but in exponential runtime. The first polynomial time algorithms for these structures have been given by [Bodwin, Dinitz and Robelle, SODA 2021]. Their algorithms, as all other prior algorithms, are greedy and thus inherently sequential. We provide algorithms for computing nearly optimal.. -VFT spanners for any n-vertex n-edge graph, with near optimal running time in several computational models: (i) A randomized sequential algorithm with a runtime of e.. (..) (i.e., independent in the number of faults..). The state-of-the-art time bound is e.. (.. 1-1/.. center dot..2+1/.. +.. 2..) by [Bodwin, Dinitz and Robelle, SODA 2021]. (ii) A distributed congest algorithm of e.. ( 1) rounds. Improving upon [Dinitz and Robelle, PODC 2020] that obtained FT spanners with near-optimal sparsity in e.. (.. 2) rounds. (iii) A PRAM (CRCW) algorithm with e.. (..) work and e.. (1) depth. Prior bounds implied by [Dinitz and Krauthgamer, PODC 2011] obtained sub-optimal FT spanners using e.. (.. 3..) work and e.. (.. 3) depth. An immediate corollary provides the first nearly-optimal PRAM algorithm for computing nearly optimal..-vertex connectivity certificates using polylogarithmic depth and near-linear work. This improves the state-of-the-art bounds of e.. (1) depth and.. (....) work, by [Karger and Motwani, STOC'93].

关键词： Spanners Connectivity Certificate Fault-Tolerance

来源：评论

学校读者我要写书评

暂无评论

A Nearly Time-Optimal distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph 34

A Nearly Time-Optimal Distributed Approximation of Minimum C...

引用

34th acm-SIAM Annual symposium on Discrete Algorithms (SODA)

作者： Dory, Michal Ghaffari, Mohsen Univ Haifa Haifa Israel MIT Cambridge MA USA

ISBN: (纸本)9781611977554

The minimum-cost k-edge-connected spanning subgraph (k-ECSS) problem is a generalization and strengthening of the well-studied minimum-cost spanning tree (MST) problem. While the round complexity of distributedly computing the latter has been well-understood, the former remains mostly open, especially as soon as k >= 3. In this paper, we present the first distributed algorithm that computes an approximation of k -ECSS in sublinear time for general k. Concretely, we describe a randomized distributed algorithm that, in (O) over tilde (k(D + k root n)) rounds, computes a k-edge-connected spanning subgraph whose cost is within an O (log n log k) factor of optimal. Here, n and D denote the number of vertices and diameter of the graph, respectively. This time complexity is nearly optimal for any k = poly(log n), almost matching an Omega(D+root n/k) lower bound. Our algorithm is the first to achieve a sublinear round complexity for k >= 3. We note that this case is considerably more challenging than the well-studied and well-understood k = 1 case|better known as MST|and the closely related k = 2 case. Our algorithm is based on reducing the k-ECSS problem to k set cover instances, in which we gradually augment the connectivity of the spanning subgraph. To solve each set cover instance, we combine new structural observations on minimum cuts with graph sketching ideas. One key ingredient in our algorithm is a novel structural lemma that allows us to compress the information about all minimum cuts in a graph into a succinct representation, which is computed in a decentralized fashion. We hope that this succinct representation may find applications in other computational settings or for other problems.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Construction of Lightweight Spanners for Unit Ball Graphs 36

Distributed Construction of Lightweight Spanners for Unit Ba...

引用

36th International symposium on distributed computing, DISC 2022

作者： Eppstein, David Khodabandeh, Hadi Department of Computer Science University of California IrvineCA United States

ISBN: (纸本)9783959772556

Resolving an open question from 2006 [14], we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple O(log∗ n)-round distributed algorithm in the LOCAL model of computation, that given a unit ball graph G with n vertices and a positive constant ϵ ∗ n) rounds in the LOCAL model, but has a O(log ∆) bound on its lightness, where ∆ is the ratio of the length of the longest edge to the length of the shortest edge in the unit ball graph. Next, we adjust our algorithm to work in the CONGEST model, without changing its round complexity, hence proposing the first spanner construction for unit ball graphs in the CONGEST model of computation. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersections per node. Lastly, we provide experimental results that confirm our theoretical bounds, and show an efficient performance from our distributed algorithm compared to the best known centralized construction. © David Eppstein and Hadi Khodabandeh.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Time-optimal construction of overlay networks

引用

distributed computing 2023年第3期36卷 313-347页

作者： Goette, Thorsten Hinnenthal, Kristian Scheideler, Christian Werthmann, Julian Paderborn Univ Dept Comp Sci Warburger Str 100 D-33098 Paderborn Germany

This article shows how to construct an overlay network of constant degree and diameter O(log n) in O(log n) time starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of, and new connections can be established by sending node identifiers. Suppose the initial network's graph is weakly connected and has constant degree. In that case, our algorithm constructs the desired topology with each node sending and receiving only O(log n) messages in each round in O(log n) time w.h.p., which beats the currently best O(log3/2 n) time algorithm of Gotte et al. (International colloquium on structural information and communication complexity (SIROCCO), Springer, 2019). Since the problem cannot be solved faster than by using pointer jumping for O(log n) rounds (which would even require each node to communicate Q(n) bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of Kwok and Lau (Approximation, randomization, and combinatorial optimization. Algorithms and techniques (APPROX/RANDOM 2014), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014). Additionally, we show how our algorithm can be used to efficiently solve graph problems in hybrid networks (Augustine et al. in proceedings of the fourteenth annual acm-SIAM symposium on discrete algorithms, SIAM, 2020). Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the initial edges is unrestricted, whereas only polylogarithmically many messages can be sent over edges that have been established throughout an algorithm's execution. For an (undirected) graph G with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in O(log n) time w.h.p.

关键词： distributed protocol Peer-to-peer network Randomized algorithm Expander

来源：评论

学校读者我要写书评

暂无评论

Practice-informed Patterns for Organising Large Groups in distributed Mixed Reality Collaboration 24

Practice-informed Patterns for Organising Large Groups in Di...

引用

acm CHI Conference on Human Factors in computing Sytems (CHI)

作者： Wong, Emily Esquivel, Juan Sanchez Leiva, German Gronbaek, Jens Emil Velloso, Eduardo Univ Melbourne Melbourne Vic Australia Aarhus Univ Aarhus Denmark

ISBN: (纸本)9798400703300

Collaborating across dissimilar, distributed spaces presents numerous challenges for computer-aided spatial communication. Mixed reality (MR) can blend selected surfaces, allowing collaborators to work in blended f-formations (facing formations), even when their workstations are physically misaligned. Since collaboration often involves more than just participant pairs, this research examines how we might scale MR experiences for large-group collaboration. To do so, this study recruited collaboration designers (CDs) to evaluate and reimagine MR for large-scale collaboration. These CDs were engaged in a four-part user study that involved a technology probe, a semi-structured interview, a speculative low-fidelity prototyping activity and a validation session. The outcomes of this paper contribute (1) a set of collaboration design principles to inspire future computer-supported collaborative work, (2) eight collaboration patterns for blended f-formations and collaboration at scale and (3) theoretical implications for f-formations and space-place relationships. As a result, this work creates a blueprint for scaling collaboration across distributed spaces.

关键词： mixed reality collaboration scale f-formations space and place

来源：评论

学校读者我要写书评

暂无评论

IOGuard: Software-Based I/O Page Fault Handling with One CPU Core 15

IOGuard: Software-Based I/O Page Fault Handling with One CPU...

引用

15th Asia-Pacific symposium on Internetware (Internetware)

作者： Dong, Yiyuan Mi, Zeyu Shanghai Jiao Tong Univ SEIEE Inst Parallel & Distributed Syst Shanghai Peoples R China

ISBN: (纸本)9798400707056

Nowadays, device passthrough I/O virtualization technology has played an essential role in cloud scenarios like network connection. However, the absence of widespread support for I/O Page Fault (IOPF) in I/O devices means that virtual machines (VMs) with directly assigned devices must pin all memory during startup, severely impacting memory efficiency and startup duration. Previous solutions addressing this issue suffered from various drawbacks, including reliance on specialized hardware, requiring VM modification, or imposing significant performance overhead. This paper introduces IOGuard, a software-based solution that universally, transparently, and efficiently removes the need for pinning all memory through the interception and analysis of I/O commands. Evaluation results demonstrate that IOGuard can support up to 16 VMs with a single host CPU core and incurs less than a 4% I/O performance overhead, substantially enhancing memory utilization for real-world workloads and significantly reducing VM startup times.

关键词： virtualization cloud computing device passthrough I/O page fault

来源：评论

学校读者我要写书评

暂无评论

Locality-aware Load-Balancing For Serverless Clusters 22

Locality-aware Load-Balancing For Serverless Clusters

引用

31st International symposium on High-Performance Parallel and distributed computing (HPDC)

作者： Fuerst, Alexander Sharma, Prateek Indiana Univ Bloomington IN 47405 USA

ISBN: (纸本)9781450391993

While serverless computing provides more convenient abstractions for developing and deploying applications, the Function-as-a-Service (FaaS) programming model presents new resource management challenges for the FaaS provider. In this paper, we investigate load-balancing policies for serverless clusters. Locality, i.e., running repeated invocations of a function on the same server, is a key determinant of performance because it increases warm-starts and reduces cold-start overheads. We find that the locality vs. load tradeoff is crucial and presents a large design space. We enhance consistent hashing for FaaS, and develop CH-RLU: Consistent Hashing with Random Load Updates, a simple practical load-balancing policy which provides more than 2x reduction in function latency. Our policy deals with highly heterogeneous, skewed, and bursty function workloads, and is a drop-in replacement for OpenWhisk's existing load-balancer. We leverage techniques from caching such as SHARDS for popularity detection, and develop a new approach that places functions based on a tradeoff between locality, load, and randomness.

关键词： Functions as a Service Serverless computing Cloud computing Load Balancing

来源：评论

学校读者我要写书评

暂无评论

HiPS2022: The 2nd Workshop on High Performance Serverless computing 22

HiPS2022: The 2nd Workshop on High Performance Serverless Co...

引用

31st International symposium on High-Performance Parallel and distributed computing (HPDC)

作者： Babuji, Yadu Chard, Kyle Foster, Ian Li, Zhuozhao Argonne Natl Lab Argonne IL 60439 USA Southern Univ Sci & Technol Shenzhen Peoples R China

ISBN: (纸本)9781450391993

Serverless computing presents an attractive model for general distributed computing as it focuses on abstracting the infrastructure required to execute an application. This workshop investigates the intersection between high performance computing and serverless computing, looking both at the high performance and distributed systems used to deliver serverless platforms and also at the use of serverless models for high performance and distributed systems.

关键词： Cloud computing Serverless distributed Systems

来源：评论

学校读者我要写书评

暂无评论

Stochastic Coordination in Heterogeneous Load Balancing Systems 21

Stochastic Coordination in Heterogeneous Load Balancing Syst...

引用

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Goren, Guy Vargaftik, Shay Moses, Yoram Technion Haifa Israel VMware Res Herzliyya Israel

ISBN: (纸本)9781450385480

Current-day data centers and high-volume cloud services employ a broad set of heterogeneous servers. In such settings, client requests typically arrive at multiple entry points, and dispatching them to servers is an urgent distributed systems problem. This paper presents an efficient solution to the load balancing problem in such systems that improves on and overcomes problems of previous solutions. The load balancing problem is formulated as a stochastic optimization problem, and an efficient algorithmic solution is obtained based on a subtle mathematical analysis of the problem. Finally, extensive evaluation of the solution on simulated data shows that it outperforms previous solutions. Moreover, the resulting dispatching policy can be computed very efficiently, making the solution practically viable.

关键词： distributed load balancing Heterogeneous load balancing Stochastically coordinated dispatching Parallel server model

来源：评论

学校读者我要写书评

暂无评论

POSTER: Learning to Parallelize in a Shared-Memory Environment with Transformers 28

POSTER: Learning to Parallelize in a Shared-Memory Environme...

引用

28th acm SIGPLAN Annual symposium on principles and Practice of Parallel Programming, PPoPP 2023

作者： Harel, Re'Em Pinter, Yuval Oren, Gal Department of Computer Science Ben-Gurion University of the Negev Department of Physics Scientific Computing Center Nuclear Research Center Negev Israel Department of Computer Science Ben-Gurion University of the Negev Israel Department of Computer Science Technion - Israel Institute of Technology Scientific Computing Center Nuclear Research Center Negev Israel

ISBN: (纸本)9798400700156

In past years, the world has switched to multi and many core shared memory architectures. As a result, there is a growing need to utilize these architectures by introducing shared memory parallelization schemes, such as OpenMP, to applications. Nevertheless, introducing OpenMP work-sharing loop construct into code, especially legacy code, is challenging due to pervasive pitfalls in management of parallel shared memory. To facilitate the performance of this task, many source-to-source (S2S) compilers have been created over the years, tasked with inserting OpenMP directives into code automatically. In addition to having limited robustness to their input format, these compilers still do not achieve satisfactory coverage and precision in locating parallelizable code and generating appropriate directives. In this work, we propose leveraging recent advances in machine learning techniques, specifically in natural language processing (NLP), to suggest the need for an OpenMP work-sharing loop directive and data-sharing attributes clauses - the building blocks of concurrent programming. We train several transformer models, named PragFormer, for these tasks and show that they outperform statistically-trained baselines and automatic source-to-source (S2S) parallelization compilers in both classifying the overall need for an parallel for directive and the introduction of private and reduction clauses. In the future, our corpus can be used for additional tasks, up to generating entire OpenMP directives. The source code and database for our project can be accessed on GitHub 1 and HuggingFace 2. © 2023 Owner/Author.

关键词： Machine learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：