Skip to main content
main-content

Über dieses Buch

ICALP 2009, the 36th edition of the International Colloquium on Automata, Languages and Programming, was held on the island of Rhodes, July 6–10, 2009. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS) which ?rst took place in 1972. This year, the ICALP program consisted of the established track A (focusing on algorithms, complexity and games) and track B (focusing on logic, automata, semantics and theory of programming), and of the recently introduced track C (in 2009 focusing on foundations of networked computation). In response to the call for papers, the Program Committee received 370 s- missions: 223 for track A, 84 for track B and 63 for track C. Out of these, 108 papers were selected for inclusion in the scienti?c program: 62 papers for track A, 24 for track B and 22 for track C. The selection was made by the Program Committees based on originality, quality, and relevance to theoretical computer science. The quality of the manuscripts was very high indeed, and many dese- ing papers could not be selected. ICALP 2009 consisted of ?ve invited lectures and the contributed papers.

Inhaltsverzeichnis

Frontmatter

Track B: Invited Lectures

A Survey of Stochastic Games with Limsup and Liminf Objectives

A stochastic game is a two-player game played on a graph, where in each state the successor is chosen either by one of the players, or according to a probability distribution. We survey stochastic games with limsup and liminf objectives. A real-valued reward is assigned to each state, and the value of an infinite path is the limsup (resp. liminf) of all rewards along the path. The value of a stochastic game is the maximal expected value of an infinite path that can be achieved by resolving the decisions of the first player. We present the complexity of computing values of stochastic games and their subclasses, and the complexity of optimal strategies in such games.

Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger

Tractable Optimization Problems through Hypergraph-Based Structural Restrictions

Several variants of the Constraint Satisfaction Problem have been proposed and investigated in the literature for modelling those scenarios where solutions are associated with some given costs. Within these frameworks computing an optimal solution is an NP-hard problem in general; yet, when restricted over classes of instances whose constraint interactions can be modelled via (nearly-)acyclic graphs, this problem is known to be solvable in polynomial time. In this paper, larger classes of tractable instances are singled out, by discussing solution approaches based on exploiting hypergraph acyclicity and, more generally, structural decomposition methods, such as (hyper)tree decompositions.

Georg Gottlob, Gianluigi Greco, Francesco Scarcello

Track B: Contributed Papers

Deciding Safety Properties in Infinite-State Pi-Calculus via Behavioural Types

In the pi-calculus, we consider decidability of certain safety properties expressed in a simple spatial logic. We first introduce a behavioural type system that, given a process

P

, tries to extract a spatial-behavioural type

T

, in the form of a

ccs

term that is logically equivalent to the given process. Using techniques based on well-structured transition systems, we then prove that, for an interesting fragment of the considered logic, satisfiability (

T

 ⊧ 

φ

) is decidable for types. As a consequence of logical equivalence between types and processes, we obtain decidability of this fragment of the logic for all well-typed pi-processes.

Lucia Acciai, Michele Boreale

When Are Timed Automata Determinizable?

In this paper, we propose an abstract procedure which, given a timed automaton, produces a language-equivalent deterministic infinite timed tree. We prove that under a certain boundedness condition, the infinite timed tree can be reduced into a classical

deterministic

timed automaton. The boundedness condition is satisfied by several subclasses of timed automata, some of them were known to be determinizable (event-clock timed automata, automata with integer resets), but some others were not. We prove for instance that strongly non-Zeno timed automata can be determinized. As a corollary of those constructions, we get for those classes the decidability of the universality and of the inclusion problems, and compute their complexities (the inclusion problem is for instance EXPSPACE-complete for strongly non-Zeno timed automata).

Christel Baier, Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye

Faithful Loops for Aperiodic E-Ordered Monoids

(Extended Abstract)

One of the main objectives of the algebraic theory of regular languages concerns the classification of regular languages based on Eilenberg’s variety theorem [10]. This theorem states that there exists a bijection between varieties of regular languages and varieties of finite monoids. For example, the variety of star-free regular languages (the closure of finite languages under Boolean operations and concatenation) is related to the monoid variety of aperiodic monoids (those with no nontrivial subgroups)[21].

Martin Beaudry, François Lemieux

Boundedness of Monadic Second-Order Formulae over Finite Words

We prove that the boundedness problem for monadic second-order logic over the class of all finite words is decidable.

Achim Blumensath, Martin Otto, Mark Weyer

Semilinear Program Feasibility

We study logical techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems (CSPs). For the fundamental algebraic structure

$\Gamma=(\mathbb R; L_1,L_2,\dots)$

where

$\mathbb R$

are the real numbers and

L

1

,

L

2

,... is an enumeration of all linear relations with rational coefficients, we prove that a semilinear relation

R

(i.e., a relation that is first-order definable with linear inequalities) either has a quantifier-free Horn definition in

Γ

or the CSP for

$(\mathbb R; R,L_1,L_2,\dots)$

is NP-hard. The result implies a complexity dichotomy for all constraint languages that are first-order expansions of

Γ

: the corresponding CSPs are either in P or are NP-complete depending on the choice of allowed relations. We apply this result to two concrete examples (generalised linear programming and metric temporal reasoning) and obtain full complexity dichotomies in both cases.

Manuel Bodirsky, Peter Jonsson, Timo von Oertzen

Floats and Ropes: A Case Study for Formal Numerical Program Verification

We present a case study of a formal verification of a numerical program that computes the discretization of a simple partial differential equation. Bounding the rounding error was tricky as the usual idea, that is to bound the absolute value of the error at each step, fails. Our idea is to find out a precise analytical expression that cancels with itself at the next step, and to formally prove the correctness of this approach.

Sylvie Boldo

Reachability in Stochastic Timed Games

We define stochastic timed games, which extend two-player timed games with probabilities (following a recent approach by Baier

et al

), and which extend in a natural way continuous-time Markov decision processes. We focus on the reachability problem for these games, and ask whether one of the players has a strategy to ensure that the probability of reaching a fixed set of states is equal to (or below, resp. above) a certain number

r

, whatever the second player does. We show that the problem is undecidable in general, but that it becomes decidable if we restrict to single-clock 1

$\frac{1}{2}$

-player games and ask whether the player can ensure that the probability of reaching the set is =1 (or >0, =0).

Patricia Bouyer, Vojtěch Forejt

Equations Defining the Polynomial Closure of a Lattice of Regular Languages

The

polynomial closure

Pol

$(\mathcal{L})$

of a class of languages

$\mathcal{L}$

of

A

*

is the set of languages that are finite unions of marked products of the form

L

0

a

1

L

1

...

a

n

L

n

, where the

a

i

are letters and the

L

i

are elements of

$\mathcal{L}$

.

The main result of this paper gives an equational description of Pol

$(\mathcal{L})$

, given an equational description of

$\mathcal{L}$

, when

$\mathcal{L}$

is a lattice of regular languages closed under quotients, or a

quotienting algebra of languages

, as we call it in the sequel. The term “equational description” refers to a recent paper [5], where it was shown that any lattice of regular languages can be defined by a set of profinite equations. More formally, our main result can be stated as follows:

Mário J. J. Branco, Jean-Éric Pin

Approximating Markov Processes by Averaging

We take a dual view of Markov processes – advocated by Kozen – as transformers of bounded measurable functions. We redevelop the theory of labelled Markov processes from this view point, in particular we explore approximation theory. We obtain three main results:

(i) It is possible to define bisimulation on general measure spaces and show that it is an equivalence relation. The logical characterization of bisimulation can be done straightforwardly and generally. (ii) A new and flexible approach to approximation based on averaging can be given. This vastly generalizes and streamlines the idea of using conditional expectations to compute approximation. (iii) It is possible to show that there is a minimal bisimulation equivalent to a process obtained as the limit of the finite approximants.

Philippe Chaput, Vincent Danos, Prakash Panangaden, Gordon Plotkin

The Theory of Stabilisation Monoids and Regular Cost Functions

We introduce the notion of regular cost functions: a quantitative extension to the standard theory of regular languages.

We provide equivalent characterisations of this notion by means of automata (extending the nested distance desert automata of Kirsten), of history-deterministic automata (history-determinism is a weakening of the standard notion of determinism, that replaces it in this context), and a suitable notion of recognisability by stabilisation monoids. We also provide closure and decidability results.

Thomas Colcombet

A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata

In this paper we establish a lower bound hist(

n

) for the problem of translating a Büchi word automaton of size

n

into a deterministic Rabin word automaton when both the Büchi and the Rabin condition label transitions rather than states. This lower bound exactly matches the known upper bound to this problem. The function hist(

n

) is in

Ω

((1.64

n

)

n

) and in

o

((1.65

n

)

n

).

Our result entails a lower bound of hist(

n

 − 1) when the input Büchi automaton has its Büchi acceptance condition labeling states (as it is usual). Those lower bounds remain when the output deterministic Rabin automaton has its Rabin acceptance condition labeling states.

Thomas Colcombet, Konrad Zdanowski

On Constructor Rewrite Systems and the Lambda-Calculus

We prove that orthogonal constructor term rewrite systems and lambda-calculus with weak (i.e., no reduction is allowed under the scope of a lambda-abstraction) call-by-value reduction can simulate each other with a linear overhead. In particular, weak call-by-value beta-reduction can be simulated by an orthogonal constructor term rewrite system in the same number of reduction steps. Conversely, each reduction in an orthogonal term rewrite system can be simulated by a constant number of weak call-by-value beta-reduction steps. This is relevant to implicit computational complexity, because the number of beta steps to normal form is polynomially related to the actual cost (that is, as performed on a Turing machine) of normalization, under weak call-by-value reduction. Orthogonal constructor term rewrite systems and lambda-calculus are thus both polynomially related to Turing machines, taking as notion of cost their natural parameters.

Ugo Dal Lago, Simone Martini

On Regular Temporal Logics with Past,

The IEEE standardized

Property Specification Language

, PSL for short, extends the well-known linear-time temporal logic LTL with so-called semi-extended regular expressions. PSL and the closely related

SystemVerilog Assertions

, SVA for short, are increasingly used in many phases of the hardware design cycle, from specification to verification. In this paper, we extend the common core of these specification languages with past operators. We name this extension RTL. Although all

ω

-regular properties are expressible in PSL, SVA, and RTL, past operators often allow one to specify properties more naturally and concisely. In fact, we show that RTL is exponentially more succinct than the cores of PSL and SVA. Furthermore, we present a translation of RTL into language-equivalent nondeterministic Büchi automata, which is based on novel constructions for 2-way alternating automata. Our translation has almost the same worst-case complexity in terms of the size of the resulting nondeterministic Büchi automata as the existing translations for PSL and SVA. Consequently, the satisfiability and the model-checking problem for RTL fall into the same complexity classes as the corresponding problems for PSL and SVA. From the translation it also follows that the blowup of translating RTL formulas into initially equivalent PSL/SVA formulas is at most triply exponential.

Christian Dax, Felix Klaedtke, Martin Lange

Forward Analysis for WSTS, Part II: Complete WSTS

We describe a simple, conceptual forward analysis procedure for ∞-complete WSTS

$\mathfrak S$

. This computes the

clover

of a state

s

0

, i.e., a finite description of the closure of the cover of

s

0

. When

$\mathfrak S$

is the completion of a WSTS

$\mathfrak X$

, the clover in

$\mathfrak S$

is a finite description of the cover in

$\mathfrak X$

. We show that this applies exactly when

$\mathfrak X$

is an

ω

2

-WSTS

, a new robust class of WSTS. We show that our procedure terminates in more cases than the generalized Karp-Miller procedure on extensions of Petri nets. We characterize the WSTS where our procedure terminates as those that are

clover-flattable

. Finally, we apply this to well-structured counter systems.

Alain Finkel, Jean Goubault-Larrecq

Qualitative Concurrent Stochastic Games with Imperfect Information

We study a model of games that combines concurrency, imperfect information and stochastic aspects. Those are finite states games in which, at each round, the two players choose,

simultaneously

and

independently

, an action. Then a successor state is chosen accordingly to some fixed probability distribution depending on the previous state and on the pair of actions chosen by the players. Imperfect information is modeled as follows: both players have an equivalence relation over states and, instead of observing the exact state, they only know to which equivalence class it belongs. Therefore, if two partial plays are indistinguishable by some player, he should behave the same in both of them. We consider reachability (does the play eventually visit a final state?) and Büchi objective (does the play visit infinitely often a final state?).

Our main contribution is to prove that the following problem is complete for 2-

ExpTime

: decide whether the first player has a strategy that ensures her to almost-surely win against

any

possible strategy of her oponent. We also characterise those strategies needed by the first player to almost-surely win.

Vincent Gripon, Olivier Serre

Diagrammatic Confluence and Completion

We give a new elegant proof that decreasing diagrams imply confluence based on a proof reduction technique, which is then the basis of a novel completion method which proof-reduction relation transforms arbitrary proofs into rewrite proofs even in presence of non-terminating reductions. Unlike previous methods, no ordering of the set of terms is required, but can be used if available. Unlike ordered completion, rewrite proofs are closed under instantiation. Examples are presented, including Kleene’s and Huet’s classical examples showing that non-terminating local-confluent relations may not be confluent.

Jean-Pierre Jouannaud, Vincent van Oostrom

Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus

Ong has shown that the modal mu-calculus model checking problem (equivalently, the alternating parity tree automaton (APT) acceptance problem) of possibly-infinite ranked trees generated by order-

n

recursion schemes is

n

-EXPTIME complete. We consider two subclasses of APT and investigate the complexity of the respective acceptance problems. The main results are that, for APT with a single priority, the problem is still

n

-EXPTIME complete; whereas, for APT with a disjunctive transition function, the problem is (

n

 − 1)-EXPTIME complete. This study was motivated by Kobayashi’s recent work showing that the resource usage verification for functional programs can be reduced to the model checking of recursion schemes. As an application, we show that the resource usage verification problem is (

n

 − 1)-EXPTIME complete.

Naoki Kobayashi, C. -H. Luke Ong

LTL Path Checking Is Efficiently Parallelizable

We present an

AC

1

(log

DCFL

) algorithm for checking LTL formulas over finite paths, thus establishing that the problem can be efficiently parallelized. Our construction provides a foundation for the parallelization of various applications in monitoring, testing, and verification.

Lars Kuhtz, Bernd Finkbeiner

An Explicit Formula for the Free Exponential Modality of Linear Logic

The exponential modality of linear logic associates a commutative comonoid !

A

to every formula

A

in order to duplicate it. Here, we explain how to compute the free commutative comonoid !

A

as a sequential limit of equalizers in any symmetric monoidal category where this sequential limit exists and commutes with the tensor product. We then apply this general recipe to two familiar models of linear logic, based on coherence spaces and on Conway games. This algebraic approach enables to unify for the first time apparently different constructions of the exponential modality in spaces and games. It also sheds light on the subtle duplication policy of linear logic. On the other hand, we explain at the end of the article why the formula does not work in the case of the finiteness space model.

Paul-André Melliès, Nicolas Tabareau, Christine Tasson

Decidability of the Guarded Fragment with the Transitive Closure

We consider an extension of the guarded fragment in which one can guard quantifiers using the transitive closure of some binary relations. The obtained logic captures the guarded fragment with transitive guards, and in fact extends its expressive power non-trivially, preserving the complexity: we prove that its satisfiability problem is

2Exptime

-complete.

Jakub Michaliszyn

Weak Alternating Timed Automata

Alternating timed automata on infinite words are considered. The main result is a characterization of acceptance conditions for which the emptiness problem for the automata is decidable. This result implies new decidability results for fragments of timed temporal logics. It is also shown that, unlike for MITL, the characterisation remains the same even if no punctual constraints are allowed.

Pawel Parys, Igor Walukiewicz

A Decidable Characterization of Locally Testable Tree Languages

A regular tree language L is locally testable if the membership of a tree into L depends only on the presence or absence of some neighborhoods in the tree. In this paper we show that it is decidable whether a regular tree language is locally testable.

Thomas Place, Luc Segoufin

The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games

We analyse the computational complexity of finding Nash equilibria in simple stochastic multiplayer games. We show that restricting the search space to equilibria whose payoffs fall into a certain interval may lead to undecidability. In particular, we prove that the following problem is undecidable: Given a game

$\mathcal G$

, does there exist a pure-strategy Nash equilibrium of

$\mathcal G$

where player 0 wins with probability 1. Moreover, this problem remains undecidable if it is restricted to strategies with (unbounded) finite memory. However, if mixed strategies are allowed, decidability remains an open problem. One way to obtain a provably decidable variant of the problem is to restrict the strategies to be positional or stationary. For the complexity of these two problems, we obtain a common lower bound of NP and upper bounds of NP and

PSpace

respectively.

Michael Ummels, Dominik Wojtczak

Track C: Invited Lecture

Google’s Auction for TV Ads

This document describes the auction system used by Google for allocation and pricing of TV ads. It is based on a simultaneous ascending auction, and has been in use since September 2008.

Noam Nisan, Jason Bayer, Deepak Chandra, Tal Franji, Robert Gardner, Yossi Matias, Neil Rhodes, Misha Seltzer, Danny Tom, Hal Varian, Dan Zigmond

Track C: Contributed Papers

Graph Sparsification in the Semi-streaming Model

Analyzing massive data sets has been one of the key motivations for studying streaming algorithms. In recent years, there has been significant progress in analysing distributions in a streaming setting, but the progress on graph problems has been limited. A main reason for this has been the existence of linear space lower bounds for even simple problems such as determining the connectedness of a graph. However, in many new scenarios that arise from social and other interaction networks, the number of vertices is significantly less than the number of edges. This has led to the formulation of the semi-streaming model where we assume that the space is (near) linear in the number of vertices (but not necessarily the edges), and the edges appear in an arbitrary (and possibly adversarial) order.

However there has been limited progress in analysing graph algorithms in this model. In this paper we focus on graph sparsification, which is one of the major building blocks in a variety of graph algorithms. Further, there has been a long history of (non-streaming) sampling algorithms that provide sparse graph approximations and it a natural question to ask: since the end result of the sparse approximation is a small (linear) space structure, can we achieve that using a small space, and in addition using a single pass over the data? The question is interesting from the standpoint of both theory and practice and we answer the question in the affirmative, by providing a one pass

$\tilde{O}(n/\epsilon^{2})$

space algorithm that produces a sparsification that approximates each cut to a (1 + 

ε

) factor. We also show that

$\Omega(n \log \frac1\epsilon)$

space is necessary for a one pass streaming algorithm to approximate the min-cut, improving upon the

Ω

(

n

) lower bound that arises from lower bounds for testing connectivity.

Kook Jin Ahn, Sudipto Guha

Sort Me If You Can: How to Sort Dynamic Data

We formulate and study a new computational model for dynamic data. In this model the data changes gradually and the goal of an algorithm is to compute the solution to some problem on the data at each time step, under the constraint that it only has a limited access to the data each time. As the data is constantly changing and the algorithm might be unaware of these changes, it cannot be expected to always output the exact right solution; we are interested in algorithms that guarantee to output an approximate solution. In particular, we focus on the fundamental problems of sorting and selection, where the true ordering of the elements changes slowly. We provide algorithms with performance close to the optimal in expectation and with high probability.

Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal

Maximum Bipartite Flow in Networks with Adaptive Channel Width

Traditionally, combinatorial optimization problems (such as maximum flow, maximum matching, etc.) have been studied for networks where each link has a fixed capacity. Recent research in wireless networking has shown that it is possible to design networks where the capacity of the links can be changed

adaptively

to suit the needs of specific applications. In particular, one gets a choice of having

few

high capacity outgoing links or

many

low capacity ones at any node of the network. This motivates us to have a re-look at the traditional combinatorial optimization problems and design algorithms to solve them in this new framework. In particular, we consider the problem of

maximum bipartite flow

, which has been studied extensively in the traditional network model. One of the motivations for studying this problem arises from the need to maximize the throughput of an infrastructure wireless network comprising base-stations (one set of vertices in the bipartition) and clients (the other set of vertices in the bipartition). We show that this problem has a significantly different combinatorial structure in this new network model from the classical one. While there are several polynomial time algorithms solving the maximum bipartite flow problem in traditional networks, we show that the problem is NP-hard in the new model. In fact, our proof extends to showing that the problem is APX-hard. We complement our lower bound by giving two algorithms for solving the problem approximately. The first algorithm is deterministic and achieves an approximation factor of

O

(log

N

), where there are

N

nodes in the network, while the second algorithm (which is our main contribution) is randomized and achieves an approximation factor of

$\frac{e}{e-1}$

.

Yossi Azar, Aleksander Mądry, Thomas Moscibroda, Debmalya Panigrahi, Aravind Srinivasan

Mediated Population Protocols

We extend here the Population Protocol model of Angluin et al. [2] in order to model more powerful networks of very small resource-limited artefacts (agents) that are possibly mobile. The main feature of our extended model is to allow edges of the communication graph,

G

, to have

states

that belong to a constant size set. We also allow edges to have

readable only costs

, whose values also belong to a constant size set. Our protocol specifications are still independent of the population size and do not use agent ids, i.e. they preserve

uniformity

and

anonymity

. Our Mediated Population Protocols (MPP) can stably compute graph properties of the communication graph. We show this for the properties of maximal matchings (in undirected communication graphs), also for finding the transitive closure of directed graphs and for finding all edges of small cost. We demonstrate that our mediated protocols are stronger than the classical population protocols, by presenting a MPP for a non-semilinear predicate. To show this fact, we state and prove a general theorem about the composition of two stably computing mediated population protocols. We also show that all predicates stably computable in our model are (non-uniformly) in the class

NSPACE

(|

E

(

G

)|).

Ioannis Chatzigiannakis, Othon Michail, Paul G. Spirakis

Rumor Spreading in Social Networks

Social networks are an interesting class of graphs likely to become of increasing importance in the future, not only theoretically, but also for its probable applications to ad hoc and mobile networking. Rumor spreading is one of the basic mechanisms for information dissemination in networks, its relevance stemming from its simplicity of implementation and effectiveness. In this paper, we study the performance of rumor spreading in the classic preferential attachment model of Bollobás et al. which is considered to be a valuable model for social networks. We prove that, in these networks: (a) The standard

PUSH-PULL

strategy delivers the message to all nodes within

O

(log

2

n

) rounds with high probability; (b) by themselves,

PUSH

and

PULL

require polynomially many rounds. (These results are under the assumption that

m

, the number of new links added with each new node is at least 2. If

m

 = 1 the graph is disconnected with high probability, so no rumor spreading strategy can work.) Our analysis is based on a careful study of some new properties of preferential attachment graphs which could be of independent interest.

Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi

MANETS: High Mobility Can Make Up for Low Transmission Power

We consider

Mobile Ad-hoc NETworks (MANETs)

formed by

n

nodes that move independently at random over a finite square region of the plane. Nodes exchange data if they are at distance at most

r

within each other, where

r

 > 0 is the

node transmission radius

. The

flooding time

is the number of time steps required to broadcast a message from a

source

node to every node of the network. Flooding time is an important measure of the speed of information spreading in dynamic networks.

We derive a nearly-tight upper bound on the

flooding time

which is a

decreasing

function of the maximal

velocity

of the nodes.

It turns out that, when the node velocity is “sufficiently” high, even if the node transmission radius

r

is far below the

connectivity threshold

, the flooding time does not asymptotically depend on

r

. So, flooding can be very fast even though every

snapshot

(i.e. the static random geometric graph at any fixed time) of the MANET is fully disconnected.

Our result is the first

analytical

evidence of the fact that high, random node mobility strongly speed-up information spreading and, at the same time, let

nodes save energy

.

Andrea E. F. Clementi, Francesco Pasquale, Riccardo Silvestri

Multiple Random Walks and Interacting Particle Systems

We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make our analysis for random regular graphs. The cover time of a random walk on a random

r

-regular graph was studied in [6], where it was shown with high probability (

whp

), that for

r

 ≥ 3 the cover time is asymptotic to

θ

r

n

ln

n

, where

θ

r

 = (

r

 − 1)/(

r

 − 2). In this paper we prove the following (

whp

) results. For

k

independent walks on a random regular graph

G

, the cover time

C

G

(

k

) is asymptotic to

C

G

/

k

, where

C

G

is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is

$\theta_r n/\binom{k}{2}$

. If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for

k

walks to broadcast a single piece of information to each other is asymptotic to 2

θ

r

n

(ln

k

)/

k

, as

k

,

n

→ ∞.

We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing, or by annihilating each other. For example, the expected extinction time of

k

explosive particles (

k

even) tends to (2ln 2)

θ

r

n

as

k

→ ∞.

The case of

n

coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbour. The expected time for a unique opinion to emerge is the expected time for all the particles to coalesce, which is asymptotic to 2

θ

r

n

.

Combining results from the predator-prey and multiple random walk models allows us to compare expected detection time in the following cops and robbers scenarios: both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, the predators move randomly and the prey stays fixed. In all cases, with

k

predators and ℓ prey the expected detection time is

θ

r

H

n

/

k

, where

H

is the ℓ-th harmonic number.

Colin Cooper, Alan Frieze, Tomasz Radzik

Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies

We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot’s walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural undirected counterparts of the rotor-router model for symmetric directed graphs.

The first of the studied strategies, known as Oldest-First (

OF

), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (

LUF

) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph

G

 = (

V

,

E

) of diameter

$\mathit{D}$

within time

$O(\mathit{D}|E|)$

, and in the long run traverses all edges of

G

with the same frequency.

Colin Cooper, David Ilcinkas, Ralf Klasing, Adrian Kosowski

On a Network Generalization of the Minmax Theorem

We consider graphical games in which the edges are zero-sum games between the endpoints/players; the payoff of a player is the sum of the payoffs from each incident edge. Such games are arguably very broad and useful models of networked economic interactions. We give a simple reduction of such games to two-person zero-sum games; as a corollary, a mixed Nash equilibrium can be computed efficiently by solving a linear program and rounding off the results. Our results render polynomially efficient, and simplify considerably, the approach in [3].

Constantinos Daskalakis, Christos H. Papadimitriou

Rate-Based Transition Systems for Stochastic Process Calculi

A variant of Rate Transition Systems (RTS), proposed by Klin and Sassone, is introduced and used as the basic model for defining stochastic behaviour of processes. The transition relation used in our variant associates to each process, for each action, the set of possible futures paired with a measure indicating their rates. We show how RTS can be used for providing the operational semantics of stochastic extensions of classical formalisms, namely CSP and CCS. We also show that our semantics for stochastic CCS guarantees associativity of parallel composition. Similarly, in contrast with the original definition by Priami, we argue that a semantics for stochastic

π

-calculus can be provided that guarantees associativity of parallel composition.

Rocco De Nicola, Diego Latella, Michele Loreti, Mieke Massink

Improved Algorithms for Latency Minimization in Wireless Networks

In the

interference scheduling problem

, one is given a set of

n

communication requests described by source-destination pairs of nodes from a metric space. The nodes correspond to devices in a wireless network. Each pair must be assigned a power level and a color such that the pairs in each color class can communicate simultaneously at the specified power levels. The feasibility of simultaneous communication within a color class is defined in terms of the Signal to Interference plus Noise Ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests.

We introduce an instance-based measure of interference, denoted by

I

, that enables us to improve on previous results for the interference scheduling problem. We prove upper and lower bounds in terms of

I

on the number of steps needed for scheduling a set of requests. For general power assignments, we prove a lower bound of

Ω

(I / (log

Δ

log n)) steps, where

Δ

denotes the aspect ratio of the metric. When restricting to the two-dimensional Euclidean space (as previous work) the bound improves to

Ω

(

I

(log

Δ

). Alternatively, when restricting to linear power assignments, the lower bound improves even to

Ω

(

I

). The lower bounds are complemented by an efficient algorithm computing a schedule for linear power assignments using only

$\mathcal O(I \log n)$

steps. A more sophisticated algorithm computes a schedule using even only

$\mathcal O(I + \log^2 n)$

steps. For dense instances in the two-dimensional Euclidean space, this gives a constant factor approximation for scheduling under linear power assignments, which shows that the price for using linear (and, hence, energy-efficient) power assignments is bounded by a factor of

$\mathcal O(\log \Delta)$

.

In addition, we extend these results for single-hop scheduling to multi-hop scheduling and combined scheduling and routing problems, where our analysis generalizes previous results towards general metrics and improves on the previous approximation factors.

Alexander Fanghänel, Thomas Keßelheim, Berthold Vöcking

Efficient Methods for Selfish Network Design

Intuitively, Braess’s paradox states that

destroying

a part of a network may

improve

the common latency of selfish flows at Nash equilibrium. Such a paradox is a pervasive phenomenon in real-world networks. Any administrator, who wants to improve equilibrium delays in selfish networks, is facing some basic questions: (i) Is the network

paradox-ridden

? (ii) How can we delete some edges to

optimize

equilibrium flow delays? (iii) How can we modify edge latencies to

optimize

equilibrium flow delays?

Unfortunately, such questions lead to NP-hard problems in general. In this work, we impose some natural restrictions on our networks, e.g. we assume strictly increasing linear latencies. Our target is to formulate

efficient algorithms

for the three questions above. We manage to provide:

A polynomial-time algorithm that decides if a network is paradox-ridden, when latencies are linear and strictly increasing.

A reduction of the problem of deciding if a network with arbitrary linear latencies is paradox-ridden to the problem of generating all optimal basic feasible solutions of a Linear Program that describes the optimal traffic allocations to the edges with constant latency.

An algorithm for finding a subnetwork that is almost optimal wrt equilibrium latency. Our algorithm is

subexponential

when the number of paths is polynomial and each path is of polylogarithmic length.

A polynomial-time algorithm for the problem of finding the best subnetwork, which outperforms any known approximation algorithm for the case of strictly increasing linear latencies.

A polynomial-time method that turns the optimal flow into a Nash flow by deleting the edges not used by the optimal flow, and performing minimal modifications to the latencies of the remaining ones.

Our results provide a deeper understanding of the computational complexity of recognizing the Braess’s paradox most severe manifestations, and our techniques show novel ways of using the probabilistic method and of exploiting convex separable quadratic programs.

Dimitris Fotakis, Alexis C. Kaporis, Paul G. Spirakis

Smoothed Analysis of Balancing Networks

In a load balancing network each processor has an initial collection of unit-size jobs, tokens, and in each round, pairs of processors connected by balancers split their load as evenly as possible. An excess token (if any) is placed according to some predefined rule. As it turns out, this rule crucially effects the performance of the network. In this work we propose a model that studies this effect. We suggest a model bridging the uniformly-random assignment rule, and the arbitrary one (in the spirit of smoothed-analysis) by starting from an arbitrary assignment of balancer directions, then flipping each assignment with probability

α

independently. For a large class of balancing networks our result implies that after

$\mathcal O(\log n)$

rounds the discrepancy is

whp

$\mathcal O( (1/2-\alpha) \log n + \log \log n)$

. This matches and generalizes the known bounds for

α

= 0 and

α

= 1/2.

Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik

Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures

We introduce a new theoretical model of ad hoc mobile computing in which agents have restricted memory, highly unpredictable movement and no initial knowledge of the system. Each agent’s memory can store

O

(1) bits, plus a unique identifier, and

O

(1) other agents’ identifiers. Inputs are distributed across

n

agents, and all agents must converge to the correct output value. We give a universal construction that proves the model is surprisingly strong: It can solve any decision problem in

NSPACE

(

n

log

n

). Moreover, the construction is robust with respect to Byzantine failures of a constant number of agents.

Rachid Guerraoui, Eric Ruppert

Multi-armed Bandits with Metric Switching Costs

In this paper we consider the stochastic multi-armed bandit with metric switching costs. Given a set of locations (arms) in a metric space and prior information about the reward available at these locations, cost of getting a sample/play at every location and rules to update the prior based on samples/plays, the task is to maximize a certain objective function constrained to a distance cost of

L

and cost of plays

C

. This fundamental and well-studied problem models several optimization problems in robot navigation, sensor networks, labor economics, etc.

In this paper we develop a general duality-based framework to provide the first

O

(1) approximation for metric switching costs; the actual constants being quite small. Since these problems are Max-SNP hard, this result is the best possible. The overall technique and the ensuing structural results are independently of interest in the context of bandit problems with complicated side-constraints. Our techniques also improve the approximation ratio of the budgeted learning problem from 4 to 3 + 

ε

.

Sudipto Guha, Kamesh Munagala

Algorithms for Secretary Problems on Graphs and Hypergraphs

We examine online matching problems with applications to Internet advertising reservation systems. Consider an edge-weighted bipartite graph

G

(

L

 ∪ 

R

,

E

). We develop an 8-competitive algorithm for the following

secretary

problem: Initially given

R

, and the size of

L

, the algorithm receives the vertices of

L

sequentially, in a random order. When a vertex

l

 ∈ 

L

is seen, all edges incident to

l

are revealed, together with their weights. The algorithm must immediately either match

l

to an available vertex of

R

, or decide that

l

will remain unmatched.

In [5], the authors show a 16-competitive algorithm for the transversal matroid secretary problem, which is the special case with weights on vertices, not edges. (Equivalently, one may assume that for each

l

 ∈ 

L

, the weights on all edges incident to

l

are identical.) We use a very similar algorithm, but simplify and improve the analysis to obtain a better competitive ratio for the more general problem. Our analysis is easily extended to obtain competitive algorithms for a class of similar problems, such as to find disjoint sets of edges in hypergraphs where edges arrive online. We also introduce secretary problems with adversarially chosen

groups

.

Finally, we give a 2

e

-competitive algorithm for the secretary problem on graphic matroids, where, with edges appearing online, the goal is to find a maximum-weight acyclic subgraph of a given graph.

Nitish Korula, Martin Pál

Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps

We address the fundamental distributed problem of leader election in ad hoc radio networks modeled as undirected graphs. Nodes are stations having distinct integer labels, and each node knows only its own label and a polynomial upper bound on all labels. A signal from a transmitting node reaches all neighbors. What distinguishes radio networks from message-passing networks is that a message is received successfully by a node, if and only if, exactly one of its neighbors transmits in this round. If two neighbors of a node transmit simultaneously in a given round, none of the messages is heard by the receiving node. In this case we say that a

collision

occurred at this node.

An important capability of nodes of a radio network is

collision detection

: the ability of nodes to distinguish a collision from the background noise occurring when no neighbor transmits. (This ability is the “keen ear” of the nodes.) Can collision detection speed up leader election in arbitrary radio networks? We give a positive answer to this question. More precisely, our main result is a deterministic leader election algorithm working in time

O

(

n

) in all

n

-node networks, if collision detection is available, while it is known that deterministic leader election requires time

Ω

(

n

log

n

), even for complete networks, if there is no collision detection. This is the first computational task whose execution for arbitrary radio networks is shown to be faster with collision detection than without it.

Dariusz R. Kowalski, Andrzej Pelc

Secure Function Collection with Sublinear Storage

Consider a center possessing a trusted (tamper proof) device that wishes to securely compute a public function over private inputs that are contributed by some network nodes. In network scenarios that support direct communication of nodes with the center, the computation can be done by the nodes encrypting their inputs under the device’s public key and sending the ciphertexts to the center which, in turn, feeds them to the trusted device that computes the function. In many modern networking scenarios, however, the center and the contributing nodes are not directly connected/connectable, in which case the discovery and collection of inputs can only be performed by an agent (or agents) released to the network by the center. This introduces a new set of issues for secure computation. In this work we consider an agent that is released, sweeps the network once and then returns to its origin. The direct solution, in this case, is for the agent to possess a certified public key of the trusted device and for the nodes to contribute their inputs as ciphertexts under this key; once the agent collects all inputs it reconnects with the center for function computation. The above single-sweep simple collection requires the agent to store a linear number of ciphertexts. The goal of this work is to formalize and solve the above problem for a general set of functions by an agent that employs sub-linear storage while maintaining input privacy (an important technical requirement akin of that of “Private Information Retrieval” protocols).

Maged H. Ibrahim, Aggelos Kiayias, Moti Yung, Hong-Sheng Zhou

Worst-Case Efficiency Analysis of Queueing Disciplines

Consider

n

users vying for shares of a divisible good. Every user

i

wants as much of the good as possible but has diminishing returns, meaning that its

utility

U

i

(

x

i

) for

x

i

 ≥ 0 units of the good is a nonnegative, nondecreasing, continuously differentiable concave function of

x

i

. The good can be produced in any amount, but producing

$X = \sum_{i=1}^n x_i$

units of it incurs a cost

C

(

X

) for a given nondecreasing and convex function

C

that satisfies

C

(0) = 0. Cost might represent monetary cost, but other interesting interpretations are also possible. For example,

x

i

could represent the amount of traffic (measured in packets, say) that user

i

injects into a queue in a given time window, and

C

(

X

) could denote aggregate delay (

X

·

c

(

X

), where

c

(

X

) is the average per-unit delay). An altruistic designer who knows the utility functions of the users and who can dictate the allocation

x

 = (

x

1

,...,

x

n

) can easily choose the allocation that maximizes the

welfare

$W(x) = \sum_{i=1}^n U_i(x_i) - C(X)$

, where

$X = \sum_{i=1}^n x_i$

, since this is a simple convex optimization problem.

Damon Mosk-Aoyama, Tim Roughgarden

On Observing Dynamic Prioritised Actions in SOC

We study the impact on observational semantics for SOC of priority mechanisms which combine dynamic priority with local pre-emption. We define manageable notions of strong and weak labelled bisimilarities for COWS, a process calculus for SOC, and provide alternative characterisations in terms of open barbed bisimilarities. These semantics show that COWS’s priority mechanisms partially recover the capability to observe receive actions (that could not be observed in a purely asynchronous setting) and that high priority primitives for termination impose specific conditions on the bisimilarities.

Rosario Pugliese, Francesco Tiezzi, Nobuko Yoshida

A Distributed and Oblivious Heap

This paper shows how to build and maintain a distributed heap which we call SHELL. In contrast to standard heaps, our heap is oblivious in the sense that its structure only depends on the nodes currently in the network but not on the past. This allows for fast join and leave operations which is desirable in open distributed systems with high levels of churn and frequent faults. In fact, a node fault or departure can be fixed in SHELL in a constant number of communication rounds, which significantly improves the best previous bound for distributed heaps. SHELL has interesting applications. First, we describe a robust distributed information system which is resilient to Sybil attacks

of arbitrary scale

. Second, we show how to organize heterogeneous nodes of

arbitrary

non-uniform capabilities in an overlay network such that the paths between any two nodes do not include nodes of lower capacities. This property is useful, e.g., for streaming. All these features can be achieved without sacrificing scalability: our heap has a de Bruijn like topology with node degree

O

(log

2

n

) and network diameter

O

(log

n

),

n

being the total number of nodes in the system.

Christian Scheideler, Stefan Schmid

Proportional Response Dynamics in the Fisher Market

In this paper, we show that the proportional response dynamics, a utility based distributed dynamics, converges to the market equilibrium in the Fisher market with constant elasticity of substitution (CES) utility functions. By the proportional response dynamics, each buyer allocates his budget proportional to the utility he receives from each good in the previous time period. Unlike the tâtonnement process and its variants, the proportional response dynamics is a large step discrete dynamics, and the buyers do not solve any optimization problem at each step. In addition, the goods are always cleared and assigned to the buyers proportional to their bids at each step. Despite its simplicity, the dynamics converges fast for strictly concave CES utility functions, matching the best upperbound of computing the market equilibrium via solving a global convex optimization problem.

Li Zhang

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise