BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Nicola Santoro

Nicola Santoro contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster Computingphysics.soc-phSocial and Information NetworksArtificial IntelligenceComputation and LanguageNetworking and Internet ArchitectureRobotics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2020arXiv

A Characterization of Semi-Synchrony for Asynchronous Robots with Limited Visibility, and its Application to Luminous Synchronizer Design

A mobile robot system consists of anonymous mobile robots, each of which autonomously performs sensing, computation, and movement according to a common algorithm, so that the robots collectively achieve a given task. There are two main models of time and activation of the robots. In the semi-synchronous model (SSYNC), the robots share a common notion of time; at each time unit, a subset of the robots is activated, and each performs all three actions (sensing, computation, and movement) in that time unit. In the asynchronous model (ASYNC), there is no common notion of time, the robots are activated at arbitrary times, and the duration of each action is arbitrary but finite. In this paper, we investigate the problem of synchronizing ASNYC robots with limited sensing range, i.e., limited visibility. We first present a sufficient condition for an ASYNC execution of a common algorithm ${\cal A}$ to have a corresponding SSYNC execution of ${\cal A}$; our condition imposes timing constraints on the activation schedule of the robots and visibility constraints during movement. Then, we prove that this condition is necessary (with probability $1$) under a randomized ASYNC adversary. Finally, we present a synchronization algorithm for luminous ASYNC robots with limited visibility, each equipped with a light that can take a constant number of colors. Our algorithm enables luminous ASYNC robots to simulate any algorithm ${\cal A}$, designed for the (non-luminous) SSYNC robots and satisfying visibility constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Mobile RAM and Shape Formation by Programmable Particles

We investigate computational issues in the distributed model Amoebots of programmable matter. In this model, the computational entities, called particles, are anonymous finite-state machines that operate and move on an hexagonal tasselation of the plane. In this paper we show how a constant number of such weak particles can simulate a powerful Turing-complete entity that is able to move on the plane while computing. We then show an application of our tool to the classical Shape-Formation problem, providing a new and much more general distributed solution protocol. Indeed, the existing algorithms would allow to form only shapes made of arrangements of segments and triangles. Our algorithm allows the particles to form more abstract and general connected shapes, including circles and spirals, as well as fractal objects of non-integer dimension, such as the Sierpinski triangle or the Koch snowflake. In lieu of the existing limitation on the formability of a shape depending on the symmetry of the initial configuration of the particles, our result provides a complete characterization of the connected shapes that can be formed by an initially simply connected set of particles. Furthermore, in the case of non-connected shapes, we give almost-matching necessary and sufficient conditions for their formability.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tight Bounds for Black Hole Search in Dynamic Rings

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 problem is solved if within finite time at least one agent survives and knows the location of BH. The main complexity parameters of BHS is the number of agents (called size) needed to solve the problem, and the number of moves (called cost) performed by the agents; in synchronous systems, such as temporal rings, an additional complexity measure is the amount of time until termination occurs. Feasibility and complexity depend on many parameters; in particular: whether the agents start from the same safe node or from possibly distinct safe locations, 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 for all instances of those parameters; all our algorithms are size optimal. Furthermore, we establish lower bounds on the cost (i.e., the number of moves) and time of size-optimal solutions for all instances of those parameters and show that our algorithms achieve those bound.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Building Fastest Broadcast Trees in Periodically-Varying Graphs

Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. Still, connectivity can generally be established over time and space. The optimality of a temporal path (journey) in this context can be defined in several terms, including topological (e.g. {\em shortest} in hops) and temporal (e.g. {\em fastest, foremost}). The combinatorial problem of computing shortest, foremost, and fastest journeys {\em given full knowledge} of the network schedule was addressed a decade ago (Bui-Xuan {\it et al.}, 2003). A recent line of research has focused on the distributed version of this problem, where foremost, shortest or fastest {\em broadcast} are performed without knowing the schedule beforehand. In this paper we show how to build {\em fastest} broadcast trees (i.e., trees that minimize the global duration of the broadcast, however late the departure is) in Time-Varying Graphs where intermittent edges are available periodically (it is known that the problem is infeasible in the general case even if various parameters of the graph are know). We address the general case where contacts between nodes can have arbitrary durations and thus fastest routes may consist of a mixture of {\em continuous} and {\em discontinuous} segments (a more complex scenario than when contacts are {\em punctual} and thus routes are only discontinuous). Using the abstraction of \tclocks to compute the temporal distances, we solve the fastest broadcast problem by first learning, at the emitter, what is its time of {\em minimum temporal eccentricity} (i.e. the fastest time to reach all the other nodes), and second by building a {\em foremost} broadcast tree relative to this particular emission date.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Expressivity of Time-Varying Graphs and the Power of Waiting in Dynamic Networks

In infrastructure-less highly dynamic networks, computing and performing even basic tasks (such as routing and broadcasting) is a very challenging activity due to the fact that connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry-forward-like mechanisms such as local buffering) than if waiting is not feasible. No quantitative corroborations of this fact exist (e.g., no answer to the question: how much easier?). In this paper, we consider these qualitative questions about dynamic networks, modeled as time-varying (or evolving) graphs, where edges exist only at some times. We examine the difficulty of the environment in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph. We prove that the set of languages $L_{nowait}$ when no waiting is allowed contains all computable languages. On the other end, using algebraic properties of quasi-orders, we prove that $L_{wait}$ is just the family of regular languages. In other words, we prove that, when waiting is no longer forbidden, the power of the accepting automaton (difficulty of the environment) drops drastically from being as powerful as a Turing machine, to becoming that of a Finite-State machine. This (perhaps surprisingly large) gap is a measure of the computational power of waiting. We also study bounded waiting; that is when waiting is allowed at a node only for at most $d$ time units. We prove the negative result that $L_{wait[d]} = L_{nowait}$; that is, the expressivity decreases only if the waiting is finite but unpredictable (i.e., under the control of the protocol designer and not of the environment).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Time-Varying Graphs and Dynamic Networks

The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems -- delay-tolerant networks, opportunistic-mobility networks, social networks -- obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe; and the formal models proposed so far to express some specific concepts are components of a larger formal description of this universe. The main contribution of this paper is to integrate the vast collection of concepts, formalisms, and results found in the literature into a unified framework, which we call TVG (for time-varying graphs). Using this framework, it is possible to express directly in the same formalism not only the concepts common to all those different areas, but also those specific to each. Based on this definitional work, employing both existing results and original observations, we present a hierarchical classification of TVGs; each class corresponds to a significant property examined in the distributed computing literature. We then examine how TVGs can be used to study the evolution of network properties, and propose different techniques, depending on whether the indicators for these properties are a-temporal (as in the majority of existing studies) or temporal. Finally, we briefly discuss the introduction of randomness in TVGs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics

Most instruments - formalisms, concepts, and metrics - for social networks analysis fail to capture their dynamics. Typical systems exhibit different scales of dynamics, ranging from the fine-grain dynamics of interactions (which recently led researchers to consider temporal versions of distance, connectivity, and related indicators), to the evolution of network properties over longer periods of time. This paper proposes a general approach to study that evolution for both atemporal and temporal indicators, based respectively on sequences of static graphs and sequences of time-varying graphs that cover successive time-windows. All the concepts and indicators, some of which are new, are expressed using a time-varying graph formalism.

0 citations0 reviewsNo code linkedOpen access