Maximum throughput of multiple access channels in adversarial environments

We consider deterministic distributed broadcasting on multiple access channels in the framework of adversarial queuing. Packets are injected dynamically by an adversary that is constrained by the injection rate and the number of packets that may be injected simultaneously; the latter we call burstiness. A protocol is stable when the number of packets in queues at the stations stays bounded. The maximum injection rate that a protocol can handle in a stable manner is called the throughput of the protocol. We consider adversaries of injection rate 1, that is, of one packet per round, to address the question if the maximum throughput 1 can be achieved, and if so then with what quality of service. We develop a protocol that achieves throughput 1 for any number of stations against leaky-bucket adversaries. The protocol has O(n²+\textburstiness){\mathcal{O}(n^2+\text{burstiness})} packets queued simultaneously at any time, where n is the number of stations; this upper bound is proved to be best possible. A protocol is called fair when each packet is eventually broadcast. We show that no protocol can be both stable and fair for a system of at least two stations against leaky-bucket adversaries. We study in detail small systems of exactly two and three stations against window adversaries to exhibit differences in quality of broadcast among classes of protocols. A protocol is said to have fair latency if the waiting time of packets is O(\textburstiness){\mathcal{O}(\text{burstiness})}. For two stations, we show that fair latency can be achieved by a full sensing protocol, while there is no stable acknowledgment based protocol. For three stations, we show that fair latency can be achieved by a general protocol, while no full sensing protocol can be stable. Finally, we show that protocols that either are fair or do not have the queue sizes affect the order of transmissions cannot be stable in systems of at least four stations against window adversaries.     

Constant-space quantum interactive proofs against multiple provers

We present upper and lower bounds of the computational complexity of the two-way communication model of multiple-prover quantum interactive proof systems whose verifiers are limited to measure-many two-way quantum finite automata. We prove that (i) the languages recognized by those multiple-prover systems running in expected polynomial time are exactly the ones in NEXP, the nondeterministic exponential-time complexity class, (ii) if we further require verifiers to be one-way quantum finite automata, then their associated proof systems recognize context-free languages but not beyond languages in NE, the nondeterministic linear exponential-time complexity class, and moreover, (iii) when no time bound is imposed, the proof systems become as powerful as Turing machines. The first two results answer affirmatively an open question, posed by Nishimura and Yamakami [J. Comput. System Sci. 75 (2009) 255–269], of whether multiple-prover quantum interactive proof systems are more powerful than single-prover ones. Our proofs are simple and intuitive, although they heavily rely on an earlier result on multiple-prover classical interactive proof systems of Feige and Shamir [J. Comput. System Sci. 44 (1992) 259–271].     

Queuing network models of packet switching networks part 1: Open networks

An overview of the application of product-form queuing network models to the performance analysis of store-and-forward packet-switching networks is presented. Multiple routing chains are used to model the different routing behaviors of data packets. Queuing networks with open chains are considered in this paper. Kleinrock's formula for the mean end-to-end delay of packets is first derived. The application of this delay formula to optimal channel capacity assignment and optimal routing is discussed. Analytic results for the mean and distribution of the end-to-end delay of each chair are presented. The issue of fairness among chains is also addressed.The application of queuing networks with closed chains and population size constraints to the performance analysis of store-and-forward packet-switching networks is illustrated in a companion paper [1].     

Surjective multidimensional cellular automata are non-wandering: A combinatorial proof

A combinatorial proof that surjective D-dimensional CA are non-wandering is given. This answers an old open question stated in Blanchard and Tisseur (2000) [3]. Moreover, an explicit upper bound for the return time is given.     

Tight Bounds on the Competitive Ratio on Accommodating Sequences for the Seat Reservation Problem

The unit price seat reservation problem is investigated. The seat reservation problem is the problem of assigning seat numbers on-line to requests for reservations in a train traveling through k stations. We are considering the version where all tickets have the same price and where requests are treated fairly, that is, a request which can be fulfilled must be granted.For fair deterministic algorithms, we provide an asymptotically matching upper bound to the existing lower bound which states that all fair algorithms for this problem are -competitive on accommodating sequences, when there are at least three seats.Additionally, we give an asymptotic upper bound of for fair randomized algorithms against oblivious adversaries.We also examine concrete on-line algorithms, First-Fit and Random for the special case of two seats. Tight analyses of their performance are given.     

A note on monotone complexity and the rank of matrices

We shall give simpler proofs of some lower bounds on monotone computations. We describe a simple condition on combinatorial structures, such that the rank of the matrix associated with these structures gives lower bounds on monotone span program size and monotone formula size. We also prove an upper bound on the rank of the corresponding matrices, and show that such structures can be constructed from self-avoiding families. As a corollary, we obtain an upper bound on the size of self-avoiding families, which solves a problem posed by Babai and Gál [Combinatorica 19 (3) (1999) 301-319].     

Õ(Congestion + Dilation) Hot-Potato Routing on Leveled Networks

We study packet routing problems, in which we are given a set of N packets which will be sent on preselected paths with congestion C and dilation D. For store-and-forward routing, in which nodes have buffers for packets in transit, there are routing algorithms with a performance that matches the lower bound Ω(C+D). Motivated from optical networks, we study hot-potato routing in which the nodes are bufferless. Due to the lack of buffers, in hot-potato routing the packets may be delayed more than in store-and-forward routing. An interesting question is how much is the performance of routing algorithms affected by the absence of buffers. Here, we answer this question for the class of leveled networks, in which the nodes are partitioned into L+1 distinct levels. We present a randomized hot-potato routing algorithm for leveled networks, which routes the packets in O((C + L) ln⁹ (LN)) time with high probability. For routing problems with dilation Ω(L), and where N is a polynonial in L, this bound is within polylogarithmic factors of the lower bound Ω(C+L). Our algorithm demonstrates that for such routing problems the benefit from using buffers is no more than polylogarithmic; thus, hot-potato routing is an efficient way to route packets in leveled networks. In hot-potato routing, due to the lack of buffers, the packets may not be able to remain on their preselected paths during the course of routing (while in store-and-forward routing the packets remain on their preselected paths). However, in our algorithm the actual path that each packet follows contains its original preselected path; thus the lower bound Ω(C+L) is also a lower bound for the new paths. Our algorithm is distributed, that is, routing decisions are taken locally at each node while packets are routed in the network. To our knowledge, this is the first hot-potato algorithm designed and analyzed, in terms of congestion and dilation, for leveled networks.     

On the supports of recognizable series over a field and a single letter alphabet

We prove that the support of a recognizable series over a field of characteristic zero and a single letter alphabet is recognizable. This provides an answer to a question of Kirsten (2009) [4]. Then we give an example of a recognizable series over a field of prime characteristic and a single letter alphabet whose support is not recognizable which provides an answer to a question of Kirsten and Quaas (2011) [5].     

A Complete 4-parametric complexity classification of short shop scheduling problems

We present a comprehensive complexity analysis of classical shop scheduling problems subject to various combinations of constraints imposed on the processing times of operations, the maximum number of operations per job, the upper bound on schedule length, and the problem type (taking values ??open shop,?? ??job shop,?? ??mixed shop??). It is shown that in the infinite class of such problems there exists a finite basis system that allows one to easily determine the complexity of any problem in the class. The basis system consists of ten problems, five of which are polynomially solvable, and the other five are NP-complete. (The complexity status of two basis problems was known before, while the status of the other eight is determined in this paper.) Thereby the dichotomy property of that parameterized class of problems is established. Since one of the parameters is the bound on schedule length (and the other two numerical parameters are tightly related to it), our research continues the research line on complexity analysis of short shop scheduling problems initiated for the open shop and job shop problems in the paper by Williamson et?al. (Oper. Res. 45(2):288?C294, 1997). We improve on some results of that paper.     

Effective Routing and Scheduling in Adversarial Queueing Networks

In an adversarial queueing network, the incoming traffic is decided by an adversary, who operates under a reasonable rate restriction. This model provides a valuable, complementary point of view to that of the traditional queueing network model in which arrivals are modeled by stochastic processes. As a result, the adversarial queueing network model has attracted much attention in recent years, especially as a way of modeling packet injections into a communication network. Our main result is a simple, effective packet routing and scheduling algorithm with a provably good performance. Specifically, our algorithm keeps the system stable (bounded number of packets in the system), with the bound on the number of packets in the system that is O((1 - r)^-1), where r can be interpreted as the arrival rate of the packets into the communication network. This improves upon the work of Gamarnik, who designed an algorithm for which the number of packets in the system is O((1 - r)^-2); moreover, our result matches the traditional queueing-theoretic number-in-system bound.     

Erratum to “Mann and Ishikawa iterative processes for multivalued mappings in Banach spaces” [Comput. Math. Appl. 54 (2007) 872–877]

We show strong convergence for Mann and Ishikawa iterates of multivalued nonexpansive mapping T under some appropriate conditions, which revises a gap in Panyanak [B. Panyanak, Mann and Ishikawa iterative processes for multivalued mappings in Banach spaces, Comput. Math. Appl. 54 (2007) 872–877]. Furthermore, we also give an affirmative answer to Panyanak’s open question.     

On Definability in Dependence Logic

We study the expressive power of open formulas of dependence logic introduced in Väänänen [Dependence logic (Vol. 70 of London Mathematical Society Student Texts), 2007]. In particular, we answer a question raised by Wilfrid Hodges: how to characterize the sets of teams definable by means of identity only in dependence logic, or equivalently in independence friendly logic.     

Optimal Reconstruction of Graphs under the Additive Model

We study the problem of reconstructing unknown graphs under the additive combinatorial search model. The main result concerns the reconstruction of bounded degree graphs, i.e., graphs with the degree of all vertices bounded by a constant d . We show that such graphs can be reconstructed in O(dn) nonadaptive queries, which matches the information-theoretic lower bound. The proof is based on the technique of separating matrices. A central result here is a new upper bound for a general class of separating matrices. As a particular case, we obtain a tight upper bound for the class of d -separating matrices, which settles an open question stated by Lindstr?m in [20]. Finally, we consider several particular classes of graphs. We show how an optimal nonadaptive solution of O(n ² / log n) queries for general graphs can be obtained. We also prove that trees with unbounded vertex degree can be reconstructed in a linear number of queries by a nonadaptive algorithm. Received August 1997; revised January 1999.     

Deadline guaranteed packet scheduling for overloaded traffic in input-queued switches

Many applications need to solve the deadline guaranteed packet scheduling problem. However, it is a very difficult problem if three or more deadlines are present in a set of packets to be scheduled. The traditional approach to dealing with this problem is to use EDF (Earliest Deadline First) or similar methods. Recently, a non-EDF based algorithm was proposed that constantly produces a higher throughput than EDF-based algorithms by repeatedly finding an optimal scheduling for two classes. However, this new method requires the two classes be non-overloaded, which greatly restricts its applications. Since the overloaded situation is not avoidable from one iteration to the next in dealing with multiple classes, it is compelling to answer the open question: Can we find an optimal schedule for two overloaded classes efficiently? This paper first proves that this problem is NP-complete. Then, this paper proposes an optimal preprocessing algorithm that guarantees to drop a minimum number of packets from the two classes such that the remaining set is non-overloaded. This result directly improves on the new method.     

Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem

We consider the single machine multi-operation jobs total completion time scheduling problem. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a set-up time. A job completes when all of its operations have been processed. The objective is to minimize the sum of the job completion times. In the literature, the computational complexity of this problem is posed as open. We show that the problem is strongly NP-hard even when the set-up times are common and the processing time of each operation is 0 or 1.     

Randomized competitive algorithms for the list update problem

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.     

Random and Periodic Sleep Schedules for Target Detection in Sensor Networks

We study random and periodic sleep schedules from the point of view of delay in detecting the target.We consider sleep schedules in which a sensor in"inactive"mode wakes up either randomly or periodically to detect presence of the target within its vicinity resulting into two sleep schedules:(a)random wake-up schedule,and(b)periodic wake-up schedule respectively.Specifically,we analyse and obtain for the random wake-up schedule the expected delay in detection, and the delay,such that with probability P,the delay is less than the computed value.For the periodic wake-up schedule we show that there exists an upper bound on the delay.Further we compute the average value of delay.We have shown that the theoretically computed averages and the upper bounds on the delay match with the simulation results for the random wake-up and periodic wake-up schedules.     

Extracting certainty from uncertainty: regret bounded by variation in costs

Prediction from expert advice is a fundamental problem in machine learning. A major pillar of the field is the existence of learning algorithms whose average loss approaches that of the best expert in hindsight (in other words, whose average regret approaches zero). Traditionally the regret of online algorithms was bounded in terms of the number of prediction rounds. Cesa-Bianchi, Mansour and Stoltz (Mach. Learn. 66(2–3):21–352, 2007) posed the question whether it is be possible to bound the regret of an online algorithm by the variation of the observed costs. In this paper we resolve this question, and prove such bounds in the fully adversarial setting, in two important online learning scenarios: prediction from expert advice, and online linear optimization.     

Perfect Code is W[1]-complete

We show that the parameterized problem Perfect Code belongs to W[1]. This result closes an old open question, because it was often conjectured that Perfect Code could be a natural problem having complexity degree intermediate between W[1] and W[2]. This result also shows W[1]-membership of the parameterized problem Weighted Exact CNF Satisfiability.     

On the challenge and design of transport protocols for MMORPGs

Although MMORPGs are becoming increasingly popular as well as a highly profitable Internet business, there is still a fundamental design question: Which transport protocol should be used—TCP, UDP, or some other protocol? In this paper, we first evaluate whether TCP is suitable for MMORPGs, and then propose some novel transport strategies for this genre of games. Our analysis of a trace collected from a TCP-based MMORPG called ShenZhou Online indicates that TCP is unwieldy and inappropriate for MMORPGs. We find that the degraded network performance problems are due to the following characteristics of MMORPG traffic: 1) tiny packets, 2) a low packet rate, 3) application-limited traffic generation, and 4) bi-directional traffic. Since not all game packets require reliable transmission or in-order delivery, transmitting all packets with a strict delivery guarantee causes high delays and delay jitters. Therefore, our proposed transport strategies assign game packets with appropriate levels of transmission guarantee depending on the requirements of the packets’ contents. To compare the performance of our approach with that of existing transport protocols, we conduct network simulations with a real-life game trace from Angel’s Love. The results demonstrate that our strategies significantly reduce the end-to-end delay and delay jitter of packet delivery. Finally, we show that our strategies effectively raise satisfaction levels of the game players.