The proceedings contain 65 papers. The topics discussed include: the greedy spanner is existentially optimal;distributed algorithms for planar networks i: planar embedding;brief announcement: labeling schemes for powe...
ISBN:
(纸本)9781450339643
The proceedings contain 65 papers. The topics discussed include: the greedy spanner is existentially optimal;distributed algorithms for planar networks i: planar embedding;brief announcement: labeling schemes for power-law graphs;brief announcement: sublinear-space distance labeling using hubs;brief announcement: optimal leader election in multi-hop radio networks;brief announcement: the small world of curious beings;a randomized concurrent algorithm for disjoint set union;brief announcement: local independent set approximation;deterministic objects: life beyond consensus;unbeatable set consensus via topological and combinatorial reasoning;and a polylogarithmic gossip algorithm for plurality consensus.
The proceedings contain 11 papers. The topics discussed include: next generation virtual network architecture for multi-tenant distributed clouds: challenges and emerging techniques;vMCN: virtual mobile cloud network ...
ISBN:
(纸本)9781450342209
The proceedings contain 11 papers. The topics discussed include: next generation virtual network architecture for multi-tenant distributed clouds: challenges and emerging techniques;vMCN: virtual mobile cloud network for realizing scalable, real-time cyber physical systems;software-defined consistency group abstractions for virtual machines;slicing in locavore infrastructures;resilient routing via preorders in SDN;the CAT theorem and performance of transactional distributed systems;new techniques to curtail the tail latency in stream processing systems;optimized VM memory allocation based on monitored cache hit ratio;the misbelief in delay scheduling;towards migrating computation to distributed memory caches;and DSB-SEIS: a deduplicating secure backup system with encryption intensity selection.
The proceedings contain 58 papers. The topics discussed include: near-optimal scheduling of distributed algorithms;new routing techniques and their applications;brief announcement: routing the internet with very few e...
ISBN:
(纸本)9781450336178
The proceedings contain 58 papers. The topics discussed include: near-optimal scheduling of distributed algorithms;new routing techniques and their applications;brief announcement: routing the internet with very few entries;terminating distributed construction of shapes and patterns in a fair solution of automata;fast and exact majority in population protocols;distributed house-hunting in ant colonies;brief announcement: on the feasibility of leader election and shape formation with self-organizing programmable matter;near-optimal distributed maximum flow;toward optimal bounds in the congested clique: graph connectivity and MST;fast distributed almost stable matchings;a (truly) local broadcast layer for unreliable radio networks;efficient communication in cognitive radio networks;and brief announcement: a hierarchy of congested clique models, from broadcast to unicast.
The proceedings contain 51 papers. The topics discussed include: asynchronous MPC with a strict honest majority using non-equivocation;distributing the setup in universally composable multi-party computation;the futur...
ISBN:
(纸本)9781450329446
The proceedings contain 51 papers. The topics discussed include: asynchronous MPC with a strict honest majority using non-equivocation;distributing the setup in universally composable multi-party computation;the future(s) of shared data structures;a paradox of eventual linearizability in shared memory;brief announcement: are lock-free concurrent algorithms practically wait-free?;brief announcement: a generic construction for nonblocking dual containers;multi-message broadcast with abstract MAC layers and unreliable links;simple and efficient local codes for distributed stable network construction;beyond set disjointness: the communication complexity of finding the intersection;breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication;and estimation for monotone sampling: competitiveness and customization.
The proceedings contain 4 papers. The topics discussed include: quantum transfer learning for sentiment analysis: an experiment on an Italian corpus;multi-class quantum convolutional neural networks;practical implemen...
ISBN:
(纸本)9798400706462
The proceedings contain 4 papers. The topics discussed include: quantum transfer learning for sentiment analysis: an experiment on an Italian corpus;multi-class quantum convolutional neural networks;practical implementation of a quantum string matching algorithm;and speeding up answer set programming by quantum computing.
Bounded timestamping systems (Israeli and Li in proceedings of the 28th Annual IEEE symposium on Foundations of Computer Science (FOCS), pp 371-382, 1987;Dolev and Shavit in SIAM J Comput 26 (2):418-455, 1997) allow a...
详细信息
Bounded timestamping systems (Israeli and Li in proceedings of the 28th Annual IEEE symposium on Foundations of Computer Science (FOCS), pp 371-382, 1987;Dolev and Shavit in SIAM J Comput 26 (2):418-455, 1997) allow a temporal ordering of events in executions of concurrent algorithms. They are a fundamental and well-studied building block used in many shared-memory algorithms (Haldar and Vit & aacute;nyi in J acm, 49 (1):101-126, 2002;Afek et al. in acm Trans Program Lang Syst 16:939-953, 1994;Abrahamson in proceedings of the 7th acmsymposium on principles of distributedcomputing (PODC), pp 291-302, 1988;Bashari and Woelfel in proceedings of the 40th acmsymposium on principles of distributedcomputing (PODC), pp 545-555, 2021). A concurrent bounded timestamping system keeps track of m timestamps, which is usually greater or equal to the number of processes in the system, n. A process may, at any point, obtain a new timestamp, and later determine a total order of all process's most recent timestamps. Known bounded timestamping algorithms (Dolev and Shavit in SIAM J Comput 26(2):418-455, 1997;Dwork and Waarts in J acm 46(5):633-666, 1999;Dwork et al. in SIAM J Comput 28(5):1848-1874, 1999;Gawlick et al. in Theory of computing and systems (ISTCS), pp 171-183, 1992;Israeli and Pinhasov in distributed algorithms, pp 95-109, 1992;Haldar and Vit & aacute;nyi in J acm 49(1):101-126, 2002) do not scale well in the number of processes as getting a new timestamp takes at least Omega(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (n)$$\end{document} steps. Moreover, a lower bound by Israeli and Li (proceedings of the 28th annual IEEE symposium on foundations of computer science (FOCS), pp 371-382, 1987) implies that timestamps need to be represented by Omega(m)\documentclass[12pt]{minim
The carbon and water footprint of large-scale computing systems poses serious environmental sustainability risks. In this study, we discover that, unfortunately, carbon and water sustainability are at odds with each o...
详细信息
ISBN:
(纸本)9798400714436
The carbon and water footprint of large-scale computing systems poses serious environmental sustainability risks. In this study, we discover that, unfortunately, carbon and water sustainability are at odds with each other - and, optimizing one alone hurts the other. Toward that goal, we introduce, WaterWise, a novel job scheduler for parallel workloads that intelligently co-optimizes carbon and water footprint to improve the sustainability of geographically distributed data centers.
In distributedcomputing, questions of computability are exquisitely sensitive to minute details of the model assumptions, and there is no universally agreed upon model of network computing. Here, we study which funct...
详细信息
Deterministic parallelism is a key building block for distributed and fault-tolerant systems that offers substantial performance benefits while guaranteeing determinism. By studying existing deterministically parallel...
详细信息
ISBN:
(纸本)9798400714436
Deterministic parallelism is a key building block for distributed and fault-tolerant systems that offers substantial performance benefits while guaranteeing determinism. By studying existing deterministically parallel systems (DPS), we identify certain design pitfalls, such as batched execution and inefficient runtime synchronization, that preclude them from meeting the demands of mu s-scale and high-throughput distributed systems deployed in modern datacenters. We present DORADD, a deterministically parallel runtime with low latency and high throughput, designed for modern datacenter services. DORADD introduces a hybrid scheduling scheme that effectively decouples request dispatching from execution. It employs a single dispatcher to deterministically construct a dynamic dependency graph of incoming requests and worker pools that can independently execute requests in a work-conserving and synchronization-free manner. Furthermore, DORADD overcomes the single-dispatcher throughput bottleneck based on core pipelining. We use DORADD to build an in-memory database and compare it with Caracal, the current state-of-the-art deterministic database, via the YCSB and TPC-C benchmarks. Our evaluation shows up to 2.5x better throughput and more than 150x and 300x better tail latency in non-contended and contended cases, respectively. We also compare DO-RADD with Caladan, the state-of-the-art non-deterministic remote procedure call (RPC) scheduler, and demonstrate that determinism in DORADD does not incur any performance overhead.
Online GNN inference has been widely explored by applications such as online recommendation and financial fraud detection systems, where even minor delays can result in significant financial impact. Real-time dynamic ...
详细信息
ISBN:
(纸本)9798400714436
Online GNN inference has been widely explored by applications such as online recommendation and financial fraud detection systems, where even minor delays can result in significant financial impact. Real-time dynamic graph sampling enables online GNN inference to reflect the latest graph updates in real-world graphs. However, online GNN inference typically demands millisecond-level latency Service Level Objectives (SLOs) as its performance guarantees, which poses great challenges for existing dynamic graph sampling approaches based on graph databases. The issues mainly arise from two aspects: long tail latency due to imbalanced data-dependent sampling and large communication overhead incurred by distributed sampling. To address these issues, we propose Helios, an efficient distributed dynamic graph sampling service to meet the stringent latency SLOs. The key ideas of Helios are 1) pre-sampling the dynamic graph in an event-driven approach, and 2) maintaining a query-aware sample cache to build the complete K-hop sampling results locally for inference requests. Experiments on multiple datasets show that Helios achieves up to 67x higher serving throughput and up to 32x lower P99 query latency compared to baselines.
暂无评论