Search

Binary consensus is a problem in which a set of processors must agree on a single binary value. In asynchronous systems, where a subset of the processors may be malicious, this challenge gets more challenging. We study malicious and more serious problems in this work: transient faults. These are temporary violations of the system's operating assumptions that might cause the system's state to change unexpectedly, making recovery impossible without human intervention. We implement an existing protocol for randomized Byzantine-tolerant binary consensus algorithm that is loosely-self-stabilizing using the Go programming language and the ZeroMQ communication framework. This approach is optimal in terms of resilience and termination, requires only bounded memory, and ensures that the system will automatically converge to a legal state. This is the first time-free Byzantine-tolerant binary consensus algorithm to make such guarantees, to our knowledge. We describe the first known implementation of this algorithm in this work. With this implementation, we were able to: (a) validate the algorithm; (b) compare the algorithm to its non-stabilizing version and estimate the cost of self-stabilization in terms of processing time and message load; and (c) notice that different failures in the system (whether due to transient faults or malicious behavior) have no significant overhead on recovery and decision time.

This paper presents a binary randomized consensus algorithm for n-process asynchronous message-passing systems in which (1) up to t O(sqrt(n)) it is no longer possible to implement a randomized consensus algorithm ensuring a constant number of communication steps despite unfair channels.

This paper addresses consensus in an asynchronous model where the processes are partitioned into clusters. Inside each cluster, processes can communicate through a shared memory, which favors efficiency. Moreover, any pair of processes can also communicate through a message-passing communication system, which favors scalability. In such a "hybrid communication" context, the paper presents two simple binary consensus algorithms (one based on local coins, the other one based on a common coin). These algorithms are straightforward extensions of existing message-passing randomized round-based consensus algorithms. At each round, the processes of each cluster first agree on the same value (using an underlying shared memory consensus algorithm), and then use a message-passing algorithm to converge on the same decided value. The algorithms are such that, if all except one processes of a cluster crash, the surviving process acts as if all the processes of its cluster were alive (hence the motto "one for all and all for one"). As a consequence, the hybrid communication model allows us to obtain simple, efficient, and scalable fault-tolerant consensus algorithms. As an important side effect, according to the size of each cluster, consensus can be obtained even if a majority of processes crash.

International audience; We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in every I(n) time units, with the objective of minimizing the idle time I(n). While patrolling has been studied previously for static networks, we investigate the problem on dynamic networks with a fixed set of nodes, but dynamic edges. In particular, we consider 1-interval-connected ring networks and provide various patrolling algorithms for such networks, for k = 2 or k > 2 agents. We also show almost matching lower bounds that hold even for the best starting configurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs.

At the core of distributed computing there is the necessity to coordinate a group of entities in face of the uncertainty present in the environment. Classically, such uncertainty was mainly the one introduced by the loss or the delay of messages (asynchrony and failures).

We consider computations by a distributed team of autonomous mobile agents that move on an unoriented dynamic ring network. In particular, we consider 1-interval connected dynamic rings (i.e. at any time, at most one of the edges might be missing). The agents move according to a Look-Compute-Move life cycle, under a synchronous scheduler. The agents may be homogenous (thus identical and monochromatic) or they may be heterogenous (distinct agents have distinct colors from a set of \(c \ge 1\) colors). For monochromatic agents starting from any dispersed configuration we want the agents to form a compact segment, where agents occupy a continuous part of the ring and no two agents are on the same node – we call this the Compact Configuration Problem. In the case of multiple colors (\(c>1\)), agents of the same color are required to occupy continuous segments, such that agents having the same color are all grouped together, while agents of distinct colors are separated. These formation problems are different from the classical and well studied problem of Gathering all agents at a node, since unlike the gathering problem, we do not allow collisions (each node may host at most one agent of a color).

Mediated population protocols are an extension of population protocols in which communication links, as well as agents, have internal states. We study the leader election problem and some applications in constant-state mediated population protocols. Depending on the power of the adversarial scheduler, our algorithms are either stabilizing or allow the agents to explicitly reach a terminal state.

In this paper we investigate the computational power of Population Protocols (PP) under some unreliable and/or weaker interaction models. More precisely, we focus on two features related to the power of interactions: omission failures and one-way communications. An omission failure, a notion that this paper introduces for the first time in the context of PP, is the loss by one or both parties of the information transmitted in an interaction. The failure may or may not be detected by either party. On the other hand, in one-way models, communication happens only in one direction: only one of the two agents can change its state depending on both agents' states, and the other agent may or may not be aware of the interaction. These notions can be combined, obtaining one-way protocols with (possibly detectable) omission failures. A general question is what additional power is necessary and sufficient to completely overcome the weakness of one-way protocols and enable them to simulate two-way protocols, with and without omission failures. As a basic feature, a simulator needs to implement an atomic communication of states between two agents; this task is further complicated by the anonymity of the agents, their lack of knowledge of the system, and the limited amount of memory that they may have. We provide the first answers to these questions by presenting and analyzing several simulators, i.e., wrapper protocols converting any protocol for the standard two-way model into one running on a weaker one.

U završnom radu obrađivala se primjena binarnog konsenzusa po povjerenju na multi agentski sustav aMussels. Promatrao se utjecaj različitih parametara na brzinu postizanja konvergencije povjerenje te na samu vrijednost povjerenje. Radila se diskretizacija povjerenje te provjera postiže li se brže konvergencija povjerenja ukoliko je isto kvantizirano. zaključak je bio da se ne postiže, no kvantizacijom je moguće uštedjeti prijenos informacija pri komunikaciji. Također, proučavale su se mogućnosti detekcije uljeza u multi agentskom sustavu, gdje je uljez agent koji namjerno radi protiv zajedničkog cilja grupe. In the thesis we observe the application of binary consensus by trust on multiple agent system aMussels. We consider the effect of various parameters on the speed of achieving convergence of trust as well as its value. We did discretization of trust and verify whether the convergence of trust was faster if it is quantified. The conclusion was that the convergence was not faster, but using quantization it is possible to save the transmission of information during communication between agents or between agent and the surface. Also, we studied the possibility of detection of intruders in multiple agent systems, where an intruder means that they are deliberately working against the common goal.

This paper is motivated by the aspiration to identify the weakest computational models that allow for efficient, robust distributed computation. We focus on one of the most fundamental building-blocks in distributed computing, namely, Broadcast. In this problem, a unique source agent $s$ needs to disseminate a bit $b$ to the rest of the population. To account for unpredictability issues that may result from uncoordinated executions, we consider a self-stabilizing setting, in which a correct configuration must be reached eventually, despite processors starting the execution with arbitrary initial states (that do not violate the requirement for the existence of a unique source). Similarly to many works on broadcast, we consider a synchronous communication model on a complete anonymous network, in which in each round, each agent can extract information from two other agents, chosen uniformly at random. Our focus is on identifying the smallest message size that is required in order to achieve fast self-stabilizing broadcast. We first observe that with an extra bit added to the message-size and a small additive penalty to the running time, the self-stabilizing broadcast problem can be reduced to a self-stabilizing clock-synchronization problem, where agents aim to synchronize their clocks modulo some integer T. Our main technical contribution lies in solving the latter problem in poly-logarithmic time using only 3 bits per interaction. This allows for a self-stabilizing broadcast protocol that uses only 4 bits per interaction and converges in O log n time.

U ovom radu razmatra se problem uspostave povjerenja u multi-agentskim sustavima na temelju binarnog konsenzusa. Sustav od n agenata je na početku decentraliziran i svaki agent ima svoj vektor povjerenja prema ostalim agentima u sustavu. Tijekom simulacije agenti razmjenjuju informacije međusobnom komunikacijom i izravnim promatranjem svojih susjeda, te na temelju dobivenih informacija obnavljaju svoje vektore povjerenja. Kada se uspostavi konsenzus, odnosno kada vektori povjerenja svih agenata postanu jednaki, agent s najvećom vrijednosti povjerenja postaje vođa sustava. Primjenom binarnog protokola na algoritam za uspostavu povjerenja u sustavu osigurana je konvergencija povjerenja u konačnom vremenu. Binarni protokol je primijenjen i na sustav od 9 CASU jedinica gdje želimo da sve CASU jedinice u konačnom vremenu postignu zadanu referentnu temperaturu koja je unaprijed poznata samo jednoj od njih. Algoritam je implementiran u Matlab okruženju, te i u ASSISI simulatoru koji opisuje realni sustav. In this paper we consider the problem of trust development in multi-agent systems based on the binary consensus. At the beginning, the system consisting of n agents is decentralized. Every agent has its own trust vector containing trust values regarding every agent in the group. During the simulation agents exchange information by communication and local observations of their neighbours. Based on these exchanged information, they update their trust vectors. Once the consensus has been achieved and trust vectors of each agent have converged to the same value, the agent with the highest trust value becomes the leader of the system. By using the binary protocol, we guarantee the finite-time convergence of trust values. Moreover, binary protocol is applied to the system consisting of 9 CASU units. We want all CASU units to reach the given reference temperature in the finite time. Only one CASU unit knows what is the value of the reference temperature. Algorithm is implemented in Matlab environment and in the ASSISI simulator that describes the real system.

U okviru ovoga diplomskog rada analiziraju se svojstva upravljanja formacijom pokretnih objekata korištenjem Gaussove funkcije potencijala . Bitno svojstvo korištenog pristupa su elementarne funkcije potencijala ovisne o parametru $\sigma$ koji je različit za svaki agent. Posljedica tog svojstva je jednak oblik privlačnih i odbojnih sila između agenata i meta, te između samih agenata. Takvo svojstvo na kraju daje željenu formaciju kao singularnu točku neovisnu o parametrima. Za razliku od centraliziranog modela upravljanja u kojem su agenti identični, u decentraliziranom sustavu upravljanja agenti nisu identični, pa struktura potencijala formacije nije invarijantna s obzirom na zamjene konfiguracija pojedinih agenata. Nadalje je pokazano da se položaj neželjenih stabilnih ravnotežnih stanja može mijenjati oblikom elementarne funkcije potencijala, odnosno načinom na koji agenti i mete međusobno djeluju. Da bi se potrebne vrijednosti kontrolnog parametra tokom rada sustava ispravno odredile, uveden je adaptivni algoritam koji, ovisno o zaposjednutom ravnotežnom stanju, skokovito mijenja vrijednost kontrolnog parametra za pojedine agente. Simulacija, izvedene u simulatoru razvijenom u Matlab programskom okruženju u laboratoriju LARICS, pokazuje ispravnost predloženog pristupa upravljanja formacija pokretnih objekata. This Master thesis uses the Gaussian potential function to analyse control characteristics of a formation of mobile objects. The analysis uses elementary potential functions dependent on a control parameter that is different for each agent. The consequence is that the attractive and repulsive forces among agents and targets, as well as among agents themselves, have the same characteristics. This approach results in a desired formation expressed as a singular point independent of these parameters. As opposed to a centralized control model for which the agents are identical, in a decentralized control system, the agents are not identical resulting in a dependence of the formation's potential structure on the swapping of agents' configurations. It is further shown that the position of the undesired stable equilibrium states can be changed by the characteristics of the elementary potential functions, i.e. by a mutual interaction of the agents and targets. An adaptive algorithm is introduced in order to determine the required values of the control parameters during the operation of the system. It step-wise changes the control parameters depending on the acquired equilibrium state. The simulation, implemented as a GUI in Matlab in the LARICS lab, confirmed the correctness of the proposed control of a formation of mobile objects.

We work on an extension of the Population Protocol model of Angluin et al. that allows edges of the communication graph, G, to have states that belong to a constant size set. In this extension, the so called Mediated Population Protocol model (MPP), both uniformity and anonymity are preserved. We study here a simplified version of MPP in order to capture MPP's ability to stably compute graph properties. To understand properties of the communication graph is an important step in almost any distributed system. We prove that any graph property is not computable if we allow disconnected communication graphs. As a result, we focus on studying (at least) weakly connected communication graphs only and give several examples of computable properties in this case. To do so, we also prove that the class of computable properties is closed under complement, union and intersection operations. Node and edge parity, bounded out-degree by a constant, existence of a node with more incoming than outgoing neighbors, and existence of some directed path of length at least k = O(1) are some examples of properties whose computability is proven. Finally, we prove the existence of symmetry in two specific communication graphs and, by exploiting this, we prove that there exists no protocol, whose states eventually stabilize, to determine whether G contains some directed cycle of length 2.

In this work, we study the Population Protocol model of Angluin et al. from the perspective of protocol verification. In particular, we are interested in algorithmically solving the problem of determining whether a given population protocol conforms to its specifications. Since this is the first work on verification of population protocols, we redefine most notions of population protocols in order to make them suitable for algorithmic verification. Moreover, we formally define the general verification problem and some interesting special cases. All these problems are shown to be NP-hard. We next propose some first algorithmic solutions for a natural special case. Finally, we conduct experiments and algorithmic engineering in order to improve our verifiers' running times.

This work focuses on the computational power of the Mediated Population Protocol model on complete communication graphs and initially identical edges (SMPP). In particular, we investigate the class MPS of all predicates that are stably computable by the SMPP model. It is already known that MPS is in the symmetric subclass of NSPACE(n2). Here we prove that this inclusion holds with equality, thus, providing the following exact characterization for MPS: A predicate is in MPS iff it is symmetric and is in NSPACE(n2).