COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2003

Wireless sensor networks consist of a large number of tiny sensors that have only limited energy supply. One of the major challenges in constructing such networks is to maintain long network lifetime as well as sufficient sensing area. To achieve this goal, a broadly-used method is to turn off redundant sensors. In this talk, we will talk about the problem of estimating redundant sensing areas among neighbouring wireless sensors. We will present an interesting observation concerning the minimum and maximum number of neighbours that are required to provide complete redundancy and introduce simple methods to estimate the degree of redundancy without the knowledge of location or directional information. We also provide tight upper and lower bounds on the probability of complete redundancy and on the average partial redundancy. With random sensor deployment, our analysis shows that partial redundancy is more realistic for real applications, since complete redundancy is expensive, requiring up to 11 neighbouring sensors to provide a 90 percent chance of complete redundancy. Several open questions will be posed.

This talk will discuss preliminary results on a project to design scalable and attack-resistant distributed networks. Our notion of attack-resistance depends on the idea of protecting critical invariants from adversarial attack. Some important critical invariants include: (i) an arbitrarily large fraction (e.g. 99%) of the unattacked peers can access an arbitrarily large fraction (e.g. 99%) of the content stored in the network, (ii) an arbitrarily large fraction of the unattacked peers remain connected in the network, and (iii) an arbitrarily large fraction of the peers must either follow a fixed set of rules, or be disconnected from the network. We require that the networks be scalable in the sense that all major operations have polylogarithmic resource bounds.

We propose to maintain these invariants under attack by an omniscient adversary, i.e. we assume that the adversary knows, for example, the topology of the network, where content is stored in the network, and the network protocols. We further assume that the adversary can attack a constant fraction of the peers in the network. In a simple model of attack, the attacked peers will simply drop out of the network(i.e. the fail-stop fault model). In a more complicated model, the attacked peers can collude, and try to disrupt the functioning of the network by sending false information to other peers (i.e. the Byzantine fault model). We will discuss strategies for handling both types of attack.

Related papers:

• Dynamically Fault-Tolerant Content Addressable Networks. Jared Saia, Amos Fiat, Steve Gribble, Anna R. Karlin and Stefan Saroiu. First International Workshop on Peer-to-Peer Systems, 2002.
• Censorship Resistant Peer-To-Peer Content Addressable Networks. Amos Fiat and Jared Saia. Symposium on Discrete Algorithms 2002.

Previous Talks:

We consider the problem of drawing Venn diagrams for which each region's area is proportional to some weight (e.g., population or percentage) assigned to that region. These area-proportional Venn diagrams have an enhanced ability over traditional Venn diagrams to visually convey information about data sets with interacting characteristics. We develop algorithms for drawing area-proportional Venn diagrams for any population distribution over two characteristics using circles and over three characteristics using rectangles and near-rectangular polygons; modifications of these algorithms are then presented for drawing the more general Euler diagrams.

We present results concerning which population distributions can be drawn using specific shapes. A program to aid further investigation of area-proportional Venn diagrams is also described.

Cops and Robber is a pursuit game usually played on a digraph G with no vertices of outdegree zero, which may have loops at some vertices. To start the game, each of the k>0 cops chooses a vertex of G, and then the robber chooses a vertex of G. The cops and the robber then move alternately, with the cops moving first. A move for the cops consists of each cop travelling along an arc from his present vertex to a neighbouring vertex. A move for the robber is defined analogously. When a vertex has a loop, a cop or the robber can use it to remain at his current position. The game is played with perfect information, so that the cops and the robber always know each other's location. The cops win the game if they can move so that one of them eventually catches -- occupies the same vertex as -- the robber. The robber wins if he can move never to be caught. A digraph is k-cop-win if k cops have a winning strategy, and robber-win otherwise. Historically, 1-cop-win digraphs have been called cop-win.

This game was first described for reflexive undirected graphs with one cop and one robber by Nowakowski and Winkler, and Quilliot, independently. Both papers characterise the cop-win graphs. Beyond the one-cop case, no characterisations are known. It is a long standing open problem to characterise the k-cop-win reflexive undirected graphs for k>1. Cops and robber games on digraphs have not received as much attention. The reflexive digraphs on which a single cop can always win have also not been characterised.

We describe an algorithmic characterisation of the cop-win finite digraphs. It is in terms of an auxiliary digraph constructible in polynomial time. We then describe how any k-cop game can be reduced to a 1-cop game, thus giving a characterisation of the k-cop-win digraphs. We conclude by describing how these methods can be applied to some variants of the game.

Suppose Alice receives a request from Bob, a previously unknown entity, to play a movie she owns and controls the rights to. Further suppose that Alice previously delegated the power to grant access, or delegate access granting power, to a number of other entities. How does Alice determine the amount of trust she has in Bob, so that she can decide whether to allow him to view the content?

The D-Trust system is a graph-based approach to constructing generalized trust representations and performing trust metric computations.

This presentation is focused on exposing current challenges in both representing and processing graph-based models of trust, with a specific focus a particular abstract trust model created by Dr. U. Maurer (Federal Institute of Technology, Zurich).

Sooner or later, everyone figures out that in tic-tac-toe the first player will lose only if he makes an error. In general, it's a natural question for any sufficiently deterministic game to ask whether either player has a winning strategy. This question often turns out to be very difficult, and answers for most games are not nearly as forthcoming as for the simple case of tic-tac-toe. Algorithmic combinatorial game theory studies the algorithms and complexity of answering this and related problems for combinatorial games. It also encompasses similar study of one-player games, or puzzles

This talk surveys a few techniques and many of the results relevant to this field. Specific topics include Sprague-Grundy theory, board games, and combinatorial puzzles.

A Bilinski diagram is a labeling of the sets of vertices and faces of a planar map with respect to a given vertex x, called its center, and the regional distance of the other vertices of the map from x. Bilinski diagrams are of particular interest when this labeling corresponds to a planar embedding wherein the sets of vertices at the same regional distance from the center induce a sequence of concentric circuits about the center. A concentric Bilinski diagram is one with this property. If all Bilinski diagrams of a map, i.e., for every choice of center, are concentric, then we say that the map is uniformly vertex-concentric. Bilinski diagrams with such concentric properties are not only aesthetically appealing but are also an essential tool in constructing geodetic paths, rays, and double rays (geodesics) in planar maps. We establish tight sufficient conditions for an infinite, locally finite planar map to be uniformly vertex-concentric, consider some necessary conditions for uniform concentricity, and develop algorithms for constructing geodesics in such graphs.

In software testing, we often need to test functions with a list of parameters, where each parameter has a set of possible input values. A test generation strategy is an approach to iterating the input values of each parameter and generating a set of test cases for the function under test. The most fundamental test generation strategy is the Cartesian product generation, where the test set generated is the Cartesian product of the sets of input values of all parameters. Pairwise generation is a more specific generation strategy. Given n sets D1,D2,...Dn, A pairwise generation strategy creates a test set S that is a subset of D1*D2*...*Dn, where for each element x in Di and y in Dj (i,j=1..n and i!=j), there is at least one test case in S with x as the ith element and y as the jth element. A good pairwise generation strategy aims at creating a pairwise test set as small as possible. One of the algorithms for generating pairwise test sets is called In-Parameter-Order (IPO). In this talk, I am going to introduce an improvement of IPO based on iterating arrangements of a sequence of integers with repetitions. I will show that the improved algorithm always generates smaller test sets than the original IPO algorithm.

A directed graph is primitive if for some fixed positive integer m and each ordered pair of vertices (u,v), there exists a walk of length m from u to v. The exponent of a primitive directed graph is the smallest such m. One walk touches another in a directed graph if they have a vertex in common. The circumdiameter of a strongly connected directed graph is the maximum, over all ordered pairs of vertices (u,v), of the length of a shortest walk from u to v that touches cycles of all lengths. The circumdiameter can be used, together with the Frobenius-Schur index, to give an upper bound on the exponent of a primitive directed graph. A rudimentary method of computing the circumdiameter is presented in the hope of requesting ideas for a better algorithm.