• Line-Recovery by Programmable Particles(1707.05041)

July 17, 2017 cs.DC
Shape formation has been recently studied in distributed systems of programmable particles. In this paper we consider the shape recovery problem of restoring the shape when $f$ of the $n$ particles have crashed. We focus on the basic line shape, used as a tool for the construction of more complex configurations. We present a solution to the line recovery problem by the non-faulty anonymous particles; the solution works regardless of the initial distribution and number $f<n-4$ of faults, of the local orientations of the non-faulty entities, and of the number of non-faulty entities activated in each round (i.e., semi-synchronous adversarial scheduler).
• Gathering in Dynamic Rings(1704.02427)

April 11, 2017 cs.DC
The gathering problem requires a set of mobile agents, arbitrarily positioned at different nodes of a network to group within finite time at the same location, not fixed in advanced. The extensive existing literature on this problem shares the same fundamental assumption: the topological structure does not change during the rendezvous or the gathering; this is true also for those investigations that consider faulty nodes. In other words, they only consider static graphs. In this paper we start the investigation of gathering in dynamic graphs, that is networks where the topology changes continuously and at unpredictable locations. We study the feasibility of gathering mobile agents, identical and without explicit communication capabilities, in a dynamic ring of anonymous nodes; the class of dynamics we consider is the classic 1-interval-connectivity. We focus on the impact that factors such as chirality (i.e., a common sense of orientation) and cross detection (i.e., the ability to detect, when traversing an edge, whether some agent is traversing it in the other direction), have on the solvability of the problem. We provide a complete characterization of the classes of initial configurations from which the gathering problem is solvable in presence and in absence of cross detection and of chirality. The feasibility results of the characterization are all constructive: we provide distributed algorithms that allow the agents to gather. In particular, the protocols for gathering with cross detection are time optimal. We also show that cross detection is a powerful computational element. We prove that, without chirality, knowledge of the ring size is strictly more powerful than knowledge of the number of agents; on the other hand, with chirality, knowledge of n can be substituted by knowledge of k, yielding the same classes of feasible initial configurations.
• Distributed Computing by Mobile Robots: Uniform Circle Formation(1407.5917)

March 29, 2017 cs.MA, cs.DC, cs.CG
Consider a set of $n$ simple autonomous mobile robots (asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, non-rigid, deterministic) initially in distinct locations, moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of the robots arranging themselves on the vertices of a regular $n$-gon not fixed in advance (Uniform Circle Formation). In the literature, the existing algorithmic contributions are limited to conveniently restricted sets of initial configurations of the robots and to more powerful robots. The question of whether such simple robots could deterministically form a uniform circle has remained open. In this paper, we constructively prove that indeed the Uniform Circle Formation problem is solvable for any initial configuration in which the robots are in distinct locations, without any additional assumption (if two robots are in the same location, the problem is easily seen to be unsolvable). In addition to closing a long-standing problem, the result of this paper also implies that, for pattern formation, asynchrony is not a computational handicap, and that additional powers such as chirality and rigidity are computationally irrelevant.
• Getting Close Without Touching: Near-Gathering for Autonomous Mobile Robots(1505.07168)

May 27, 2015 cs.DC, cs.CG, cs.RO
In this paper we study the Near-Gathering problem for a finite set of dimensionless, deterministic, asynchronous, anonymous, oblivious and autonomous mobile robots with limited visibility moving in the Euclidean plane in Look-Compute-Move (LCM) cycles. In this problem, the robots have to get close enough to each other, so that every robot can see all the others, without touching (i.e., colliding with) any other robot. The importance of solving the Near-Gathering problem is that it makes it possible to overcome the restriction of having robots with limited visibility. Hence it allows to exploit all the studies (the majority, actually) done on this topic in the unlimited visibility setting. Indeed, after the robots get close enough to each other, they are able to see all the robots in the system, a scenario that is similar to the one where the robots have unlimited visibility. We present the first (deterministic) algorithm for the Near-Gathering problem, to the best of our knowledge, which allows a set of autonomous mobile robots to nearly gather within finite time without ever colliding. Our algorithm assumes some reasonable conditions on the input configuration (the Near-Gathering problem is easily seen to be unsolvable in general). Further, all the robots are assumed to have a compass (hence they agree on the "North" direction), but they do not necessarily have the same handedness (hence they may disagree on the clockwise direction). We also show how the robots can detect termination, i.e., detect when the Near-Gathering problem has been solved. This is crucial when the robots have to perform a generic task after having nearly gathered. We show that termination detection can be obtained even if the total number of robots is unknown to the robots themselves (i.e., it is not a parameter of the algorithm), and robots have no way to explicitly communicate.
• Phospholipid-Dextran with a Single Coupling Point: a Useful Amphiphile for Functionalization of Nanomaterials(0902.0048)

Jan. 31, 2009 cond-mat.mtrl-sci
Nanomaterials hold much promise for biological applications, but they require appropriate functionalization to provide biocompatibility in biological environments. For non-covalent functionalization with biocompatible polymers, the polymer must also remain attached to the nanomaterial after removal of its excess to mimic the high dilution conditions of administration in vivo. Reported here are the synthesis and utilization singly-substituted conjugates of dextran and a phospholipid (Dextran-DSPE) as stable coatings for nanomaterials. Suspensions of single walled carbon nanotubes were found not only to be stable to phosphate buffered saline (PBS), serum, and a variety of pHs after excess polymer removal, but also provide brighter photoluminescence than carbon nanotubes suspended by poly(ethylene glycol)-DSPE. In addition, both gold nanoparticles (AuNPs) and gold nanorods (AuNRs) were found to maintain their dispersion and characteristic optical absorbance after transfer into Dextran-DSPE, and were obtained in much better yield than similar suspensions with PEG-phospholipid and commonly used thiol-PEG. These suspensions were also stable to PBS, serum, and a variety of pHs after removal of excess polymer. Dextran-DSPE thus shows great promise as a general surfactant material for the functionalization of a variety of nanomaterials, which could facilitate future biological applications.
• PEG Branched Polymer for Functionalization of Nanomaterials with Ultralong Blood Circulation(0901.4961)

Jan. 30, 2009 cond-mat.mtrl-sci
Nanomaterials have been actively pursued for biological and medical applications in recent years. Here, we report the synthesis of several new poly(ethylene glycol) grafted branched-polymers for functionalization of various nanomaterials including carbon nanotubes, gold nanoparticles (NP) and gold nanorods (NRs), affording high aqueous solubility and stability for these materials. We synthesize different surfactant polymers based upon poly-(g-glutamic acid) (gPGA) and poly(maleic anhydride-alt-1-octadecene) (PMHC18). We use the abundant free carboxylic acid groups of gPGA for attaching lipophilic species such as pyrene or phospholipid, which bind to nanomaterials via robust physisorption. Additionally, the remaining carboxylic acids on gPGA or the amine-reactive anhydrides of PMHC18 are then PEGylated, providing extended hydrophilic groups, affording polymeric amphiphiles. We show that single-walled carbon nanotubes (SWNTs), Au NPs and NRs functionalized by the polymers exhibit high stability in aqueous solutions at different pHs, at elevated temperatures and in serum. Morever, the polymer-coated SWNTs exhibit remarkably long blood circulation (t1/2 22.1 h) upon intravenous injection into mice, far exceeding the previous record of 5.4 h. The ultra-long blood circulation time suggests greatly delayed clearance of nanomaterials by the reticuloendothelial system (RES) of mice, a highly desired property for in vivo applications of nanomaterials, including imaging and drug delivery.