The proceedings contain 62 papers. The topics discussed include: determining recoverable consensus numbers;history-independent concurrent objects;MemSnap: a fast adaptive snapshot algorithm for RMWable shared-memory;b...
ISBN:
(纸本)9798400706684
The proceedings contain 62 papers. The topics discussed include: determining recoverable consensus numbers;history-independent concurrent objects;MemSnap: a fast adaptive snapshot algorithm for RMWable shared-memory;brief announcement: randomized consensus: common coins are not the holy grail!;game dynamics and equilibrium computation in the population protocol model;brief announcement: optimally encoding information in chemical reaction networks;polylogarithmic time algorithms for shortest path forests in programmable matter;majority consensus thresholds in competitive Lotka-Volterra populations;brief announcement: self-stabilizing mis computation in the beeping model;brief announcement: on the limits of information spread by memory-less agents;and system optimizations for enabling training of extreme long sequence transformer models.
The proceedings contain 44 papers. The topics discussed include: a near time-optimal population protocol for self-stabilizing leader election on rings with a poly-logarithmic number of states;fast convergence of k-opi...
ISBN:
(纸本)9798400701214
The proceedings contain 44 papers. The topics discussed include: a near time-optimal population protocol for self-stabilizing leader election on rings with a poly-logarithmic number of states;fast convergence of k-opinion undecided state dynamics in the population protocol model;brief announcement: efficient collaborative tree exploration with breadth-first depth-next;brief announcement: population protocols decide double-exponential thresholds;the complexity of distributed approximation of packing and covering integer linear programs;efficient distributed decomposition and routing algorithms in minor-free networks and their applications;brief announcement: distributed construction of near-optimal compact routing schemes for planar graphs;brief announcement: the Laplacian paradigm in deterministic congested clique;asynchronous wait-free runtime verification and enforcement of linearizability;and asynchronous wait-free runtime verification and enforcement of linearizability.
The proceedings contain 59 papers. The topics discussed include: node and edge averaged complexities of local graph problems;overcoming congestion in distributed coloring;the landscape of distributed complexities on t...
ISBN:
(纸本)9781450392624
The proceedings contain 59 papers. The topics discussed include: node and edge averaged complexities of local graph problems;overcoming congestion in distributed coloring;the landscape of distributed complexities on trees and beyond;brief announcement: on polynomial-time local decision;brief announcement: distributed MST computation in the sleeping model: awake-optimal algorithms and lower bounds;brief announcement: broadcasting time in dynamic rooted trees is linear;a recursive early-stopping phase king protocol;optimal synchronous approximate agreement with asynchronous fallback;perfectly-secure synchronous MPC with asynchronous fallback guarantees;brief announcement: asynchronous randomness and consensus without trusted setup;and brief announcement: deterministic consensus and checkpointing with crashes: time and communication efficiency.
The proceedings contain 60 papers. The topics discussed include: separating bounded and unbounded asynchrony for autonomous robots: point convergence with limited visibility;on implementing stabilizing leader election...
ISBN:
(纸本)9781450385480
The proceedings contain 60 papers. The topics discussed include: separating bounded and unbounded asynchrony for autonomous robots: point convergence with limited visibility;on implementing stabilizing leader election with weak assumptions on network dynamics;time-optimal self-stabilizing leader election in population protocols;lower bounds on the state complexity of population protocols;comparison dynamics in population protocols;diversity, fairness and sustainability in population protocols;brief announcement: a time and space optimal stable population protocol solving exact majority;a thin self-stabilizing asynchronous unison algorithm with applications to fault tolerant biological networks;and decision power of weak asynchronous models of distributedcomputing.
The proceedings contain 66 papers. The topics discussed include: an adaptive approach to recoverable mutual exclusion;upper and lower bounds on the space complexity of detectable objects;long-lived snapshots with poly...
ISBN:
(纸本)9781450375825
The proceedings contain 66 papers. The topics discussed include: an adaptive approach to recoverable mutual exclusion;upper and lower bounds on the space complexity of detectable objects;long-lived snapshots with polylogarithmic amortized step complexity;from Bezout's identity to space-optimal election in anonymous memory systems;brief announcement: store-collect in the presence of continuous churn with application to snapshots and lattice agreement;brief announcement: why extension-based proofs fail;exponentially faster shortest paths in the congested clique;lower bounds for distributed sketching of maximal matchings and maximal independent sets;seeing far vs. seeing wide: volume complexity of local graph problems;computing shortest paths and diameter in the hybrid network model;revisiting asynchronous fault tolerant computation with optimal resilience;and asynchronous byzantine approximate consensus in directed networks.
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 proceedings contain 70 papers. The topics discussed include: composable computation in discrete chemical reaction networks;how to spread a rumor: call your neighbors or take a walk?;efficient size estimation and i...
ISBN:
(纸本)9781450362177
The proceedings contain 70 papers. The topics discussed include: composable computation in discrete chemical reaction networks;how to spread a rumor: call your neighbors or take a walk?;efficient size estimation and impossibility of termination in uniform dense population protocols;on counting the population size;self-stabilizing leader election;brief announcement: logarithmic expected-time leader election in population protocol model;brief announcement: on site fidelity and the price of ignorance in swarm robotic central place foraging algorithms;improved distributed expander decomposition and nearly optimal triangle enumeration;fast approximate shortest paths in the congested clique;brief announcement: optimal distributed covering algorithms;and with great speed come small buffers: space-bandwidth tradeoffs for routing.
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.
暂无评论