As part of the Vitamin-V European project, we have built a prototype of a RISC-V cluster managed by OpenStack, with the goal of realizing a functional RISC-V cloud ecosystem. In this poster we explain the hardware and software challenges encountered while porting some elements of OpenStack. We also discuss the current performance gaps that challenge a performance-ready cloud environment over such new ISA, an essential element to fulfill in order to achieve european technological sovereignty.
A previous case study measured performance vs source-code complexity across multiple languages. The case study identified Chapel and HPX provide similar performance and code complexity. This paper is the result of initial steps toward closing the source-code complexity gap between Chapel and HPX by using a source-to-source compiler. The investigation assesses the single-machine performance of both Chapel and Chplx applications across Arm and x86.
A reliable communication primitive guarantees the delivery, integrity, and authorship of messages exchanged between correct processes of a distributed system. We investigate the necessary and sufficient conditions for reliable communication in dynamic networks, where the network topology evolves over time despite the presence of a limited number of Byzantine faulty processes that may behave arbitrarily (i.e., in the globally bounded Byzantine failure model). We identify classes of dynamic networks where such conditions are satisfied, and extend our analysis to message losses, local computation with unbounded finite delay, and authenticated messages.
In this paper, we look at and expand the problems of dispersion and Byzantine dispersion of mobile robots on a graph, introduced by Augustine and Moses~Jr.~[ICDCN~2018] and by Molla, Mondal, and Moses~Jr.~[ALGOSENSORS~2020], respectively, to graphs where nodes have variable capacities. We use the idea of a single shepherd, a more powerful robot that will never act in a Byzantine manner, to achieve fast Byzantine dispersion, even when other robots may be strong Byzantine in nature. We also show the benefit of a shepherd for dispersion on capacitated graphs when no Byzantine robots are present.
Azita Nouri, Philip E. Davis, Pradeep Subedi
et al.
In this survey, we discuss the challenges of executing scientific workflows as well as existing Machine Learning (ML) techniques to alleviate those challenges. We provide the context and motivation for applying ML to each step of the execution of these workflows. Furthermore, we provide recommendations on how to extend ML techniques to unresolved challenges in the execution of scientific workflows. Moreover, we discuss the possibility of using ML techniques for in-situ operations. We explore the challenges of in-situ workflows and provide suggestions for improving the performance of their execution using ML techniques.
While checkpointing is typically combined with a restart of the whole application, localized recovery permits all but the affected processes to continue. In task-based cluster programming, for instance, the application can then be finished on the intact nodes, and the lost tasks be reassigned. This extended abstract suggests to adapt a checkpointing and localized recovery technique that has originally been developed for independent tasks to nested fork-join programs. We consider a Cilk-like work stealing scheme with work-first policy in a distributed memory setting, and describe the required algorithmic changes. The original technique has checkpointing overheads below 1% and neglectable costs for recovery, we expect the new algorithm to achieve a similar performance.
Magnus M. Halldorsson, Fabian Kuhn, Yannic Maus
et al.
We give an improved randomized CONGEST algorithm for distance-$2$ coloring that uses $Δ^2+1$ colors and runs in $O(\log n)$ rounds, improving the recent $O(\log Δ\cdot \log n)$-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to $O(\log Δ) + 2^{O(\sqrt{\log\log n})}$.
Indexing sequence data is important in the context of Precision Medicine, where large amounts of ``omics'' data have to be daily collected and analyzed in order to categorize patients and identify the most effective therapies. Here we propose an algorithm for the computation of Burrows Wheeler transform relying on Big Data technologies, i.e., Apache Spark and Hadoop. Our approach is the first that distributes the index computation and not only the input dataset, allowing to fully benefit of the available cloud resources.
We compare different methods for sampling from discrete probability distributions and introduce a new algorithm which is especially efficient on massively parallel processors, such as GPUs. The scheme preserves the distribution properties of the input sequence, exposes constant time complexity on the average, and significantly lowers the average number of operations for certain distributions when sampling is performed in a parallel algorithm that requires synchronization afterwards. Avoiding load balancing issues of naïve approaches, a very efficient massively parallel construction algorithm for the required auxiliary data structure is complemented.
We introduce a structure for the directed acyclic graph (DAG) and a mechanism design based on that structure so that peers can reach consensus at large scale based on proof of work (PoW). We also design a mempool transaction assignment method based on the DAG structure to render negligible the probability that a transaction being processed by more than one miners. The result is a significant scale-up of the capacity without sacrificing security and decentralization.
Piotr Dziurzanski, Shuai Zhao, Leandro Soares Indrusiak
This paper describes the possibility of applying a generic, cloud-based Optimisation as a Service facility to food cooking planning and scheduling in a commercial kitchen. We propose a chromosome encoding and customisation of the classic MOEA/D multi-objective genetic algorithm. The applicability of the proposed approach is evaluated experimentally for two scenarios different with respect to the number of cooking appliances and the amount of the ordered food. The proposed system managed to determine the trade-offs between cooking time, energy dissipation and food quality.
We study a proof methodology for verifying the safety of data invariants of highly-available distributed applications that replicate state. The proof is (1) modular: one can reason about each individual operation separately, and (2) sequential: one can reason about a distributed application as if it were sequential. We automate the methodology and illustrate the use of the tool with a representative example.
As mobile devices have become the preferred tool for communication, work, and entertainment, traffic at the edge of the network is growing more rapidly than ever. To improve user experience, commodity servers are deployed in the edge to form a decentralized network of mini datacenters each serving a localized region. A challenge is how to place these servers geographically to maximize the offloading benefit and be close to the users they respectively serve. We introduce a formulation for this problem to serve applications that involve pairwise communication between mobile devices at different geolocations. We explore several heuristic solutions and compare them in an evaluation using both real-world and synthetic datasets.
Ensuring reliable communication despite possibly malicious participants is a primary objective in any distributed system or network. In this paper, we investigate the possibility of reliable broadcast in a dynamic network whose topology may evolve while the broadcast is in progress. In particular, we adapt the Certified Propagation Algorithm (CPA) to make it work on dynamic networks and we present conditions (on the underlying dynamic graph) to enable safety and liveness properties of the reliable broadcast. We furthermore explore the complexity of assessing these conditions for various classes of dynamic networks.
Jerzy Mieścicki, Wiktor B. Daszczuk, Waldemar Grabski
et al.
The paper, based on authors' experience from several distributed systems integration projects, summarizes briefly practical designer's view on methodological requirements and overall system organization, including clues as to the organization of the application layer, use of operating system and preferred communication protocols.
In this paper, we explore remarkable similarities between multi-transactional behaviors of smart contracts in cryptocurrencies such as Ethereum and classical problems of shared-memory concurrency. We examine two real-world examples from the Ethereum blockchain and analyzing how they are vulnerable to bugs that are closely reminiscent to those that often occur in traditional concurrent programs. We then elaborate on the relation between observable contract behaviors and well-studied concurrency topics, such as atomicity, interference, synchronization, and resource ownership. The described contracts-as-concurrent-objects analogy provides deeper understanding of potential threats for smart contracts, indicate better engineering practices, and enable applications of existing state-of-the-art formal verification techniques.
Sandeep Chandran, Eldhose Peter, Preeti Ranjan Panda
et al.
In this report, we report some fundamental results and bounds on the number of messages and storage required to implement barriers using futuristic on-chip optical and RF networks. We prove that it is necessary to maintain a count to at least N (number of threads) in memory, broadcast the barrier id at least once, and if we elect a co-ordinator, we can reduce the number of messages by a factor of O(N ).