1,721,031 research outputs found

    Distributed Computing by Oblivious Mobile Robots

    No full text
    The study of what can be computed by a team of autonomous mobile robots, originally started in robotics and AI, has become increasingly popular in theoretical computer science (especially in distributed computing), where it is now an integral part of the investigations on computability by mobile entities. The robots are identical computational entities located and able to move in a spatial universe; they operate without explicit communication and are usually unable to remember the past; they are extremely simple, with limited resources, and individually quite weak. However, collectively the robots are capable of performing complex tasks, and form a system with desirable fault-tolerant and self-stabilizing properties. The research has been concerned with the computational aspects of such systems. In particular, the focus has been on the minimal capabilities that the robots should have in order to solve a problem. This book focuses on the recent algorithmic results in the field of distributed computing by oblivious mobile robots (unable to remember the past). After introducing the computational model with its nuances, we focus on basic coordination problems: pattern formation, gathering, scattering, leader election, as well as on dynamic tasks such as flocking. For each of these problems, we provide a snapshot of the state of the art, reviewing the existing algorithmic results. In doing so, we outline solution techniques, and we analyze the impact of the different assumptions on the robots' computability power

    Dynamic Monopolies in Tori

    No full text
    Let G be a simple connected graph where every node is colored either black or white. Consider now the following repetitive process on G: each node recolors itself, at each local time step, with the color held by the majority of its neighbors. Depending on the initial assignment of colors to the nodes and to the definition of majority, different dynamics can occur. We are interested to 'dynamos", i.e., initial assignments of colors which lead the system to a monochromatic configuration in a finite number of steps. In the context of distributed computing and communication networks, this repetitive process is particularly important in that it describes the impact that a set of initial faults can have in majority-based systems (where black nodes correspond to faulty elements and white to non-faulty ones). In this paper we study two particular forms of dynamos (irreversible and monotone) in tori, under different assumptions on the majority rule (simple and strong). These bounds are tight within an additive constant. The upper bounds are constructive: for each topology and each majority rule, we exhibit a dynamo of the claimed size
    corecore