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

proceedings of the acm symposium on principles of distributed computing

作者： Alkida Balliu Pierre Fraigniaud Dennis Olivetti Mikaël Rabie Gran Sasso Science Institute L'Aquila Italy IRIF CNRS Université Paris Cité Paris France

ISBN: (纸本)9798400718854

We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a subset of problems solvable by sequential greedy algorithms, such as (Δ + 1)-coloring and maximal independent set. It is known from previous work that, in n-node graphs of maximum degree Δ, any problem in the class O-LOCAL can be solved by a deterministic distributed algorithm with awake complexity O (log Δ + log* n).In this paper, we show that any problem belonging to the class O-LOCAL can be solved by a deterministic distributed algorithm with awake complexity [EQUATION]. This leads to a polynomial improvement over the state of the art when [EQUATION], e.g., Δ = n∊ for some arbitrarily small ∊ > 0. The key ingredient for achieving our results is the computation of a network decomposition that uses a small-enough number of colors in sub-logarithmic time in the Sleeping model, which can be of independent interest.

关键词： distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Fully-distributed Scalable Peer-to-Peer Protocol for Byzantine-Resilient distributed Hash Tables 22

A Fully-Distributed Scalable Peer-to-Peer Protocol for Byzan...

引用

34th acm symposium on Parallelism in Algorithms and Architectures (SPAA)

作者： Augustine, John Chatterjee, Soumyottam Pandurangan, Gopal Indian Inst Technol Madras Dept Comp Sci & Engg Chennai India Ashoka Univ Dept Comp Sci Sonipat India Univ Houston Dept Comp Sci Houston TX USA

ISBN: (纸本)9781450391467

Performing computation in the presence of faulty and malicious nodes is a central problem in distributed computing. Over 35 years ago, Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] studied the fundamental Byzantine agreement problem in sparse, bounded degree networks and presented the first protocol that achieved almost-everywhere agreement among good nodes. However, this protocol and several subsequent protocols including that of King, Saia, Sanwalani, and Vee [FOCS 2006] had the drawback that they were not fully-distributed - in those protocols, nodes are required to have initial knowledge of the entire network topology. This drawback makes such protocols not applicable to real-world communication networks such as peer-to-peer (P2P) networks, which are typically sparse and bounded degree and where nodes initially have only local knowledge of themselves and of their neighbors. In this work, we present the first scalable, fully-distributed Byzantine protocol for sparse, bounded degree, P2P networks that can tolerate a large number of Byzantine nodes. We assume that the Byzantine nodes can behave arbitrarily and maliciously, have unlimited computational power, and may collude among themselves. However, they are oblivious to (direct) communication between good nodes, i.e., we assume the existence of private channels, but make no cryptographic assumptions. In particular, Byzantine nodes do have knowledge of the messages sent by good nodes if those messages go through a Byzantine node. As is standard in P2P networks, we assume that nodes can communicate with each other if they know their identities. Our main contribution is a (randomized) fully-distributed protocol that guarantees with high probability the construction of an addressable P2P network that can be used to build a distributed hash table (DHT) that enables efficient, robust, and reliable storage and search of data even in the presence of up to n/polylog n number of Byzantine nodes (where n is th

关键词： peer-to-peer networks Byzantine fault tolerance distributed hash tables random walks

来源：评论

学校读者我要写书评

暂无评论

distributed Randomness from Approximate Agreement 36

Distributed Randomness from Approximate Agreement

引用

36th International symposium on distributed computing, DISC 2022

作者： Freitas, Luciano Kuznetsov, Petr Tonkikh, Andrei LTCI Télécom Paris Institut Polytechnique de Paris France

ISBN: (纸本)9783959772556

Randomisation is a critical tool in designing distributed systems. The common coin primitive, enabling the system members to agree on an unpredictable random number, has proven to be particularly useful. We observe, however, that it is impossible to implement a truly random common coin protocol in a fault-prone asynchronous system. To circumvent this impossibility, we introduce two relaxations of the perfect common coin: (1) approximate common coin generating random numbers that are close to each other;and (2) Monte Carlo common coin generating a common random number with an arbitrarily small, but non-zero, probability of failure. Building atop the approximate agreement primitive, we obtain efficient asynchronous implementations of the two abstractions, tolerating up to one third of Byzantine processes. Our protocols do not assume trusted setup or public key infrastructure and converge to the perfect coin exponentially fast in the protocol running time. By plugging one of our protocols for Monte Carlo common coin in a well-known consensus algorithm, we manage to get a binary Byzantine agreement protocol with O(n3 log n) communication complexity, resilient against an adaptive adversary, and tolerating the optimal number f 4). We also show how the approximate common coin, combined with a variant of Gray code, can be used to solve an interesting problem of Intersecting Random Subsets, which we introduce in this paper. © Luciano Freitas, Petr Kuznetsov, and Andrei Tonkikh.

关键词： Monte Carlo methods

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Energy-Efficient Maximal Independent Sets in Radio Networks 25

Brief Announcement: Energy-Efficient Maximal Independent Set...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Dominick Banasik Varsha Dani Fabien Dufoulon Aayush Gupta Thomas Hayes Gopal Pandurangan Rochester Institute of Technology Rochester USA Lancaster University Lancaster United Kingdom University of Houston Houston Texas USA University at Buffalo Buffalo USA

ISBN: (纸本)9798400718854

Maximal Independent Set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on the MIS problem in the radio networks model, a standard model widely used to model wireless networks, particularly ad hoc wireless and sensor networks. Energy is a premium resource in these networks, which are typically battery-powered. Hence, designing distributed algorithms that use as little energy as possible is crucial. We use the well-established energy model where a node can be sleeping or awake in a round, and only the awake rounds (when it can send or listen) determine the energy complexity of the *** present the first energy-efficient MIS algorithms in radio networks with arbitrary and unknown graph topology. We present algorithms for two popular variants of the radio model - with collision detection (CD) and without collision detection (no-CD). Specifically, we obtain the following results:(1) CD model: We present a distributed MIS algorithm with O (log n) energy complexity (n is the network size). We also show a matching Ω (log n) lower bound for the energy complexity.(2) no-CD model: In the more challenging no-CD model, we present a distributed MIS algorithm with energy complexity O (log2 n log log n). The energy complexity of our algorithm is significantly lower than the round (and energy) complexity of O (log3 n) of the best-known distributed MIS algorithm of Davies [PODC 2023] for arbitrary graph topology.

关键词： distributed computing

来源：评论

学校读者我要写书评

暂无评论

Improved distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees 21

Improved Distributed Lower Bounds for MIS and Bounded (Out-)...

引用

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

作者： Balliu, Alkida Brandt, Sebastian Kuhn, Fabian Olivetti, Dennis Univ Freiburg Freiburg Germany Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450385480

Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first omega(log* n) lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bounds for a much more relaxed family of distributed symmetry breaking problems. As a by-product, we obtain improved lower bounds for the distributed MIS problem in trees. For a parameter k and an orientation of the edges of a graph G, we say that a subset S of the nodes of G is a k-outdegree dominating set if S is a dominating set of G and if in the induced sub- graph G [S], every node in S has outdegree at most k. Note that for k = 0, this definition coincides with the definition of an MIS. For a given k, we consider the problem of computing a k-outdegree dominating set. We show that, even in regular trees of degree at most A, in the standard LOCAL model, there exists a constant omega > 0 such that for k <= Delta(epsilon), for the problem of computing a k-outdegree dominating set, any randomized algorithm requires at least Omega ( min {log Delta, root log log n}) rounds and any deterministic algorithm requires at least Omega ( min {log Delta, root log log n} ) rounds. The proof of our lower bounds is based on the recently highly successful round elimination technique. We provide a novel way to do simplifications for round elimination, which we expect to be of independent interest. Our new proof is considerably simpler than the lower bound proof in [FOCS '20]. In particular, our round elimination proof uses a family of problems that can be described by only a constant number of labels. The existence of such a proof for the MIS problem was believed impossible by the authors of [FOCS '20].

关键词： maximal independent set dominating set LOCAL model lower bounds

来源：评论

学校读者我要写书评

暂无评论

Ultra-Sparse Near-Additive Emulators 21

Ultra-Sparse Near-Additive Emulators

引用

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

作者： Elkin, Michael Matar, Shaked Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9781450385480

Near-additive (aka (1 + epsilon, beta)-) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related problems in distributed, streaming and dynamic settings. Known constructions of near-additive emulators enable one to trade between their sparsity (i.e., number of edges) and the additive stretch beta. Specifically, for any pair of parameters epsilon > 0, kappa = 1, 2, ..., one can have a (1 + epsilon, beta)-emulator with O(n(1+1/kappa)) edges, with beta = (log kappa/epsilon)(log kappa). At their sparsest, these emulators employ c . n edges, for some constant c >= 2. We tighten this bound, and show that in fact precisely n(1+1/kappa )edges suffice. In particular, our emulators can be ultra-sparse, i.e., we can have an emulator with n + o(n) edges and beta (log log n/epsilon)(log log n (1+o(1))).( ) We also devise a distributed deterministic algorithm in the CONG EST model that builds these emulators in low polynomial time (i.e., in O(n(rho)) time, for an arbitrarily small constant parameter time, for an arbitrarily small constant parameter rho > 0). Finally, we also improve the state-of-the-art distributed deterministic CONGEST-model construction of (1 + epsilon, beta)-spanners devised in the PODC'19 paper [13]. Specifically, the spanners of [13] have O(beta . n(1+1/kappa)) edges, i.e., at their sparsest they employ O(log log n/epsilon) (log log n). n edges. In this paper, we devise an efficient distributed deterministic CONGEST-model algorithm that builds such spanners with O(n(1+1/kappa)) edges for kappa = O (log n/log((3) )n). K = 0 At their sparsest, these spanners employ only O(n. log log n) edges.

关键词： Emulators Deterministic distributed Algorithms

来源：评论

学校读者我要写书评

暂无评论

Time-space trade-offs in population protocols for the majority problem

引用

distributed computing 2021年第2期34卷 91-111页

作者： Berenbrink, Petra Elsaesser, Robert Friedetzky, Tom Kaaser, Dominik Kling, Peter Radzik, Tomasz Univ Hamburg Vogt Kolln Str 3 D-22527 Hamburg Germany Univ Salzburg Jakob Haringer Str 2 A-5020 Salzburg Austria Univ Durham Lower Mountjoy South Rd Durham DH1 3LE England Kings Coll London Strand CampusBush House London WC2B 4BG England

Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system ofnidentical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in proceedings of the 2015 acm symposium on principles of distributed computing, Donostia-San Sebastian, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population sizen), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.

关键词： distributed computing Majority Population protocols Stochastic processes

来源：评论

学校读者我要写书评

暂无评论

2022 Edsger W. Dijkstra Prize in distributed computing 22

2022 Edsger W. Dijkstra Prize in Distributed Computing

引用

proceedings of the 2022 acm symposium on principles of distributed computing

作者： Marcos Aguiliera Andrea Richa Alexander Schwarzmann Alessandro Panconesi Christian Scheideler Philipp Woelfel VMware Research Germany Arizona State University AZ USA Augusta University APO AA Sapienza Università Di Roma Rome Italy Universität Paderborn Paderborn Germany University of Calgary Calgary AB Canada

ISBN: (纸本)9781450392624

The Edsger W. Dijkstra Prize in distributed computing is awarded for outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributed computing have been evident for at least a decade. It is sponsored jointly by the acm symposium on principles of distributed computing (PODC) and the EATCS symposium on distributed computing (DISC). The prize is presented annually, with the presentation taking place alternately at PODC and DISC.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Strong-Diameter Network Decomposition 21

Strong-Diameter Network Decomposition

引用

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

作者： Chang, Yi-Jun Ghaffari, Mohsen Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450385480

Network decomposition is a central concept in the study of distributed graph algorithms. We present the first polylogarithmic-round deterministic distributed algorithm with small messages that constructs a strong-diameter network decomposition with polylogarithmic parameters. Concretely, a (C, D) strong-diameter network decomposition is a partitioning of the nodes of the graph into disjoint clusters, colored with C colors, such that neighboring clusters have different colors and the subgraph induced by each cluster has a diameter at most D. In the weak-diameter variant, the requirement is relaxed by measuring the diameter of each cluster in the original graph, instead of the subgraph induced by the cluster. A recent breakthrough of Rozhon and Ghaffari [STOC 2020] presented the first poly(log n)-round deterministic algorithm for constructing a weak-diameter network decomposition where C and D are both in poly(log n). Their algorithm uses small O(log n)-bit messages. One can transform their algorithm to a strong-diameter network decomposition algorithm with similar parameters. However, that comes at the expense of requiring unbounded messages. The key remaining qualitative question in the study of network decompositions was whether one can achieve a similar result for strong-diameter network decompositions using small messages. We resolve this question by presenting a novel technique that can transform any black-box weak-diameter network decomposition algorithm to a strong-diameter one, using small messages and with only moderate loss in the parameters.

关键词： ball carving distributed graph algorithms network decomposition

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: computing Power of Hybrid Models in Synchronous Networks 36

Brief Announcement: Computing Power of Hybrid Models in Sync...

引用

36th International symposium on distributed computing, DISC 2022

作者： Fraigniaud, Pierre Montealegre, Pedro Paredes, Pablo Rapaport, Ivan Ríos-Wilson, Martín Todinca, Ioan IRIF Université Paris Cité CNRS France Faculty of Engineering and Science Universidad Adolfo Ibáñez Santiago Chile Department of Mathematical Engineering University of Chile Santiago Chile DIM-CMM UMI 2807 CNRS University of Chile Santiago Chile LIFO Université d'Orléans France INSA Centre-Val de Loire Bourges France

ISBN: (纸本)9783959772556

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. © Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca.

关键词： computing power

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：