Deterministic Algorithms in Dynamic Networks – Problems, Analysis, and Algorithmic Tools

PDF

Authors
  1. Casteigts, A.
  2. Flocchini, P.
Corporate Authors
Defence R&D Canada - Ottawa, Ottawa ONT (CAN);OTTAWA UNIV, OTTAWA ON (CAN) SCHOOL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE
Abstract
The number of telecommunication networks deployed in a dynamic environment is quickly growing. This is true in our everyday life (e.g., smartphones, vehicles, or satellites) as well as in the military context (e.g., dismounted soldiers or swarms of UAVs). Unfortunately, few theoretical tools enable, to date, the study of dynamic networks in a formal and rigorous way. As a result, it is hard and sometimes impossible to guarantee, mathematically, that a given algorithm will reach its objectives once deployed in real conditions. Having such guarantees would seem to be crucial in a military context. In a previous report we identified a collection of recent theoretical tools whose purpose is to model, describe, and leverage dynamic networks in a formal way. This report focuses on problems, algorithms, and analysis techniques. We review recent efforts towards the design and analysis of distributed algorithms in dynamic networks, with an emphasis on those results that are of a deterministic and analytical nature. The topics include a discussion on how mobility impacts the very definition of problems; a set of generic tools to be used in the design or analysis of dynamic network algorithms; a discussion on the impact of various types of dynamics on the feasibility and complexity of given problems; a classification of dynamic networks based on dynamic graph properties; and finally, a discussion on how real-world mobility contexts relate to some of these classes.

Il y a un résumé en français ici.

Report Number
DRDC-OTTAWA-CR-2013-021 — Contractor Report
Date of publication
01 Apr 2013
Number of Pages
92
DSTKIM No
CA037820
CANDIS No
537588
Format(s):
Electronic Document(PDF)

Permanent link

Document 1 of 1

Date modified: