We formulate a private learning model to study an intrinsic tradeoff between privacy and query complexity in sequential learning. Our model involves a learner who aims to determine a scalar value, $v^*$, by sequentially querying an external database and receiving binary responses. In the meantime, an adversary observes the learner’s queries, though not the responses, and tries to infer from them the value of $v^*$. The objective of the learner is to obtain an accurate estimate of $v^*$ using only a small number of queries, while simultaneously protecting her privacy by making $v^*$ provably difficult to learn for the adversary. Our main results provide tight upper and lower bounds on the learner’s query complexity as a function of desired levels of privacy and estimation accuracy. We also construct explicit query strategies whose complexity is optimal up to an additive constant.

We consider the following distributed service model: jobs with unit mean, exponentially distributed, and independent processing times arrive as a Poisson process of rate λ N, with 0<λ<1, and are immediately dispatched to one of several queues associated with N identical servers with unit processing rate. We assume that the dispatching decisions are made by a central dispatcher endowed with a finite memory, and with the ability to exchange messages with the servers. We study the fundamental resource requirements (memory bits and message exchange rate), in order to drive the expected steady-state queueing delay of a typical job to zero, as N increases. We propose a certain policy and establish (using a fluid limit approach) that it drives the delay to zero when either (i) the message rate grows superlinearly with N, or (ii) the memory grows superlogarithmically with N. Moreover, we show that any policy that has a certain symmetry property, and for which neither condition (i) or (ii) holds, results in an expected queueing delay which is bounded away from zero.

We study multihop networks with flow-scheduling constraints, no constraints on simultaneous activation of different links, potentially multiple source-destination routes, and a mix of heavy-tailed and light-tailed traffic. In this setting, we analyze the delay performance of the widely studied class of Back-Pressure scheduling policies, known for their throughput optimality property, using as a performance criterion the notion of delay stability, i.e., whether the expected end-to-end delay in steady state is finite. Our analysis highlights the significance of “bottleneck links,” i.e., links that are allowed to serve the source queues of heavy-tailed flows. The main idea is that traffic that has to pass through bottleneck links experiences large delays under Back-Pressure. By means of simple examples, we provide insights into how the network topology, the routing constraints, and the link capacities may facilitate or hinder the ability of light-tailed flows to avoid bottlenecks. Our delay-stability analysis is greatly simplified by the use of fluid approximations, allowing us to derive analytical results that would have been hard to obtain through purely stochastic arguments. Finally, we show how to achieve the best performance with respect to the delay stability criterion, by using a parameterized version of the Back-Pressure policy.

We analyze the effect of tumor repopulation on optimal dose delivery in radiation therapy. We are primarily motivated by accelerated tumor repopulation toward the end of radiation treatment, which is believed to play a role in treatment failure for some tumor sites. A dynamic programming framework is developed to determine an optimal fractionation scheme based on a model of cell kill from radiation and tumor growth in between treatment days. We find that faster tumor growth suggests shorter overall treatment duration. In addition, the presence of accelerated repopulation suggests larger dose fractions later in the treatment to compensate for the increased tumor proliferation. We prove that the optimal dose fractions are increasing over time. Numerical simulations indicate a potential for improvement in treatment effectiveness.

We study the problem of scheduling over time varying links in a network that serves both heavy-tailed and light tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic (the heavy queue), and the other receives light-tailed traffic (the light queue). The queues are connected to the server through time-varying ON/OFF links, which model fading wireless channels. We first show that the policy that gives complete priority to the light-tailed traffic guarantees the best possible tail behavior of both queue backlog distributions, whenever the queues are stable. However, the priority policy is not throughput maximizing, and can cause undesirable instability effects in the heavy queue. Next, we study the class of throughput optimal max-weight-α scheduling policies. We discover a threshold phenomenon, and show that the steady state light queue backlog distribution is heavy-tailed for arrival rates above a threshold value, and light-tailed otherwise. We also obtain the exact tail coefficient of the light queue backlog distribution under max-weight-α scheduling. Finally, we study a log-max-weight scheduling policy, which is throughput optimal, and ensures that the light queue backlog distribution is light-tailed.

We consider the problem of scheduling in a single-hop switched network with a mix of heavy-tailed and light-tailed traffic and analyze the impact of heavy-tailed traffic on the performance of Max-Weight scheduling. As a performance metric, we use the delay stability of traffic flows: A traffic flow is delay-stable if its expected steady-state delay is finite, and delay-unstable otherwise. First, we show that a heavy-tailed traffic flow is delay-unstable under any scheduling policy. Then, we focus on the celebrated Max-Weight scheduling policy and show that a light-tailed flow that conflicts with a heavy-tailed flow is also delay-unstable. This is true irrespective of the rate or the tail distribution of the light-tailed flow or other scheduling constraints in the network. Surprisingly, we show that a light-tailed flow can become delay-unstable, even when it does not conflict with heavy-tailed traffic. Delay stability in this case may depend on the rate of the light-tailed flow. Finally, we turn our attention to the class of Max-Weight-α scheduling policies. We show that if the α-parameters are chosen suitably, then the sum of the α-moments of the steady-state queue lengths is finite. We provide an explicit upper bound for the latter quantity, from which we derive results related to the delay stability of traffic flows, and the scaling of moments of steady-state queue lengths with traffic intensity.

We study a multi-server model with n flexible servers and rn queues, connected through a fixed bipartite graph, where the level of flexibility is captured by the average degree, d(n), of the queues. Applications in content replication in data centers, skill-based routing in call centers, and flexible supply chains are among our main motivations. We focus on the scaling regime where the system size n tends to infinity, while the overall traffic intensity stays fixed. We show that a large capacity region (robustness) and diminishing queueing delay (performance) are jointly achievable even under very limited flexibility (d(n) l n). In particular, when d(n) gg ln n , a family of random-graph-based interconnection topologies is (with high probability) capable of stabilizing all admissible arrival rate vectors (under a bounded support assumption), while simultaneously ensuring a diminishing queueing delay, of order ln n/ d(n), as n-> ∞. Our analysis is centered around a new class of virtual-queue-based scheduling policies that rely on dynamically constructed partial matchings on the connectivity graph.

We consider an infinite collection of agents who make decisions, sequentially, about an unknown underlying binary state of the world. Each agent, prior to making a decision, receives an independent private signal whose distribution depends on the state of the world. Moreover, each agent also observes the decisions of its last K immediate predecessors. We study conditions under which the agent decisions converge to the correct value of the underlying state. We focus on the case where the private signals have bounded information content and investigate whether learning is possible, that is, whether there exist decision rules for the different agents that result in the convergence of their sequence of individual decisions to the correct state of the world. We first consider learning in the almost sure sense and show that it is impossible, for any value of K. We then explore the possibility of convergence in probability of the decisions to the correct state. Here, a distinction arises: if K=1, learning in probability is impossible under any decision rule, while for K ≥ 2, we design a decision rule that achieves it. We finally consider a new model, involving forward looking strategic agents, each of which maximizes the discounted sum (over all agents) of the probabilities of a correct decision. (The case, studied in the previous literature, of myopic agents who maximize the probability of their own decision being correct is an extreme special case.) We show that for any value of K, for any equilibrium of the associated Bayesian game, and under the assumption that each private signal has bounded information content, learning in probability fails to obtain.

We consider the problem of packet scheduling in a single-hop network with a mix of heavy-tailed and light-tailed traffic, and analyze the impact of heavy-tailed traffic on the performance of Max-Weight scheduling. As a performance metric we use the delay stability of traffic flows: a traffic flow is delay stable if its expected steady-state delay is finite, and delay unstable otherwise. First, we show that a heavy-tailed traffic flow is delay unstable under any scheduling policy. Then, we focus on the celebrated Max-Weight scheduling policy, and show that a light-tailed flow that conflicts with a heavy-tailed flow is also delay unstable. This is true irrespective of the rate or the tail distribution of the light-tailed flow, or other scheduling constraints in the network. Surprisingly, we show that a light-tailed flow can be delay unstable, even when it does not conflict with heavy-tailed traffic. Furthermore, delay stability in this case may depend on the rate of the light-tailed flow. Finally, we turn our attention to the class of Max-Weight-α scheduling policies; we show that if the α-parameters are chosen suitably, then the sum of the α-moments of the steady-state queue lengths is finite. We provide an explicit upper bound for the latter quantity, from which we derive results related to the delay stability of traffic flows, and the scaling of moments of steady-state queue lengths with traffic intensity.

We investigate the asymptotic behavior of the steady-state queue-length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput-optimal max-weight-$\alpha $scheduling policies and derive an exact asymptotic characterization of the steady-state queue-length distributions. In particular, we show that the tail of the light queue distribution is at least as heavy as a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also shows that the celebrated max-weight scheduling policy leads to the worst possible tail coefficient of the light queue distribution, among all nonidling policies. Motivated by the above negative result regarding the max-weight-$\alpha $policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light queue tail while still being throughput-optimal.

We consider the decentralized Bayesian binary hypothesis testing problem in feedback architectures, in which the fusion center broadcasts information based on the messages of some sensors to some or all sensors in the network. We show that the asymptotically optimal detection performance (as quantified by error exponents) does not benefit from the feedback messages. In addition, we determine the corresponding optimal error exponents.

We investigate the asymptotic behavior of the steady-state queue length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput optimal max-weight-α scheduling policies, and derive an exact asymptotic characterization of the steady-state queue length distributions. In particular, we show that the tail of the light queue distribution is heavier than a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also shows that the celebrated max-weight scheduling policy leads to the worst possible tail of the light queue distribution, among all non-idling policies. Motivated by the above `negative' result regarding the max-weight-α policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light queue tail, while still being throughput optimal.

We propose and analyze a multi-server model that captures a performance trade-off between centralized and distributed processing. In our model, a fraction p of an available resource is deployed in a centralized manner (e.g., to serve a most loaded station) while the remaining fraction 1-p is allocated to local servers that can only serve requests addressed specifically to their respective stations.

We consider a communication network and study the problem of designing a high-throughput and low-delay scheduling policy that only requires a polynomial amount of computation at each time step. The well-known maximum weight scheduling policy, proposed by Tassiulas and Ephremides (1992), has favorable performance in terms of throughput and delay but, for general networks, it can be computationally very expensive. A related randomized policy proposed by Tassiulas (1998) provides maximal throughput with only a small amount of computation per step, but seems to induce exponentially large average delay. These considerations raise some natural questions. Is it possible to design a policy with low complexity, high throughput, and low delay for a general network? Does Tassiulas' randomized policy result in low average delay? In this paper, we answer both of these questions negatively. We consider a wireless network operating under two alternative interference models: (a) a combinatorial model involving independent set constraints and (b) the standard SINR (signal to interference noise ratio) model. We show that unlessNP⊆BPP(orP=NPfor the case of determistic arrivals and deterministic policies), and even if the required throughput is a very small fraction of the network's capacity, there does not exist a low-delay policy whose computation per time step scales polynomially with the number of queues. In particular, the average delay of Tassiulas' randomized algorithm must grow super-polynomially. To establish our results, we employ a clever graph transformation introduced by Lund and Yannakakis (1994).

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any connected, directed or undirected graph. Unlike most previous gossip algorithms, Weighted Gossip admits stochastic update matrices which need not be doubly stochastic. Double-stochasticity being very restrictive in a distributed setting, this novel degree of freedom is essential and it opens the perspective of designing a large number of new gossip-based algorithms. To give an example, we present one of these algorithms, which we call One-Way Averaging. It is based on random geographic routing, just like Path Averaging, except that routes are one way instead of round trip. Hence in this example, getting rid of double stochasticity allows us to add robustness to Path Averaging.

We consider a switched network, a fairly general constrained queueing network model that has been used successfully to model the detailed packet-level dynamics in communication networks, such as input-queued switches and wireless networks. The main operational issue in this model is that of deciding which queues to serve, subject to certain constraints.

We consider the problem of decentralized detection in a network consisting of a large number of nodes arranged as a tree of bounded height, under the assumption of conditionally independent and identically distributed (i.i.d.) observations. We characterize the optimal error exponent under a Neyman-Pearson formulation. We show that the Type II error probability decays exponentially fast with the number of nodes, and the optimal error exponent is often the same as that corresponding to a parallel configuration. We provide sufficient, as well as necessary, conditions for this to happen. For those networks satisfying the sufficient conditions, we propose a simple strategy that nearly achieves the optimal error exponent, and in which all non-leaf nodes need only send 1-bit messages.

We consider the problem of Bayesian decentralized binary hypothesis testing in a network of sensors arranged in a tandem. We show that the rate of error probability decay is always subexponential, establishing the validity of a long-standing conjecture. Under the additional assumption of bounded Kullback-Leibler (KL) divergences, we show that for alld> 1/2, the error probability is Omega(e-cnd), wherecis a positive constant. Furthermore, the bound Omega(e-c(logn)d) , for alld> 1, holds under an additional mild condition on the distributions. This latter bound is shown to be tight.

We study the asymptotic detection performance of large sensor networks, configured as trees with bounded height, in which information is progressively compressed as it moves towards the root of the tree. We show that the error probability decays exponentially fast, and we provide bounds for the error exponent. We analyze further the case where the tree has certain symmetry properties, and derive simple, easily implementable, suboptimal strategies

We consider the problem of decentralized binary hypothesis testing in a network of sensors arranged in a tandem. We show that the rate of error probability decay is always sub-exponential, establishing the validity of a long-standing conjecture. Under the additional assumption of bounded Kullback-Leibler divergences, we show that for all d > 1/2, the error probability is Omega(e-cnd), where c is a positive constant. Furthermore, the bound Omega(e-c(logn)d), for all d > 1, holds under an additional mild condition on the distributions. This latter bound is shown to be tight.

We study decentralized detection in tree networks with bounded height, and in which there are either sensor failures or unreliable communications between sensors. We characterize the asymptotically optimal performance of such tree networks, when certain parameters are allowed to become large, to model the case of dense sensor networks. We also develop simple strategies that nearly achieve the optimal performance.

We consider a slotted system with N queues, and independent and identically distributed (i.i.d.) Bernoulli arrivals at each queue during each slot. Each queue is associated with a channel that changes between "on" and "off" states according to i.i.d. Bernoulli processes. We assume that the system has K identical transmitters ("servers"). Each server, during each slot, can transmit up to C packets from each queue associated with an "on" channel. We show that a policy that assigns the servers to the longest queues whose channel is "on" minimizes the total queue size, as well as a broad class of other performance criteria. We provide several extensions, as well as some qualitative results for the limiting case where N is very large. Finally, we consider a "fluid" model under which fractional packets can be served, and subject to a constraint that at most C packets can be served in total from all of the N queues. We show that when K=N, there is an optimal policy which serves the queues so that the resulting vector of queue lengths is "Most Balanced" (MB)

We consider the problem of decentralized binary detection in a sensor network where the sensors have access to side information that affects the statistics of their measurements, or reflects the quality of the available channel to a fusion center. Sensors can decide whether or not to make a measurement and transmit a message to the fusion center ("censoring"), and also have a choice of the mapping from measurements to messages. We consider the case of a large number of sensors, and an asymptotic criterion involving error exponents. We study both a Neyman-Pearson and a , Bayesian formulation, characterize the optimal error exponent, and derive asymptotically optimal strategies for the case where sensor decisions are only allowed to depend on locally available information. Furthermore, we show that for the Neyman-Pearson case, global sharing of side information ("sensor cooperation") does not improve asymptotic performance, when the Type I error is constrained to be small.

We consider the problem of Bayesian decentralized binary detection in a sensor network in which the sensors have access to some side information that affects the statistics of the measurements they make. Sensors can decide whether or not to make a measurement and transmit a message to the fusion center ("censoring"), and also have a choice of the transmission function from measurements to messages. We consider the case of a large number of sensors, characterize the optimal error exponent, and derive asymptotically optimal strategies. We show that the optimal strategy consists of dividing the sensors into two groups, with sensors in each group using the same policy

The design of pricing mechanisms for network resource allocation has two important objectives: 1) a simple and scalable end-to-end implementation and 2) efficiency of the resulting equilibria. Both objectives are met by certain recently proposed mechanisms when users are price taking, but not when users can anticipate the effects of their actions on the resulting prices. In this paper, we partially close this gap, by demonstrating an alternative resource allocation mechanism which is scalable and guarantees a fully efficient allocation when users are price taking. In addition, when links have affine marginal cost, this mechanism has efficiency loss bounded by 1/3 when users are price anticipating. These results are derived by studying Cournot games, and in the process we derive the first nontrivial constant factor bounds on efficiency loss in these well-studied economic models.

We seek to maximize the average data throughput of a single transmitter sending data over a fading channel to a single user class. The transmitter has a fixed amount of energy and a limited amount of time to send data. Given that the channel state determines the throughput obtained per unit of energy expended, the goal is to obtain a policy for scheduling transmissions that maximizes the expected data throughput. We develop a dynamic programming formulation that leads to an optimal transmission schedule, first where the present channel state is known just before transmission, and then to the case where the current channel state is unknown before transmission, but observed after transmission and evolves according to a Markov process. We then extend our approach to the problem of minimizing the expected energy required to send a fixed amount of data over a fading channel given deadline constraints.

We consider the bias and variance of value function estimation that are caused by using an empirical model instead of the true model. We analyze these bias and variance for Markov processes from a classical (frequentist) statistical point of view, and in a Bayesian setting. Using a second order approximation, we provide explicit expressions for the bias and variance in terms of the transition counts and the reward statistics. We present supporting experiments with artificial Markov chains and with a large transactional database provided by a mail-order catalog firm.

We seek to maximize the data throughput of an energy and time constrained transmitter sending data over a fading channel. The transmitter has a fixed amount of energy and a limited amount of time to send data. Given that the channel fade state determines the throughput obtained per unit of energy expended, the goal is to obtain a policy for scheduling transmissions that maximizes the expected data throughput. We develop a dynamic programming formulation that leads to an optimal closed-form transmission schedule. We then extend our approach to the problem of minimizing the energy required to send a fixed amount of data over a fading channel given deadline constraints.

We address the issue of optimal energy allocation and admission control for communications satellites in Earth orbit. Such satellites receive requests for transmission as they orbit the Earth, but may not be able to serve them all, due to energy limitations. The objective is to choose which requests to serve so that the expected total reward is maximized. The special case of a single energy-constrained satellite is considered. Rewards and demands from users for transmission (energy) are random and known only at request time. Using a dynamic programming approach, an optimal policy is derived and is characterized in terms of thresholds. Furthermore, in the special case where demand for energy is unlimited, an optimal policy is obtained in closed form. Although motivated by satellite communications, our approach is general and can be used to solve a variety of resource allocation problems in wireless communications.

We address the issue of optimal energy allocation and admission control for communications satellites in Earth orbit. These satellites receive requests for transmission as they orbit the Earth, but may not be able to serve them all, due to energy limitations. The objective is to choose which requests to serve so that the expected total reward is maximized. The special case of a single energy-constrained satellite is considered. Rewards and demands from users for transmission (energy) are random and known only at request time. Using a dynamic programming approach, an optimal policy is derived and is characterized in terms of thresholds. Furthermore, in the special case where demand for energy is unlimited, an optimal policy is obtained in dosed form. Although motivated by satellite communications, our approach is general and can be used to solve a variety of resource allocation problems in wireless communications.

We introduce and analyze a simulation-based approximate dynamic programming method for pricing complex American-style options, with a possibly high-dimensional underlying state space. We work within a finitely parameterized family of approximate value functions, and introduce a variant of value iteration, adapted to this parametric setting. We also introduce a related method which uses a single (parameterized) value function, which is a function of the time-state pair, as opposed to using a separate (independently parameterized) value function for each time. Our methods involve the evaluation of value functions at a finite set, consisting of "representative" elements of the state space. We show that with an arbitrary choice of this set, the approximation error can grow exponentially with the time horizon (time to expiration). On the other hand, if representative states are chosen by simulating the state process using the underlying risk-neutral probability distribution, then the approximation error remains bounded.

We consider the problem of call admission control (CAC) and routing in an integrated services network that handles several classes of calls of different value and with different resource requirements. The problem of maximizing the average value of admitted calls per unit time (or of revenue maximization) is naturally formulated as a dynamic programming problem, but is too complex to allow for an exact solution. We use methods of neuro-dynamic programming (NDP) [reinforcement learning (RL)], together with a decomposition approach, to construct dynamic (state-dependent) call admission control and routing policies. These policies are based on state-dependent link costs, and a simulation-based learning method is employed to tune the parameters that define these link costs. A broad set of experiments shows the robustness of our policy and compares its performance with a commonly used heuristic.

We consider a service provider (SP) who provides access to a communication network or some other form of on-line services. Users initiate calls that belong to a set of diverse service classes, differing in resource requirements, demand pattern, and call duration. The SP charges a fee per call, which can depend on the current congestion level, and which affects users' demand for calls. We provide a dynamic programming formulation of the problems of revenue and welfare maximization, and derive some qualitative properties of the optimal solution. We also provide a number of approximate approaches, together with an analysis that indicates that near-optimality is obtained for the case of many, relatively small, users. In particular, we show analytically as well as computationally, that the performance of an optimal pricing strategy is closely matched by a suitably chosen static price, which does not depend on instantaneous congestion. This indicates that the easily implementable time-of-day pricing will often suffice. Throughout, we compare the alternative formulations involving revenue or welfare maximization, respectively, and draw some qualitative conclusions.

Article Estimation of time-varying parameters in statistical models: an optimization approach Share on Authors: Dimitris Bertsimas Sloan School of Management and Operations Research Center, MIT Cambridge, MA Sloan School of Management and Operations Research Center, MIT Cambridge, MAView Profile , David Gamarnik Operations Research Center, MIT Cambridge, MA Operations Research Center, MIT Cambridge, MAView Profile , John N. Tsitsiklis Laboratory for Information and Decision Sciences and Operations Research Center, MIT Cambridge, MA Laboratory for Information and Decision Sciences and Operations Research Center, MIT Cambridge, MAView Profile Authors Info & Claims COLT '97: Proceedings of the tenth annual conference on Computational learning theoryJuly 1997 Pages 314–324https://doi.org/10.1145/267460.267519Online:01 July 1997Publication History 1citation173DownloadsMetricsTotal Citations1Total Downloads173Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We are interested in solving large-scale Markov decision problems. The classical method of dynamic programming provides a mathematical framework for finding optimal solutions for a given Markov decision problem. However, dynamic programming algorithms become computationally infeasible when the underlying Markov decision problem evolves over a large state space. In recent years, a new methodology, called neuro-dynamic programming, has emerged which tries to overcome this "curse of dimensionality". We show how neuro-dynamic programming can be applied to the admission control problem for a single link in an ATM environment. Based on results obtained through neuro-dynamic programming, we derive a heuristic "threshold" policy. Performances of the policies obtained through neuro-dynamic programming are compared with a policy which always accepts a customer when the required resources are available.

We consider shortest path problems defined on graphs with random arc costs. We assume that information on arc cost values is accumulated as the graph is being traversed. The objective is to devise a policy that leads from an origin to a destination node with minimal expected cost. We provide dynamic programming algorithms, estimates for their complexity, negative complexity results, and analysis of some possible heuristic algorithms. © 1996 John Wiley & Sons, Inc.

We study the communication complexity of asynchronous distributed algorithms. Such algorithms can generate excessively many messages in the worst case. Nevertheless, we show that, under certain probabilistic assumptions, the expected number of messages generated per time unit is bounded by a polynomial function of the number of processors under a very general model of distributed computation. Furthermore, for constant-degree processor graphs, the expected number of generated messages is only O(nT) , where n is the number of processors and T is the running time. We conclude that (under our model) any asynchronous algorithm with good time complexity will also have good communication complexity, on the average.

We study the problem of statistical multiplexing of cell streams that have correlations at multiple time-scales. Each stream is modeled by a singularly perturbed Markov-modulated process with some state transitions occurring much less frequently than others. One motivation of this model comes from variable-rate compressed video, where the fast time-scale dynamics may correspond to correlations between adjacent frames, while the slow time-scale dynamics may correspond to correlations which in the same scene of a video sequence. We develop a set of large deviations results to estimate the buffer overflow probabilities in various asymptotic regimes in the buffer size, rare transition probabilities, and the number of streams. Using these results, we characterize the multiplexing gain in both the channel capacity and the buffering requirements and highlight the impact of the slow time-scale of the streams.>

Considers the problem of computing the length of a curve from digitized versions of the curve using parallel computation. The authors' aim is to study the inherent parallel computational complexity of this problem as a function of the digitization level. Precise formulations for the digitization, the parallel computation, and notions of local and nonlocal computations are given. It is shown that length cannot be computed locally from digitizations on rectangular tessellations. However, for a random tessellation and appropriate deterministic ones, the authors show that the length of straight line segments can be computed locally. Implications of the authors' results for a method for image segmentation and a number of open problems are discussed.>

We analyze the following problem. Each node of the d-dimensional hypercube independently generates packets according to a Poisson process with rate /spl lambda/. Each of the packets is to be sent to a randomly chosen destination; each of the nodes at Hamming distance k from a packet's origin is assigned an a priori probability p/sup k/(1-p)/sup d-k/. Packets are routed under a simple greedy scheme: each of them is forced to cross the hypercube dimensions required in increasing index-order, with possible queueing at the hypercube nodes. Assuming unit packet length and no other communications taking place, we show that this scheme is stable (in steady-state) if /spl rho/>

Two sensors obtain data vectors x and y, respectively, and transmit real vectors m/spl I.oarr//sub 1/(x) and m/spl I.oarr//sub 2/(y), respectively, to a fusion center. The authors obtain tight lower bounds on the number of messages (the sum of the dimensions of m/spl I.oarr//sub 1/ and m/spl I.oarr//sub 2/) that have to be transmitted for the fusion center to be able to evaluate a given function f/spl I.oarr/(x,y). When the function f/spl I.oarr/ is linear, they show that these bounds are effectively computable. Certain decentralized estimation problems can be cast in the framework and are discussed in some detail. In particular, the authors consider the case where x and y are random variables representing noisy measurements and f/spl I.oarr/(x,y)=E[z|x,y], where z is a random variable to be estimated. Furthermore, it is established that a standard method for combining decentralized estimates of Gaussian random variables has nearly optimal communication requirements.>

We consider a situation where two processors F'l and Pz are to evaluate a collection of functions f], . . . .f, of two-vector variables x, v, under the assumption that processor P] (respectively, Pz ) has access only to the value of the variable x (respectively, y) and the functional form of ~1,. . . .f,.We provide some new bounds on the communication complexity (the amount of information that has to be exchanged between the processors) for this problem.An almost optimal bound is derived for the case of one-way communication when the functions ~1, . . . .~, are polynomials.We also derive some new lower bounds for the case of two-way communication that improve on earlier bounds by Abelson [2].As an application, we consider the case where x and y are n X t~matrices and f(x, y) is a particular entry of the inverse of .r+ y.Under a certain restriction on the class of allowed communication protocols, we obtain an fl(n2) lower bound, in contrast to the Q(n) lower bound obtained by applying Abelson's results.Our results are based on certain tools from classical algebraic geomet~and field extension theory.

An extension of the standard probably approximately correct (PAC) learning model that allows the use of generalized samples is introduced. A generalized sample is viewed as a pair consisting of a functional on the concept class together with the value obtained by the functional operating on the unknown concept. It appears that this model can be applied to a number of problems in signal processing and geometric reconstruction to provide sample size bounds under a PAC criterion. A specific application of the generalized model to a problem of curve reconstruction is considered, and some connections with a result from stochastic geometry are discussed.>

M hypotheses and a random variable Y with a different probability distribution under each hypothesis are considered. A quantizer is applied to form a quantized random variable gamma (Y). The extreme points of the set of possible probability distributions of gamma (Y), as gamma ranges over all quantizers, is characterized. Optimality properties of likelihood-ratio quantizers are established for a very broad class of quantization problems, including problems involving the maximization of an Ali-Silvey (1966) distance measure and the Neyman-Pearson variant of the decentralized detection problem.>

The authors analyze the problem in which each node of the binary hypercube independently generates packets according to a Poisson process with rate lambda ; each of the packets is to be broadcast to all other nodes. Assuming unit packet length and no other communications taking place, it is observed that the system can be stable in steady-state only if the load factor rho identical to lambda (2/sup d/-1)/d satisfies rho>

In this paper, we introduce an extension of the standard PAC learning model which allows the use of generalized samples. We view a generalized sample as a pair consisting of a functional on the concept class together with the value obtained by the functional operating on the unknown concept. It appears that this model can be applied to a number of problems in signal processing and geometric reconstruction to provide sample size bounds under a PAC criterion. We consider a specific application of the model to a problem of curve reconstruction, and discuss some connections with a result from stochastic geometry.

Abstract Consider a complete directed graph in which each arc has a given length. There is a set of jobs, each job i located at some node of the graph, with an associated processing time hi, and whose execution has to start within a presepecified time window [ri, di]. We have a single server that can move on the arcs of the graph, at unit speed, and that has to execute all of the jobs within their respective time windows. We consider the following two problems: (a) minimize the time by which all jobs are executed (traveling salesman problem) and (b) minimize the sum of the waiting times of the jobs (traveling repairman problem). We focus on the following two special cases: (a) The jobs are located on a line and (b) the number of nodes of the graph is bounded by some integer constant B. Furthermore, we consider in detail the special cases where (a) all of the processing times are 0, (b) all of the release times ri are 0, and (c) all of the deadlines di are infinite. For many of the resulting problem combinations, we settle their complexity either by establishing NP‐completeness or by presenting polynomial (or pseudopolynomial) time algorithms. Finally, we derive algorithms for the case where, for any time t, the number of jobs that can be executed at that time is bounded.

We analyze the following problem: Each node of the d-

This paper considers the problem of evaluating a function $f(x,y)(x \in \Re ^m ,y \in \Re ^n )$ using two processors $P_1 $ and $P_2 $, assuming that processor $P_1 $ (respectively, $P_2 $) has access to input x (respectively, y) and the functional form of f. A new general lower bound is established on the communication complexity (i.e., the minimum number of real-valued messages that have to be exchanged). The result is then applied to the case where $f(x,y)$ is defined as a root z of a polynomial equation $\sum _{i = 0}^{n - 1} (x_i + y_i )z^i = 0$ and a lower bound of n is obtained. This is in contrast to the $\Omega (1)$ lower bound obtained by applying earlier results of Abelson.

A proof is provided that a logarithmic redundancy factor is necessary for the reliable computation of the parity function by means of a network with noisy gates. This result was first stated by R.L. Dobrushin and S.I. Ortyukov (1977). However, the authors believe that the analysis given by Dobrushin and Ortyukov is not entirely correct. The authors establish the result by following the same steps and by replacing the questionable part of their analysis with entirely new arguments.>

The authors show a sharp dichotomy between systems of identical automata with symmetric global control whose behavior is easy to predict and those whose behavior is hard to predict. The division pertains to whether the global control rule is invariant with respect to permutations of the states of the automaton. It is also shown that testing whether the global control rule has this invariance property is an undecidable problem. It is argued that there is a natural analog between complexity in the present model and chaos in dynamical systems.>

The authors consider a situation in which two processors P/sub 1/ and P/sub 2/ are to evaluate one or more functions f/sub 1/, . . ., f/sub s/ of two vector variables x and y, under the assumption that processor P/sub 1/ (respectively, P/sub 2/) has access only to the value of x (respectively, y) and the functional form of f/sub 1/, . . ., f/sub s/. They consider a continuous model of communication whereby real-valued messages are transmitted, and they study the minimum number of messages required for the desired computation. Tight lower bounds are established for the following three problems: (1) each f/sub i/ is a rational function and only one-way communication is allowed. (2) The variables x and y are matrices and the processors wish to solve the linear system (x+y)z=b for the unknown z. (3) The processors wish to evaluate a particular root of the polynomial equation Sigma (x/sub i/+y/sub i/)z/sup i/=0, where the sum is from i=0 to n-1.>

We consider iterative algorithms of the form x := ƒ(x), executed by a parallel or distributed computing system. We focus on asynchronous implementations whereby each processor iterates on a different component of x, at its own pace, using the most recently received (but possibly outdated) information on the remaining components of x. We provide results on the convergence rate of such algorithms and make a comparison with the convergence rate of the corresponding synchronous methods in which the computation proceeds in phases. We also present results on how to terminate asynchronous iterations in finite time with an approximate solution of the computational problem under consideration.

We consider the problem of optimal scheduling of a set of jobs obeying in-tree precedence constraints, when a number M of processors is available. It is assumed that the service times of different jobs are independent identically distributed random variables. Subject to a minor assumption on the service time distribution, we show that policies of the “Highest Level First” type are optimal asymptotically, as the number of jobs tends to infinity.

A queuing system with infinitely many servers, and with the following queuing discipline is considered: For any two jobs i and j in the system, such that i arrived later than j , there is a fixed probability p that i will have to wait for j 's execution to terminate before i starts executing. This queuing system is a very simple model for database concurrency control via “static” locking, as well as of parallel execution of programs consisting of several interdependent processes. The problem of determining the maximum arrival rate (as a function of p ) that can be sustained before this system becomes unstable is studied. It is shown that this rate is inversely proportional to p , and close upper and lower bounds on the constant for the case of deterministic departures are found. The result suggests that the degree of multiprogramming of multiuser databases, or the level of parallelism of concurrent programs, is inversely proportional to the probability of conflict, and that the constant is small and known within a factor of 2. The technique used involves the computation of certain asymptotic parameters of a random infinite directed acyclic graph (dag) that seem of interest by themselves.

The problem considered involves estimating a two-dimensional isotropic random field given noisy observations of this field over a disk of finite radius. By expanding the field and observations in Fourier series, and exploiting the covariance structure of the resulting Fourier coefficient processes, recursions are obtained for efficiently constructing the linear least-squares estimate of the field as the radius of the observation disk increases. These recursions are similar to the Levinson equations of one-dimensional linear prediction. In the spectral domain they take the form of Schrödinger equations, which are used to give an inverse spectral interpretation of our estimation procedure.