Work on optimal protocols for Eventual Byzantine Agreement (EBA)-protocols that, in a precise sense, decide as soon as possible in every run and guarantee that all nonfaulty agents decide on the same value-has focused...
详细信息
ISBN:
(纸本)9798400701214
Work on optimal protocols for Eventual Byzantine Agreement (EBA)-protocols that, in a precise sense, decide as soon as possible in every run and guarantee that all nonfaulty agents decide on the same value-has focused on full-information protocols (FIPs), where agents repeatedly send messages that completely describe their past observations to every other agent. While it can be shown that, without loss of generality, we can take an optimal protocol to be an FIP, full information exchange is impractical to implement for many applications due to the required message size. We separate protocols into two parts, the information-exchange protocol and the action protocol, so as to be able to examine the effects of more limited information exchange. We then define a notion of optimality with respect to an information-exchange protocol. Roughly speaking, an action protocol P is optimal with respect to an information-exchange protocol epsilon if, with P, agents decide as soon as possible among action protocols that exchange information according to epsilon. We present a knowledge-based EBA program for omission failures all of whose implementations are guaranteed to be correct and are optimal if the information exchange satisfies a certain safety condition. We then construct concrete programs that implement this knowledge-based program in two settings of interest that are shown to satisfy the safety condition. Finally, we show that a small modification of our program results in an FIP that is both optimal and efficiently implementable, settling an open problem posed by Halpern, Moses, and Waarts (SIAM J. Comput., 2001).
Implicitly parallel programming systems must solve the joint problems of dependence analysis and coherence to ensure apparently-sequential semantics for applications run on distributed memory machines. Solving these p...
详细信息
We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent Local algorithm for (degree + 1)-list-coloring (D1LC)...
详细信息
ISBN:
(纸本)9781450392624
We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent Local algorithm for (degree + 1)-list-coloring (D1LC), this allows us to solve D1LC in O(log(5) log n) Congest rounds, and in only O(log* n) rounds when the graph has minimum degree Omega(log(7) n), w.h.p. The technique also has immediate applications in testing some graph properties locally, and for estimating the sparsity/density of local subgraphs in O(1) CONGEST rounds, w.h.p.
High-precision integer multiplication is crucial in privacypreserving computational techniques but poses acceleration challenges on GPUs due to its complexity and the diverse bit lengths in cryptosystems. This paper i...
详细信息
ISBN:
(纸本)9798400704352
High-precision integer multiplication is crucial in privacypreserving computational techniques but poses acceleration challenges on GPUs due to its complexity and the diverse bit lengths in cryptosystems. This paper introduces GIM, an efficient high-precision integer multiplication algorithm accelerated with GPUs. It employs a novel segmented integer multiplication algorithm that separates implementation details from bit length, facilitating code optimizations. We also present a computation diagram to analyze parallelization strategies, leading to a series of enhancements. Experiments demonstrate that this approach achieves a 4.47x speedup over the commonly used baseline.
Cryptographic Hardware Engineering (CHE) is an emerging field that amalgamates cryptography principles with hardware design and implementation. It plays an increasingly important role as secure and trustworthy computi...
详细信息
ISBN:
(纸本)9798400706059
Cryptographic Hardware Engineering (CHE) is an emerging field that amalgamates cryptography principles with hardware design and implementation. It plays an increasingly important role as secure and trustworthy computing and communication is needed in all applications. In order to introduce CHE into undergraduate curriculum to prepare the next generation workforce, students must have a solid theoretical foundation in cryptography, be proficient in digital circuit design, and have access to commercial design tools and equipment. In this paper, we report our experience in developing and teaching a CHE course for junior students. The course consists of three components that are complementary to each other: digital circuits and FPGA design fundamentals, hardware implementation of cryptographic algorithms, and security analysis of cryptographic hardware. Through this course, students get a good comprehension of CHE principles and gain hands-on experience in secure cryptographic hardware design and analysis.
The proceedings contain 63 papers. The topics discussed include: Hops: fine-grained heterogeneous sensing, efficient and fair deep learning cluster scheduling system;queue management for SLO-oriented large language mo...
ISBN:
(纸本)9798400712869
The proceedings contain 63 papers. The topics discussed include: Hops: fine-grained heterogeneous sensing, efficient and fair deep learning cluster scheduling system;queue management for SLO-oriented large language model serving;KALE: elastic GPU scheduling for online DL model training;FedCaSe: enhancing federated learning with heterogeneity-aware caching and scheduling;QLStateGuard: statement-level SQL injection defense based on learning-driven middleware;vista: machine learning based database performance troubleshooting framework in Amazon RDS;building AI agents for autonomous clouds: challenges and design principles;and Zero-SAD: zero-shot learning using synthetic abnormal data for abnormal behavior detection on private cloud.
The proceedings contain 43 papers. The topics discussed include: SWARM: replicating shared disaggregated-memory data in no time;efficient reproduction of fault-induced failures in distributed systems with feedback-dri...
ISBN:
(纸本)9798400712517
The proceedings contain 43 papers. The topics discussed include: SWARM: replicating shared disaggregated-memory data in no time;efficient reproduction of fault-induced failures in distributed systems with feedback-driven fault injection;if at first you don’t succeed, try, try, again...? insights and LLM-informed tooling for detecting retry bugs in software systems;tiered memory management: access latency is the key!;CHIME: a cache-efficient and high-performance hybrid index on disaggregated memory;Aceso: achieving efficient fault tolerance in memory-disaggregated key-value stores;reducing energy bloat in large model training;and uncovering nested data parallelism and data reuse in DNN computation with FractalTensor.
In 2016, College Board launched Advanced Placement (AP) Computer Science principles (CSP) as a college-level introductory course to the breadth of Computer Science (CS). This was a joint effort with National Science F...
详细信息
The maximum weighted matching (mwm) problem is one of the most well-studied combinatorial optimization problems in distributed graph algorithms. Despite a long development on the problem, and the recent progress of Fi...
详细信息
The very edge of the rapidly evolving computing continuum is characterized by a wide variety of different hardware architectures, software platforms, and in general diverse device constraints and capabilities. While i...
详细信息
暂无评论