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

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Delporte-Gallet, Carole Fauconnier, Hugues Fraigniaud, Pierre Rajsbaum, Sergio Travers, Corentin IRIF University Paris Cité CNRS Paris France Irif and Instituto de Matemàticas Unam Mexico City Mexico Lis University Aix-Marseille CNRS Marseille France

ISBN: (纸本)9798400706684

The celebrated Asynchronous Computability Theorem of Herlihy and Shavit (Jacm 1999) provided a topological characterization of the tasks that are wait-free solvable by processes communicating through writing and reading shared registers. This characterization assumes the use of full-information protocols, in which each time a process writes in the shared memory, it communicates everything it learned since the beginning of the execution. Thus, each register in the shared memory is of unbounded size. Whether unbounded size registers are unavoidable for the model of computation to be universal is the central question studied in this paper. More generally, when at most t out of n processes can crash, is the model with bounded size registers universal?We show that when 1 ≤ t 2, there exists a task that cannot be solved by n processes communicating via registers of size f(n) bits, but is solvable by n processes using unbounded registers. The case n = 2, t = 1, where 1-resilient computing and wait-free computing coincide, does not display the same behavior. We show that any task solvable by 2 processes in the wait-free shared-memory model with unbounded-size registers can be solved by 2 processes in the wait-free shared-memory model with constant size ***, we consider the iterated shared memory model, which has played a crucial role since Herlihy and Shavit's characterization. We show that 1-bit registers (per iteration) are sufficient for solving wait-free any task that is solvable by a full-information wait-free protocol. Therefore, while the wait-free read/write shared-memory model is known to be computationally equivalent to the iterated model, this equivalence only holds if registers are unbounded. © 2024 Copyright is held by the owner/author(s). Publication rights licensed to acm.

关键词： Memory architecture

来源：评论

学校读者我要写书评

暂无评论

PhD Forum: Efficient Privacy-Preserving Processing via Memory-Centric computing 43

PhD Forum: Efficient Privacy-Preserving Processing via Memor...

引用

43rd International symposium on Reliable distributed Systems

作者： Mwaisela, Mpoki Univ Neuchatel Neuchatel Switzerland

ISBN: (纸本)9798331530044;9798331530037

Privacy-preserving computation techniques like homomorphic encryption (HE) and secure multi-party computation (SMPC) enhance data security by enabling processing on encrypted data. However, the significant computational and CPU-DRAM data movement overhead resulting from the underlying cryptographic algorithms impedes the adoption of these techniques in practice. Existing approaches focus on improving computational overhead using specialized hardware like GPUs and FPGAs, but these methods still suffer from the same processor-DRAM overhead. Novel hardware technologies that support in-memory processing have the potential to address this problem. Memory-centric computing, or processing-in-memory (PIM), brings computation closer to data by introducing low-power processors called data processing units (DPUs) into memory. Besides its in-memory computation capability, PIM provides extensive parallelism, resulting in significant performance improvement over state-of-the-art approaches. We propose a framework that uses recently available PIM hardware to achieve efficient privacy-preserving computation. Our design consists of a four-layer architecture: (1) an application layer that decouples privacy-preserving applications from the underlying protocols and hardware;(2) a protocol layer that implements existing secure computation protocols (HE and MPC);(3) a data orchestration layer that leverages data compression techniques to mitigate the data transfer overhead between DPUs and host memory;(4) a computation layer which implements DPU kernels on which secure computation algorithms are built.

关键词： privacy-preserving processing secure multi-party computation homomorphic encryption processing in-memory memory-centric computing

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Simpler and More General distributed Coloring Based on Simple List Defective Coloring Algorithms 24

Brief Announcement: Simpler and More General Distributed Col...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Fuchs, Marc Kuhn, Fabian University of Freiburg Germany

ISBN: (纸本)9798400706684

In this paper, we give list coloring variants of simple iterative defective coloring algorithms. Formally, in a list defective coloring instance, each node v of a graph is given a list Lv of colors and a list of allowed defects dv(x) for the colors. Each node v needs to be colored with a color x ϵ Lv such that at most dv(x) neighbors (or outneighbors) of v also pick the same color *** a defect parameter d, it is known that by making two sweeps in opposite order over the nodes of an edge-oriented graph with maximum outdegree β, one can compute a coloring with O(β2/d2) colors such that every node has at most d outneighbors of the same color. We generalize this and show that if all nodes have lists of size p2 and ĝv : ςxϵLv(dv(x) + 1) > p · β, we can make two sweeps of the nodes such that at the end, each node v has chosen a color x ϵ Lv for which at most dv(x) outneighbors of v are colored with color x. Our algorithm is simpler and computationally significantly more efficient than existing algorithms for similar list defective coloring problems. We show that the above result can in particular be used to obtain an alternative [EQUATION]-round algorithm for the (Δ+ 1)-coloring problem in the CONGEST *** neighborhood independence θ of a graph is the maximum number of pairwise non-adjacent neighbors of some node of the graph. Notable examples of graphs of bounded neighborhood independence are the line graphs of bounded-rank hypergraphs. It is well known that by doing a single sweep over the nodes of a graph of neighborhood independence θ, one can compute a d-defective coloring with O(θ · δ/d) colors. We extend this approach to the list defective coloring setting and use it to obtain a recursive (Δ+ 1)-coloring algorithm with a round complexity that is parameterized by the neighborhood independence θ. In particular, if θ = O(1), we get an (log δ)O(log log δ) + O(log∗n)-round algorithm to compute a (Δ+ 1)-coloring. The algorithm generalizes an algorithm from [Balliu

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

Even-Cycle Detection in the Randomized and Quantum CONGEST Model 24

Even-Cycle Detection in the Randomized and Quantum CONGEST M...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Fraigniaud, Pierre Luce, Maël Magniez, Frederic Todinca, Ioan Université Paris Cité CNRS IRIF Paris France Université d'Orléans INSA-Centre Val de Loire LIFO Orléans France

ISBN: (纸本)9798400706684

We show that, for every k ≥ 2, C2k-freeness can be decided in O(n1 - 1/k) rounds in the CONGEST model by a randomized Monte-Carlo distributed algorithm with one-sided error probability 1/3. This matches the best round-complexities of previously known algorithms for k ϵ {2, 3, 4, 5} by Drucker et al. [PODC'14] and Censor-Hillel et al. [DISC'20], but improves the complexities of the known algorithms for k > 5 by Eden et al. [DISC'19], which were essentially of the form Õ (n1 - 2/k2). Our algorithm uses colored BFS-explorations with threshold, but with an original global approach that enables to overcome a recent impossibility result by Fraigniaud et al. [SIROCCO'23] about using colored BFS-exploration with local threshold for detecting *** also show how to quantize our algorithm for achieving a round-complexity Õ(n1/2 - 1/2k) in the quantum setting for deciding C2k freeness. Furthermore, this allows us to improve the known quantum complexities of the simpler problem of detecting cycles of length at most 2k by van Apeldoorn and de Vos [PODC'22]. Our quantization is in two steps. First, the congestion of our randomized algorithm is reduced, to the cost of reducing its success probability too. Second, the success probability is boosted using a new quantum framework derived from sequential algorithms, namely Monte-Carlo quantum amplification. © 2024 Association for computing Machinery. All rights reserved.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

distributed programming and consistency: principles and practice

Distributed programming and consistency: Principles and prac...

引用

3rd acm symposium on Cloud computing, SoCC 2012

作者： Alvaro, Peter Conway, Neil Hellerstein, Joseph M. UC Berkeley United States

ISBN: (纸本)9781450317610

In recent years, distributed programming has become a topic of widespread interest among developers. However, writing reliable distributed programs remains stubbornly difficult. In addition to the inherent challenges of distribution - asynchrony, concurrency, and partial failure - many modern distributed systems operate at massive scale. Scalability concerns have in turn encouraged many developers to eschew strongly consistent distributed storage in favor of application-level consistency criteria [5, 10, 18], which has raised the degree of difficulty still further. © 2012 acm.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Efficient Top-K query calculation in distributed networks 04

Efficient Top-K query calculation in distributed networks

引用

proceedings of the 23rd Annual acm symposium on principles of distributed computing

作者： Cao, Pei Wang, Zhe Department of Computer Science Stanford University Stanford CA 94305 United States Department of Computer Science Princeton University Princeton NJ 08540 United States

ISBN: (纸本)9781581138023

This paper presents a new algorithm to answer top-k queries (e.g. "find the k objects with the highest aggregate values") in a distributed network. Existing algorithms such as the Threshold Algorithm [10] consume an excessive amount of bandwidth when the number of nodes, m, is high. We propose a new algorithm called "Three-Phase Uniform Threshold" (TPUT). TPUT reduces network bandwidth consumption by pruning away ineligible objects, and terminates in three round-trips regardless of data input. The paper presents two sets of results about TPUT. First, trace-driven simulations show that, depending on the size of the network, TPUT reduces network traffic by one to two orders of magnitude compared to existing algorithms. Second, TPUT is proven to be instance-optimal on common data series. In particular, analysis shows that by using a pruning parameter α

关键词： Telecommunication networks

来源：评论

学校读者我要写书评

暂无评论

Adaptive resource management and scheduling for cloud computing 3

Adaptive resource management and scheduling for cloud comput...

引用

3rd Internatioal Workshop on Adaptive Resource Management and Scheduling for Cloud computing, ARMS-CC 2016

作者： Pop, Florin Prodan, Radu Computer Science Department University Politehnica of Bucharest Romania Institute for Computer Science University of Innsbruck Austria

来源：评论

学校读者我要写书评

暂无评论

Lock-free linked lists and skip lists 04

Lock-free linked lists and skip lists

引用

proceedings of the 23rd Annual acm symposium on principles of distributed computing

作者： Fomitchev, Mikhail Ruppert, Eric Department of Computer Science York University Canada

ISBN: (纸本)9781581138023

Lock-free shared data structures implement distributed objects without the use of mutual exclusion, thus providing robustness and reliability. We present a new lock-free implementation of singly-linked lists. We prove that the worst-case amortized cost of the operations on our linked lists is linear in the length of the list plus the contention, which is better than in previous lock-free implementations of this data structure. Our implementation uses backlinks that are set when a node is deleted so that concurrent operations visiting the deleted node can recover. To avoid performance problems that would arise from traversing long chains of backlink pointers, we introduce Hag bits, which indicate that a deletion of the next node is underway. We then give a lock-free implementation of a skip list dictionary data structure that uses the new linked list algorithms to implement individual levels. Our algorithms use the single-word C&S synchronization primitive.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Swiper: a new paradigm for efficient weighted distributed protocols 24

Swiper: a new paradigm for efficient weighted distributed pr...

引用

43rd acm SIGACT-SIGOPS symposium on principles of distributed computing, PODC 2024

作者： Tonkikh, Andrei Freitas, Luciano Ltci Télécom Paris Institut Polytechnique de Paris Palaiseau France

ISBN: (纸本)9798400706684

The majority of fault-tolerant distributed algorithms are designed assuming a nominal corruption model, in which at most a fraction fn of parties can be corrupted by the adversary. However, due to the infamous Sybil attack, nominal models are not sufficient to express the trust assumptions in open (i.e., permissionless) settings. Instead, permissionless systems typically operate in a weighted model, where each participant is associated with a weight and the adversary can corrupt a set of parties holding at most a fraction fw of the total *** this paper, we suggest a simple way to transform a large class of protocols designed for the nominal model into the weighted model. To this end, we formalize and solve three novel optimization problems, which we collectively call the weight reduction problems, that allow us to map large real weights into small integer weights while preserving the properties necessary for the correctness of the protocols. In all cases, we manage to keep the sum of the integer weights to be at most linear in the number of parties, resulting in extremely efficient protocols for the weighted model. Moreover, we demonstrate that, on weight distributions that emerge in practice, the sum of the integer weights tends to be far from the theoretical worst case and, sometimes, even smaller than the number of ***, for some protocols, our transformation requires an arbitrarily small reduction in resilience (i.e., fw = fn - ϵ), surprisingly, for many important problems, we manage to obtain weighted solutions with the same resilience (fw = fn) as nominal ones. Notable examples include erasure-coded distributed storage and broadcast protocols, verifiable secret sharing, and asynchronous consensus. Although there are ad-hoc weighted solutions to some of these problems, the protocols yielded by our transformations enjoy all the benefits of nominal solutions, including simplicity, efficiency, and a wider range of possible cryptographic assumpt

关键词： Cryptography

来源：评论

学校读者我要写书评

暂无评论

Failure detectors as type boosters

引用

distributed computing 2008年第5期20卷 343-358页

作者： Guerraoui, Rachid Kouznetsov, Petr Ecole Polytech Fed Lausanne Distributed Programming Lab CH-1015 Lausanne Switzerland Max Planck Inst Software Syst D-66123 Saarbrucken Germany

The power of an object type T can be measured as the maximum number n of processes that can solve consensus using only objects of T and registers. This number, denoted cons(T), is called the consensus power of T. This paper addresses the question of the weakest failure detector to solve consensus among a number k > n of processes that communicate using shared objects of a type T with consensus power n. In other words, we seek for a failure detector that is sufficient and necessary to "boost" the consensus power of a type T from n to k. It was shown in Neiger (proceedings of the 14th annual acm symposium on principles of distributed computing (PODC), pp. 100-109, 1995) that a certain failure detector, denoted Omega (n) , is sufficient to boost the power of a type T from n to k, and it was conjectured that Omega (n) was also necessary. In this paper, we prove this conjecture for one-shot deterministic types. We first show that, for any one-shot deterministic type T with cons(T) <= n, Omega (n) is necessary to boost the power of T from n to n + 1. Then we go a step further and show that Omega(n) is also the weakest to boost the power of (n + 1)-ported one-shot deterministic types from n to any k > n. Our result generalizes, in a precise sense, the result of the weakest failure detector to solve consensus in asynchronous message-passing systems (Chandra et al. in J acm 43(4):685-722, 1996). As a corollary, we show that Omega (t) is the weakest failure detector to boost the resilience level of a distributed shared memory system, i.e., to solve consensus among n > t processes using (t - 1)-resilient objects of consensus power t.

关键词： ALGORITHMS STANDArdS MEMORY REGISTERS (Computers) COMPUTER file sharing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：