1,721,090 research outputs found
Gathering of oblivious robots on infinite grids with minimum traveled distance
No full textA largely studied version of the gathering problem asks to move a set of robots initially placed at different vertices of an anonymous graph toward a common vertex, and to let them remain at such a vertex. Asynchronous robots move based on the so-called Look-Compute-Move model. Each time a robot wakes-up, it perceives the current configuration in terms of occupied vertices (Look), it decides whether to move toward one of its neighbors (Compute), and then it performs the computed move (Move), eventually. So far, the main goal has been to detect the minimal assumptions that allow to accomplish the task, without taking care of any cost measure. In this paper, we are interested in optimal algorithms in terms of total number of moves. We consider infinite grids, and we fully characterize when optimal gathering is achievable by providing a distributed algorithm
Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings
No full textThe paper presents general results about the gathering problem on graphs. A team of robots placed at the vertices of a graph, have to meet at some vertex and remain there. Robots operate in LookâComputeâMove cycles; in one cycle, a robot perceives the current configuration in terms of robots disposal (Look), decides whether to move towards one of its neighbors (Compute), and in the positive case makes the computed move (Move). Cycles are performed asynchronously for each robot. So far, the goal has been to provide feasible resolution algorithms with respect to different assumptions about the capabilities of the robots as well as the topology of the underlying graph. In this paper, we are interested in studying the quality of the resolution algorithms in terms of the minimum number of asynchronous moves performed by the robots to accomplish the gathering task. We provide results for general graphs that suggest resolution techniques and provide feasibility properties. Then, we apply the obtained theory on specific topologies like trees and rings. The resulting algorithms for trees and rings are then compared with the existing ones, hence showing how the old solutions can be far apart from the optimum
The Game of Scintillae: From Cellular Automata to Computing and Cryptography Systems
No full textThe paper deals with a very simple game called Scintillae. Like in a domino game, Scintillae provides the player with limited basic pieces that can be placed over a chessboard-like area. After the placement, the game starts in a sort of runtime mode, and the player enjoys his creation.
The evolution of the system is based on few basic rules.
Despite its simplicity, Scintillae turns out to provide the player with a powerful mean able to achieve high computational power, storage capabilities and many other peculiarities based on the ability of the player to
suitably dispose the pieces.
We show some of the potentials of this simple game by providing basic configurations that can be used as “sub-programs” for composing bigger systems. Moreover, the interest in Scintillae also resides in its potentials for educational purposes, as many basic concepts related to
the computer science architecture can be approached with fun by means of this game
A structured methodology for designing distributed algorithms for mobile entities
No full textFollowing the wide investigation in distributed computing issues by mobile entities of the last two decades, we consider the need of a structured methodology to tackle the arisen problems. The aim is to simplify both the design of the resolution algorithms and the writing of the required correctness proofs. We would encourage the usage of a common framework in order to help both algorithm designers and reviewers in the intricate work of delivering and analyzing the proposed resolution strategies.
We demonstrate the effectiveness and usefulness of the new methodology by highlighting various peculiarities arising in different scenarios. In particular, we consider two different tasks for asynchronous entities moving in the Euclidean plane and in graphs, respectively. We show how two resolution strategies have been designed by following the accurate guide dictated by the methodology. Furthermore, we also show how the corresponding correctness proofs are obtained
Bamboo Garden Trimming Problem: Priority Schedulings
No full textThe paper deals with the Bamboo Garden Trimming (BGT) problem introduced in [Gąsieniec et al., SOFSEM’17]. The problem is difficult to solved due to its close relationship to Pinwheel scheduling. The garden with n bamboos is an analogue of a system of n machines that have to be attended (e.g., serviced) with different frequencies. During each day, bamboo b i grows an extra height h i , for i = 1 , ... , n and, on the conclusion of the day, at most one bamboo has its entire height cut.The goal is to design a perpetual schedule of cuts to keep the height of the tallest ever bamboo as low as possible. The contribution in this paper is twofold, and is both theoretical and experimental. In particular, the focus is on understanding what has been called priority schedulings, i.e., cutting strategies where priority is given to bamboos whose current height is above a threshold greater than or equal to H = ∑ i = 1 n h i . Value H represents the total daily growth of the system and it is known that one cannot keep bamboos in the garden below this threshold indefinitely. As the first result, it is proved that, for any distribution of integer growth rates h 1 , ... , h n and any priority scheduling, the system stabilises in a fixed cycle of cuts. Then, the focus is on the so-called ReduceMax strategy, a greedy priority scheduling that each day cuts the tallest bamboo, regardless of the growth rates distribution. ReduceMax is known to provide a O ( log n ) -approximation, with respect to the lower bound H. One of the main results achieved is that, if ReduceMax stabilises in a round-robin type cycle, then it guarantees 2-approximation. Furthermore, preliminary results are provided relating the structure of the input instance, in terms of growth rates, and the behavior of ReduceMax when applied to such inputs. Finally, a conjecture that ReduceMax is 2-approximating for the BGT problem is claimed, hence an extended experimental evaluation was conducted to support the conjecture and to compare ReduceMax with other relevant scheduling algorithms. The obtained results show that ReduceMax : (i) provides 2-approximation in all considered inputs; and (ii) always outperforms other considered strategies, even those for which better worst case approximation guarantees have been proven
Minimize the Maximum Duty in Multi-interface Networks
No full textWe consider devices equipped with multiple wired or wireless interfaces. By switching of various interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider two basic networking problems in the field of multi-interface networks. The first one, known as the Coverage problem, requires to establish the connections defined by a network. The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network. Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node. We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case. We prove that the Coverage problem is NP-hard for any fixed Delta a parts per thousand yen5 and ka parts per thousand yen16, with Delta being the maximum degree, and k being the number of different interfaces among the network. We also show that, unless P=NP, the problem cannot be approximated within a factor of eta ln I", for a certain constant eta. We then provide a general approximation algorithm which guarantees a factor of O((1+b)ln I"), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented. Concerning the Connectivity problem, we prove that it is NP-hard for any fixed Delta a parts per thousand yen3 and ka parts per thousand yen10. Also for this problem, the inapproximability result holds, that is, unless P=NP, the problem cannot be approximated within a factor of eta ln I", for a certain constant eta. We then provide approximation and exact algorithms for the general problem and for special cases, respectively
Connectionless Probabilistic (CoP) routing: an efficient protocol for Mobile, Wireless, Ad-Hoc Sensor Networks
No full textWe present a protocol that manages wireless ad-hoc sensor networks in several scenarios including large scale, high density and high mobility deployments. One of the main applications is to communicate important information from inaccessible areas by spreading just "enough" mobile sensors which must self-configure and assemble. According to our protocol, connectionless probabilistic (CoP) routing, the information is routed in a multi-hop, cluster level fashion by enabling each sensor to make individual decisions regarding its mode of operation. The aim is to prolong the network's lifetime by minimizing the energy spent for each communication. CoP is capable of addressing high mobility requirements as it is completely independent of any kind of topological knowledge and control messages. We show by extended experiments that CoP performs very well in terms of consumed energy by comparing it to a standard directed flooding and a greedy forwarding protocol
Gathering Six Oblivious Robots on Anonymous Symmetric Rings
No full textA recent model for robot-based computing systems makes use of identical, memoryless, and mobile robots placed on nodes of anonymous graphs. Robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current robots disposal on the entire ring (Look), takes a decision whether to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes a move to this neighbor (Move). Cycles are performed asynchronously for each robot.
We consider the case of six robots placed on the nodes of an anonymous ring in such a way they constitute a symmetric placement with respect to one single axis of symmetry, and we ask whether there exists a strategy that allows the robots to gather at one node. This is the first case left open after a series of papers dealing with the gathering of oblivious robots on anonymous rings. As long as the gathering is feasible, we provide a new distributed approach that guarantees a positive answer to the posed question
- …
