Arnaud Casteigts
email: arnaud.casteigts@labri.fr

JBotSim: a Tool for Fast Prototyping of Distributed Algorithms in Dynamic Networks *

JBOTSIM is a java library that offers basic primitives for prototyping, running, and visualizing distributed algorithms in dynamic networks. With JBOTSIM, one can implement an idea in minutes and interact with it (e.g., add, move, or delete nodes) while it is running. JBOTSIM is well suited to prepare live demonstrations of algorithms to colleagues or students; it can also be used to evaluate performance at the algorithmic level (number of messages, number of rounds, etc.). Unlike most simulation tools, JBOTSIM is not an integrated environment. It is a lightweight library to be used in java programs. In this paper, I present an overview of its distinctive features and architecture.

INTRODUCTION

JBotSim is an open source simulation library that is dedicated to distributed algorithms in dynamic networks. I developed it with the purpose in mind to make it possible to implement an algorithmic idea in minutes and interact with it while it is running (e.g., add, move, or delete nodes). Besides interaction, JBOTSIM can also be used to prepare live demos of an algorithm and to show it to colleagues or students, as well as to assess the algorithm performance. JBOTSIM is not a competitor of mainstream simulators such as NS3 [START_REF]The NS-3 network simulator[END_REF], OMNet [START_REF] Varga | The OMNeT++ discrete event simulation system[END_REF], or The One [START_REF] Keränen | The one simulator for dtn protocol evaluation[END_REF], in the sense that it does not aim to implement real-world networking protocols. Quite the opposite, JBOTSIM aims to remain technology-insensitive and to be used at the algorithmic level, in a way closer in spirit to the ViSiDiA project (a general-purpose platform for distributed algorithms). Unlike ViSiDiA, however, JBOTSIM natively supports mobility and dynamic networks (as well as wireless communication). Another major difference with the above tools is that it is a library rather than a software: its purpose is to be used in other programs, whether these programs are simple scenarios of full-fledged software. Finally, JBOTSIM is distributed under the terms of the LGPL licence, which makes it easily extensible by the community.

Whether the algorithms are centralized or distributed, the natural way of programming in JBOTSIM is event-driven: algorithms are specified as subroutines to be executed when particular events occur (appearance or disappearance of a link, arrival of a message, clock pulse, etc.). Movements of the nodes can be controlled either by program or by means of live interaction with the mouse (adding, deleting, or moving nodes around with left-click, rightclick, or drag and drop, respectively). These movements are typically performed while the algorithm is running, in order to visualize it or test its behavior in challenging configurations.

The present document offers a broad view of JBOTSIM's main features and design traits. I start with preliminary information in Section 2 regarding installation and documentation. Section 3 reviews JBOTSIM's main components and specificities such as programming paradigms, clock scheduling, user interaction, or global architecture. Section 4 zooms on key features such as the exchange of messages between nodes, graph-level APIs, or the creation of online demos. Finally, I discuss in Section 5 some extensions of JBOTSIM, including TikZ exportation feature and edge-markovian dynamic graph generator.

Besides its features, the main asset of JBotSim is its simplicity of use -an aim that I pursued at the cost of re-writing it several times from scratch (the API is now stable).

PRACTICAL ASPECTS

In this short section, I show how to install JBOTSIM and run it with a first basic example (this step is not required to keep reading the present document). I also provide links to online documentation and examples, for readers who would like to explore JBOTSIM's features beyond this paper.

Fetching JBOTSIM

The straightest (and safest) way to obtain JBOTSIM is to fetch the latest release, as a jar package on JBOTSIM's website [START_REF]JBOTSIM's website[END_REF]. One can also get the latest development version from SourceForge's GIT repository and compile it as shown below, keeping in mind that online documentation refers to the official release rather than this version. Here is the command: > git clone git://git.code.sf.net/p/jbotsim/git target where target is the local directory in which to put JBOTSIM. From that directory, one can produce the JAR package using a simple make.

After more than seven years of development, JBOTSIM is finally approaching version 1.0 (as of today, version 1.0-prealpha) and I think it is ready to be tested by the community. How to use the JAR file and run the HelloWorld example:

First steps

• If using IntelliJ, go to Project structure > Modules (select the module) > Dependencies > "+" and add jbotsim.jar.

• If using Eclipse, go to Project > Properties > Java build path > Librairies > Add external jar and add jbotsim.jar.

• From the terminal, the following commands can be used: javac -cp jbotsim.jar HelloWorld.java (compilation) java -cp .:jbotsim.jar HelloWorld (execution)

By running the program, one should see an empty gray surface in which nodes can be added, moved, or deleted using the mouse.

Sources of documentation

In this document, I provide a general overview of what JBOTSIM is and how it is designed. This is by no means a comprehensive programming manual. The reader who wants to explore further some features or develop complex programs with JBOTSIM is referred to the API documentation (see javadoc on the website).

Examples can also be found on JBOTSIM's website, together with comments and explanations. These examples offer a good starting point to learn specific components of the API from an operational standpoint -the present document essentially focuses on concepts. Most of the online examples feature embedded videos. Finally, most of the examples in this paper are also available on JBOTSIM's website. Feel free to check them when the code given here is incomplete (e.g. I often omit package imports and main() methods for conciseness).

FEATURES AND ARCHITECTURE

This section provides an overview of JBOTSIM's key features and discusses the reason why some design choices were made. I review topics as varied as programming paradigms, clock scheduling, user interaction, and global architecture. JBOTSIM consists of a small number of classes, the most central being Node, Link, and Topology. The contexts in which dynamic networks apply are varied. In order to accommodate a majority of cases, these classes offer a number of conceptual variations around the notions of nodes and links. Nodes may or may not possess wireless communication capabilities, sensing abilities, or self-mobility. They may differ in clock frequency, color, communication range, or any other user-defined property. Links between the nodes account for potential communication among them. The nature of links varies as well; a link can be directed or undirected, as well as it can be wired or wireless -in the latter case JBOTSIM's topology will update the set of links automatically, as a function of nodes distances and communication ranges.

Basic features of nodes and links

Figures 1 and2 illustrate two different contexts. Figure 1 depicts a highway scenario where three types of nodes are used: vehicles, road-side units (towers), and central servers. This scenario is semiinfrastructured: Servers share a dedicated link with each tower. These links are wired and thus exist irrespective of distance. On the other hand, towers and vehicles communicates through wireless links that are automatically updated. Figure 2 illustrates a purely ad hoc scenario, whereby a heterogeneous swarm of UAVs and robots strives to clean a public park collectively. In this scenario, robots can detect and clean wastes of a certain type (red or blue) only if these are within their sensing range (depicted by a surrounding circle). However, they are pretty slow to move and cannot detect remote wastes. In the meantime, a set of UAVs is patrolling over the park at higher speed and with larger sensing range. Whenever they detect a waste of some type, they store its position and start searching for a capable robot. In addition to sensing capabilities, UAVs can exchange messages with each other to optimize the process.

Besides nodes and links, the concept of topology is central in JBOTSIM. Topologies can be thought of as containers for nodes and links, together with dedicated operations like updating wireless links. They also play a central role in JBOTSIM's event architecture, as explained later on.

Distributed vs. centralized algorithms

JBOTSIM supports the manipulation of centralized or distributed algorithms (possibly simultaneously). The natural way to implement a distributed algorithm is by extending the Node class, in which the desired behavior is implemented. Centralized algorithms are not constrained to a particular model, they can take the form of any standard java class.

Distributed algorithm.

JBOTSIM comes with a default type of node that is implemented in the Node class. This class provides the most general features a node could have, including primitives for moving, exchanging messages, or tuning basic parameters (e.g. communication range and sensing range). Distributed algorithms are naturally implemented through adding specific features to this class. Listing 2 provides a basic example in which the nodes are endowed with self-mobility. The class relies on a key mechanism in JBOTSIM: performing periodic operations that are triggered by the pulse of the system clock. This is done by overriding the onClock() method, which is called periodically by JBotSim's engine (by default, at every pulse of the clock). The rest of the code is responsible for moving the node, setting a random direction at construction time nodes of the desired type (here, MovingNode) are added through the addNode() method at random locations (using -1 for xcoordinate or y-coordinate generates a random location for that coordinate; here both are random). In order to use MovingNode through the GUI, for instance when clicking with the mouse to add new nodes, this class must be registered as a node model. This is done by calling method setDefaultNodeModel() with the class itself as an argument, as shown on Listing 4. JBOTSIM will create new instances on the fly, using reflexivity. Several models can be registered simultaneously, using setNodeModel() with an additional argument that corresponds to the model name. If several models exist, JBOTSIM's GUI (the viewer) displays a selection list when a node is added by the user (in this example, only one model is set and it is used by default). In the scenario of Fig- new JViewer(tp); } ure 1, however, left-clicking on the surface would give the choice between car, tower, and server, the names of the three registered models for that scenario.

Centralized algorithms.

There are many reasons why a centralized algorithm can be preferred over a distributed one. The object of study might be centralized in itself (e.g. network optimization, scheduling, graph algorithms in general). It may also be simpler to simulate distributed things in a centralized way. Listing 5 implements such a version of the random waypoint mobility model, in which nodes repeatedly move toward a randomly selected destination, called target. Unlike a distributed implementation, the movements of nodes are here driven by a global loop at every pulse of the clock. For each node, a target is created if it does not exists yet or if it has just been reached; then the node's direction is set accordingly and the node is moved (by default, by 1 unit of distance). For convenience, the main() method is included in the same class.

Notice the use of setProperty() and getProperty() in this example. These methods allow to store any object directly into a node, using a key/value scheme (where key is a string). Both Link and Topology objects offer the same feature.

Architecture of the event system

So far, we have seen one type of event: clock pulses, to be listened to through the ClockListener interface. JBOTSIM offers a number of such events and interfaces, some of which become are ubiquitous. The main ones are depicted on Figure 3 on the following page. This architecture allows one to specify dedicated operations in reaction to various events. For instance, one may ask to be notified whenever a link appears or disappears somewhere. Same for messages, which are typically listened to by the nodes themselves or can be watched at a global scale (e.g. to keep a log of all communications). In fact, every node is automatically notified for its own events; it just needs to override the corresponding methods from the parent class Node in order to specify event handlings (e.g. onClock(), onMessage(), onLinkAdded(), onSensingIn(), onSelection(), etc.). Explicit listeners, on the other hand, like the ones in Figure 3, are meant to be used by centralized programs which do not extend class Node.

Listing 6 gives one such example, consisting of a mobility trace recorder. This program listens to topological events of various kinds, including appearance or disappearance of nodes or links, and movements of the nodes. Upon each of these events, it outputs a string representation of the event using a dedicated human readable format called DGS [START_REF] Dutot | GraphStream: A Tool for bridging the gap between Complex Systems and Dynamic Graphs[END_REF]. Similar code could be written for Gephi [START_REF] Bastian | Gephi: An open source software for exploring and manipulating networks[END_REF].

Other events exist besides those represented in Figure 3, such as the SelectionListener interface, which makes it possible to be notified when a node is selected (middle-click) and make it initiate some tasks, for instance broadcast, distinguished role, etc.

Single threading: why and how?

It seems convenient at first, to assign every node a dedicated thread, however JBOTSIM was designed differently. JBOTSIM is single-threaded, and definitely so. This section explains the why and the how. Understanding these aspects are instrumental in developing well-organized and bug-free programs. println("an " + node.hashCode() + " x:" + node.getX() + " y:" + node.getY()); } public void onNodeRemoved(Node node) { println("dn " + node.hashCode()); } // ConnectivityListener public void onLinkAdded(Link link) { println("ae " + link.hashCode() + " " + link.endpoint(0) + " " + link.endpoint(1)); } public void onLinkRemoved(Link link) { println("de " + link.hashCode()); } // MovementListener public void onNodeMoved(Node node) { println("cn " + node.hashCode() + " x:" + node.getX() + " y:" + node.getY()); } }

In JBOTSIM, all the nodes, and in fact all of JBOTSIM's life (GUI excepted) is articulated around a single thread, which is driven by the central clock. The clock pulses at regular interval (whose period can be tuned) and notifies its listeners in a specific order. JBOTSIM's internal engines, such as the message engine, are served first. Then come those nodes whose wait period has expired (remind that nodes can choose to register to the clock with different periods). These nodes are notified in a random order. Hence, if all nodes listen to the clock at a rate of 1 (the default value), they will all be notified in a random order in each round, which makes JBOTSIM's scheduler a non-deterministic 2-bounded fair scheduler. (Other policies will be available eventually.) A simplified version of the current scheduling process is depicted on Figure 4.

One consequence of single-threading is that all computations (GUI excepted) take place in a sequential order that makes it possible to use unsynchronized data structures and simpler code. This also improves the scalability of JBOTSIM when the number of nodes grows large. One can rely on other user-defined threads in the program, however one should be careful that these thread do not interfer with JBOTSIM's. The canonical example is when a sce- nario is set up by program from within the thread of the main() method. If the initialization makes extensive use of JBOTSIM's API from within that thread and the clock starts triggering events at the same time, then problems might occur (and a Concurrent ModificationException be raised). The easy way around is to pause the clock before executing these instructions and to resume it after (using the pause() and the resume() methods on the topology, respectively).

Interactivity

I designed JBOTSIM with a clear separation in mind between GUI and internal features. In particular, it can be run without GUI (i.e. without creating the JViewer object), and things will work exactly the same, though invisibly. As such, JBOTSIM can be used to perform batch simulations (e.g. sequences of unattended runs that log the effects of some varying parameter). This also enables to withstand heavier simulations in terms of the number of nodes and links.

This being said, one of the most distinctive features of JBOTSIM remains interactivity, e.g., the ability to challenge the algorithm in difficult configurations through adding, removing, or moving nodes during the execution. This approach proves useful to think of a problem visually and intuitively. It also makes it possible to explain someone an algorithm through showing its behavior.

The architecture of JBOTSIM's viewer is depicted on Figure 5. As one can see, the viewer relies heavily on events related to nodes, links, and topology. The influence also goes the other way, with mouse actions being translated into topological operations. These features are realized by a class called JTopology. This class can often be ignored by the developer, which creates and manipulates the viewer through the higher JViewer class. The latter adds external features such as tuning slide bars, popup menus, or self-containment in a system window.

While natural to JBOTSIM's users, the viewer remains, in all technical aspects, an independent piece of software. Alternative viewers could very well be designed with specific uses in mind.

container. This feature enables the customization of JBOTSIM's UI at will, as well as the creation of java applets. (which is a JPanel) is created manually from the topology. Its reference is then used to augment it with standard viewer features, and finally added to the applet container. Another important step is to pause the clock in the destroy() method (otherwise JBot-Sim's engine would keep running in background).

CONCLUDING REMARKS

I my view, JBOTSIM is a kernel, in the sense that it encapsulates a number of generic features whose purpose is to be used by higher programs. As of today, the plan is to keep it this way and try containing the growth of the number of features, to the profit of quality and simplicity. This does not mean, of course, that JBOT-SIM should not be extended externally.

In particular, JBOTSIM's distribution already incorporates an extension package called jbotsimx, in which more specific features could be found. For instance, it incorporates a static class called Tikz that makes it possible to export the current topology as a TikZ picture -a powerful format for drawing pictures in L A T E X documents. Figure 6 Once exported as a Tikz picture, they were twicked manually to add shading, color, etc.

have generated. The Tikz class is composed of a single method, exportAsTikz(), which takes a mandatory Topology argument, and an optional scaling argument. Other extensions include basic topology algorithms for testing, e.g., if a given topology is connected or 2-connected, if a given node is critical (its removal would disconnect the graph) or compute the diameter. A set of extensions dedicated to dynamic graph are currently being developped (by myself and others). For instance, the EMEGPlayer takes as input a birth rate, death rate, and an underlying graph (given as a Topology), and generates an edgemarkovian dynamic graph based on these parameters, the dynamics of which can be listened to through the ConnectivityListener interface.

Contributions are most welcome, as well as suggestions of improvement or feature requests.

Figure 1 :

 1 Figure 1: A highway scenario composed of vehicles, road-side units, and central servers. Part of the network is ad hoc (and wireless); the rest is infrastructured (and wired).

Figure 2 :

 2 Figure 2: A swarming scenario, whereby mobiles robots and UAVs collaborate in order to clean a public park.

Listing 4

 4 Using a defined node as default public static void main(String[] args){ Topology tp = new Topology(400, 300); tp.setDefaultNodeModel(MovingNode.class);

Figure 3 :Listing 6

 36 Figure 3: Main sources of events and corresponding interfaces in JBOTSIM.

TopologyFigure 4 :

 4 Figure 4: Simplified version of the internal scheduler.

  illustrates this with two pictures that I

Figure 6 :

 6 Figure 6: Two examples of pictures whose underlying topology was generated using JBOTSIM Tikz extension. The topology on the left was created by adding and moving nodes using the mouse; the topology on the right was generated by program. Once exported as a Tikz picture, they were twicked manually to add shading, color, etc.

  As a first program, one can copy the code from Listing 1 into a file named HelloWorld.java.

	Listing 1 HelloWorld with JBOTSIM
	import jbotsim.Topology;
	import jbotsim.ui.JViewer;
	public class HelloWorld{
	public static void main(String[] args){
	new JViewer(new Topology());
	}
	}

  Listing 2 Extending the Node class (in radian), then moving in this direction periodically. (More details about the movement API can be found online.)Once this class is defined, new nodes of this type can be added to the topology in the same way as if they were of class Node, as illustrated in Listing 3. Here, a new topology is created first, then 10

	import jbotsim.Node;
	public class MovingNode extends Node{
	public MovingNode(){
	setDirection(Math.random() * 2 * Math.PI);
	}
	public void onClock(){
	move(2);
	}
	}
	Listing 3 Adding nodes manually
	public static void main(String[] args){
	Topology tp = new Topology(400,300);
	for (int i=0; i<10; i++)
	tp.addNode(-1,-1, new MovingNode());
	new JViewer(tp);
	}

  Listing 5 Centralized version of Random Waypoint

	public class CentralizedRWP implements ClockListener{
	Topology tp;
	public CentralizedRWP (Topology tp){
	this.tp = tp;
	tp.addClockListener(this);
	}
	public void onClock(){
	for (Node n : tp.getNodes()){
	Point2D target=(Point2D)n.getProperty("target");
	if (target == null || n.distance(target)<1){
	target = new Point2D.Double(Math.random() * 400,
	Math.random() * 300);
	n.setProperty("target", target);
	n.setDirection(target);
	}
	n.move();
	}
	}
	public static void main(String[] args){
	Topology tp = new Topology(400,300);
	new CentralizedRWP(tp);
	new JViewer(tp);
	}
	}

  Listing 9 shows an example java applet corresponding to the HelloWorld program from Listing 1. Here, a JTopology object Listing 9 Embedding a JBOTSIM demo into a java applet

	import javax.swing.JApplet;
	import jbotsim.Clock;
	import jbotsim.Topology;
	import jbotsim.ui.JTopology;
	import jbotsim.ui.JViewer;
	@SuppressWarnings("serial")
	public class HelloWorld_Applet extends JApplet{
	Topology tp;
	public void init(){
	tp = new Topology();
	JTopology jtp = new JTopology(tp);
	new JViewer(jtp, false);
	this.add(jtp);
	}
	public void destroy(){
	tp.pause();
	}
	}

JTopology

A ZOOM ON SELECTED FEATURES

This section provides more details on a handful of selected features. It covers, namely, the topics of message passing, graph-level algorithms, and java applets for online web demos.

Exchanging messages

The way messages are used in JBOTSIM is independent from the communication technology considered. Indeed, the API is quite simple, messages are sent directly by the sender, through calling the send() method on its own instance (inherited from Node). Messages are typically received through overriding the onMessage() method (also from class Node). Another way to receive messages, which is not event-based, is for a node to check its mailbox manually through the getMailbox() method, for instance when it is executing the onClock() method (this is the natural way to implement round-based communication models).

Listing 7 shows a message-based implementation of the flooding principle. Initially, none of the nodes are informed. Then, if a node is selected (either through middle-click or through direct call to the selectNode() method), then this node is notified in the onSelection() method and initiates a basic broadcast scheme. Here, the algorithm consists in retransmitting the received message upon first reception to all the local neighbors (sendAll()). In this example, the message is empty, however in general any object can be inserted in the message (no copy is made and the very same object is to be delivered, unless a copy is made at sending time). By default, a message takes one time unit to be transmitted (i.e. it is delivered at the next clock pulse). The delivery happens only for those links which exist by the time of reception. Since any object can be used as message content, it often has to be cast upon reception. All these aspects correspond to JBOTSIM's default message engine. Other message engines can be written, and indeed some exist in the jbotsimx package. For instance, the DelayMessageEngine makes it possible to add deterministic or random delays to the delivery of messages, possibly even in a non FIFO manner. Implementing an algorithm in the message passing model is sometimes difficult. JBOTSIM makes it possible to sketch an idea, play with it, and share it with others, in minutes, thanks to working at a (more abstract) graph-level. This level of abstraction also is relevant in its own right, when the object of study is itself at the graph level, such as classical graph algorithms or distributed coarse-grain models like graph relabeling systems [START_REF] Litovsky | Graph relabelling systems and distributed algorithms[END_REF] or population protocols [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF].

Working at the graph level

To illustrate the simplicity of the graph level, let us consider a scenario where a type of node called SocialNode, dislikes being isolated. Such a node is happy (green) if it has at least one neighbor, unhappy (red) otherwise. In the message passing paradigm, this principle would require to send periodic messages (beacons) and track the reception of these messages, as well as using a timer to decide when a node becomes isolated. Listing 8 shows a possible implementation at the graph level, which is pretty concise and self-explanatory. Topological events are directly detected by the nodes, which can update their status. (These events could also be listened to globally through the ConnectivityListener() interface. This is the way one might want to implement centralized dynamic graph algorithms.) Of course, from a message passing perspective, this implementation is cheating. Thus, methods like onLinkAdded(), hasNeighbors(), or getNeighbors() should not be used in a message-passing setting.

Embedding JBOTSIM in a java applet

One of the features of JBOTSIM's viewer is to create a windowed frame automatically for the topology. This is the default behavior of JViewer's constructor when a single parameter of type Topology or JTopology is used. Other behaviors can be obtained by using different versions of the constructor. In particular, one can specify that no windowed frame should be created, and the JTopology object be plugged manually into a different


Carlos Gómez-Calzado
email: carlos.gomez@ehu.es

Arnaud Casteigts
email: arnaud.casteigts@labri.fr

Alberto Lafuente
email: alberto.lafuente@ehu.es

Mikel Larrea
email: mikel.larrea@ehu.es

A Connectivity Model for Agreement in Dynamic Systems

The consensus problem is a fundamental paradigm in distributed systems, because it captures the difficulty to solve other agreement problems. Many current systems evolve with time, e.g., due to node mobility, and consensus has been little studied in these systems so far. Specifically, it is not well established how to define an appropriate set of assumptions for consensus in dynamic distributed systems. This paper studies a hierarchy of three classes of time-varying graphs, and provides a solution for each class to the problem of Terminating Reliable Broadcast (TRB). The classes introduce increasingly stronger assumptions on timeliness, so that the trade-off between weakness versus implementability and efficiency can be analysed. Being TRB equivalent to consensus in synchronous systems, the paper extends this equivalence to dynamic systems.

Introduction

The consensus problem is a central paradigm in distributed systems, as it represents many agreement problems, e.g., leader election, atomic commitment and total-order broadcast. Solving consensus has attracted a lot of attention in dependable computing and has generated fundamental results. In this regard, it is known that in crash-prone asynchronous distributed systems it is impossible to solve consensus deterministically due to the impossibility of distinguishing between "slow" processes and crashed ones, a result known as FLP impossibility [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF]. Alternatively, consensus can be easily solved in synchronous systems, where perfect failure detection can be implemented [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF].

Most of the research on consensus has considered a static distributed system with permanent connectivity among nodes. In many current distributed systems, however, these assumptions are not valid any more. Instead, these new systems exhibit a dynamic behavior, with nodes joining the system, leaving it or just moving, which implies uncertain connectivity conditions. Indeed, and unlike in classical static systems, these events are no longer considered incorrect or sporadic behaviors, but rather the natural dynamics of the system.

Clearly, even the synchrony assumptions of classical (static) models of distributed systems are not enough to solve agreement problems in dynamic systems. For example, having an upper bound on link latencies is pointless if the link is not available at the time of transmission of the message. Note however that the nodes could still communicate using an alternative path in the network. Thus, assumptions should consider the overall system connectivity, which encourages for a holistic approach to model dynamic distributed systems.

In recent years there was a rising interest in modeling dynamic distributed systems from the perspective of graph theory. In this regard, there exist several works that study the solvability of deterministic problems, including consensus, in highly-dynamic systems [START_REF] Biely | Agreement in directed dynamic networks[END_REF][START_REF] Casteigts | Shortest, Fastest, and Foremost Broadcast in Dynamic Networks[END_REF][START_REF] Fernández-Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF][START_REF] Kuhn | Distributed computation in dynamic networks[END_REF][START_REF] Kuhn | Dynamic networks: models and algorithms[END_REF]. However, regarding consensus, none of them lowers the assumptions to the realm of temporal connectivity, i.e., not requiring that the graph be connected at every instant, but only that paths exist over time and space (temporal path, aka journeys). The time-varying graph formalism [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] (TVG, for short) provides a useful qualitative framework to model dynamic distributed systems. In this formalism, the dynamic network is represented as a graph, together with a presence function that tells whether a given edge is present at a given time and a latency function that tells how long it takes to cross a given edge at a given time. In [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF], Casteigts et al. define a hierarchy of classes of dynamic networks, most of which are based on temporal connectivity concepts. Among them, the recurrent connectivity class requires that a journey exists between any two nodes infinitely often (that is, recurrently). Nevertheless, this class lacks the necessary timeliness (i.e. time bounds in communication) to describe the specific assumptions that are required by synchronous agreement algorithms, such as TRB, to terminate. One of the goals of our paper is to extend some of the existing TVG classes by introducing timeliness constraints, together with practical considerations, and analyze the impact of these new constraints on solving consensus.

Our contribution

In this paper, we address timeliness in evolving systems (i.e., time-varying graphs, TVG) from a synchronous point of view, i.e., systems where the transmission delay of messages is bounded and the bound is known a priori by the processes. The resulting set of concepts and mechanisms makes it possible to describe system dynamics at different levels of abstraction and with a gradual set of assumptions.

We first formulate a very abstract property on the temporal connectivity of the TVG, namely, that the temporal diameter (i.e. maximum duration of a foremost journey) of a component in the TVG is always bounded by ∆. We refer to such a component as a ∆-component, and define the concept of correct process in terms of this component. We then specify a version of the Terminating Reliable Broadcast problem (TRB) for ∆-components, which we relate to the ability of solving agreement at component level.

Although ∆-components are proven to be a sufficient concept at the most abstract level, they rely on non implementable communication patterns in message-passing systems. Indeed, the solution to TRB proposed in this abstract model relies on an oracle that provides the algorithm with instantaneous knowledge of the appearance of an edge. Unfortunately, this oracle does not have a straightforward implementation in terms of real processes and communication links. Therefore, we introduce a first constraint to force the existence of journeys whose edges presence duration is lower-bounded by some duration β (which holds a relation to the maximal latency of a link), thereby enabling repetitive communication attempts to succeed eventually. These journeys are called β-journeys and their existence makes it possible to implement the TRB algorithm without oracle. We then look at a further constrained class of TVG, inspired by the work of Fernández-Anta et al [START_REF] Fernández-Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF], whereby the local appearance of the edge used by every next hop of (at least one of the possibly many) β-journeys also must be bounded by some duration α, yielding to the concept of (α, β)-journeys. The existence of recurrent (α, β)-journeys allows the nodes to stop sending a message α time after they receive it, which is much more efficient.

The rest of the paper is organized as follows. Section 2 introduces basic time-varying graph notations, used in Section 3 to define the abstract timely connectivity model based on ∆-components. In the same section we redefine the TRB problem with respect to ∆components and give a solution to it. Then, in Section 4, we introduce β-journeys (and the corresponding β-components), which we show to be sufficient to implement an effective (i.e., oracle-free) version of the algorithm. We then define (α, β)-journeys and components, and discuss their advantages (and disadvantages) over β-journeys. In Section 5, we describe how consensus can be solved by using the TRB implementations introduced in Sections 3 and 4. We finally conclude in Section 6 with open questions and future work.

Time-Varying Graphs

A recent framework called time-varying graphs, proposed by Casteigts et al. [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF], aims to provide a precise formalism for describing dynamic networks. As usual, the entities of the system and the communication links between them are represented as a graph. More specifically, a time-varying graph (TVG, for short) is defined as a tuple G = (V, E, T , ρ, ζ), where: -V is the set of communicating entities (or nodes, or processes, interchangeably). -E is the set of edges (or links, interchangeably) that interconnect the nodes in V. In this work, all edges are undirected. -T is the lifetime of G, i.e. the interval of time over which the graph is defined. It is a subset of the temporal domain T, itself being N or R + depending on whether time is discrete or continuous (in this work, it is continuous). For convenience, both endpoints of T are referred to as T -and T + , the latter being possibly +∞. -ρ : E × T → {true, f alse}, i.e., the presence function, indicates whether a given edge is present at a given time (i.e., ρ(e, t) = true iff edge e is present at time t) -ζ : E × T → T, i.e., the latency function, indicates how long it takes to send a message across a given edge for a given emission time (assuming the edge is present at that time)

The kind of network we are addressing is possibly disconnected at every instant. Still, a form of communication can be achieved over time by means of journeys (a.k.a. temporal path). Formally, a journey J = {((e 1 , t 1 ), (e 2 , t 2 ), . . . , (e k , t k ))} is a sequence such that (e 1 , e 2 , . . . , e k ) is a valid path in the underlying graph (V, E), and (1) for every i ∈ [1, k] edge e i is present at time t i long enough to send a message across (formally, ρ(e i , t i + δ) = true for all δ ∈ [0, ζ(e i , t i )]), and (2) the times when edges are crossed (we also say activated) and the corresponding latencies allow a sequential traversal (formally, t i+1 ≥ t i + ζ(e i , t i ) for all i ∈ [1, k)). What makes this form of connectivity temporal is the fact that a journey can pause in between hops, e.g. if the next link is not yet available.

Given a journey J , departure(J ) and arrival(J ) denote respectively its starting time t 1 and its ending time t k + ζ(e k , t k ). Journeys can be thought of as paths over time, having both a topological length k (i.e., the number of hops) and a temporal length (i.e., a duration) arrival(J )-departure(J ) = t k + ζ(e k , t k ) -t 1 . Note that journeys describe opportunities of communication between an emitter and a receiver. J * G is the set of all such opportunities over G's lifetime, while J * (p,q) ⊆ J * G are those journeys from p to q. A simplified way of denoting the existence of a journey between a process p and a process q, when the context of G is clear, is p ; q. Finally, the graph is temporally connected if for every p, q ∈ V, p ; q.

An induced sub-TVG G ⊆ G is obtained by restricting either the set of vertices V ⊆ V or the lifetime T ⊆ T , resulting in the tuple (V , E , T , ρ , ζ ) such that:

-(V , E ) is the subgraph of (V, E) induced (in the usual sense) by V -ρ : E × T → {true, f alse} where ρ (e, t) = ρ(e, t) -ζ : E × T → T where ζ (e, t) = ζ(e, t)
If only the lifetime is restricted, say to some interval [t a , t b ), then the resulting graph G is called a temporal subgraph of G and denoted G [ta,t b ) . The temporal diameter of a graph G at time t is the smallest duration d such that G [t,t+d) is temporally connected.

Finally, following Bhadra and Ferreira in [START_REF] Bhadra | Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks[END_REF], we consider a temporal variant of connected components (hereafter, simply called components), which are maximal sets of nodes V ⊆ V such that ∀p, q ∈ V , p ; q. Two variants are actually considered, whether the corresponding journeys can also use nodes that are in V \ V (open components) or not (closed components). Observe that a close component is equivalent to an induced sub-TVG being temporally connected.

A Timely Model for Dynamic Systems

This section focuses on the analysis of timeliness in dynamic systems at the most abstract level, i.e. considering only a general communication bound ∆ for end-to-end communication. We first provide a set of definitions related to this bound, which leads to the formulation of a new class of TVGs that is a strict subset of Class 5 (recurrent connectivity) in [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF]. We then specify a solution to the problem of Terminating Reliable Broadcast (TRB) in the corresponding context.

Definitions

We define the concept of bounded-time journey as follows:

Definition 1. A journey J is a ∆-journey if and only if arrival(J ) -departure(J ) ≤ ∆.
Based on ∆-journeys we define the concept of bounded-time component. Unlike components, we require here that connectivity also be recurrent by definition.

Definition 2. A ∆-component in G = (V, E, T , ρ, ζ) is a set V ⊆ V such that for every t in [T -, T + -∆],
for every p, q in V , there exists a ∆-journey from p to q in G [t,t+∆) .

Similarly to components, ∆-components can be open or closed, depending on whether the ∆-journeys use nodes in V \ V . Observe that, a graph behaving in an open way provides flexibility in mobility, and therefore, a model allowing open ∆-components is weaker (in the sense that it requires less assumption) than a model strictly based on closed ∆-components. Henceforth we assume that in our system model ∆-components are by default open.

Informally, ∆-components allow us to think about subsets of nodes behaving timely with each other. Hence, nodes in a ∆-component are also timely connected. We define the (parametrized) class of timely (and recurrently) connected TVGs T C(∆) as follows:

Definition 3. G ∈ T C(∆) ⇐⇒ V is a ∆-component.

Terminating Reliable Broadcast in T C(∆)

According to [START_REF] Feldman | Optimal algorithms for byzantine agreement[END_REF], consensus is equivalent to Terminating Reliable Broadcast in static synchronous systems. We take this as a starting point and describe here a solution for TRB in the scope of a ∆-component.

We assume that processes know a global time. Processing times are negligible with respect to communication time. The system is composed by processes that can crash/recover, and leave/join the system. Processes that crash or leave the system, even if they recover or join again later, are by definition excluded from any ∆-component, however since we assume the existence of open ∆-components, they can punctually take part on various journeys.

Recall that a distributed system G may have several ∆-components. There may exist values of ∆ for which a process belongs to different components, which are thus overlapping. However, since every component is recurrently connected, then overlapping components become naturally merged as the value for ∆ increases, and transitively, there must exist a sufficiently large value of ∆ such that all remaining components are disjoint. Henceforth, we consider ∆ to be (an upper bound on) such a value.

We define now which processes are correct in terms of the classical terminology. In a classical partitioned system it can be considered that a process p behaves correctly in its partition, and incorrectly with respect to the other partitions in the system. Similarly, in our ∆-component based system a process p behaves correctly with respect to the ∆-component p belongs to, e.g. C. Hence, a member of a ∆-component C is by definition correct with respect to C. However p could still sporadically communicate timely with some processes in another ∆-component, C . Obviously, we consider p incorrect with respect to C , but a message m from p received by some process in C should either be delivered by all processes in C , or by none of them in order to hold the agreement property of reliable broadcast.

Thus, in T C(∆) a set of properties should be hold by a process with respect to a ∆component in order to provide ∆-TRB:

-∆-Termination: Every process in the same ∆-component eventually delivers some message. -∆-Validity: If a process in a ∆-component broadcasts a message m, then all processes in the same ∆-component eventually deliver m. -∆-Agreement: If a process in a ∆-component delivers a message m, then all processes in the same ∆-component eventually deliver m.

-∆-Integrity: For any message m, every process in the same ∆-component delivers m at most once, and if it delivers m = SF (sender faulty) then the sender(m) must have broadcast m.

As usual, the broadcast at time t init of a message m is considered in the scope of m.

To guarantee the ∆-Agreement property we should correctly understand when a message m broadcast by p / ∈ C should be delivered by all processes in C. If p has been able to propagate m to some process q ∈ C, then we assume that there exists a ∆-journey from p to q. Observe that this assumption is consistent with the fact that our model allows the existence of open ∆-components. A solution to the TRB problem is described in Figure 1 (see [START_REF] Gómez-Calzado | A Connectivity Model for Agreement in Dynamic Systems[END_REF] for details). Informally, the distinguished process p B ∆-TRBroadcasts a message m by sending m on all its active edges at time t init . Whenever an edge in p B 's neighborhood appears 3 , p B also sends m on that edge. Every other process p, upon reception of m for the first time, forwards m on all its active edges, as well as upon the appearance of a new edge. Finally, at time t init + 2∆ every process p ∆-TRBdelivers either m (if m has been received) or SF .

We explain next why a time of 2∆ is necessary and sufficient to deliver m.

Observe that, since we are assuming that p B could be not in C, p B could not be able to communicate to all nodes in C in ∆ time, (otherwise p B ∈ C), thus, after m is resent by q, every process in C will receive m into a second ∆ time interval. Henceforth the bound for a process in C to T RDeliver a message is 2∆.

Theorem 1. The specification in Figure 1 satisfies the properties of ∆-TRB in T C(∆).

Implementability of TRB

The specification of TRB provided in Figure 1 relies on an "oracle" available at every process p, which informs p instantaneously upon appearance of a new edge in its neighbourhood. Such an abstraction has been recently used by Raynal et al. [START_REF] Raynal | A simple broadcast algorithm for recurrent dynamic systems[END_REF] to implement a broadcast algorithm for recurrent dynamic systems. However, a strict implementation of this oracle in a real system is far from being trivial, as we discuss now.

Observe that the only temporal assumption on ∆-journeys is that they satisfy a given upper-bound ∆ in its temporal length, thus the duration of an edge may be as short as the latency of the message. In consequence, an implementation of this oracle should be able to allow the sending of a message at the very same time that the edge get activated, which is unrealistic since the oracle should be able to predict the behaviour of the links in a real network. Alternatively, an algorithm could continuously send message m along the whole time interval in the hope that one of the sending attempts will success in the appearance of an edge. Observe, however, that this iteration would require a period of time zero between two consecutive sends. In other words, the algorithm should be able to send an infinite number of messages per unit of time, which is impossible.

Therefore, additional assumptions should be introduced in order to provide an implementation for the above specification of TRB. Specifically we first propose an extra assumption that allow to maintain active the edge not only for communicating the message but also to detect its appearance.

(Lower)-bounding the edge stability

We assume that the edge latency is bounded, i.e, there exist a bound on max{ζ(e, t) : t ∈ T , e ∈ E}, that we call ζ M AX . Additionally, we assume that edges are active at least β time. Let us call β-edge an edge that fulfils this bounded disposability. For this new model we define β-journeys as follows: Definition 4. A β-journey J = {((e 1 , t 1 ), . . . , (e k , t k ))} is a ∆-journey such that:

1. ζ M AX < β ≤ ∆. 2. ∀i ∈ [1, k), e i is a β-edge. 3. the times when edges are activated and their corresponding latencies allow a bounded sequential traversal (formally, ∀i ∈ [1, k), t i+1 ≥ t i + β).

We now define β-components as a subset of ∆-components that uses β-journeys. Formally:

Fig. 1 .

 1 Fig. 1. Terminating Reliable Broadcast for T C(∆).

We assume here the existence of an abstract oracle to capture events of edge appearance. In the next section we will board the implementation of such an oracle.

Research supported by the Spanish Research Council, grant TIN2013-41123-P, the Basque Government, grant IT395-10, and the University of the Basque Country UPV/EHU, grant UFI11/45. Carlos Gómez-Calzado is recipient of a doctoral fellowship from the Basque Government. This work has been carried out during a research stay of Carlos Gómez-Calzado at the University of Bordeaux. for his valuable comments.

Definition 5. A β-component is a ∆-component where a set V ⊆ V satisfies that ∀t ∈ [T -, T + -∆], V is a β-journey based temporal component in G [t,t+∆) .

We define the parametrized timely connectivity class T C (β) as follows:

TRB in T C (β)

We give now a TRB algorithm for the T C (β) model, which is shown in Figure 2.

To ∆-TRBroadcast a message m at time tinit: In the algorithm proposed in Figure 2 a process p B sends at time t init a message m by ∆-TRBroadcasting it, and p B keeps sending m each W time in order to assure the correct send of m by every β-journey. Observe that, according to the definition of β-edge, for a βedge e = (p, q) in a β-journey, if process p sends a message m on e each W ≤ β -ζ M AX time during ∆, q will receive m at least once (see [START_REF] Gómez-Calzado | A Connectivity Model for Agreement in Dynamic Systems[END_REF] for the complete correctness proof). When a process p receives the message m automatically ∆-TRDelivers m, and additionally, if p = p B , p sends m each W time during ∆. Finally, if a process does not receive the message m, at time t init + 2∆, it ∆-TRDelivers the special message SF .

Theorem 2. The specification in Figure 2 satisfies the properties of ∆-TRB in T C (β).

(Upper)-bounding the edge appearance

Observe that, in the algorithm in Figure 2 messages are forwarded during the whole ∆ interval. This is necessary because the ending edge of a β-journey could be activated at a time as late as t init + ∆ -β. It is apparent that more efficient implementations of a TRB algorithm in terms of number of messages could be envisaged if stronger connectivity assumptions are introduced in the model. Specifically, in this section we introduce an additional timely assumption on the appearance of edges.

We adopt the assumption of [START_REF] Fernández-Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF], where, besides β, a bound α on the appearance of links is defined. We define a new type of journey, that we call (α, β)-journey. Formally:

1. The appearance of e 1 is bounded by α. 2. The appearance of the subsequent edges are also bounded by α. Formally,

We define a (α, β)-component as follows:

We define the parametrized timely connectivity class T C (α, β) as follows:

The algorithm in Figure 3, describes a TRB algorithm executable in a T C (α, β) dynamic system.

The new bound α, altogether with the latency bound β and ζ M AX , allows to calculate global system bounds, namely the period W and a time to deliver Γ , strictly in terms of specific network parameters. In the algorithm proposed in Figure 3 a process p B ∆-TRBroadcast a message m at time t init by sending each W time m until the time is strictly higher than t init + α, in order to assure the correct sending of m by every (α, β)-journey. When a process p receives the message m at time t rec for the first time, automatically ∆-TRDelivers m and, additionally, if p = p B , p sends m each W until the time is strictly higher than t rec + α. Finally, if any of the process in p does not receive the message m at time t init + Γ , ∆-TRDelivers the special message SF denoting the sender failure.

A detailed explanation of how Γ is obtained can be found in the extended version of this paper [START_REF] Gómez-Calzado | A Connectivity Model for Agreement in Dynamic Systems[END_REF]. It is important to note that in the TRB algorithm for T C (α, β), differently to the previous classes, processes need to known the network diameter, which is bounded by |V | -1. This is a consequence of the fact of considering strictly local bounds in T C (α, β). Instead, both T C(∆) and T C (β) rely on a system-wide bound, ∆.

Theorem 3. The specification in Figure 3 satisfies the properties of ∆-TRB in T C (α, β).

Relating timely classes

We have defined a hierarchy of classes with increasingly stronger timely assumptions. Being T C(∆), T C (β) and T C (α, β) the parametrized classes, we define now for each one the union of all its possible instances:

To ∆-TRBroadcast a message m at time tinit:

G ∈ T C

In spite of the different strength of the parametrized classes, we show in [START_REF] Gómez-Calzado | A Connectivity Model for Agreement in Dynamic Systems[END_REF] that T C * ≡ T C * . Besides, T C * ⊂ T C * and T C * ⊂ T C * .

From ∆-TRB to ∆-Consensus in Dynamic Systems

In this section we analyse the equivalence between TRB and consensus, originally stated for synchronous static systems [START_REF] Feldman | Optimal algorithms for byzantine agreement[END_REF], in terms of a dynamic system as the one we have modelled.

In the previous sections we have presented three ∆-TRB algorithms in the scope of respectively ∆-, βand (α, β)-components. We show now how the consensus problem can be reduced 4 to a ∆-TRB problem. We will refer as ∆-Consensus to this kind of consensus in the scope of ∆-components.

By the properties of ∆-TRB, it is straightforward to define the ∆-Consensus properties as follows: 4 We say that a problem A can be reduced to a problem B if A can be solved using B.

-∆-Termination: Every process in the ∆-component eventually decides.

-∆-Agreement: Every process in the ∆-component decides the same value.

-∆-Validity: The decided value is a proposed one.

Without loosing generality we focus here on ∆-Consensus using the ∆-TRB specification of Figure 1 for the T C(∆) Class.

Vector

To ∆-Propose v at time tinit: The resulting ∆-Consensus algorithm is shown in Figure 4. Every process p holds a vector V p initialized to ⊥. At time t init , |V | instances of ∆-TRB are started, one per process, being each process the sender in one instance. Every process p records in vector V p (q) the message m q delivered from process q (or SF in case m q has not been received on time). At time t init + 2∆, p decides on the first non-SF value of V p .

Note that solving consensus at system level would require a second ∆-TRB round to agree on the decision of the majority, provided that the temporal interval [T -, T + ] in which the ∆-component is defined covers both rounds. In other words, the stability of ∆-components must be temporally extended to solve consensus at system level.

Conclusions

In this paper we studied how to introduce timeliness in evolving systems so that the resolution of agreement problems (specifically consensus) is possible. On the basis of previous works, we have adopted the concept of journey or temporal path and have introduced the necessary timeliness (i.e., time bounds) to describe the specific assumptions that are required by an agreement algorithm to terminate and satisfy the consensus properties.

We have first proposed a general class, T C(∆), with a very abstract property on the temporal connectivity of the TVG to provide the necessary stability conditions, namely, that the temporal diameter of a recurrent component in the TVG is bounded. We refer to such a component as a ∆-component. To approach the consensus problem we have defined a TRB specification in terms of ∆-components, ∆-TRB. However, ∆-TRB is not implementable in T C(∆) by message-passing without zero processing time assumptions. Henceforth, by introducing increasingly stronger connectivity assumptions, we have provided two implementable connectivity classes, namely T C (β) and T C (α, β), as well as two respective implementations of ∆-TRB in these classes. Finally, we have shown that consensus at ∆-component level is easily reduced to ∆-TRB.

An open issue is the search of the weakest connectivity class that allows to implement ∆-TRB (and henceforth consensus) in message-passing systems. Of additional interest is to extend the proposed classes to partially synchronous models. In this regard, in [START_REF] Gomez-Calzado | Fault-tolerant leader election in mobile dynamic distributed systems[END_REF], leader election is implemented in a partially synchronous system with dynamic partitions that could be modelled as ∆-components.