Markov chains defined on the set of permutations of n elements have been studied widely by mathematicians and theoretical computer scientists. We consider chains in which a position i

We consider the following cryptographic secret leaking problem. A group of players communicate with the goal of learning (and perhaps revealing) a secret held initially by one of them. Their conversation is monitored by a computationally unlimited eavesdropper, who wants to learn the identity of the secret-holder. Despite the unavailability of key, some protection can be provided to the identity of the secret-holder. We call the study of such communication problems, either from the group's or the eavesdropper's point of view, cryptogenography. We introduce a basic cryptogenography problem and show that two players can force the eavesdropper to missguess the origin of a secret bit with probability 1/3; we complement this with a hardness result showing that they cannot do better than than 3/8. We prove that larger numbers of players can do better than 0.5644, but no group of any size can achieve 0.75.

In sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to make room. (In fact, a special case of this algorithm is commonly used to hand-sort files.) However, it is not obvious that this algorithm necessarily terminates. We show that in fact the algorithm terminates after at most 2n−1 – 1 steps in the worst case (confirming a conjecture of L. Larson), and that there are super-exponentially many permutations for which this exact bound can be achieved. The proof involves a curious symmetrical binary representation.

Let $f:{\cal L}\to\mathbb{R}$ be a submodular function on a modular lattice ${\cal L}$; we show that there is a maximal chain ${\cal C}$ in ${\cal L}$ on which the sequence of values of f is minimal among all paths from 0 to 1 in the Hasse diagram of ${\cal L}$, in a certain well-behaved partial order on sequences of reals. One consequence is that the maximum value of f on ${\cal C}$ is minimized over all such paths—i.e., if one can percolate from 0 to 1 on lattice points X with $f(X)\le b$, then one can do so along a maximal chain. The partial order on real sequences is defined by putting $\langle a(0),a(1),\dots,a(m)\rangle\preceq\langle b(0),\dots,b(n)\rangle$ if there is a way to “schedule” the sequences starting at $(a(0),b(0))$ and ending at $(a(m),b(n))$ so that always $a(i)\le b(j)$. Putting ${\bf a}\equiv{\bf b}$ if ${\bf a}\preceq{\bf b}\preceq{\bf a}$, each equivalence class has a unique shortest sequence which we call a worm. We use the properties of worms to give an efficient method to schedule many real sequences in parallel. The results in the paper are applied in a number of other settings, including obstacle navigation, graph search, coordinate percolation, and finding a lost child in a field.

Abstract – In contrast to a typical single source of data updates in Internet applications, data files in a networked information system are often distributed, replicated, accessed and updated by multiple nodes. Due to concurrent updates, replicated data files must be synchronized. For certain applications, stringent concurrency control must be employed to ensure data integrity, while for other applications, periodic data synchronization may enable very efficient data sharing. For the latter applications, this paper devises the ShuffleNet and hypercube schemes for data synchronization in such networked information systems. Their performance in terms of update delay, processing complexity, failure tolerance and growth complexity is examined. Our results reveal that the ShuffleNet and hypercube scheme provide identical maximum update delay and similar processing complexity. However, as the number of nodes in the system changes (e.g., due to failure or temporary out of service for maintenance), the hypercube scheme maintains all existing synchronization sessions and greatly simplifies system administration overhead such as moving files from node to node for the purpose of data synchronization. The ShuffleNet scheme does provide a higher degree of failure tolerance for global data files, but the hypercube scheme provides more than adequate failure tolerance. Lastly, a generalization of the hypercube scheme, based on the ideas of shift registers, is also proposed for systems where the number of nodes is a perfect power of 2. I.

We analyze and solve a game in which a player chooses which of several Markov chains to advance, with the object of minimizing the expected time (or cost) for one of the chains to reach a target state. The solution entails computing (in polynomial time) a function $\gamma$---a variety of "Gittins index"---on the states of the individual chains, the minimization of which produces an optimal strategy. It turns out that $\gamma$ is a useful cousin of the expected hitting time of a Markov chain but is defined, for example, even for random walks on infinite graphs. We derive the basic properties of $\gamma$ and consider its values in some natural situations.

Summary form only given. In the past decade many proofs of tractability, have involved showing that some Markov chain "mixes rapidly". We do a fast tour of the highlights of Markov chain mixing, with a view toward answering, or at least addressing, the following questions: What is rapid mixing? How do you prove it, and why would you want to? Does it really have anything to do with computational complexity? And, most disturbing: is there any truth to the rumor that complexity and rapid mixing are related to phase transitions in statistical physics?.

We consider the problem of client assignment in a distributed system of content servers. We present a system called Webmapper for clustering IP addresses and assigning each cluster to an optimal content server. The system is passive in that the only information it uses comes from monitoring the TCP connections between the clients and the servers. It is also flexible in that it makes no a priori assumptions about network topology and server placement and it can react quickly to changing network conditions. We present experimental results to evaluate the performance of Webmapper.

The following problem arose in the planning of optical communications networks which use bidirectional SONET rings. Traffic demands d i,j are given for each pair of nodes in an n-node ring; each demand must be routed one of the two possible ways around the ring. The object is to minimize the maximum load on the cycle, where the load of an edge is the sum of the demands routed through that edge. We provide a fast, simple algorithm which achieves a load that is guaranteed to exceed the optimum by at most 3/2 times the maximum demand, and that performs even better in practice. En route we prove the following curious lemma: for any x 1 ,..., x n in [0,1] there exist y 1 ,..., y n such that for each k, $|y_k|=x_k$ and $$ \left| \sum_{i=1}^k y_i - \sum_{i=k+1}^n y_i \right| \le 2. $$

Let lf be the transition matrix, and a the initial state distribution.for a discrete-time finite-state irreducible Markov chain.A stopping rule for M is an algorithm which observes the progress of the chain and then stops it at some random time r; the distribution of the final state is denoted by ar.We give a useful characterization for stopping rules which are optimal for given target distribution r, in the sense that Some of the work described herein is joint with David Aldous.

A token located at some vertex $v $ of a connected, undirected graph G on n vertices is said to be taking a “random walk” on G if, whenever it is instructed to move, it moves with equal probability to any of the neighbors of $v $. The authors consider the following problem: Suppose that two tokens are placed on G, and at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying to keep the tokens apart as long as possible. What is the expected time M before they meet? The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing. Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound. The authors use a novel potential function argument to show that in the worst case $M = ( \frac{4}{27} + o ( 1 ) )n^3 $.

LetX1,...,Xn be pairwise independent random variables of known (but not necessarily identical) distribution; we wish to select a subset of these whose sum will be as close as possible to some known target value T. Conditions described below force the selections to be made by a primitive distributed system (similar to one considered by Papadimitriou and Yannakakis [2] in PODC '91); here we are able to obtain a surprising amount of information about optimal solutions.The conditions are that each variable must be “programmed” in advance, joining the selected set according to its own value. Thus, for example, one variable might be programmed to join just if its value lies between a and b, while another is told to join regardless of its value. Our object is to find a strategy, that is, a collection of programs, which minimizes the mean square error in approximating T. Typical applications involve producing a steady flow of some commodity when supply is controlled at a multiplicity of random sources.It turns out that there is always an optimal strategy in which each Xi is programmed to join if its value is between 0 and ti, for appropriate choice of thresholds ti. When the variables are identically distributed, we examine conditions under which the ti's must be equal. The case of uniform distributions on [0,1], for which the above conditions are not satisfied, is analyzed in detail, showing the rather bizarre behavior of the ti's which may take place in general as the target value is gradually changed.Next, we analyze the problem in which the variables are permitted to contribute any part of themselves to the sum; here it turns out that in an optimal strategy each program will be of the form “contribute the minimum of Xi and ei” with all the ei's equal in the i.i.d. case.Finally, we show how the original target shooting problem can be generalized to a kind of load balancing, where variables are assigned to different buckets, each with its own target, and the penalty is a weighted sum of squared errors. The surprising result here is that when the weights are equal, an optimal solution assigns variables only according to their signs.

We show that the token management protocol proposed by Israeli and Jalfon in PODC '90 self-stabilizes in polynomial time.The protocol makes use of accidental meetings in random walks to reduce a multiplicity of tokens to only one.In an abstract setting, our theorem reads as follows:Let two tokens be placed on vertices of a connected, undirected, n-vertex graph.Suppose that at each tick of a clock a "schedule demon" points to one of the tokens, which then takes a random step to a neighboring vertex.Then, regardless of the demon's strategy, the tokens will meet in expected time at most 8n3/27.Our proof technique makes novel use of a potential function on pairs of vertices, a "remoteness" ordering and a random walk identity, all of which may be of independent theoretical interest.

We show that the problem of counting the number of linear extensions of a given partially ordered set is #P-complete.This settles a long-standing open question and contrssts with recent results giving randomized polynomial-time algorit hms for estimating the number of linear extensions.One consequence is that computing the volume of a rational polyhedron is strongly #P-hard.We also show that the closely related problems of determining the average height of an element c of a given poset, and of determining the probability that z lies below y in a random linear extension, are #P-complete.

Directed, strongly connected networks of finite-state automata, of bounded in- and outdegree but unknown topology and unbounded size n, are considered. Protocols that are quadratic or linear in n and accomplish the following tasks are provided: waking up and reporting when done, constructing smart spanning trees out from the root and in to the root, conducting breadth-first and depth-first searches, sending a message from the endpoint of a (directed) edge to its startpoint, running a slow clock, and solving the firing squad synchronization problem. The protocols are highly parallel and entail the use of sequences of signals called 'snakes''. All the tasks are accomplished in less time than is possible with any previously known techniques.>

The following equivalent results in the Boolean lattice $2^n $ are proven. (a) Every fibre of $2^n $ contains a maximal chain. (b) Every cutset of $2^n $ contains a maximal antichain. (c) Every red-blue colouring of the vertices of $2^n $ produces either a red maximal chain or a blue maximal antichain. (d) Given any n antichains in $2^n $ there is a disjoint maximal antichain. Statement (a) is then improved to: (a') Every fibre of $2^n $ contains at least $n!/2^{n - 1} $ maximal chains. One conjecture of Lonc and Rival is supported, and another conjecture disproved, by showing: (i) Every fibre of $2^n $ has order $\Omega ( 1.25^n )$elements. (ii) There is a minimal fibre of $2^n ( n\geqq 4 )$ of size $2^{n - 1} + 2$.

It is shown that for any graph G on n vertices, there is a number N (of order at most $n^3 (\log n)^2 $) and a graph H on N vertices such that for any ordering of the vertices of G and any ordering of the vertices of H, there is an order-isomorphism from G into H.

It is shown that the problem of realizing a metric by a graph or network with minimum total edge-length is, depending on the version, NP-hard or NP-complete. In particular, Discrete Metric Realization (DMR) is NP-complete “in the strong sense,” where DMR is defined as follows: INSTANCE. An n-by-n integer-entry distance matrix $D = ( d_{i,j} )$ and a positive integer k; QUESTION. Is there a graph $G = \langle V,E \rangle $ with distinguished vertices $v _1 ,v _2 , \cdots ,v _n $ that realize D, i.e., the number of edges in a shortest path between $v _i $ and $v _j $ is exactly $d_{i,j} $ for each $1\leqq i\leqq j\leqq n$, and such that the total number of edges of G is at most k?