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

29th ACM symposium on Operating Systems principles (SOSP)

作者： Seemakhupt, Korakit Stephens, Brent E. Khan, Samira Liu, Sihang Wassel, Hassan Yeganeh, Soheil Hassas Snoeren, Alex C. Krishnamurthy, Arvind Culler, David E. Levy, Henry M. Univ Virginia Charlottesville VA 22903 USA Google Mountain View CA USA Univ Utah Salt Lake City UT 84112 USA Univ Waterloo Waterloo ON N2L 3G1 Canada Univ Calif San Diego La Jolla CA 92093 USA Univ Washington Seattle WA 98195 USA

ISBN: (纸本)9798400702297

The global scale and challenging requirements of modern cloud applications have led to the development of complex, widely distributed, service-oriented applications. One enabler of such applications is the remote procedure call (RPC), which provides location-independent communication and hides the myriad of cloud communication complexities and requirements within the RPC stack. Understanding RPCs is thus one key to understanding the behavior of cloud applications. While there have been numerous studies of RPCs in distributed systems, as well as attempts to optimize RPC overheads with both software and hardware, there is still a lack of knowledge about the characteristics of RPCs "in the wild" in the modern cloud environment. To address this gap, we present, to the best of our knowledge, the first large-scale fleet-wide study of RPCs. Our study is conducted at Google, where we measured the infrastructure supporting Google's user-facing, billion-user web services, such as Google Search, Gmail, Maps, and YouTube, and the information and data management systems that support them. To carry out the study, we examined over 10,000 different RPC methods sampled from over one billion traces, along with statistics collected every 30 minutes over a period of nearly two years. Among other things, we consider the volume, throughput and growth rate of RPCs in the datacenter, the latency of RPCs and their components (the "RPC latency tax"), and the structure of RPC call chains. Our analysis shows that the characteristics, scope and complexity of RPCs at hyperscale differ significantly from the assumptions made in prior research. Overall, our work provides new insights into RPC usage and characteristics at the largest scale and motivates further research on optimizing the diverse behavior of this crucial communication mechanism.

关键词： Remote procedure call Cloud computing distributed computing Communications systems

来源：评论

学校读者我要写书评

暂无评论

Deterministic Near-Optimal distributed Listing of Cliques 22

Deterministic Near-Optimal Distributed Listing of Cliques

引用

41st ACM symposium on principles of distributed computing, PODC 2022

作者： Censor-Hillel, Keren Leitersdorf, Dean Vulakh, David Technion - Israel Institute of Technology Haifa Israel Massachusetts Institute of Technology CambridgeMA United States

ISBN: (纸本)9781450392624

The importance of classifying connections in large graphs has been the motivation for a rich line of work on distributed subgraph finding that has led to exciting recent breakthroughs. A crucial aspect that remained open was whether deterministic algorithms can be as efficient as their randomized counterparts, where the latter are known to be tight up to polylogarithmic factors. We give deterministic distributed algorithms for listing cliques of size p in n1 - 2/p + o(1) rounds in the Congest model. For triangles, our n1/3+o(1) round complexity improves upon the previous state of the art of n2/3+o(1) rounds [Chang and Saranurak, FOCS 2020]. For cliques of size p ≥ 4, ours are the first non-trivial deterministic distributed algorithms. Given known lower bounds, for all values p ≥ 3 our algorithms are tight up to a no(1) subpolynomial factor, which comes from the deterministic routing procedure we use. © 2022 ACM.

关键词： congest distributed graph algorithms cliques

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

KnightKing: A Fast distributed Graph Random Walk Engine 19

KnightKing: A Fast Distributed Graph Random Walk Engine

引用

27th ACM symposium on Operating Systems principles (SOSP)

作者： Yang, Ke Zhang, MingXing Chen, Kang Ma, Xiaosong Bai, Yang Jiang, Yong Tsinghua Univ Beijing Natl Res Ctr Informat Sci & Technol BNRis Dept Comp Sci & Technol Beijing Peoples R China Tsinghua Univ Res Inst Shenzhen Peoples R China Sangfor Technol Inc Shenzhen Peoples R China Hamad Bin Khalifa Univ Qatar Comp Res Inst Ar Rayyan Qatar 4Paradigm Co Ltd Beijing Peoples R China

ISBN: (纸本)9781450368735

Random walk on graphs has recently gained immense popularity as a tool for graph data analytics and machine learning. Currently, random walk algorithms are developed as individual implementations and suffer significant performance and scalability problems, especially with the dynamic nature of sophisticated walk strategies. We present KnightKing, the first general-purpose, distributed graph random walk engine. To address the unique interaction between a static graph and many dynamic walkers, it adopts an intuitive walker-centric computation model. The corresponding programming model allows users to easily specify existing or new random walk algorithms, facilitated by a new unified edge transition probability definition that applies across popular known algorithms. With KnightKing, these diverse algorithms benefit from its common distributed random walk execution engine, centered around an innovative rejection-based sampling mechanism that dramatically reduces the cost of higher-order random walk algorithms. Our evaluation confirms that KnightKing brings up to 4 orders of magnitude improvement in executing algorithms that currently can only be afforded with approximation solutions on large graphs.

关键词： graph computing random walk rejection sampling

来源：评论

学校读者我要写书评

暂无评论

An algorithmic approach to the asynchronous computability theorem

引用

Journal of Applied and Computational Topology 2018年第3-4期1卷 451-474页

作者： Saraph, Vikram Herlihy, Maurice Gafni, Eli Brown University Providence RI United States UCLA Los Angeles CA United States

The asynchronous computability theorem (ACT) uses concepts from combinatorial topology to characterize which tasks have wait-free solutions in read–write memory. A task can be expressed as a relation between two chromatic simplicial complexes. The theorem states that a task has a protocol (algorithm) if and only if there is a certain color-preserving simplicial map compatible with that relation. The original proof of the ACT, given by Herlihy and Shavit (proceedings of the 25th annual ACM symposium on theory of computing, pp 111–120, 1993;J ACM 46(6):858–923, 1999) relied on an involved geometric argument. Borowsky and Gafni (proceedings of the 16th annual ACM symposium on principles of distributed computing, pp 189–198, 1997) later proposed an alternative proof based on a distributed algorithmic, termed the “convergence algorithm”. However the description of this algorithm was incomplete, and presented without proof. In this paper, we give the first complete description, along with a proof of correctness. © 2018, Springer International Publishing AG, part of Springer Nature.

关键词： Asynchronous computability Combinatorial algebraic topology distributed computing Link-connectivity

来源：评论

学校读者我要写书评

暂无评论

2019 Edsger W. Dijkstra Prize in distributed computing 19

2019 Edsger W. Dijkstra Prize in Distributed Computing

引用

proceedings of the 2019 ACM symposium on principles of distributed computing

作者： Lorenzo Alvisi Shlomi Dolev Faith Ellen Idit Keidar Fabian Kuhn Jukka Suomela Cornell University Ithaca NY USA Ben Gurion University of the Negev Beer-Sheva Israel University of Toronto Toronto ON Canada Technion Haifa Israel University of Freiburg Freiburg Germany Aalto University Espoo Finland

ISBN: (纸本)9781450362177

The committee decided to award the 2019 Edsger W. Dijkstra Prize in distributed computing to Alessandro Panconesi and Aravind Srinivasan for their paper Randomized distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds, SIAM Journal on computing, volume 26, number 2, 1997, pages 350-368. A preliminary version of this paper appeared as Fast Randomized Algorithms for distributed Edge Coloring, proceedings of the Eleventh annual ACM symposium principles of distributed computing (PODC), 1992, pages *** paper presents a simple synchronous algorithm in which processes at the nodes of an undirected network color its edges so that the edges adjacent to each node have different colors. It is randomized, using 1.6Δ + O(log1+ζn) colors and O(log n) rounds with high probability for any constant ζ>0, where n is the number of nodes and is the maximum degree of the nodes. This was the first nontrivial distributed algorithm for the edge coloring problem and has influenced a great deal of follow-up work. Edge coloring has applications to many other problems in distributed computing such as routing, scheduling, contention resolution, and resource *** spite of its simplicity, the analysis of their edge coloring algorithm is highly nontrivial. Chernoff-Hoeffding bounds, which assume random variables to be independent, cannot be used. Instead, they develop upper bounds for sums of negatively correlated random variables, for example, which arise when sampling without replacement. More generally, they extend Chernoff-Hoeffding bounds to certain random variables they call λ-correlated. This has directly inspired more specialized concentration inequalities. The new techniques they introduced have also been applied to the analyses of important randomized algorithms in a variety of areas including optimization, machine learning, cryptography, streaming, quantum computing, and mechanism design.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Deterministic distributed (Δ + o(Δ))-edge-coloring, and vertex-coloring of graphs with bounded diversity 17

Deterministic distributed (Δ + o(Δ))-edge-coloring, and ve...

引用

36th ACM symposium on principles of distributed computing, PODC 2017

作者： Beranboim, Leonid Elkin, Michael Maimon, Tzalik Open University of Israel Raananna Israel Ben-Gurion University of the Negev Beer Sheva Israel

ISBN: (纸本)9781450349925

In the distributed message-passing setting a communication network is represented by a graph whose vertices represent processors that perform local computations and communicate over the edges of the graph. In the distributed edge-coloring problem the processors are required to assign colors to edges, such that all edges incident on the same vertex are assigned distinct colors. The previouslyknown deterministic algorithms for edge-coloring employed at least (2Δ - 1) colors, even though any graph admits an edge-coloring with Δ + 1 colors [36]. Moreover, the previously-known deterministic algorithms that employed at most O(Δ) colors required superlogarithmic time [3, 6, 7, 17]. In the current paper we devise deterministic edge-coloring algorithms that employ only Δ + o(Δ) colors, for a very wide family of graphs. Specifically, as long as the arboricity a of the graph is a = O(Δ1-ϵ), for a constant ϵ > 0, our algorithm computes such a coloring within polylogarithmic deterministic time. We also devise significantly improved deterministic edge-coloring algorithms for general graphs for a very wide range of parameters. Specifically, for any value κ in the range [4Δ, 2o(log Δ) · Δ], our κ-edge-coloring algorithm has smaller running time than the best previously-known κ-edge-coloring algorithms. Our algorithms are actually much more general, since edge-coloring is equivalent to vertex-coloring of line graphs. Our method is applicable to vertexcoloring of the family of graphs with bounded diversity that contains line graphs, line graphs of hypergraphs, and many other graphs. We significantly improve upon previous vertex-coloring of such graphs, and as an implication also obtain the improved edge-coloring algorithms for general graphs. Our results are obtained using a novel technique that connects vertices or edges in a certain way that reduces clique size. The resulting structures, which we call connectors, can be colored more efficiently than the original graph. Moreover, th

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

Optimal mobile byzantine fault tolerant distributed storage: [Extended Abstract] 16

Optimal mobile byzantine fault tolerant distributed storage:...

引用

35th ACM symposium on principles of distributed computing, PODC 2016

作者： Bonomi, Silvia Del Pozzo, Antonella Potop-Butucaru, Maria Tixeuil, Sébastien DIAG University of Rome la Sapienza Rome Italy Sorbonne Universités UPMC LIP6-CNRS 7606 Paris France

ISBN: (纸本)9781450339643

We present an optimal emulation of a server based regular read/write storage in a synchronous round-free messagepassing system that is subject to mobile Byzantine failures and prove that the problem is impossible to solve in asynchronous settings. In a system with n servers implementing a regular register, our construction tolerates faults (or attacks) that can be abstracted by agents that are moved (in an arbitrary and unforeseen manner) by a computationally unbounded adversary from a server to another in order to deviate the server's computation. When a server is infected by an adversarial agent, it behaves arbitrarily until the adversary decides to "move" the agent to another server. We investigate the case where the movements of the mobile Byzantine agents are decided by the adversary and are completely decoupled from the message communication delay. Our emulation spans two awareness models: servers with and without self-diagnosis mechanism. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state. Our results, proven optimal with respect to the threshold of the tolerated mobile Byzantine faults in the first model, are significantly different from the round-based synchronous models. Another interesting side result of our study is that, contrary to the round-based synchronous consensus implementation for systems prone to mobile Byzantine faults, our storage emulation does not rely on the necessity of a core of correct processes all along the computation. That is, every server in the system can be compromised by the mobile Byzantine agents at some point in the computation. This leads to another interesting conclusion: storage is easier than consensus in synchronous settings, when the system is hit by mobile Byzantine failures. © 2016

关键词： Mobile agents

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Fast and Simple Node Coloring in the SINR Model 15

Brief Announcement: Fast and Simple Node Coloring in the SIN...

引用

34th annual ACM symposium on principles of distributed computing (PODC)

作者： Fuchs, Fabian KIT Inst Theoret Informat Karlsruhe Germany

ISBN: (纸本)9781450336178

We present two distributed node coloring algorithms operating in the Signal-to-interference-and-noise-ratio (SINR) model. The first algorithm is very simple and achieves a (4 Delta)-coloring in O(Delta log n) time slots. The results of our experimental evaluation show that the algorithm is extremely fast. Combined with a new color reduction scheme, the algorithm computes a (Delta+1)-coloring in O(Delta log n) time. This improves on current distributed coloring algorithms for the SINR model either in terms of the number of colors or runtime, and matches the asymptotical runtime of one round of local broadcasting, which can be seen as a lower bound.

关键词： Algorithms distributed Node Coloring SINR Model Wireless Ad Hoc Networks Experiments

来源：评论

学校读者我要写书评

暂无评论

No compromises: distributed transactions with consistency, availability, and performance 15

No compromises: distributed transactions with consistency, a...

引用

25th ACM symposium on Operating Systems principles (SOSP)

作者： Dragojevic, Aleksandar Narayanan, Dushyanth Nightingale, Edmund B. Renzelmann, Matthew Shamis, Alex Badam, Anirudh Castro, Miguel Microsoft Res Redmond WA 98052 USA

ISBN: (纸本)9781450338349

Transactions with strong consistency and high availability simplify building and reasoning about distributed systems. However, previous implementations performed poorly. This forced system designers to avoid transactions completely, to weaken consistency guarantees, or to provide single-machine transactions that require programmers to partition their data. In this paper, we show that there is no need to compromise in modern data centers. We show that a main memory distributed computing platform called FaRM can provide distributed transactions with strict serializability, high performance, durability, and high availability. FaRM achieves a peak throughput of 140 million TATP transactions per second on 90 machines with a 4.9 TB database, and it recovers from a failure in less than 50 ms. Key to achieving these results was the design of new transaction, replication, and recovery protocols from first principles to leverage commodity networks with RDMA and a new, inexpensive approach to providing non-volatile DRAM.

关键词： Dynamic random access storage

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：