Compiler optimizations may lead to loss of debug information, hampering developer productivity and techniques that rely on binary-to-source mappings, such as sampling-based feedback-directed optimization. While recent endeavors exposed debug information correctness and completeness bugs in compiler transformations, understanding where a complex optimizing pipeline "loses" debug information is an understudied problem.In this paper, we first rectify accuracy issues in methods for measuring the availability of debug information, and show that the synthetic programs evaluated so far lead to metric values that differ from those we observe for real-world programs. Building on this, we present DebugTuner, a framework for systematically analyzing the impact of individual compiler optimization passes on debug information, and assemble a test suite of programs for collecting more realistic metrics. Using DebugTuner and the test suite, we identify transformations in gcc and clang that cause more debug information loss, and construct modified optimization levels that improve debuggability while retaining competitive performance. We obtain levels that outperform gcc’s Og for both debuggability and performance, and make recommendations for constructing an Og level for clang. Finally, we present a case study on AutoFDO where, by disabling selected passes in the profiling stage, the final optimized binary is more performant due to the improved quality of the binary-to-source mapping.

In the content-oblivious (CO) model, proposed by Censor-Hillel et al. (PODC 2022 & Distributed Computing 2023), processes operate in an asynchronous network and communicate solely through pulses: zero-size messages that carry no information beyond their mere existence.

We study leader election in oriented ring networks under a content-oblivious asynchronous message-passing model in which an adversary may arbitrarily corrupt message contents. This highly stringent model captures extreme communication unreliability.

A communication network is said to be anonymous if its agents are indistinguishable from each other; it is dynamic if its communication links may appear or disappear unpredictably over time. Assuming that each of the n agents of an anonymous dynamic network is initially given an input, it takes 2 τn communication rounds for the agents to compute an arbitrary (frequency-based) function of such inputs (Di Luna–Viglietta, DISC 2023), where τ is a parameter called dynamic disconnectivity , and measures how far the network is from being always connected (for always connected dynamic networks, τ = 1 ). It is known that, without making additional assumptions on the network and without knowing the number of agents n , it is impossible to compute most functions and explicitly terminate . In fact, current state-of-the-art algorithms only achieve stabilization , i.e., allow each agent to return an output after every communication round. Outputs can be changed, and are guaranteed to be all correct after 2 τn rounds. Such algorithms rely on the incremental construction of a data structure called a history tree , which is augmented at every round. Thus, they end up consuming an unlimited amount of memory, and are also prone to errors in case of memory loss or corruption. In this paper, we provide a general self-stabilizing algorithm for anonymous dynamic networks that stabilizes in max { 4 τ n − 2 μ , 2 μ } rounds (where μ measures the smallest amount of potentially corrupted history initially stored by any agent), as well as a general finite-state algorithm that stabilizes in τ ( 2 n 2 + n ) rounds. Our work improves upon previously known methods that only apply to static networks (Boldi–Vigna, Dist. Comp. 2002). In addition, we develop new fundamental techniques and operations involving history trees, which are of independent interest.

Ensuring the security and confidentiality of cloud computing workloads is essential. To this end, major cloud providers offer computing instances based on trusted execution environments (TEEs) to support confidential computing in virtual machines. TEEs are hardware-based shielded environments building on technologies available today, such as Intel TDX or AMD SEV-SNP or that will soon be, as with ARM CCA.To lower the barriers to experimenting with these technologies for researchers and practitioners, we developed ConfBench, a tool for easy evaluation of confidential virtual machines. ConfBench supports both cloud-native workloads (Function-as-a-Service) and classic applications. ConfBench facilitates the management of the full lifecycle of such workloads, from their deployment to the gathering of performance metrics, taking into account the specifics of TEE-enabled confidential virtual machines. We use ConfBench to collect execution overhead measurements for different VM-enabled TEEs (Intel TDX and AMD SEV-SNP) through extensive experiments. We also showcase how ConfBench’s architecture allows for validating also simulation-based TEEs, reporting preliminary results with ARM CCA. We highlight the intrinsic overheads of such confidential VMs by conducting stress tests against machine learning inference tasks, DBMS and native-OS operations benchmarking, as well as by evaluating the costs of attestation operations required in the context of confidential computing. The results indicate generally tenable overheads with modern TEEs, with exceptions mainly from I/O-intensive tasks, especially with TDX. ConfBench’s multi-language support for FaaS workloads also lets us gain insights into differences stemming from varying complexities behind language runtimes. We release ConfBench to the research community and provide instructions to reproduce our experiments.

Binary function similarity, which often relies on learning-based algorithms to identify what functions in a pool are most similar to a given query function, is a sought-after topic in different communities, including machine learning, software engineering, and security. Its importance stems from the impact it has in facilitating several crucial tasks, from reverse engineering and malware analysis to automated vulnerability detection. Whereas recent work cast light around performance on this long-studied problem, the research landscape remains largely lackluster in understanding the resiliency of the state-of-the-art machine learning models against adversarial attacks. As security requires to reason about adversaries, in this work we assess the robustness of such models through a simple yet effective black-box greedy attack, which modifies the topology and the content of the control flow of the attacked functions. We demonstrate that this attack is successful in compromising all the models, achieving average attack success rates of 57.06% and 95.81% depending on the problem settings (targeted and untargeted attacks). Our findings are insightful: top performance on clean data does not necessarily relate to top robustness properties, which explicitly highlights performance-robustness trade-offs one should consider when deploying such models, calling for further research.

In networked systems supporting mobile agents, a particularly dangerous security threat facing the agents is the presence of a black hole (Bh): a network host that destroys any incoming agent without leaving any trace. The problem, called Black hole search (Bhs), of efficiently determining the location of such a dangerous host has been extensively studied under a variety of different assumptions. In spite of their differences, the existing results share the same assumption that all the searching agents are reliable.In this paper, we start the investigation of the Bhs problem when some of the searching agents are faulty in a malicious way. More precisely, we consider that up to f of the k searching agents are Byzantine: they may behave in an arbitrary manner, actively misleading other agents; furthermore, they are in collusion with the black hole, and immune to its destructive power.We study under what conditions the Bhs problem can be solved in a synchronous network of arbitrary topology in spite of the malicious agents, examining the impact on complexity of two factors: the a-priori topological knowledge held by the agents, and the communication mechanism available to them.We prove that, with prior knowledge about the graph topology (i.e., a network map), Bhs can be solved by k ≥ 2f +2 agents in O(n + f) synchronous rounds both with whiteboards and with just local communication, where n is the number of nodes in the network.Without any knowledge about the topological structure, using whiteboard communication Bhs can be solved by k ≥ (f+1)(∆+ 1) agents in O(m+f) rounds; instead, using local communication, Bhs can be solved by k ≥ (f + 1)(∆ + 1) + 3f + 1 agents in O(m • n + f) rounds, where m is the number of links of the network and ∆ is the maximum degree of the network.In all cases, as we show, the bound on the total number k of agents is asymptotically optimal.

One of the core aspects of distributed computing is the design of algorithms that tolerate failures [Cachin et al., 2011; Raynal, 2018]. Failures may involve processes (in which case we may encounter crash-stop, memory corruption, or Byzantine failures) or the communication among processes. When processes communicate through message passing, failures may include message loss, message addition (either duplication or fabrication), and message corruption [Santoro and Widmayer, 1989]. Tight bounds are known for agreement in the synchronous setting under these types of failures [Santoro and Widmayer, 1989], and numerous works have investigated message loss in the synchronous setting and asynchronous setting for many other problems [Herlihy et al., 2013; Raynal, 2018; Santoro and Widmayer, 1990; Schmid et al., 2009]. In this talk, we focus on what can be computed when the system is asynchronous and messages may be corrupted; that is, a sent message can be arbitrarily modified by an adversary, but it cannot be deleted or duplicated. We specifically consider the bleak scenario in which all messages sent by processes are corrupted. Alternatively, one can view this as a setting where all messages have zero size, consisting only of simple pulses. This content-oblivious model is reminiscent of the beeping model [A. Casteigts et al., 2019], but in the beeping model, synchrony allows silence to be used as a means of communication. Surprisingly, contrary to what one might expect at first glance, [Censor-Hillel et al., 2023] has recently shown that, in the content-oblivious setting, when a predetermined leader is present and the network topology is 2-connected, it is possible to simulate an environment that is completely fault-free. While [Censor-Hillel et al., 2023] has shown that 2-connectivity is necessary, it also conjectured that the presence of a leader was a required assumption. [Frei et al., 2024] disproved this conjecture for the special case of oriented ring graphs by presenting a composable leader election algorithm. This result was later extended in [Chalopin et al., 2025] to the case of unoriented graphs, and, under the mild assumption of an upper bound on the network size, for any 2-edge-connected network. Thus, for the special case of ring topologies, we have a computational equivalence between content-oblivious and classic asynchronous message passing. Always in oriented in rings [Chalopin et al., 2025] has shown a non-uniform leader election algorithm with an optimal dependency on process IDs. The talk will discuss these results, focusing on the open problems and the current state of computation in systems where messages carry no content.

Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may arbitrarily corrupt messages. The model is equivalent to content-oblivious computation, where nodes communicate solely via pulses. They showed that if the network is 2-edge-connected, then any algorithm for a noiseless setting can be simulated in the fully-defective setting; otherwise, no non-trivial computation is possible in the fully-defective setting. However, their simulation requires a predesignated leader, which they conjectured to be necessary for any non-trivial content-oblivious task. Recently, Frei, Gelles, Ghazy, and Nolin (DISC 2024) refuted this conjecture for the special case of oriented ring topology. They designed two asynchronous content-oblivious leader election algorithms with message complexity O(n ⋅ ID_{max}), where n is the number of nodes and ID_{max} is the maximum ID. The first algorithm stabilizes in unoriented rings without termination detection. The second algorithm quiescently terminates in oriented rings, thus enabling the execution of the simulation algorithm after leader election. In this work, we present two results: General 2-edge-connected topologies: First, we show an asynchronous content-oblivious leader election algorithm that quiescently terminates in any 2-edge-connected network with message complexity O(m ⋅ N ⋅ ID_{min}), where m is the number of edges, N is a known upper bound on the number of nodes, and ID_{min} is the smallest ID. Combined with the above simulation, this result shows that whenever a size bound N is known, any noiseless algorithm can be simulated in the fully-defective model without a preselected leader, fully refuting the conjecture. Unoriented rings: We then show that the knowledge of N can be dropped in unoriented ring topologies by presenting a quiescently terminating election algorithm with message complexity O(n ⋅ ID_{max}) that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous state of the art and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions.

In this paper, we study the leader election problem in oriented ring networks under content-oblivious asynchronous message-passing systems, where an adversary may arbitrarily corrupt message contents. Frei et al. (DISC 2024) recently presented a uniform terminating leader election algorithm for oriented rings in this setting, with message complexity O(nIDmax) on a ring of size n, where IDmax is the largest identifier in the system. In this paper, we investigate the message complexity of leader election in this model, showing that no uniform algorithm can solve the problem if each process is limited to sending a constant number of messages in one direction. Interestingly, this limitation hinges on the uniformity assumption. In the non-uniform setting – where processes know an upper bound U ≥ n on the ring size – we present an algorithm with message complexity O(nUIDmin), in which each process sends O(UIDmin) messages clockwise and only three messages counter-clockwise. Here, IDmin is the smallest identifier in the system. This dependence on the identifiers compares favorably with the dependence on IDmax of Frei et al. (DISC 2024). We also show a non-uniform algorithm where each process sends O(U log IDmin) messages in one direction and O(log IDmin) in the other. The factor log IDmin is optimal, matching the lower bound of Frei et al. (DISC 2024). Finally, in the anonymous setting, we propose a randomized algorithm where each process sends only O(log2 U) messages, with a success probability of 1 − U−c

In networked environments supporting mobile agents , a pressing problem is the presence of network sites harmful for the agents. In this paper we consider the danger posed by a node that destroys any incoming agent without leaving any trace. Such a dangerous node is known in the literature as a black hole ( Bh ). The problem of a team of system agents determining its location, known as black hole search ( Bhs ), has been extensively studied in the literature under a variety of assumptions, both in synchronous and asynchronous settings. The main complexity parameter of Bhs is the number of system agents (called size ) needed to solve the problem; other parameters are the number of moves (called cost ) performed by the agents, and the time until termination. In the existing literature, with only a couple of exceptions, all results are based on a common assumption that the network is static , i.e. its topology does not change in time. We consider instead the Bhs when the network is dynamic : the link structure of the graph changes over time. While time-varying graphs have been the focus of intense research in the last two decades, very little is known on the problem of locating the Bh in such networks. In this paper, we contribute to fill this research gap by studying Bhs in dynamic ring networks, focusing on the 1-interval connectivity adversarial dynamics. Feasibility and complexity of the problem depend on many factors, specifically on the size n of the ring, whether or not n is known, and the type of inter-agent communication (whiteboards, tokens, face-to-face, visual). In this paper, we provide a complete feasibility characterization presenting size optimal algorithms. Furthermore, we establish lower bounds on the cost and time of size-optimal solutions and show that our algorithms achieve those bounds.

A recent trend in binary code analysis promotes the use of neural solutions based on instruction embedding models. An instruction embedding model is a neural network that transforms assembly instructions into embedding vectors. If the embedding network is able to processes sequences of assembly instructions transforming them into a sequence of embedding vectors, then the network effectively represents anassembly code model. In this paper we present BinBert, a novel assembly code model. BinBert is built on a transformer pre-trained on a huge dataset of both assembly instruction sequences and symbolic execution information. BinBert can be applied to assembly instructions sequences and it isfine-tunable, i.e. it can be re-trained as part of a neural architecture on task-specific data. Through fine-tuning, BinBert learns how to apply the general knowledge acquired with pre-training to the specific task. We evaluated BinBert on a multi-task benchmark that we specifically designed to test the understanding of assembly code. The benchmark is composed of several tasks, some taken from the literature, and a few novel tasks that we designed, with a mix of intrinsic and downstream tasks. Our results show that BinBert outperforms state-of-the-art models for binary instruction embedding, raising the bar for binary code understanding.

An anonymous dynamic network is a network of indistinguishable processes whose communication links may appear or disappear unpredictably over time. Previous research has shown that deterministically computing an arbitrary function of a multiset of input values given to these processes takes only a linear number of communication rounds (Di Luna-Viglietta, FOCS 2022). However, fast algorithms for anonymous dynamic networks rely on the construction and transmission of large data structures called "history trees", whose size is polynomial in the number of processes. This approach is unfeasible if the network is congested, and only messages of logarithmic size can be sent through its links. Observe that sending a large message piece by piece over several rounds is not in itself a solution, due to the anonymity of the processes combined with the dynamic nature of the network. Moreover, it is known that certain basic tasks such as all-to-all token dissemination (by means of single-token forwarding) require $Ω(n^2/\log n)$ rounds in congested networks (Dutta et al., SODA 2013). In this work, we develop a series of practical and efficient techniques that make it possible to use history trees in congested anonymous dynamic networks. Among other applications, we show how to compute arbitrary functions in such networks in $O(n^3)$ communication rounds, greatly improving upon previous state-of-the-art algorithms for congested networks.

The availability of debug information for optimized executables can largely ease crucial tasks such as crash analysis. Source-level debuggers use this information to display program state in terms of source code, allowing users to reason on it even when optimizations alter program structure extensively. A few recent endeavors have proposed effective methodologies for identifying incorrect instances of debug information, which can mislead users by presenting them with an inconsistent program state.

An anonymous dynamic network is a network of indistinguishable processes whose communication links may appear or disappear unpredictably over time. Previous research has shown that deter-ministically computing an arbitrary function of a multiset of input values given to these processes takes only a linear number of communication rounds (Di Luna-Viglietta, FOCS 2022).

We give the first linear-time counting algorithm for processes in anonymous 1-interval-connected dynamic networks with a leader. As a byproduct, we are able to compute in 3n rounds every function that is deterministically computable in such networks. If explicit termination is not required, the running time improves to 2n rounds, which we show to be optimal up to a small additive constant (this is also the first non-trivial lower bound for counting). As our main tool of investigation, we introduce a combinatorial structure called history tree, which is of independent interest. This makes our paper completely self-contained, our proofs elegant and transparent, and our algorithms straightforward to implement.In recent years, considerable effort has been devoted to the design and analysis of counting algorithms for anonymous 1-interval-connected networks with a leader. A series of increasingly sophisticated works, mostly based on classical mass-distribution techniques, have recently led to a celebrated counting algorithm in $O(n^{4+\epsilon}\log^{3}(n))$ rounds (for ϵ > 0), which was the state of the art prior to this paper. Our contribution not only opens a promising line of research on applications of history trees, but also demonstrates that computation in anonymous dynamic networks is practically feasible, and far less demanding than previously conjectured.

In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Robots are punctiform and memoryless, they operate in $$\mathbb {R}^m$$ , they have local reference systems independent of each other, and are activated asynchronously by an adversarial scheduler. Moreover, robots are non-rigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange $$3m+3k$$ of these weak entities in $$\mathbb {R}^m$$ to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.

The binary similarity problem consists in determining if two functions are similar considering only their compiled form. Advanced techniques for binary similarity recently gained momentum as they can be applied in several fields, such as copyright disputes, malware analysis, vulnerability detection, etc. In this article we describe SAFE, a novel architecture for function representation based on a self-attentive neural network. SAFE works directly on disassembled binary functions, does not require manual feature extraction, is computationally more efficient than existing solutions, and is more general as it works on stripped binaries and on multiple architectures. Results from our experimental evaluation show how SAFE provides a performance improvement with respect to previous solutions. Furthermore, we show how SAFE can be used in widely different use cases, thus providing a general solution for several application scenarios.

Despite the advancements in software testing, bugs still plague deployed software and result in crashes in production. When debugging issues —sometimes caused by “heisenbugs”— there is the need to interpret core dumps and reproduce the issue offline on the same binary deployed. This requires the entire toolchain (compiler, linker, debugger) to correctly generate and use debug information. Little attention has been devoted to checking that such information is correctly preserved by modern toolchains’ optimization stages. This is particularly important as managing debug information in optimized production binaries is non-trivial, often leading to toolchain bugs that may hinder post-deployment debugging efforts.

In this paper, we start the investigation of distributed computing by mobile agents in dangerous dynamic networks. The danger is posed by the presence in the network of a black hole (BH), a harmful site that destroys all incoming agents without leaving any trace. The problem of determining the location of the black hole in a network, known as black hole search (BHS), has been extensively studied in the literature, but always and only assuming that the network is static. At the same time, the existing results on mobile agents computing in dynamic networks never consider the presence of harmful sites. In this paper we start filling this research gap by studying black hole search in temporal rings, specifically focusing on 1-interval connectivity adversarial dynamics. The main complexity parameter of BHS is the number of agents (called size) needed to solve the problem; other parameters are the number of moves (called cost) performed by the agents, and the time until termination. Feasibility and complexity depend on many factors; the size n of the ring, whether or not n is known, and the type of inter-agent communication (whiteboards, tokens, face-to-face, visual). In this paper, we provide a complete feasibility characterization presenting size optimal algorithms. Furthermore, we establish lower bounds on the cost and time of size-optimal solutions and show that our algorithms achieve those bounds.

In the Lattice Agreement (LA) problem, originally proposed by Attiya et al. [1], a set of processes has to decide on a chain of a lattice. More precisely, each correct process proposes an element e of a certain join-semi lattice L and it has to decide on a value that contains e. Moreover, any pair pi, pjof correct processes has to decide two values deciand decjthat are comparable (e.g., deci≤ decjor decji). In this paper we present new contributions for the synchronous case. We investigate the problem in the usual message passing model for a system of n processes with distinct unique IDs. We first prove that, when only authenticated channels are available, the problem cannot be solved if f = n/3 or more processes are Byzantine. We then propose a novel algorithm that works in a synchronous system model with signatures (i.e., the authenticated message model), tolerates up to f byzantine failures (where f <; n/3) and that terminates in O(log f) rounds. We discuss how to remove authenticated messages at the price of algorithm resiliency (f <; n/4). Finally, we present a transformer that converts any synchronous LA algorithm to an algorithm for synchronous Generalised Lattice Agreement.

The paper investigates the Lattice Agreement (LA) problem in asynchronous systems. In LA each process proposes an element e from a predetermined lattice, and has to decide on an element e' of the lattice such that e ≤ e'. Moreover, decisions of different processes have to be comparable (no two processes can decide two elements e' and e such that (e ≤ e') ∧ (e' ≤ e)).It has been shown that Generalized LA (i.e., a version of LA proposing and deciding on sequences of values) can be used to build a Replicated State Machine (RSM) with commutative update operations. The key advantage of LA and Generalized LA is that they can be solved in asynchronous systems prone to crash-failures (which is not the case with standard Consensus).In this paper we assume Byzantine failures. We propose the Wait Till Safe (WTS) algorithm for LA, and we show that its resilience to f ≤ (n - 1)/3 Byzantine processes is optimal. We then generalize WTS obtaining a Generalized LA algorithm, namely GWTS. We use GWTS to build a RSM with commutative updates. Our RSM works in asynchronous systems and tolerates f ≤ (n - 1)/3 malicious entities. All our algorithms use the minimal assumption of authenticated channels. When the more powerful public signatures are available, we discuss how to improve the message complexity of our results (from quadratic to linear, when f = O(1)). To the best of our knowledge this is the first paper proposing a solution for Byzantine LA that works on any possible lattice, and it is the first work proposing a Byzantine tolerant RSM built on it.

A swarm of anonymous oblivious mobile robots, operating in deterministic Look-Compute-Move cycles, is confined within a circular track. All robots agree on the clockwise direction (chirality), they are activated by an adversarial semi-synchronous scheduler (SSYNCH), and an active robot always reaches the destination point it computes (rigidity). Robots have limited visibility: each robot can see only the points on the circle that have an angular distance strictly smaller than a constant $\vartheta$ from the robot's current location, where $0<\vartheta\leqπ$ (angles are expressed in radians). We study the Gathering problem for such a swarm of robots: that is, all robots are initially in distinct locations on the circle, and their task is to reach the same point on the circle in a finite number of turns, regardless of the way they are activated by the scheduler. Note that, due to the anonymity of the robots, this task is impossible if the initial configuration is rotationally symmetric; hence, we have to make the assumption that the initial configuration be rotationally asymmetric. We prove that, if $\vartheta=π$ (i.e., each robot can see the entire circle except its antipodal point), there is a distributed algorithm that solves the Gathering problem for swarms of any size. By contrast, we also prove that, if $\vartheta\leq π/2$, no distributed algorithm solves the Gathering problem, regardless of the size of the swarm, even under the assumption that the initial configuration is rotationally asymmetric and the visibility graph of the robots is connected. The latter impossibility result relies on a probabilistic technique based on random perturbations, which is novel in the context of anonymous mobile robots. Such a technique is of independent interest, and immediately applies to other Pattern-Formation problems.

International audience

In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Each robot is punctiform and memoryless, it operates in R m , it has a local reference system independent of the other robots’ ones, and is activated asynchronously by an adversarial scheduler. Moreover, the robots are nonrigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange 3m+3k of these weak entities in R m to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient. © Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, and Giovanni Viglietta.

In this paper we investigate the computational power of population protocols under some unreliable or weaker interaction models. More precisely, we focus on two features related to the power of interactions: omission failures and one-way communications. We start our investigation by providing a complete classification of all the possible models arising from the aforementioned weaknesses, and establishing the computational hierarchy of these models. We then address for each model the fundamental question of what additional power is necessary and sufficient to completely overcome the model's weakness and make it able to simulate faultless two-way protocols. We answer this question by presenting simulators that work under certain assumptions and by proving that simulation is impossible without such assumptions.

Shape formation (or pattern formation) is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter, where entities are assumed to be small and with severely limited capabilities. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessellation of the plane and have limited computational power (they have constant memory), strictly local interaction and communication capabilities (only with particles in neighboring nodes of the grid), and limited motorial capabilities (from a grid node to an empty neighboring node); their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization (i.e., particles can flip coins to elect a leader). In this paper we provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of n particles. The characterization is constructive: we provide a universal shape formation algorithm that, for each feasible pair of shapes (S0, SF), allows the particles to form the final shape SF (given in input) starting from the initial shape S0, unknown to the particles. The final configuration will be an appropriate scaled-up copy of SF depending on n. If randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that there are enough particles. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n2) rounds and moves: this number of moves is also asymptotically worst-case optimal.

The Meeting problem for k>=2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order sigma (where sigma=1 corresponds to no rotational symmetry), we prove that k=sigma+1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k=2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon's vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.

Shape formation is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessellation of the plane, have constant memory, can only communicate with neighboring particles, and can only move from a grid node to an empty neighboring node; their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization. In this paper we provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of n particles. As a byproduct, if randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that n is large enough. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n^2) rounds and moves: this number of moves is also asymptotically optimal.

Almost all the vast literature on graph exploration assumes that the graph is static: its topology does not change during the exploration, except for occasional faults. To date, very little is known on exploration of dynamic graphs, where the topology is continously changing. The few studies have been limited to the centralized (or post-mortem) case, assuming complete a priori knowledge of the changes and the times of their occurrence, and have only considered fully synchronous systems. In this paper, we start the study of the decentralized (or live) exploration of dynamic graphs, i.e. when the agents operate in the graph unaware of the location and timing of the changes. We consider dynamic rings under the standard 1-interval-connected restriction, and investigate the feasibility of their exploration, in both the fully synchronous and semi-synchronous cases. When exploration is possible we examine at what cost, focusing on the minimum number of agents capable of exploring the ring. We establish several results highlighting the impact that anonymity and structural knowledge have on the feasibility and complexity of the problem.

In this paper we consider a static set of anonymous processes, i.e., they do not have distinguished IDs, that communicate with neighbors using a local broadcast primitive. The communication graph changes at each computational round with the restriction of being always connected, i.e., the network topology guarantees 1-interval connectivity. In such setting non trivial computations, i.e., answering to a predicate like "there exists at least one process with initial input a?", are impossible. In a recent work, it has been conjectured that the impossibility holds even if a distinguished leader process is available within the computation. In this paper we prove that the conjecture is false. We show this result by implementing a deterministic leader-based terminating counting algorithm. In order to build our counting algorithm we first develop a counting technique that is time optimal on a family of dynamic graphs where each process has a fixed distance h from the leader and such distance does not change along rounds. Using this technique we build an algorithm that counts in anonymous 1-interval connected networks.

In this paper we study the problem of counting processes in a synchronous dynamic network where a distinguished leader is available and other nodes share the same identifier. The network topology may change at each synchronous round and each node communicates with its neighbors by broadcasting messages. In such networks it is well known that counting requires Ω(D) rounds where D is the network diameter. We identify a non-trivial subset of dynamic net- works where counting requires Ω(log |V|) rounds even when the dynamic diameter, D, is constant with respect to the network size and the bandwidth is unlimited.

In this paper we investigate the problem of counting the size of a network where processes are anonymous (i.e., they share the same identifier) and the network topology constantly changes controlled by an adversary able to look internal process states and add and remove edges in order to contrast the convergence of the algorithm to the correct count. It is easy to show that, if the adversary can generate graphs without any constraint on the connectivity (i.e. it can generate topologies where there exist nodes not able to influence the others), counting is impossible. In this paper we consider a synchronous round based computation and the dynamicity is governed by a worst-case adversary that generates a sequence of graphs, one for each round, with the only constraint that each graph must be connected (1-interval connectivity property). It has been conjectured that counting in a finite time against such adversary is impossible and the existing solutions consider that each process has some knowledge about network topologies generated by the adversary, i.e. at each round, each node has a degree lesser than D. Along the path of proving the validity (or not) of the conjecture, this paper presents an algorithm that counts in a finite time against the worst-case adversary assuming each process is equipped with an oracle. The latter provides a process at each round r with an estimation of the process degree in the graph generated by the adversary at round r. To the best of our knowledge, this is the first counting algorithm (terminating in a finite time) where processes exploit the minimal knowledge about the behavior of the adversary. Interestingly, such oracle can be implemented in a wide range of real systems.