The network-based study of financial systems has received considerable attention in recent years but has seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view and introduce the Interval Debt Model (IDM) and some scheduling problems based on it, namely: Bankruptcy Minimization/Maximization, in which the aim is to produce a payment schedule with at most/at least a given number of bankruptcies; Perfect Scheduling, the special case of the minimization variant where the aim is to produce a schedule with no bankruptcies (that is, a perfect schedule); and Bailout Minimization, in which a financial authority must allocate a smallest possible bailout package to enable a perfect schedule. We show that each of these problems is NP-complete, in many cases even on very restricted input instances. On the positive side, we provide for Perfect Scheduling a polynomial-time algorithm on (rooted) out-trees although in contrast we prove NP-completeness on directed acyclic graphs, as well as on instances with a constant number of nodes (and hence also constant treewidth). When we allow non-integer payments, we show by a linear programming argument that the problem Bailout Minimization can be solved in polynomial time.

A hybrid network is a static (electronic) network that is augmented with optical switches. The Reconfigurable Routing Problem (RRP) in hybrid networks is the problem of finding settings for the optical switches augmenting a static network so as to achieve optimal delivery of some given workload. The problem has previously been studied in various scenarios with both tractability and NP-hardness results obtained. However, the data center and interconnection networks to which the problem is most relevant are almost always such that the static network is highly structured (and often node-symmetric) whereas all previous results assume that the static network can be arbitrary (which makes existing computational hardness results less technologically relevant and also easier to obtain). In this paper, and for the first time, we prove various intractability results for RRP where the underlying static network is highly structured, for example consisting of a hypercube, and also extend some existing tractability results.

Stellar datacenter networks are a recent generic construction designed to transform a base-graph into a dual-port, server-centric datacenter network. We prove that the S-bisection width of any stellar datacenter network can be obtained from the solution of isoperimetric problems on the base-graph, provided that the base-graph is regular. We extend previous research on the stellar datacenter networks GQ⁎, instantiated with generalized hypercubes, and show that with respect to S-bisection width, GQ⁎ performs well in comparison with the dual-port datacenter network FiConn. Our work develops a strong combinatorial link between graph bisection width and throughput metrics for stellar datacenter networks.

This paper presents INRFlow, a mature, frugal, flow-level simulation framework for modelling large-scale networks and computing systems. INRFlow is designed to carry out performance-related studies of interconnection networks for both high performance computing systems and datacentres. It features a completely modular design in which adding new topologies, routings or traffic models requires minimum effort. Moreover, INRFlow includes two different simulation engines: a static engine that is able to scale to tens of millions of nodes and a dynamic one that captures temporal and causal relationships to provide more realistic simulations. We will describe the main aspects of the simulator, including system models, traffic models and the large variety of topologies and routings implemented so far. We conclude the paper with a case study that analyses the scalability of several typical topologies. INRFlow has been used to conduct a variety of studies including evaluation of novel topologies and routings (both in the context of graph theory and optimization), analysis of storage and bandwidth allocation strategies and understanding of interferences between application and storage traffic. • We present our flow-level simulation framework INRFlow. • It is a mature, flexible and efficient tool for simulating large scale systems. • It models network, storage, scheduler and applications. • It has been used extensively for our research in the past. • INRFlow is open source and programmed in C.

We undertake the first formal analysis of the role of symmetry, interpreted broadly, in the design of server-centric datacenter networks. Although symmetry has been mentioned by other researchers, we explicitly relate it to various specific, structural, graph-theoretic properties of datacenter networks. Our analysis of symmetry is motivated by the need to ascertain the usefulness of a datacenter network as regards the support of network virtualization and prevalent communication patterns in multitenanted clouds. We argue that a number of structural concepts relating to symmetry from general interconnection networks, such as recursive-definability, the existence and dynamic construction of spanning trees, pancyclicity, and variations in Hamiltonicity, are appropriate topological metrics to use in this regard. In relation to symmetry, we highlight the relevance of algebraic properties and algebraic constructions within datacenter network design. Built upon our analysis of symmetry, we outline the first technique to embed guest datacenter networks in a host datacenter network that is specifically oriented towards server-centric datacenter networks. In short, we provide the graph-theoretic foundations for the design of server-centric datacenter networks so as to support network virtualization and communication patterns in cloud computing.

The first dual-port server-centric datacenter network, FiConn, was introduced in 2009 and there are several others now in existence; however, the pool of topologies to choose from remains small. We propose a new generic construction, the stellar transformation, that dramatically increases the size of this pool by facilitating the transformation of well-studied topologies from interconnection networks, along with their networking properties and routing algorithms, into viable dual-port server-centric datacenter network topologies. We demonstrate that under our transformation, numerous interconnection networks yield datacenter network topologies with potentially good, and easily computable, baseline properties. We instantiate our construction so as to apply it to generalized hypercubes and obtain the datacenter networks GQ⋆. Our construction automatically yields routing algorithms for GQ⋆ and we empirically compare GQ⋆ (and its routing algorithms) with the established datacenter networks FiConn and DPillar (and their routing algorithms); this comparison is with respect to network throughput, latency, load balancing, fault-tolerance, and cost to build, and is with regard to all-to-all, many all-to-all, butterfly, random, hot-region, and hot-spot traffic patterns. We find that GQ⋆ outperforms both FiConn and DPillar (sometimes significantly so) and that there is substantial scope for our stellar transformation to yield new dual-port server-centric datacenter networks that are a considerable improvement on existing ones.

We present significantly improved one-to-one routing algorithms in the datacenter networks HCN and BCN in that our routing algorithms result in much shorter paths when compared with existing routing algorithms. We also present a much tighter analysis of HCN and BCN by observing that there is a very close relationship between the datacenter networks HCN and the interconnection networks known as WK-recursive networks. We use existing results concerning WK-recursive networks to prove the optimality of our new routing algorithm for HCN and also to significantly aid the implementation of our routing algorithms in both HCN and BCN. Furthermore, we empirically evaluate our new routing algorithms for BCN, against existing ones, across a range of metrics relating to path-length, throughput, and latency for the traffic patterns all-to-one, bisection, butterfly, hot-region, many-all-to-all, and uniform-random, and we also study the completion times of workloads relating to MapReduce, stencil and sweep, and unstructured applications. Not only do our results significantly improve routing in our datacenter networks for all of the different scenarios considered but they also emphasize that existing theoretical research can impact upon modern computational platforms.

The theory of combinatorial designs has recently been used in order to build switch-centric data centre networks incorporating a large number of servers, in comparison with the popular Fat-Tree data centre network. We clarify and extend these results and prove that in these data centre networks: there are pairwise link-disjoint paths joining all the servers adjacent to some switch with all the servers adjacent to any other switch; and there are pairwise link-disjoint paths from all the servers adjacent to some switch to any identically-sized collection of target servers where these target servers need not be adjacent to the same switch. In both cases, we always control the path lengths. Our constructions and analysis are undertaken on bipartite graphs with the applications to data centre networks being easily derived. Our results show the potential of the application of results and methodologies from combinatorics to data centre network design.

OTIS networks are interconnection networks amenable to deployment as hybrid networks containing both electronic and optical links. Deficiencies as regards symmetry led to the subsequent formulation of biswapped networks which were later generalized to multiswapped networks so as to still enable optoelectronic implementation (as it happens, multiswapped networks also generalize previously studied hierarchical crossed cubes). Multiswapped networks of the form M s w ( H ; G ) are known to possess good (graph-theoretic) properties as regards their use as (optoelectronic) interconnection networks (in distributed-memory multiprocessors) and in relation to those of the component networks G and H . Combinatorially, they provide a hierarchical mechanism to define new networks from existing networks (so that the properties of the new network can be controlled in terms of the constituent networks). In this paper, we prove that if G and H are Hamiltonian networks then the multiswapped network M s w ( H ; G ) is also Hamiltonian. At the core of our proof is finding specially designed Hamiltonian cycles in 2-dimensional and heavily pruned 3-dimensional tori, irrespective of the actual networks G and H we happen to be working with. This lends credence to the role of tori as fundamental networks within the study of interconnection networks.

DPillar has recently been proposed as a server-centric datacenter network and is combinatorially related to (but distinct from) the well-known wrapped butterfly network. We explain the relationship between DPillar and the wrapped butterfly network before proving that the underlying graph of DPillar is a Cayley graph; hence, the datacenter network DPillar is node-symmetric. We use this symmetry property to establish a single-path routing algorithm for DPillar that computes a shortest path and has time complexity O(k), where k parameterizes the dimension of DPillar (we refer to the number of ports in its switches as n). Our analysis also enables us to calculate the diameter of DPillar exactly. Moreover, our algorithm is trivial to implement, being essentially a conditional clause of numeric tests, and improves significantly upon a routing algorithm earlier employed for DPillar. Furthermore, we provide empirical data in order to demonstrate this improvement. In particular, we empirically show that our routing algorithm improves the average length of paths found, the aggregate bottleneck throughput, and the communication latency. A secondary, yet important, effect of our work is that it emphasises that datacenter networks are amenable to a closer combinatorial scrutiny that can significantly improve their computational efficiency and performance.

Ant Colony Optimization (ACO) is a nature-inspired metaheuristic that can be applied to a wide range of optimization problems. In this paper we present the first parallel implementation of an ACO-based (image processing) edge detection algorithm on the Graphics Processing Unit (GPU) using NVIDIA CUDA. We extend recent work so that we are able to implement a novel data-parallel approach that maps individual ants to thread warps. By exploiting the massively parallel nature of the GPU, we are able to execute significantly more ants per ACO-iteration allowing us to reduce the total number of iterations required to create an edge map. We hope that reducing the execution time of an ACO-based implementation of edge detection will increase its viability in image processing and computer vision.

We study an interconnection network that we call$3Torus(m,n)$obtained by pruning the$4m \times 4n$torus (of links) so that the resulting network is regular of degree 3. We show that$3Torus(m,n)$retains many of the useful properties of tori (although, of course, there is a price to be paid due to the reduction in links). In particular, we show that$3Torus(m,n)$is node-symmetric; we establish closed-form expressions on the length of a shortest path joining any two nodes of the network; we calculate the diameter precisely; we obtain an upper bound on the average inter-node distance; we develop an optimal distributed routing algorithm; we prove that$3Torus(m,n)$has connectivity 3 and is Hamiltonian; we obtain a precise expression for (an upper bound on) the wide-diameter; and we derive optimal one-to-all broadcast and personalized one-to-all broadcast algorithms under both a one-port and all-port communication model. We also undertake a preliminary performance evaluation of our routing algorithm. In summary, we find that$3Torus(m,n)$compares very favourably with tori.

We solve the Travelling Salesman Problem (TSP) using a parallel implementation of the Ant System (AS) algorithm for execution on the Graphics Processing Unit (GPU) using NVIDIA CUDA. Extending some recent research, we implement both the tour construction and pheromone update stages of Ant Colony Optimization (ACO) on the GPU using a data parallel approach. In this recent work, roulette wheel selection is used during the tour construction phase; however, we propose a new parallel implementation of roulette wheel selection called Double-Spin Roulette (DS-Roulette) which significantly reduces the running time of tour construction. We also develop a new implementation of the pheromone update stage. Our results show that compared to its sequential counterpart our new parallel implementation executes up to 82× faster whilst preserving the quality of the tours constructed, and up to 8.5× faster than the best existing parallel GPU implementation.

Let u and v be any two given nodes in a k-ary n-cube Qnkwith at most 2n-2 faulty edges. Suppose that the number of healthy links incident with u is no more than that of v, and denote this number by m. In this paper, we show that there are m mutually node-disjoint paths between u and v.

Biswapped networks of the form Bsw(G) have recently been proposed as interconnection networks to be implemented as optical transpose interconnection systems. We provide a systematic construction of κ+1 vertex-disjoint paths joining any two distinct vertices in Bsw(G), where κ≥1 is the connectivity of G. In doing so, we obtain an upper bound of max{2Δ(G)+5, Δκ(G)+Δ(G)+2} on the (κ+1)-diameter of Bsw(G), where Δ(G) is the diameter of G and Δκ(G) the κ-diameter. Suppose that we have a deterministic multipath source routing algorithm in an interconnection network G that finds κ mutually vertex-disjoint paths in G joining any two distinct vertices and does this in time polynomial in Δκ(G), Δ(G) and κ (and independently of the number of vertices of G). Our constructions yield an analogous deterministic multipath source routing algorithm in the interconnection network Bsw(G) that finds κ+1 mutually vertex-disjoint paths joining any two distinct vertices in Bsw(G) so that these paths, all have length bounded as above. Moreover, our algorithm has time complexity polynomial in Δκ(G), Δ(G) and κ. We also show that if G is Hamiltonian, then Bsw (G) is Hamiltonian, and that if G is a Cayley graph, then Bsw(G) is a Cayley graph.

We prove that a k-ary 2-cube Q_2^k with three faulty edges but where every vertex is incident with at least two healthy edges is bipancyclic, if k\ge 3, and k-pancyclic, if k\ge 5 is odd (these results are optimal). We go on to show that when k\ge 4 is even and n\ge 3, any k-ary n-cube Q_n^k with at most 4n-5 faulty edges so that every vertex is incident with at least two healthy edges is bipancyclic, and that this result is optimal.

We develop a widely applicable algorithm to solve the fault diagnosis problem in certain distributed-memory multiprocessor systems in which there are a limited number of faulty processors. In particular, we prove that if the underlying graph forming the interconnection network has connectivity no less than its diagnosability ¿ and can be partitioned into enough connected components of large enough size then given a syndrome of test results under the comparison diagnosis model resulting from some set of faulty nodes of size at most ¿, we can find the actual set of faulty nodes with time complexity O(¿N), where ¿ is the maximal degree of any node of the graph and N is the number of nodes.

The augmented k-ary n-cube AQn,kis a recently proposed interconnection network that incorporates an extension of a k-ary n-cube Qnkinspired by the extension of a hypercube Qnto the augmented hypercube AQn(as developed by Choudom and Sunita). We extend a recent topological investigation of augmented k-ary n-cubes by proving that any augmented k-ary n-cube AQn,kis edge-pancyclic and that AQ2,kis panconnected.

We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ(1), is such that the class of problems accepted by these program schemes is exactly the class of recursively enumerable problems. The class of problems accepted by the program schemes of the class NPSQ(1) where only access to a queue, and not the additional numeric universe, is allowed is exactly the class of recursively enumerable problems that are closed under extensions. We define an infinite hierarchy of classes of program schemes for which NPSQ(1) is the first class and the union of the classes of which is the class NPSQ.We show that the class of problems accepted by the program schemes of NPSQ is the union of the classes of problems defined by the sentences of all vectorized Lindström logics formed using operators whose corresponding problems are recursively enumerable and closed under extensions, and, as a result, has a zero-one law. Moreover, we also show that this class of problems can be realized as the class of problems defined by the sentences of a particular vectorized Lindström logic. Finally, we show how our results can be applied to yield logical characterizations of complexity classes and provide logical analogues to a number of inequalities and hypotheses from computational complexity theory involving (non-deterministic) complexity classes ranging from NP through to ELEMENTARY.

We study a class of program schemes, NPSB, in which, aside from basic assignments, non-deterministic guessing and while loops, we have access to arrays; but where these arrays are binary write-once in that they are initialized to ‘zero’ and can only ever be set to ‘one’. We show, amongst other results, that: NPSB can be realized as a vectorized Lindström logic; there are problems accepted by program schemes of NPSB that are not definable in the bounded-variable infinitary logic L∞ωω⁠; all problems accepted by the program schemes of NPSB have asymptotic probability 1 and on ordered structures, NPSB captures the complexity class LNP. We give equivalences (on the class of all finite structures) of the complexity-theoretic question ‘Does NP equal PSPACE?’, where the logics and classes of program schemes involved in the equivalent statements define or accept only problems with asymptotic probability 0 or 1 and so do not cover many computationally trivial problems. The class of program schemes NPSB is actually the union of an infinite hierarchy of classes of program schemes. Finally, when we amend the semantics of our program schemes slightly, we find that the classes of the resulting hierarchy capture the complexity classes Σpi (where i≥2) of the Polynomial Hierarchy PH.

In this paper we give precise solutions to problems posed by Wang, An, Pan, Wang and Qu and by Hsieh, Lin and Huang. In particular, we show that Qnkis bipanconnected and edge-bipancyclic, when k ges 3 and n ges 2, and we also show that when k is odd, Qnkis m-panconnected, for m=(n(k-1)+2k-6)/2, and (k-1)-pancyclic (these bounds are optimal). We introduce a path-shortening technique, called progressive shortening, and strengthen existing results, showing that when paths are formed using progressive shortening then these paths can be efficiently constructed and used to solve a problem relating to the distributed simulation of linear arrays and cycles in a parallel machine whose interconnection network is Qnk, even in the presence of a faulty processor.

Let k ges 4 be even and let n ges 2. Consider a faulty k-ary n-cube Qknin which the number of node faults fv and the number of link faults feare such that fv+ feles 2n-2. We prove that given any two healthy nodes s and e of Qkn, there is a path from s to e of length at least kn- 2 fv-1 (respectively, kn- 2 fv-2) if the nodes s and e have different (respectively the same) parities (the parity of a node in Qknis the sum modulo 2 of the elements in the n-tuple over {0,1,...,k 1} representing the node). Our result is optimal in the sense that there are pairs of nodes and fault configurations for which these bounds cannot be improved, and it answers questions recently posed by Yang, Tan et al. (2007) and by Fu (2006). Furthermore, we extend known results, obtained by Kim and Park (2000), for the case when n=2.

In the 1990s, Feder and Vardi attempted to find a large subclass of NP which exhibits a dichotomy, that is, where every problem in the subclass is either solvable in polynomial‐time or NP‐complete. Their studies resulted in a candidate class of problems, namely, those definable in the logic MMSNP. While it remains open as to whether MMSNP exhibits a dichotomy, for various reasons it remains a strong candidate. Feder and Vardi added to the significance of MMSNP by proving that, although MMSNP strictly contains CSP, the class of constraint satisfaction problems, MMSNP and CSP are computationally equivalent. We introduce here a new class of combinatorial problems, the class of forbidden patterns problems FPP, and characterize MMSNP as the finite unions of problems from FPP. We use our characterization to detail exactly those problems that are in MMSNP but not in CSP. Furthermore, given a problem in MMSNP, we are able to decide whether the problem is in CSP or not (this whole process is effective). If the problem is in CSP, then we can construct a template for this problem; otherwise, for any given candidate for the role of template, we can build a counterexample (again, this process is effective).

We consider the fault-tolerant capabilities of networks of processors whose underlying topology is that of the k-ary n-cube $Q_n^k$, where $k\geq 3$ and $n\geq 2$. In particular, given a copy of $Q_n^k$ where some of the interprocessor links may be faulty but where every processoris incident with at least two healthy links, we show that if the number of faults is at most 4n-5, then $Q_n^k$ still contains a Hamiltonian circuit, but that there are situations where the number of faults is 4n-4 (and every processor is incident with at least two healthy links) and no Hamiltonian circuit exists. We also remark that given a faulty $Q_n^k$, the problem of deciding whether there exists a Hamiltonian circuit is NP-complete.

We begin by proving that the class of problems accepted by the program schemes of NPS is exactly the class of problems defined by the sentences of transitive closure logic (program schemes of NPS are obtained by generalizing basic non-deterministic while-programs whose tests within while instructions are quantifier-free first-order formulae). We then show that our program schemes form a proper infinite hierarchy within NPS whose analogy in transitive closure logic is a proper infinite hierarchy, the union of which is full transitive closure logic but for which every level of the hierarchy has associated with it a first-order definable problem not in that level. We then proceed to add a stack to our program schemes, so obtaining the class of program schemes NPSS, and characterize the class of problems accepted by the program schemes of NPSS as the class of problems defined by the sentences of path system logic. We show that there is a proper infinite hierarchy within NPSS, with an analogous hierarchy within path system logic (again, such that every level of the hierarchy has associated with it a first-order definable problem not in that level). Like the hierarchies in transitive closure logic and NPS, the hierarchies in path system logic and NPSS are all proper even when we consider only problems involving undirected trees or problems involving out-trees. One aspect of our analysis that we believe to be particularly interesting is that we do not use Ehrenfeucht-Fraïssé games for our inexpressibility results, as is usually the case in finite model theory, but we simply consider computations of program schemes on certain finite structures.

We investigate the existence of cycles, meshes and tori in a k-ary n-cube Q/sub n//sup k/ in which a limited number of nodes and links are faulty. Our main result is that in a k-ary n-cube Q/sub n//sup k/ in which there are v faulty nodes /spl lambda/faulty links where v+/spl lambda//spl les/n, there is a cycle of length at least k/sup n/-vw, where w=1 if k is odd and w=2 if k is even (throughout k/spl ges/3 and n/spl ges/2). We extend this result so as to prove the existence of large meshes and tori in such a faulty k-ary n-cube.

Continuing a line of research opened up by Grigni and Sipser (1992) and further pursued by Stewart (1994), we show that a wide variety of equivalent characterizations of P still remain equivalent when restricted to be positive. All these restrictions thus define the same class posP, a proper subclass of monP, the class of monotone problems in P. We also exhibit complete problems for posP under very weak reductions.

We motivate the study of certain classes of acyclic Petri nets and consider the reachability problem for these classes of Petri nets, providing various NP-completeness results. We also show how the reachability problem for the class of acyclic elementary net systems appears to be harder than it is for the (seemingly comparable) class of 1-bounded acyclic Petri nets.

We introduce the class of problems NPC-RAT accepted by polynomial time (nondeterministic) conjunctive random-access Turing machines (C-RATs): such machines crash when the oracle answers ‘no’ (the oracle is always the input structure). We show that NPC-RAT consists of all monotone problems in NP and we logically characterize this complexity class in two ways: the first involves an extension of first-order logic using an operator corresponding to some problem (an approach initiated by Immerman); the second involves a restricted version of existential second-order logic (in the style of Fagin). In both logics, symbols belonging to the problem vocabulary are only allowed to occur positively. We also show that NPC-RAT possesses complete problems via monotone projection translations. It had previously been shown that certain complete problems for NP (via logspace reductions) are unlikely to be complete for NP via monotone projection translations.

We consider three sub-logics of the logic (±HP)*[FOs] and show that these sub-logics capture the complexity classes obtained by considering logspace deterministic oracle Turing machines with oracles in NP where the number of oracle calls is unrestricted and constant, respectively; that is, the classes LNP and LNP[O(1)]. We conclude that if certain logics are of the same expressibility then the Polynomial Hierarchy collapses. We also exhibit some new complete problems for the complexity class LNP via projection translations (the first to be discovered: projection translations are extremely weak logical reductions between problems) and characterize the complexity class LNP[O(1)] as the closure of NP under a new, extremely strict truth-table reduction (which we introduce in this paper).

This paper continues an investigation into the expressibility of the logic (±HP)*[FOS]. In particular, we show that the logic (±HP)*[FOS] has the same expressibility as its sub-logic (±HP)1[FOS] which is known to capture the complexity class LNP (this class being those sets of strings accepted by some logspace deterministic oracle Turing machine with an oracle in NP). We consequently show that a naturally defined hierarchy within PNP collapses.

In this paper, we consider extending the first-order language FO by the operator 3COL, corresponding to the problem of deciding whether a graph can be properly coloured using at most three colours, just as FO has, in the past, been extended by the operators DTC, STC, TC, ATC, and HP: in particular, HP is the operator corresponding to the problem of deciding whether a digraph has a directed Hamiltonian path between two distinguished vertices. We find that if the language (FO + pos3COL) has the same expressibility as the (seemingly comparable) language (FO+posHP), then NP= co-NP; perhaps a surprising result given that both the problems HP and 3COL are NP-complete via logspace reductions. We show that the problem 3COL is complete for the complexity class FO1pos3COL (a sub-class of NP) via projection translations, but it is open as to whether FO1pos3COL coincides with NP. We also present general techniques which might be used to show that other languages capture NP and other problems are complete for NP via projection translations.

We show that the classes of the polynomial hierarchy have complete problems via projection translations (without successor) and we exhibit some new, natural complete problems for the complexity classes co-NP and IIp2 via projection translations: these problems were not even known to be complete for co-NP and IIp2 via polynomial-time reductions. Most of the problems involve the reliability of networks of processors where the links may fail and where these failures may be related to one another in a restricted way, but we show how our trick of labelling discrete structures with Boolean literals can be applied to yield other new natural complete problems involving digraphs and Boolean formulae. We also show that it is unlikely that certain problems (known to be complete for the respective complexity class via projection translations) are complete for L, NL, and NP via monotone projection translations; for if any of them are then L = NP, NL = NP, or NP = co-NP.