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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

distributed Maximum Flow in Planar Graphs 25

Distributed Maximum Flow in Planar Graphs

引用

proceedings of the acm symposium on principles of distributed computing

作者： Yaseen Abd-Elhaleem Michal Dory Merav Parter Oren Weimann University of Haifa Haifa Israel Weizmann Institute of Science Rehovot Israel

ISBN: (纸本)9798400718854

The dual of a planar graph G is a planar graph G* that has a vertex for each face of G and an edge for each pair of adjacent faces of G. The profound relationship between a planar graph and its dual has been the algorithmic basis for solving numerous (centralized) classical problems on planar graphs involving distances, flows, and cuts. In the distributed setting however, the only use of planar duality is for finding a recursive decomposition of G [DISC 2017, STOC 2019].In this paper, we initiate the study of distributed algorithms on dual planar graphs. Namely, we extend the distributed algorithmic toolkit (such as recursive decomposition and minor-aggregation) to work on the dual graph G*. These tools can then facilitate various algorithms on G by solving a suitable dual problem on G*.Given a directed planar graph G with positive and negative edge-lengths and hop-diameter D, our key result is an Õ(D2)-round algorithm1 for Single Source Shortest Paths on G*. This algorithm implies an Õ(D2)-round algorithm for Maximum st-Flow in G. Prior to our work, no Õ(poly(D))-round algorithms were known for this problem. When G is undirected, we further obtain a near optimal Õ(D)-round algorithm for computing the weighted girth of G, and a D · no(1)-rounds (1 - ϵ)-approximation algorithm for Maximum st-Flow in G when s and t lie on the same *** main challenges in our work are that G* is not the communication graph (e.g., a vertex of G is mapped to multiple vertices of G*), and that the diameter of G* can be much larger than D (i.e., possibly by a linear factor). We overcome these challenges by carefully defining and maintaining subgraphs of the dual graph G* while applying the recursive decomposition on the primal graph G The main technical difficulty, is that along the recursive decomposition, a face of G gets shattered into (disconnected) components yet we still need to treat it as a dual *** believe that the toolkit developed in this paper for exploiting planar dual

关键词： maximum flow

来源：评论

学校读者我要写书评

暂无评论

Time-Optimal Construction of Overlay Networks 21

Time-Optimal Construction of Overlay Networks

引用

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

作者： Goette, Thorsten Hinnenthal, Kristian Scheideler, Christian Werthmann, Julian Paderborn Univ Paderborn Germany

ISBN: (纸本)9781450385480

We show how to construct an overlay network of constant degree and diameter O(log n) in time O(log n) 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 establish new connections by sending node identifiers. If the initial network's graph is weakly connected and has constant degree, then our algorithm constructs the desired topology with each node sending and receiving only O(log n) messages in each round in time O(log n), w.h.p., which beats the currently best O(log(3/2) n) time algorithm of [Gotte et al., SIROCCO'19]. 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 Omega(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, APPROX' 14]. Additionally, we show how our algorithm can be used to efficiently solve graph problems in hybrid networks [Augustine et al., SODA'20]. Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the initial edges is unrestricted. In contrast, only polylogarithmically many messages can be communicated 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 time O (log n), w.h.p. Furthermore, we show how to compute an MIS in time O(log d + log log n), w.h.p., where d is the initial degree of G.

关键词： distributed Protocol Peer-to-Peer Network Randomized Algorithm Expander

来源：评论

学校读者我要写书评

暂无评论

Asynchronous Fault-Tolerant Language Decidability for Runtime Verification of distributed Systems 25

Asynchronous Fault-Tolerant Language Decidability for Runtim...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Armando Castañeda Gilde Valeria Rodríguez Instituto de Matemáticas Universidad Nacional Autónoma de México (UNAM) Mexico City Mexico Universidad Nacional Autónoma de México (UNAM) Mexico City Mexico

ISBN: (纸本)9798400718854

Implementing correct distributed systems is an error-prone task. Runtime Verification (RV) offers a lightweight formal method to improve reliability by monitoring system executions against correctness properties. However, applying RV in distributed settings—where no process has global knowledge—poses fundamental challenges, particularly under full asynchrony and fault tolerance. This paper addresses the distributed Runtime Verification (DRV) problem under such conditions. In our model, each process in a distributed monitor receives a fragment of the input word describing system behavior and must decide whether this word belongs to the language representing the correctness property being verified. Hence, the goal is to decide languages in a distributed fault-tolerant manner. We propose several decidability definitions, study the relations among them, and prove possibility and impossibility results. One of our main results is a characterization of the correctness properties that can be decided asynchronously. Remarkably, it applies to any language decidability definition. Intuitively, the characterization is that only properties with no real-time order constraints can be decided in asynchronous fault-tolerant settings. These results expose the expressive limits of DRV in realistic systems, as several properties of practical interest rely on reasoning about real-time order of events in executions. To overcome these limitations, we introduce a weaker model where the system under inspection is verified indirectly. Under this weaker model we define predictive decidability, a decidability definition that turn some real-time sensitive correctness properties verifiable. Our framework unifies and extends existing DRV theory and sharpens the boundary of runtime monitorability under different assumptions.

关键词： concurrent algorithms

来源：评论

学校读者我要写书评

暂无评论

Sublinear-Time Sampling of Spanning Trees in the Congested Clique 25

Sublinear-Time Sampling of Spanning Trees in the Congested C...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Sriram V. Pemmaraju Sourya Roy Joshua Z. Sobel University of Iowa Iowa City USA

ISBN: (纸本)9798400718854

We present the first sublinear-in-n round algorithm for sampling an approximately uniform spanning tree of an n-vertex graph in the CongestedClique model of distributed computing. In particular, our algorithm requires Õ (n0.657) rounds for sampling a spanning tree within total variation distance 1/nc, for arbitrary constant c > 0, from the uniform distribution. More precisely, our algorithm requires Õ (n1/2+α) rounds, where O (nα) is the running time of matrix multiplication in the CongestedClique model (currently α = 1-2/ω = 0.157, where ω is the sequential matrix multiplication time exponent). We can adapt our algorithm to give exact rather than approximate samples, but with a larger, though still o (n), runtime of Õ(n2/3+α) = O(n0.824).In a remarkable result, Aldous (SIDM 1990) and Broder (FOCS 1989) showed that the first visit edge to each vertex, excluding the start vertex, during a random walk forms a uniformly chosen spanning tree of the underlying graph. The biggest challenge with implementing the Aldous-Broder algorithm in a distributed setting is that it requires a very long random walk, i.e., a walk that covers the graph and might have to be Θ(mn) steps long for an n-vertex, m-edge graph, in the worst case. The most common technique for constructing random walks in "all-to-all" communication models such as CongestedClique and MPC are bottom-up techniques which start with many short walks and repeatedly stitch these together to build longer walks. These techniques fail to efficiently build the long random walk required by the Aldous-Broder algorithm. Our algorithm is a significant departure from known techniques, featuring a top-down walk filling approach paired with Schur complement graphs for walk shortcutting. To make this idea work in the CongestedClique model, we present a novel compressed random walk reconstruction algorithm, based on randomly sampling a weighted perfect *** addition, we show how to take somewhat shorter random walks even mor

关键词： distributed sampling

来源：评论

学校读者我要写书评

暂无评论

Byzantine Agreement and Leader Election: From Classical to the Modern 21

Byzantine Agreement and Leader Election: From Classical to t...

引用

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

作者： Augustine, John Molla, Anisur Rahaman Pandurangan, Gopal IIT Madras Dept Comp Sci & Engn Chennai Tamil Nadu India Indian Stat Inst Kolkata Crypto & Secur Res Unit Kolkata W Bengal India Univ Houston Dept Comp Sci Houston TX 77204 USA

ISBN: (纸本)9781450385480

We will present the fundamentals of Byzantine agreement and leader election problems from a modern perspective. Byzantine fault tolerant protocols are at the heart of secure and robust protocols that can tolerate the presence of malicious nodes in a distributed system, such as a Peer-to-Peer (P2P) network, which allows a large number of peers to enter the network with little or no admission control. Such malicious peers acting alone or in collaboration can cause disruption of service in P2P systems. Our tutorial is largely inspired by recent P2P applications like Blockchain and cryptocurrencies that espouse permissionless settings whereby peers can anonymously and dynamically join and leave the network at will. Our presentation will be in three parts. In the first part, we will present the historic foundations of Byzantine agreement and leader election and describe the fundamentals that underlie our modern understanding of these problems. Much of the classical results focus on complete networks where nodes have global knowledge. In the second part, motivated by real-world distributed networks such as P2P networks which are typically sparse and bounded degree with nodes having only local knowledge, we focus on Byzantine protocols for sparse networks. While the first two parts will focus on static settings, motivated by modern applications such as blockchains and cryptocurrencies which operate on dynamic P2P networks, the third part will delve into Byzantine procotols for dynamic networks where nodes continuously join and leave the system. The tutorial will cover various tools and techniques that are useful in designing Byzantine protocols in sparse and dynamic networks and will discuss key open problems in the area.

关键词： Byzantine protocols leader election agreement consensus distributed algorithms blockchain sparse networks P2P networks dynamic networks

来源：评论

学校读者我要写书评

暂无评论

Faster distributed Δ-Coloring via Ruling Subgraphs 25

Faster Distributed Δ-Coloring via Ruling Subgraphs

引用

proceedings of the 57th Annual acm symposium on Theory of computing

作者： Yann Bourreau Sebastian Brandt Alexandre Nolin CISPA Helmholtz Center for Information Security Saarbrücken Germany

ISBN: (纸本)9798400715105

Brooks’ theorem states that all connected graphs but odd cycles and cliques can be colored with Δ colors, where Δ is the maximum degree of the graph. Such colorings have been shown to admit non-trivial distributed algorithms [Panconesi and Srinivasan, Combinatorica 1995] and have been studied intensively in the distributed literature. In particular, it is known that any deterministic algorithm computing a Δ-coloring requires Ω(logn) rounds in the LOCAL model [Chang, Kopelowitz, and Pettie, FOCS 2016], and that this lower bound holds already on constant-degree graphs. In contrast, the best upper bound in this setting is given by an O(log2 n)-round deterministic algorithm that can be inferred already from the works of [Awerbuch, Goldberg, Luby, and Plotkin, FOCS 1989] and [Panconesi and Srinivasan, Combinatorica 1995] roughly three decades ago, raising the fundamental question about the true complexity of Δ-coloring in the constant-degree *** answer this long-standing question almost completely by providing an almost-optimal deterministic O(logn log* n)-round algorithm for Δ-coloring, matching the lower bound up to a log* n-factor. Similarly, in the randomized LOCAL model, we provide an O(loglogn log* n)-round algorithm, improving over the state-of-the-art upper bound of O(log2 logn) [Ghaffari, Hirvonen, Kuhn, and Maus, distributed computing 2021] and almost matching the Ω(loglogn)-round lower bound by [BFHKLRSU, STOC 2016].Our results make progress on several important open problems and conjectures. One key ingredient for obtaining our results is the introduction of ruling subgraph families as a novel tool for breaking symmetry between substructures of a graph, which we expect to be of independent interest.

关键词： Brooks' theorem

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: distributed Quantum Interactive Proofs 36

Brief Announcement: Distributed Quantum Interactive Proofs

引用

36th International symposium on distributed computing, DISC 2022

作者： Le Gall, François Miyamoto, Masayuki Nishimura, Harumichi Graduate School of Mathematics Nagoya University Japan Graduate School of Informatics Nagoya University Japan

ISBN: (纸本)9783959772556

The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an n-node network G can exchange short messages (called certificates) with a powerful prover. The goal is to decide if the input (including G itself) belongs to some language, with as few turns of interaction and as few bits exchanged between nodes and the prover as possible. There are several results showing that the size of certificates can be reduced drastically with a constant number of interactions compared to non-interactive distributed proofs. In this brief announcement, we introduce the quantum counterpart of distributed interactive proofs: certificates can now be quantum bits, and the nodes of the network can perform quantum computation. The main result of this paper shows that by using quantum distributed interactive proofs, the number of interactions can be significantly reduced. More precisely, our main result shows that for any constant k, the class of languages that can be decided by a k-turn classical (i.e., non-quantum) distributed interactive protocol with f(n)-bit certificate size is contained in the class of languages that can be decided by a 5-turn distributed quantum interactive protocol with O(f(n))-bit certificate size. We also show that if we allow to use shared randomness, the number of turns can be reduced to 3-turn. Since no similar turn-reduction classical technique is currently known, our result gives evidence of the power of quantum computation in the setting of distributed interactive proofs as well. © François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura.

关键词： Quantum computers

来源：评论

学校读者我要写书评

暂无评论

Search via Parallel Levy Walks on Z² 21

Search via Parallel Levy Walks on Z<SUP>2</SUP>

引用

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

作者： Clementi, Andrea D'Amore, Francesco Giakkoupis, George Natale, Emanuele Univ Roma Tor Vergata Rome Italy Univ Cote dAzur INRIA CNRS I3S Sophia Antipolis France Univ Rennes CNRS INRIA IRISA Rennes France

ISBN: (纸本)9781450385480

Motivated by the Levy foraging hypothesis - the premise that various animal species have adapted to follow Levy walks to optimize their search efficiency - we study the parallel hitting time of Levy walks on the infinite two-dimensional grid. We consider k independent discrete-time Levy walks, with the same exponent alpha is an element of(1, infinity), that start from the same node, and analyze the number of steps until the first walk visits a given target at distance l. We show that for any choice of k and l from a large range, there is a unique optimal exponent alpha(k,l) is an element of(2, 3), for which the hitting time is (O) over tilde (l(2)/k) w.h.p., while modifying the exponent by any constant term epsilon > 0 increases the hitting time by a factor polynomial in l, or the walks fail to hit the target almost surely. Based on that, we propose a surprisingly simple and effective parallel search strategy, for the setting where k and l are unknown: The exponent of each Levy walk is just chosen independently and uniformly at random from the interval (2, 3). This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know k). Our results should be contrasted with a line of previous work showing that the exponent alpha = 2 is optimal for various search problems. In our setting of k parallel walks, we show that the optimal exponent depends on k and l, and that randomizing the choice of the exponents works simultaneously for all k and l.

关键词： Levy walk parallel Levy walks infinite 2D grid hitting time distributed search Levy foraging hypothesis ANTS problem biological distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：