Distributed Computing and Networking

This section of Discrete Mathematics & Theoretical Computer Science seeks high quality articles on structural and algorithmic aspects of graphs and related discrete mathematical models. We particularly seek topics with an intersection between discrete mathematics and computer science. We handle submissions in all areas of finite graph theory.

Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps

Devismes, Stéphane ; Ilcinkas, David ; Johnen, Colette.
We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V_r, and make all processes of other components detecting […]

Witness structures and immediate snapshot complexes

Kozlov, Dmitry N..
In this paper we introduce and study a new family of combinatorial simplicial complexes, which we call immediate snapshot complexes. Our construction and terminology is strongly motivated by theoretical distributed computing, as these complexes are combinatorial models of the standard protocol […]

Combinatorial optimization in networks with Shared Risk Link Groups

Coudert, David ; Pérennes, Stéphane ; Rivano, Hervé ; Voge, Marie-Emilie.
The notion of Shared Risk Link Groups (SRLG) captures survivability issues when a set of links of a network may fail simultaneously. The theory of survivable network design relies on basic combinatorial objects that are rather easy to compute in the classical graph models: shortest paths, minimum […]

Robust Wireless Sensor Network Deployment

Erdelj, Milan ; Mitton, Nathalie ; Razafindralambo, Tahiry.
In this work we present a decentralized deployment algorithm for wireless mobile sensor networks focused on deployment Efficiency, connectivity Maintenance and network Reparation (EMR). We assume that a group of mobile sensors is placed in the area of interest to be covered, without any prior […]

Sticky Seeding in Discrete-Time Reversible-Threshold Networks

Spencer, Gwen.
When nodes can repeatedly update their behavior (as in agent-based models from computational social science or repeated-game play settings) the problem of optimal network seeding becomes very complex. For a popular spreading-phenomena model of binary-behavior updating based on thresholds of adoption […]

An efficient certificateless aggregate signature scheme for vehicular ad-hoc networks

Malhi, Avleen Kaur ; Batra, Shalini.
The state-of-the-art telecommunication technologies have widely been adapted for sensing the traffic related information and collection of it. Vehicular Ad-Hoc Networks (VANETs) have emerged as a novel technology for revolutionizing the driving experiences of human. The most effective and widely […]

On the complexity of distributed BFS in ad hoc networks with non-spontaneous wake-ups

Kowalski, Dariusz ; Krzywdziński, Krzysztof.
We study time and message complexity of the problem of building a BFS tree by a spontaneously awaken node in ad hoc network. Computation is in synchronous rounds, and messages are sent via point-to-point bi-directional links. Network topology is modeled by a graph. Each node knows only its own id […]

Optimal Computer Crash Performance Precaution

Laksman, Efraim ; Lennerstad, Hakan ; Lundberg, Lars.
For a parallel computer system with m identical computers, we study optimal performance precaution for one possible computer crash. We want to calculate the cost of crash precaution in the case of no crash. We thus define a tolerance level r meaning that we only tolerate that the completion time of […]

Deterministic Recurrent Communication and Synchronization in Restricted Sensor Network

Fernández Anta, Antonio ; Mosteiro, Miguel ; Thraves Caro, Christopher.
Monitoring physical phenomena in Sensor Networks requires guaranteeing permanent communication between nodes. Moreover, in an effective implementation of such infrastructure, the delay between any two consecutive communications should be minimized. The problem is challenging because, in a restricted […]

Tight Bounds for Delay-Sensitive Aggregation

Pignolet, Yvonne Anne ; Schmid, Stefan ; Wattenhofer, Roger.
This article studies the fundamental trade-off between delay and communication cost in networks. We consider an online optimization problem where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about the changes of their states and to use as few […]

An optimal permutation routing algorithm on full-duplex hexagonal networks

Sau, Ignasi ; Žerovnik, Janez.
In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations, under the constraint that each link can be crossed […]

FP/FIFO scheduling: coexistence of deterministic and probabilistic QoS guarantees

Minet, Pascale ; Martin, Steven ; Saidane, Leila Azouz ; Azzaz, Skander.
In this paper, we focus on applications having quantitative QoS (Quality of Service) requirements on their end-to-end response time (or jitter). We propose a solution allowing the coexistence of two types of quantitative QoS garantees, deterministic and probabilistic, while providing a high resource […]