The data transfer problem in a system of systems

Ronan Bocquillon, Antoine Jouglet and Jacques Carlier

European Journal of Operational Research, 2015, vol. 244, issue 2, 392-403

Abstract: Systems of systems are collections of independent systems which interact and share information to provide services. To communicate, systems can opportunistically make use of contacts that occur when two entities are close enough to each other. In this paper, it is assumed that reliable predictions can be made about the sequence of such contacts for each system. An information item (a datum) is split into several datum units which are to be delivered to recipient systems. During a contact between two systems, a sending system can transfer one stored datum unit to a receiving system. Source systems initially store some of the datum units. The data transfer problem consists in searching for a valid transfer plan, i.e. a transfer plan allowing the datum units to be transmitted from their source systems to the recipient systems. The dissemination problem consists in searching a valid transfer plan which minimizes the dissemination length, i.e. the number of contacts which are necessary to deliver all the datum units to the recipient nodes. To our knowledge, there is no previous work attempting to determine the theoretical complexity of these problems. The aim of this paper is to determine the frontier between easy and hard problems. We show that the problems are strongly NP-Hard when the number of recipients is equal to 2 or more (while the number of datum units is unbounded) or the number of datum units is equal to 2 or more (while the number of recipients is unbounded). We also show that these problems are polynomially solvable when the number of datum units or the number of recipient nodes is equal to 1, or when these parameters are all upper bounded by given positive numbers. The complexity of two related problems is also studied. It is shown that knowing whether there exist k mutually arc-disjoint branchings in an evolving graph and k arc-disjoint Steiner trees in a directed graph without circuit are strongly NP-Complete.

Keywords: Combinatorial optimization; Data transfer; Scheduling; Routing (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715000636
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:244:y:2015:i:2:p:392-403

DOI: 10.1016/j.ejor.2015.01.043

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().