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

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

作者： Hadzilacos, Vassos Hu, Xing Toueg, Sam Univ Toronto Toronto ON Canada

ISBN: (纸本)9781450385480

It is well-known that, for deterministic algorithms, linearizable objects can be used as if they were atomic objects. As pointed out by Golab, Higham, and Woelfel, however, a randomized algorithm that works with atomic objects may lose some of its properties if we replace the atomic objects that it uses with objects that are only linearizable. It was not known whether the properties that can be lost include the all-important property of termination (with probability 1). In this paper, we first show that a randomized algorithm can indeed lose its termination property if we replace the atomic registers that it uses with linearizable ones. Golab et al. also introduced strong linearizability, and proved that strongly linearizable objects can be used as if they were atomic objects, even for randomized algorithms: they can replace atomic objects while preserving the algorithm's correctness properties, including termination. Unfortunately, there are important cases where strong linearizability is impossible to achieve. In particular, Helmi, Higham, and Woelfel showed a large class of "non-trivial" objects, including MWMR registers, do not have strongly linearizable implementations from SWMR registers. Thus we propose a new type of register linearizability, called write strong-linearizability, that is strictly stronger than (plain) linearizability but strictly weaker than strong linearizability. This intermediate type of linearizability has some desirable properties. We prove that some randomized algorithms that fail to terminate with linearizable registers, work with write strongly-linearizable ones. In other words, there are cases where linearizability is not sufficient but write strong-linearizability is. In contrast to the impossibility result mentioned above, we prove that write strongly-linearizable MWMR registers are implementable from SWMR registers. While the well-known ABD implementation of SWMR registers in message-passing system is not strongly linearizable, we

关键词： distributed computing concurrency linearizability shared registers

来源：评论

学校读者我要写书评

暂无评论

Message Optimality and Message-Time Trade-offs for APSP and Beyond 25

Message Optimality and Message-Time Trade-offs for APSP and ...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Fabien Dufoulon Shreyas Pai Gopal Pandurangan Sriram Pemmaraju Peter Robinson School of Computing and Communications Lancaster University Lancaster United Kingdom IIT Madras Chennai India Department of Computer Science University of Houston Houston Texas USA University of Iowa Iowa City Iowa USA Augusta University Augusta Georgia USA

ISBN: (纸本)9798400718854

Round complexity is an extensively studied metric of distributed algorithms. In contrast, our knowledge of the message complexity of distributed computing problems and its relationship (if any) with round complexity is still quite limited. To illustrate, for many fundamental distributed graph optimization problems such as (exact) diameter computation, All-Pairs Shortest Paths (APSP), Maximum Matching etc., while (near) round-optimal algorithms are known, message-optimal algorithms are hitherto unknown. More importantly, the existing round-optimal algorithms are not message-optimal. This raises two important questions: (1) Can we design message-optimal algorithms for these problems? (2) Can we give message-time tradeoffs for these problems in case the message-optimal algorithms are not round-optimal?In this work, we focus on a fundamental graph optimization problem, All Pairs Shortest Path (APSP), whose message complexity is still unresolved. We present two main results:(1) An algorithm that solves weighted APSP, using Õ(n2) messages in Õ(n2) rounds. This algorithm is message-optimal (up to logarithmic factors) for algorithms that take poly(n) rounds.(2) For any 0 ≤ ϵ ≤ 1, we show how to solve unweighted APSP in Õ(n2–ϵ) rounds and Õ(n2+ϵ) messages. At one end of this smooth trade-off, we obtain a (nearly) message-optimal algorithm (for algorithms that take poly(n) rounds) using Õ(n2) messages (for ϵ = 0), whereas at the other end we get a (nearly) round-optimal algorithm using Õ(n) rounds (for ϵ = 1).

关键词： distributed APSP

来源：评论

学校读者我要写书评

暂无评论

Understanding and Detecting Software Upgrade Failures in distributed Systems 21

Understanding and Detecting Software Upgrade Failures in Dis...

引用

28th acm symposium on Operating Systems principles (SOSP)

作者： Zhang, Yongle Yang, Junwen Jin, Zhuqi Sethi, Utsav Rodrigues, Kirk Lu, Shan Yuan, Ding Purdue Univ W Lafayette IN 47907 USA Univ Chicago Chicago IL 60637 USA Univ Toronto Toronto ON Canada

ISBN: (纸本)9781450387095

Upgrade is one of the most disruptive yet unavoidable maintenance tasks that undermine the availability of distributed systems. Any failure during an upgrade is catastrophic, as it further extends the service disruption caused by the upgrade. The increasing adoption of continuous deployment further increases the frequency and burden of the upgrade task. In practice, upgrade failures have caused many of today's high-profile cloud outages. Unfortunately, there has been little understanding of their characteristics. This paper presents an in-depth study of 123 real-world upgrade failures that were previously reported by users in 8 widely used distributed systems, shedding lights on the severity, root causes, exposing conditions, and fix strategies of upgrade failures. Guided by our study, we have designed a testing framework DUPTester that revealed 20 previously unknown upgrade failures in 4 distributed systems, and applied a series of static checkers DUPChecker that discovered over 800 cross-version data-format incompatibilities that can lead to upgrade failures. DUPChecker has been requested by HBase developers to be integrated into their toolchain.

关键词： upgrade failure distributed systems study bug detection

来源：评论

学校读者我要写书评

暂无评论

distributed (Δ+1)-COLORING VIA ULTRAFAST GRAPH SHATTERING

引用

SIAM JOURNAL ON computing 2020年第3期49卷 497-539页

作者： Chang, Yi-Jun Li, Wenzheng Pettie, Seth Swiss Fed Inst Technol Inst Theoret Studies CH-8092 Zurich Switzerland Stanford Univ Comp Sci Dept Stanford CA 94305 USA Univ Michigan EECS Ann Arbor MI 48109 USA

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Delta+1)-list coloring in the randomized LOCAL model running in O(Det(d)(polylogn)) time, where Det(d)(n') is the deterministic complexity of (deg+1)-list coloring on n'-vertex graphs. (In this problem, each v has a palette of size deg(v)+1.) This improves upon a previous randomized algorithm of Harris, Schneider, and Su [J. acm, 65 (2018), 19] with complexity O(root log Delta+log log n+Det(d)(poly log n)) = O(root log n). Unless Delta is small, it is also faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [proceedings of the 57th Annual IEEE symposium on Foundations of Computer Science (FOCS), 2016] and Barenboim, Elkin, and Goldenberg [proceedings of the 38th Annual acm symposium on principles of distributed computing (PODC), 2018], with complexity O(root Delta log log* Delta + log* n). Our algorithm's running time is syntactically very similar to the Omega(Det(poly log n)) lower bound of Chang, Kopelowitz, and Pettie [SIAM J. Comput., 48 (2019), pp. 122-143], where Det(n') is the deterministic complexity of (Delta + 1)-list coloring on n'-vertex graphs. Although distributed coloring has been actively investigated for 30 years, the best determin- istic algorithms for (deg +1)- and (Delta + 1)-list coloring (that depend on n' but not Delta) use a black-box application of network decompositions. The recent deterministic network decomposition algorithm of Rozhoil and Ghaffari [proceedings of the 52nd Annual acm SIGACT symposium on Theory of computing (STOC), 2020] implies that Det(d)(n') and Det(n') are both poly(log n'). Whether they are asymptotically equal is an open problem.

关键词： distributed algorithm local model graph coloring

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes 36

Brief Announcement: Foraging in Particle Systems via Self-In...

引用

36th International symposium on distributed computing, DISC 2022

作者： Oh, Shunhao Randall, Dana Richa, Andréa W. School of Computer Science Georgia Institute of Technology AtlantaGA United States School of Computing and Augmented Intelligence Arizona State University TempeAZ United States

ISBN: (纸本)9783959772556

The foraging problem asks how a collective of particles with limited computational, communication and movement capabilities can autonomously compress around a food source and disperse when the food is depleted or shifted, which may occur at arbitrary times. We would like the particles to iteratively self-organize, using only local interactions, to correctly gather whenever a food particle remains in a position long enough and search if no food particle has existed recently. Unlike previous approaches, these search and gather phases should be self-induced so as to be indefinitely repeatable as the food evolves, with microscopic changes to the food triggering macroscopic, system-wide phase transitions. We present a stochastic foraging algorithm based on a phase change in the fixed magnetization Ising model from statistical physics: Our algorithm is the first to leverage self-induced phase changes as an algorithmic tool. A key component of our algorithm is a careful token passing mechanism ensuring a dispersion broadcast wave will always outpace a compression wave. © Shunhao Oh, Dana Randall, and Andréa W. Richa.

关键词： Ising model

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: New distributed Interactive Proofs for Planarity: A Matter of Left and Right 25

Brief Announcement: New Distributed Interactive Proofs for P...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Yuval Gil Merav Parter Weizmann Institute of Science Rehovot Israel

ISBN: (纸本)9798400718854

We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In this setting, the verifier consists of n nodes connected by a communication graph G. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G satisfies a certain property (e.g., planarity) in a small number of rounds, and with a small communication bound, denoted as the proof *** work by Naor, Parter and Yogev (SODA 2020) presented a DIP for planarity that uses three interaction rounds and a proof size of O (log n). Feuilloley et al. (PODC 2020) showed that the same can be achieved with a single interaction round and without randomization, by providing a proof labeling scheme with a proof size of O (log n). In this work, we design new DIPs that use exponentially shorter proofs compared to the state-of-the-art bounds. Our main results are:• There is a 5-round protocol with O (log log n) proof size for outerplanarity.• There is a 5-round protocol with O (log log n) proof size for verifying embedded planarity and O (log log n + log Δ) proof size for general planar graphs, where Δ is the maximum degree in the graph. In the former setting, it is assumed that an embedding of the graph is given (e.g., each node holds a clockwise orientation of its neighbors) and the goal is to verify that it is a valid planar embedding. The latter result should be compared with the non-interactive setting for which there is lower bound of Ω (log n) bits for graphs with Δ = O(1) by Feuilloley et al. (PODC 2020).• The non-interactive deterministic lower bound of Ω (log n) bits by Feuilloley et al. (PODC 2020) can be extended to hold even if the verifier is randomized. Moreover, the lower bound holds even with the assumption that the verifier's randomness comes in the form of an unbounded random string shared among the nod

关键词： distributed interactive proofs

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Towards Optimal distributed Delta Coloring 25

Brief Announcement: Towards Optimal Distributed Delta Colori...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Manuel Jakob Yannic Maus TU Graz Graz Austria

ISBN: (纸本)9798400718854

The Δ-vertex coloring problem has become one of the prototypical problems for understanding the complexity of local distributed graph problems on constant-degree graphs. The major open problem is whether the problem can be solved deterministically in logarithmic time, which would match the lower bound [Chang et al., FOCS'16]. Despite recent progress in the design of efficient Δ-coloring algorithms, there is currently a polynomial gap between the upper and lower *** this work we present a O (log n)-round deterministic Δ-coloring algorithm for dense constant-degree graphs, matching the lower bound for the problem on general graphs. For general Δ the algorithms' complexity is min{Õ(log5/3 n), O (Δ + log n)}. All recent distributed and sublinear graph coloring algorithms (also for coloring with more than Δ colors) decompose the graph into sparse and dense parts. Our algorithm works for the case that this decomposition has no sparse vertices. Ironically, in recent (randomized) Δ-coloring algorithms, dealing with sparse parts was relatively easy and these dense parts arguably posed the major hurdle. We present a solution that addresses the dense parts and may have the potential for extension to sparse *** approach is fundamentally different from prior deterministic algorithms and hence hopefully contributes towards designing an optimal algorithm for the general case. Additionally, we leverage our result to also obtain a randomized min{Õ(log5/3 log n), O (Δ + log log n)}-round algorithm for Δ-coloring dense graphs that also matches the lower bound for the problem on general constant-degree graphs [Brandt et al.; STOC'16].

关键词： distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Revisiting Lower Bounds for Two-Step Consensus 25

Brief Announcement: Revisiting Lower Bounds for Two-Step Con...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Fedor Ryabinin Alexey Gotsman Pierre Sutra IMDEA Software Institute Madrid Spain Universidad Politécnica de Madrid Madrid Spain Télécom SudParis Palaiseau France Inria Saclay Palaiseau France Institut Polytechnique de Paris Palaiseau France

ISBN: (纸本)9798400718854

A seminal result by Lamport shows that at least max{2e + f + 1, 2f + 1} processes are required to implement partially synchronous consensus that tolerates f process failures and can furthermore decide in two message delays under f failures. This lower bound is matched by the classical Fast Paxos protocol. However, more recent practical protocols, such as Egalitarian Paxos, provide two-step decisions with fewer processes, seemingly contradicting the lower bound. We show that this discrepancy arises because the classical bound requires two-step decisions under a wide range of scenarios, not all of which are relevant in practice. We propose a more pragmatic condition for which we establish tight bounds on the number of processes required. Interestingly, these bounds depend on whether consensus is implemented as an atomic object or a decision task. For consensus as an object, max{2e + f - 1, 2f + 1} processes are necessary and sufficient for two-step decisions, while for a task the tight bound is max{2e + f, 2f + 1}.

关键词： distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks 21

Brief Announcement: Wake Up and Join Me! An Energy-Efficient...

引用

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

作者： Dani, Varsha Gupta, Aayush Hayes, Thomas P. Pettie, Seth Ronin Inst Montclair NJ 07043 USA Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA Univ Michigan Dept EECS Ann Arbor MI 48109 USA

ISBN: (纸本)9781450385480

We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology. We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is O(log(2) n), and the time complexity is O(Delta log(n)). Here n is any upper bound on the number of nodes, and Delta is any upper bound on the maximum degree;n and Delta are parameters of our algorithm that we assume are known a priori to all the processors. We note that there exist families of graphs for which our bounds on energy cost and time complexity are simultaneously optimal up to polylog factors, so any significant improvement would need additional assumptions about the network topology. We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of eventual node failure. Here, a key goal is to minimize the maximum load, defined as the number of nodes assigned to a single node. We present an efficient decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog(n) factor bigger that the optimum.

关键词： distributed Algorithms Energy-Aware Computation Radio Networks Maximal Matching Sensor Networks

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement 21

Brief Announcement: On the Message Complexity of Fault-Toler...

引用

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

作者： Kumar, Manish Molla, Anisur Rahaman Indian Stat Inst Kolkata India

ISBN: (纸本)9781450385480

This paper investigates on the message complexity of the two fundamental problems, namely, leader election and agreement in the crash-fault synchronous and fully-connected distributed network. We present randomized algorithms for both the problems and also develop non-trivial lower bounds on the message complexity. In the so-called implicit version of the two problems, our algorithms achieve sublinear message complexity while tolerating more than a constant fraction of faulty nodes. The algorithms work in anonymous networks, where nodes do not know each other. Specifically, our main results are: (1) A randomized leader election algorithm which elects a leader with high probability in a complete network with n nodes, in which at least [alpha n] nodes are non-faulty and the remaining can be faulty, where alpha >= (log(2) n)In. The time complexity of the algorithm is O(log n/alpha) rounds and message complexity is O((n(0.5) log(2.5) n)/alpha(2.5)) with high probability (i.e., with probability >= 1 - 1/n). A non-trivial lower bound of Omega (n(0.)(5)/alpha(1.5)) messages for any leader election algorithm that tolerates at most (1- alpha)-fraction faulty nodes and succeeds with high probability. (2) A randomized algorithm, tolerating at most left perpendicular(1 - alpha)nright perpendicular faulty nodes, solves agreement in O (log n/alpha) rounds and with high probability uses only O ((n(0.5) log(1.5)n)/alpha(1.)(5)) messages. A match- ing lower bound (up to a polylog n factor) of Omega(n(0.)(5)/alpha(1.5)) messages for any agreement algorithm that tolerates at most (1-alpha)-fraction faulty nodes and succeeds with high probability. A full version of the paper is available at [17].

关键词： distributed algorithm randomized algorithm fault-tolerant algorithm crash-fault leader election agreement message complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：