In this work, we address vertex partitioning problems in digraphs. We study whether it is possible to colour the vertices of a digraph with large out-degree so that every vertex has many out-neighbours of the same colour (related to conjectures by Bermond-Thomassen and questions of Alon), as well as the opposite question: whether it is possible to colour the vertices so that no vertex has many out-neighbours of the same colour (related to the majority colouring conjecture of Kreutzer et al.). We study both problems in detail for concave-round digraphs, a class introduced by Bang-Jensen, Huang, and Yeo. We also make progress on the majority colouring conjecture for tournaments.

A set V is separated by a family of sets F if for every pair of elements in V, there exists F ε f which contains exactly one of the elements of the pair. Given a tree T , we wish to separate V(T) only using sets of the form V(P) , where P is a path in T. We give closed formulas for sp (T) (the least size of such a separating family) in various classes of trees, including all trees without vertices of degree two. The formula we find depends on local parameters of the tree, such as its number of leaves. This parallels previous results for the edge-separation version of the problem. On the other hand, we give constructions of trees showing that as soon as we allow vertices of degree two, the local parameters we consider are not sufficient to describe sp( T ), thus uncovering a surprising and unexpected difference from previous results.

The two most intensively studied communication paradigms for spreading rumors are the so-called PUSH and PULL algorithms. The previous analysis of these protocols assumed that every node could process all such push/pull operations within a single step, which could be unrealistic in practical situations. We propose a new framework for the analysis of rumor spreading accommodating buffers, in which a node can process only few push/pull messages at a time. We develop time complexity upper and lower bounds for randomized rumor spreading in the new framework, and compare the results with analogous ones in the classical setting. Our results highlight that there might be a very significant performance loss if messages are processed at each network node in first-in first-out order.

In this paper, we consider the problem of assigning a set of clients with demands to a set of servers with capacities and degree constraints. The goal is to find an allocation such that the number of clients assigned to a server is smaller than the server's degree and their overall demand is smaller than the server's capacity, while maximizing the overall throughput. This problem has several natural applications in the context of independent tasks scheduling or virtual machines allocation. We consider both the offline (when clients are known beforehand) and the online (when clients can join and leave the system at any time) versions of the problem. We first show that the degree constraint on the maximal number of clients that a server can handle is realistic in many contexts. Then, our main contribution is to prove that even if it makes the allocation problem more difficult (NP-Complete), a very small additive resource augmentation on the servers degree is enough to find in polynomial time a solution that achieves at least the optimal throughput. After a set of theoretical results on the complexity of the offline and online versions of the problem, we propose several other greedy heuristics to solve the online problem and we compare the performance (in terms of throughput) and the cost (in terms of disconnections and reconnections) of all proposed algorithms through a set of extensive simulation results.

The peer sampling service is a core building block for gossip protocols in peer-to-peer networks. Ideally, a peer sampling service continuously provides each peer with a sample of peers picked uniformly at random in the network. While empirical studies have shown that uniformity was achieved, analysis proposed so far assume strong restrictions on the topology of the overlay network it continuously generates. In this work, we analyze a Generic Random Peer Sampling Service (GRPS) that satisfies the desirable properties for any peer sampling service-small views, uniform sample, load balancing, and independence- and relieve strong degree connections in the nodes assumed in previous works. The main result we prove is: starting from any simple (without loops and parallel edges) directed graph with out-degree equal to c for all nodes, and recursively applying GRPS, eventually results in a random simple directed graph with out-degree equal to c for all nodes. We test empirically convergence time and independence time for GRPS. Finally, We use this empirical evaluation to show that GRPS performs better than previously presented peer sampling services.

In this paper, we consider the problem of the online allocation of a very large number of identical tasks on a master-slave platform. Initially, several masters hold or generate tasks that are transfered and processed by slave nodes. The goal is to maximize the overall throughput achieved using this platform, i. e., the (fractional) number of tasks that can be processed within one time unit. We model the communications using the so-called bounded degree multi-port model, in which several communications can be handled by a master node simultaneously, provided that bandwidths limitation are not exceeded and that a given server is not involved in more simultaneous communications than its maximal degree. Under this model, it has been proved that maximizing the throughput (MTBD problem) is NP-Complete in the strong sense but that a small additive resource augmentation (of 1) on the servers degrees is enough to find in polynomial time a solution that achieves at least the optimal throughput. In this paper, we consider the reasonable setting where the set of slave processors is not known in advance but rather join and leave the system at any time, i. e., the online version of MTBD. We prove that no fully online algorithm (where only one change is allowed for each event) can achieve a constant approximation ratio, whatever the resource augmentation on servers degrees. Then, we prove that it is possible to maintain the optimal solution at the cost of at most four changes per server each time a new node joins or leaves the system. At last, we propose several other greedy heuristics to solve the online problem and we compare the performance (in terms of throughput) and the cost (in terms of disconnections and reconnections) of proposed algorithms through a set of extensive simulation results.

We consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous large scale computing platform. We model the platform using a set of servers (masters) that initially hold (or generate) the tasks to be processed by a set of clients (slaves). All resources have different speeds of communication and computation and we model contentions using the bounded multi-port model. This model corresponds well to modern networking technologies, but for the sake of realism, another parameter needs to be introduced in order to bound the number of simultaneous connections that can be opened at a server node. We prove that unfortunately, this additional parameter makes the problem of maximizing the overall throughput NP-complete. On the other hand, we also propose a polynomial time algorithm, based on a slight resource augmentation, to solve this problem. More specifically, we prove that, ifdjdenotes the maximal number of connections that can be opened at server nodeSj, then the throughput achieved using this algorithm anddj+ 1 simultaneous connections is at least the same as the optimal one withdjsimultaneous connections. This algorithm also provides a good approximation for the dual problem of minimizing the maximal number of connections that need to be opened in order to achieve a given throughput, and it can be turned into a standard approximation algorithm (i.e., without resource augmentation). Finally, we also propose extensive simulations to assess the performance of the proposed algorithm.

In this paper, we study algebraic aggregate computations in Sensor Networks. The main contribution is the presentation of an early-stopping protocol that computes the average function under a harsh model of the conditions under which sensor nodes operate. This protocol is shown to be time-optimal in presence of unfrequent failures. The approach followed saves time and energy by relying the computation on a small network of delegate nodes that can be rebuilt fast in case of node failures and communicate using a collision-free schedule. Delegate nodes run simultaneously two protocols, namely, a collection/dissemination tree-based algorithm, which is shown to be optimal, and a mass-distribution algorithm. Both algorithms are analyzed under a model where the frequency of failures is a parameter. Other aggregate computation algorithms can be easily derived from this protocol. To the best of our knowledge, this is the first optimal early-stopping algorithm for aggregate computations in Sensor Networks.

In this paper we generalize the Continuous Adversarial Queuing Theory (CAQT) model [5] by considering the possibility that the router clocks in the network are not synchronized. Clearly, this new extension to the model only affects those scheduling policies that use some form of timing. First, if all clocks run at the same speed, maintaining constant differences, we show that all universally stable policies in CAQT that use the injection time and the remaining path to schedule packets remain universally stable. These policies include, for instance, Shortest in System (SIS) and Longest in System (LIS). Then, if clock differences can vary over time, but difference is bounded, we show the universal stability of SIS and a family of policies related to LIS. The bounds we obtain in this case depend on the maximum difference between clocks. We then present a new policy that we call Longest in Queues (LIQ), which gives priority to the packet that has been waiting the longest in edge queues. This policy is universally stable and, if clocks maintain constant differences, the bounds do not depend on them. To finish, we provide with simulation results that compare the behavior of some of these protocols in a network with stochastic injection of packets.