In local certification, vertices of a $n$-vertex graph perform a local verification to check if a given property is satisfied by the graph. This verification is performed thanks to certificates, which are pieces of information that are given to the vertices. In this work, we focus on the local certification of $P_5$-freeness, and we prove a $O(n^{3/2})$ upper bound on the size of the certificates, which is (to our knowledge) the first subquadratic upper bound for this property.
A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected with locks. It was already shown that simple stochastic analysis can predict the throughput of coarse-grained lock-based algorithms using CLH lock. In this short paper, we extend this analysis to algorithms based on the popular MCS lock.
This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for randomized obstruction-free algorithms. The approach extends to lower bounds for randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case contention incurred by a processor in an execution.
This paper proposes a simple topological characterization of a large class of fair adversarial models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. Fair adversaries include, but are not restricted to, the models of wait-freedom, t-resilience, and $k$-concurrency. Our results generalize and improve all previously derived topological characterizations of the ability of a model to solve distributed tasks.
We describe a Common Lisp package suitable for the high-level design, specification, simulation, and instrumentation of real-time distributed algorithms and hardware on which to run them. We discuss various design decisions around the package structure, and we explore their consequences with small examples.
Quentin Betti, Raphaël Khoury, Sylvain Hallé
et al.
The Physical Internet and hyperconnected logistics concepts promise an open, more efficient and environmentally friendly supply chain for goods. Blockchain and Internet of Things technologies are increasingly regarded as main enablers of improvements in this domain. We describe how blockchain and smart contracts present the potential of being applied to hyperconnected logistics by showing a concrete example of its implementation.
Serverless computing is an emerging Cloud service model. It is currently gaining momentum as the next step in the evolution of hosted computing from capacitated machine virtualisation and microservices towards utility computing. The term "serverless" has become a synonym for the entirely resource-transparent deployment model of cloud-based event-driven distributed applications. This work investigates how adaptive event dispatching can improve serverless platform resource efficiency and contributes a novel approach that allows for better scaling and fitting of the platform's resource consumption to actual demand.
Murat Demirbas, Aleksey Charapko, Ailidani Ailijiang
The last decade has witnessed rapid proliferation of cloud computing. While even the smallest distributed programs (with 3-5 actions) produce many unanticipated error cases due to concurrency involved, it seems short of a miracle these web-services are able to operate at those vast scales. In this paper, we explore the factors that contribute most to the high-availability of cloud computing services and examine where self-stabilization could fit in that picture.
We present elements of a typing theory for flow networks, where "types", "typings", and "type inference" are formulated in terms of familiar notions from polyhedral analysis and convex optimization. Based on this typing theory, we develop an alternative approach to the design and analysis of network algorithms, which we illustrate by applying it to the max-flow problem in multiple-source, multiple-sink, capacited directed planar graphs.
This paper made a short review of Cloud Computing and Big Data, and discussed the portability of general data mining algorithms to Cloud Computing platform. It revealed the Cloud Computing platform based on Map-Reduce cannot solve all the Big Data and data mining problems. Transplanting the general data mining algorithms to the real-time Cloud Computing platform will be one of the research focuses in Cloud Computing and Big Data.
The article is devoted to the verification of the BSF parallel computing model. The BSF-model is an evolution of the "master-slave" model and SPMD-model. The BSF-model is oriented to iterative algorithms that are implemented in cluster computing systems. The article briefly describes the basics of the BSF-model and its cost metrics. The structure of the BSF program is shown in the form of a UML activity diagram. The simulator of BSF-programs, implemented in C++ language using the MPI-library, is described. The results of computational experiments confirming the adequacy of the cost metrics of the BSF-model are presented.
This paper focuses on the problem of consistency in distributed data stores.We define strong consistency model which provides a simple semantics for application programmers, but impossible to achieve with availability and partition-tolerance. We also define weaker consistency models including causal and eventual consistency. We review COPS and GentleRain as two causally consistent data stores as well as Dynamo as an eventually consistent data store. We provide insights about scenarios where each of these methods is suitable, and some future research directions.
This report presents an adaptive work-efficient approach for implementing the Connected Components algorithm on GPUs. The results show a considerable increase in performance (up to 6.8$\times$) over current state-of-the-art solutions.