Decentralized collaborative mean estimation (colME) is a fundamental task in heterogeneous networks. Its graph-based variants B-colME and C-colME achieve high scalability of the problem. This paper evaluates the consensus-based C-colME framework, which relies on doubly stochastic averaging matrices to ensure convergence to the oracle solution. We propose CL-colME, a novel variant utilizing Laplacian-based consensus to avoid the computationally expensive normalization processes. Simulation results show that the proposed CL-colME maintains the convergence behavior and accuracy of C-colME while improving computational efficiency.
Aaron Buchwald, Stephen Buttolph, Andrew Lewis-Pye
et al.
Snowman is the consensus protocol run by blockchains on Avalanche. Recent work established a rigorous proof of probabilistic consistency for Snowman in the \emph{synchronous} setting, under the simplifying assumption that correct processes execute sampling rounds in `lockstep'. In this paper, we describe a modification of the protocol that ensures consistency in the \emph{partially synchronous} setting, and when correct processes carry out successive sampling rounds at their own speed, with the time between sampling rounds determined by local message delays.
The consensus number of a w-bit register supporting logical left shift and right shift operations is exactly w, giving an example of a class of types, widely implemented in practice, that populates all levels of the consensus hierarchy. This result generalizes to w-wide shift registers over larger alphabets. In contrast, a register providing arithmetic right shift, which replicates the most significant bit instead of replacing it with zero, is shown to solve consensus for any fixed number of processes as long as its width is at least two.
Andrey Prokopenko, Daniel Arndt, Damien Lebrun-Grandié
et al.
This paper provides an overview of the 2.0 release of the ArborX library, a performance portable geometric search library based on Kokkos. We describe the major changes in ArborX 2.0 including a new interface for the library to support a wider range of user problems, new search data structures (brute force, distributed), support for user functions to be executed on the results (callbacks), and an expanded set of the supported algorithms (ray tracing, clustering).
Serverless computing has gained popularity due to its cost efficiency, ease of deployment, and enhanced scalability. However, in serverless environments, servers are initiated only after receiving a request, leading to increased response times. This delay is commonly known as the cold start problem. In this study, we explore the in-place scaling feature released in Kubernetes v1.27 and examine its impact on serverless computing. Our experimental results reveal improvements in request latency, with reductions ranging from 1.16 to 18.15 times across various workloads when compared to traditional cold policy.
We consider the problem of determining the top-$k$ largest measurements from a dataset distributed among a network of $n$ agents with noisy communication links. We show that this scenario can be cast as a distributed convex optimization problem called sample quantile inference, which we solve using a two-time-scale stochastic approximation algorithm. Herein, we prove the algorithm's convergence in the almost sure sense to an optimal solution. Moreover, our algorithm handles noise and empirically converges to the correct answer within a small number of iterations.
CASPaxos is a wait-free, linearizable, multi-writer multi-reader register in unreliable, asynchronous networks supporting arbitrary update operations including compare-and-set (CAS). The register acts as a replicated state machine providing an interface for changing its value by applying an arbitrary user-provided function (a command). Unlike Multi-Paxos and Raft which replicate the log of commands, CASPaxos replicates state, thus avoiding associated complexity, reducing write amplification, increasing concurrency of disk operations and hardware utilization. The paper describes CASPaxos, proves its safety properties and evaluates the characteristics of a CASPaxos-based prototype of key-value storage.
The paper is devoted to an analytical study of the "master-worker" framework scalability on multiprocessors with distributed memory. A new model of parallel computations called BSF is proposed. The BSF model is based on BSP and SPMD models. The scope of BSF model is the compute-intensive applications. The architecture of BSF-computer is defined. The structure of BSF-program is described. The Using this metric, the upper scalability bounds of BSF programs on distributed memory multiprocessors are evaluated. The formulas for estimating the parallel efficiency of BSF programs also proposed.
Elaheh Sadredini, Mohammad Hashem Haghbayan, Mahmood Fathy
et al.
This paper presents a novel approach for test generation and test scheduling for multi-clock domain SoCs. A concurrent hybrid BIST architecture is proposed for testing cores. Furthermore, a heuristic for selecting cores to be tested concurrently and order of applying test patterns is proposed. Experimental results show that the proposed heuristics give us an optimized method for multi clock domain SoC testing in comparison with the previous works.
In this note, we observe a safety violation in Zyzzyva and a liveness violation in FaB. To demonstrate these issues, we require relatively simple scenarios, involving only four replicas, and one or two view changes. In all of them, the problem is manifested already in the first log slot.
In recent years the two trends of edge computing and artificial intelligence became both crucial for information processing infrastructures. While the centralized analysis of massive amounts of data seems to be at odds with computation on the outer edge of distributed systems, we explore the properties of eventually consistent systems and statistics to identify sound formalisms for probabilistic inference on the edge. In particular we treat time itself as a random variable that we incorporate into statistical models through probabilistic programming.
This paper analyzes the problem of assigning weights to edges incrementally in a dynamic complete bipartite graph consisting of producer and consumer nodes. The objective is to minimize the overall cost while satisfying certain constraints. The cost and constraints are functions of attributes of the edges, nodes and online service requests. Novelty of this work is that it models real-time distributed resource allocation using an approach to solve this theoretical problem. This paper studies variants of this assignment problem where the edges, producers and consumers can disappear and reappear or their attributes can change over time. Primal-Dual algorithms are used for solving these problems and their competitive ratios are evaluated.
The main purpose of this paper is to study the attenuation of the jump phenomena associated with the Sommerfeld Effect introduced by the nonlinearities of a magnetic rheological damper (MRD) in a non-ideal vibrational system, excited by a DC motor modeled as limited power source. Numerical simulations of the nonlinear vibrations of the system are carried out for different values of the MRD control parameter in order to show the amplitude reduction of the vibrations close to the system resonance introduced by the nonlinear damping effect of the MR system.
In this paper we introduce a novel gossiping primitive to support privacy preserving data analytics (PPDA). In contrast to existing computational PPDA primitives such as secure multiparty computation and data randomization based approaches, the proposed primitive `anonymous gossiping' is a communication primitive for privacy preserving personalized information aggregation complementing such traditional computational analytics. We realize this novel primitive by composing existing gossiping mechanisms for peer sampling & information aggregation and onion routing technique for establishing anonymous communication. This is more an `ideas' paper, rather than providing concrete and quantified results.