Interest in multirobot systems is rising rapidly both in academia and in industry. The use of multiple robots working in a coordinated way, rather than a single robot, has several advantages in a diverse range of applications. However, few studies have focused on operations in which robots can behave maliciously and alter the outcome of the collective mission. In this article, we present a set of Byzantine Follow The Leader (BFTL) problems, in which a subset of robots in the system shows unintended or inconsistent behavior (i.e., Byzantine robots). In the BFTL problems,leadersdiscover routes from their starting positions to specific destinations and guide thefollowers, whileByzantinerobots try to hinder the leaders and mislead the followers. In this research, blockchain technology is used as a communication tool within multirobot systems, forleadersto broadcast directions to the whole group. We propose algorithms to tackle the BFTL problems, prove their correctness, and validate them in simulated experiments of realistic scenarios. Results show that the proposed algorithms mitigate the impact of Byzantine robots in multirobot systems conducting a BFTL mission. Our analysis provides minimum and maximum boundary calculations for important metrics including number of robots reaching their destination, number of steps taken, and weight requirements of the chain used during the mission. Our results provide a path toward the deployment of byzantine-resistant real-world multirobot systems.

Peer to peer (P2P) systems have moved from application specific architectures to a generic service oriented design philosophy. This raised interesting problems in connection with providing useful P2P middleware services capable of dealing with resource assignment and management in a large-scale, heterogeneous and unreliable environment. The slicing problem consists of partitioning a P2P network into$k$groups (slices) of a given portion of the network nodes that share similar resource values. As the network is large and dynamic this partitioning is continuously updated without any node knowing the network size. In this paper, we propose the first algorithm to solve the slicing problem. We introduce the metric of slice disorder and show that the existing ordering algorithm cannot nullify this disorder. We propose a new algorithm that speeds up the existing ordering algorithm but that suffers from the same inaccuracy. Then, we propose another algorithm based on ranking that is provably convergent under reasonable assumptions. In particular, we notice experimentally that ordering algorithms suffer from resource-correlated churn while the ranking algorithm can cope with it. These algorithms are proved viable theoretically and experimentally.

Fault-tolerant broadcast is a fundamental service in distributed systems, by which processes can communicate with each other consistently and reliably. It has two main forms: Reliable Broadcast (RB) and Uniform Reliable Broadcast (URB). This service has been extensively investigated in non-anonymous distributed systems where processes have unique identifers, usually assume the communication channels are reliable, which is not always the case in real systems. In this paper, the fault-tolerant broadcast service is studied in an anonymous asynchronous message passing distributed system model with fair lossy communication channels. Firstly, two simple and non-quiescent algorithms implementing RB and URB are given. Secondly, two new classes of failure detectors A_Theta and AP* are proposed. Finally, with the information provided by A_Theta and AP*, quiescent algorithms for both RB and URB are given.

This paper is on homonymous distributed systems where processes are prone to crash failures and have no initial knowledge of the system membership (``homonymous'' means that several processes may have the same identifier). New classes of failure detectors suited to these systems are first defined. Among them, the classes $\HO$ and $\HS$ are introduced that are the homonymous counterparts of the classes $\Omega$ and $\Sigma$, respectively. (Recall that the pair $\langle \Omega, \Sigma\rangle$ defines the weakest failure detector to solve consensus.) Then, the paper shows how $\HO$ and $\HS$ can be implemented in homonymous systems without membership knowledge (under different synchrony requirements). Finally, two algorithms are presented that use these failure detectors to solve consensus in homonymous asynchronous systems where there is no initial knowledge of the membership. One algorithm solves consensus with $\langle \HO, \HS\rangle$, while the other uses only $\HO$, but needs a majority of correct processes. Observe that the systems with unique identifiers and anonymous systems are extreme cases of homonymous systems from which follows that all these results also apply to these systems. Interestingly, the new failure detector class $\HO$ can be implemented with partial synchrony, while the analogous class $\AO$ defined for anonymous systems can not be implemented (even in synchronous systems). Hence, the paper provides us with the first proof showing that consensus can be solved in anonymous systems with only partial synchrony (and a majority of correct processes).

The paper proposes a simple protocol that ensures sequential consistency. The protocol assumes that the shared memory abstraction is supported by the local memories of nodes that can communicate only by exchanging messages through reliable channels. Unlike other sequential consistency protocols, the one proposed here does not rely on a strong synchronization mechanism, such as an atomic broadcast primitive or a central node managing a copy of every shared object. From a methodological point of view, the protocol is built incrementally starting from the very definition of sequential consistency. It has the noteworthy property that a process that issues a write operation never has to wait for other processes. Depending on the current local state, most read operations issued also have the same property.

Unreliable failure detectors are mechanisms providing information about process failures that allow solving several problems in asynchronous systems, e.g., Consensus. A particular class of failure detectors, Omega, provides an eventual leader election functionality. This paper addresses the implementation of Omega in the crash-recovery failure model. Recently we have proposed an algorithm assuming that eventually the correct process with the smallest identifier and minimum incarnation number can communicate timely with the rest of processes. Here we propose two Omega algorithms which assume only that processes are reachable from some correct process, independently of its identifier and incarnation number. The first one requires the membership to be known a priori, while the second one relaxes this assumption too

This paper considers the problem of electing an eventual leader in an asynchronous shared memory system. While this problem has received a lot of attention in message- passing systems, very few solutions have been proposed for shared memory systems. As an eventual leader cannot be elected in a pure asynchronous system prone to process crashes, the paper first proposes to enrich the asynchronous system model with an additional assumption. That assumption, denoted AWB, requires that after some time (1) there is a process whose write accesses to some shared variables are timely, and (2) the timers of the other processes are asymptotically well-behaved. The asymptotically well-behaved timer notion is a new notion that generalizes and weakens the traditional notion of timers whose durations are required to monotonically increase when the values they are set to increase. Then, the paper presents two A WB-based algorithms that elect an eventual leader. Both algorithms are independent of the value of t (the maximal number of processes that may crash). The first algorithm enjoys the following noteworthy properties: after some time only the elected leader has to write the shared memory, and all but one shared variables have a bounded domain, be the execution finite or infinite. This algorithm is consequently optimal with respect to the number of processes that have to write the shared memory. The second algorithm enjoys the following property: all the shared variables have a bounded domain. This is obtained at the following additional price: all the processes are required to forever write the shared memory. A theorem is proved which states that this price has to be paid by any algorithm that elects an eventual leader in a bounded shared memory model. This second algorithm is consequently optimal with respect to the number of processes that have to write in such a constrained memory model. In a very interesting way, these algorithms show an inherent tradeoff relating the number of processes that have to write the shared memory and the bounded/unbounded attribute of that memory.

Peer to peer (P2P) systems are moving from application specific architectures to a generic service oriented design philosophy. This raises interesting problems in connection with providing useful P2P middleware services capable of dealing with resource assignment and management in a large-scale, heterogeneous and unreliable environment. The slicing service, has been proposed to allow for an automatic partitioning of P2P networks into groups (slices) that represent a controllable amount of some resource and that are also relatively homogeneous with respect to that resource. In this paper we propose two gossip-based algorithms to solve the distributed slicing problem. The first algorithm speeds up an existing algorithm sorting a set of uniform random numbers. The second algorithm statistically approximates the rank of nodes in the ordering. The scalability, efficiency and resilience to dynamics of both algorithms rely on their gossip-based models. These algorithms are proved viable theoretically and experimentally.

While electing an eventual common leader, despite process crashes, in a shared memory system where the processes communicate only by reading and writing shared registers is possible when the processes progress synchronously, this problem becomes impossible to solve as soon as the processes can progress in a fully asynchronous way. So, an important problem consists in finding additional behavioral assumptions that are, at the same time, "as weak as possible" (in order they are practically always satisfied), and "strong enough" in order to allow implementing an eventual leader service despite the net effect of asynchrony and failures. This paper focuses on this dilemma. More explicitly, it investigates a timing assumption that allows implementing an eventual leader in presence of partial asynchrony and process crashes. The proposed timing assumptions are particularly weak. They are the following: after some time (i) there is a process that behaves synchronously, and (ii) (t - f) other processes have timers that work correctly (t is the maximal number of processes that may crash, and f the actual number of process crashes; a timer works incorrectly when it expires too early with respect to the value it has been set). Then, the paper proposes a t-resilient protocol that elects an eventual common leader in any shared memory system that satisfies the previous assumption. Interestingly, this protocol is based on simple design principles.

This paper considers the eventual leader election problem in asynchronous message-passing systems where an arbitrary number t of processes can crash (t

In this paper we explore the minimal system requirements to implement unreliable failure detectors. We first consider systems formed by lossy asynchronous and eventually timely links. On these systems we define two properties, the weak property and the strong property, depending on whether all correct processes can be reached with links that are not lossy asynchronous from one or from all correct processes, respectively. We present necessary conditions based on these properties. We show that there is no algorithm that implements diamS, Omega, nor S (resp. diamP nor P) if we allow one single failure in a system that, when all processes are correct, does not satisfy the weak (resp. strong) property. Then, we propose an algorithm that implements diamP if the strong property is satisfied, and diamS (and Omega with an additional assumption) if only the weak property is satisfied. For systems formed by synchronous and lossy asynchronous links only, we propose another algorithm that implements detector class P4if the strong property is satisfied, and implements a new detector class S1(and Omega with an additional assumption) if only the weak property is satisfied

No abstract available.

A concurrent object is an object that can be concurrently accessed by several processes. Sequential consistency is a consistency criterion for such objects. Informally, it states that a multiprocess program executes correctly if its results could have been produced by executing that program on a single processor system. (Sequential consistency is weaker than atomic consistency -the usual consistency criterion- as it does not refer to real-time.) The paper proposes a simple protocol that ensures sequential consistency when the shared memory abstraction is supported by the local memories of nodes that can communicate only by exchanging messages through reliable channels. Differently from other sequential consistency protocols, the proposed protocol does not rely on a strong synchronization mechanism such as an atomic broadcast primitive or a central node managing a copy of every shared object. From a methodological point of view, the protocol is built incrementally starting from the very definition of sequential consistency. It lies the noteworthy property of providing fast writes operations (i.e., a process has never to wait when it writes a new value in a shared object). According to the current local state, some read operations can also be fast. An experimental evaluation of the protocol is also presented. The proposed protocol could be used to manage Web page caching.

We present an automatic implementation system of security protocols based in formal description techniques. A sufficiently complete and concise formal specification that has allowed us to define the state machine that corresponds to a security protocol has been designed to achieve our goals. This formal specification makes it possible to incorporate in a flexible way the security mechanisms and functions (random numbers generation, timestamps, symmetric-key encryption, public-key cryptography, etc). Our solution implies the incorporation of an additional security layer LEI (Logical Element of Implementation) in the TCP/IP architecture. This additional layer be able both to interpret and to implement any security protocol from its formal specification. Our system provides an applications programming interface (API) for the development of distributed applications in the Internet like the e-commerce, bank transfers, network management or distribution information services that makes transparent to them the problem of security in the communications.

A large amount of work has been invested in devising algorithms to implement distributed shared memory (DSM) systems under different consistency models. However, to our knowledge, the possibility of interconnecting DSM systems with simple protocols and the consistency of the resulting system has never been studied. With this paper, we start a series of works on the properties of the interconnection of DSM systems, which tries to fill this void.