Synchronization-Free Load-Balancing
Since the meet with the long-expected ``power wall'' in 2005, hardware
manufacturers have been developing multicore/parallel computers that
can host multiple of cores or processors in a single machine. Current
multicore computers feature as many an several dozens of processors.
In the near future, the numbers are expected to grow to hundreds and
even thousands. To harness the power of multicore computers, nearly
any parallel programming systems rely on a load-balancing algorithm
that can efficiently distribute parallel tasks among available
processors. Many such load-balancing algorithms have been developed
over the several decades. Unfortunately, all existing algorithms rely
on synchronization operations, such as memory fences (barriers) and
atomic read-write operations (e.g., compare and swap) for controlling
access to shared, concurrent data structures. Since such operations
require agreement between multiple processors, they tend to be
expensive and can lead to serialization of parallel computations,
thus, limiting scalability. In this talk, I present a load-balancing
algorithm that requires no atomic read-modify-write operations and no
memory fences on modern hardware such as Intel's multicore chips. The
algorithm eliminates synchronization by relying on asynchronous
messages (exchanged via memory) and by taking advantage of some unique
properties of hardware shared memory systems, e.g., the ability to
drop messages (via overriding).
Michael A. Bender, Stony Brook and Tokutek, Inc., USA
Cache-Adaptive Algorithms
For decades practitioners have recognized the desirability of algorithms that adapt as the availability of RAM changes. There exists a theoretical framework for designing algorithms that adapt to these memory fluctuations, but the last decade and a half has seen essentially no theoretical followup work.
We prove that a general class of cache-oblivious algorithms (but not all of them) are optimally cache-adaptive.
Joint work with Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley.
Keren Censor-Hillel, Technion, Israel
A New Perspective on Vertex Connectivity
Vertex and edge connectivity are fundamental graph-theoretic concepts, as they give measures for flows and robustness. While there is extensive knowledge in the literature about edge connectivity, using the essential tool of edge-disjoint spanning trees, much less is known about vertex connectivity, mainly due to the exponential number of vertex cuts, as opposed to the polynomial number of edge cuts.
In this talk I will present new results that propose CDS (connected dominating set) partitions and packings as tools that help us argue about the vertex connectivity of graphs. I will show algorithms for obtaining an optimal CDS packing of size Omega(k/logn) and a CDS partition of size Omega(k/log^5n) in k-vertex connected graphs. Our results also apply to analyzing vertex connectivity under random vertex sampling, showing an almost optimal bound of \tilde{Omega}(kp^2) for the vertex connectivity of a graph whose vertexes are sampled with probability p from a k-vertex connected graph. Finally, I will discuss applications to the throughput of store-and-forward broadcast algorithms.
Based on joint work with Mohsen Ghaffari and Fabian Kuhn.
Customizable Route Planning in Road Networks
In this talk, I will present the latest version of our customizable route planning engine. It can compute exact shortest paths in continental road networks (with tens of millions of road segments) and is able to incorporate realistic turn costs, custom height and weight restrictions, personal preferences, and traffic in real time. Moreover, it can efficiently answer extended queries such as computing distance tables or best points-of-interest, which are important building blocks for advanced map applications.
Joint work with Andrew Goldberg, Thomas Pajor, and Renato Werneck
Camil Demetrescu, "Sapienza" U. Rome, Italy
Algorithmic challenges in dynamic program analysis
Dynamic program analysis encompasses the development of tools
and techniques for analyzing computer software by gathering information from
programs at runtime. Relevant applications include performance profi ling, debugging,
intrusion detection, and program understanding. Optimizing the performance
of dynamic analysis tools is of fundamental importance for their effective
deployment and usability, and poses many algorithmic challenges. The
highly data-intensive nature of the problem has several consequences. First,
since analysis routines are typically inlined with program execution, analyzed
programs may be substantially slowed down. Second, tools must be able to
analyze huge streams of low-level events generated by a program at typical
rates of several megabytes per second. Dealing with such problems requires a
genuine combination of application-oriented research and innovative contributions
in algorithm engineering and general algorithmic techniques.
In this talk I plan to discuss examples of algorithmic problems arising in
this speci c application domain and to show how results in algorithmic
theory can be applied to the design and implementation of analysis tools. I will
also address examples of how novel analysis methodologies can help algorithm
engineers tune the performance of their code.
Faith Ellen, U. of Toronto, Canada
Efficient Fetch-and-Increment
A Fetch-and-Increment object stores a non-negative integer and supports a single operation,
FI, that returns the value of the object and increments
it. Such objects are used in many asynchronous shared memory algorithms,
such as renaming, mutual exclusion, and barrier synchronization.
We present the first implementation of a wait-free Fetch-and-Increment
object from registers and LL/SC objects that has poly-logarithmic step
complexity and polynomial space complexity, using logarithmic sized words.
This work is joint with Vijaya Ramachandran and Philipp Woelfel
and appeared at DISC 2012.
Funda Ergun, Simon Fraser U., Canada
Streaming algorithms where order matters
In most streaming problems, we strive to compute
statistical properties of the input stream. In
such cases, we are mostly interested in the frequency
of objects in the stream rather then when they appear. In
this talk, we will make a case for algorithms
computing functions on streams where the order of elements
in the stream matter. This includes the (almost entire)
string algorithms literature, as well as part of the online
algorithms area.
Amos Fiat, Tel Aviv U., Israel
TBA
Loukas Georgiadis, U. Ioannina, Greece
Finding Dominators in Interprocedural Flowgraphs
The computation of dominators in a flowgraph has applications in diverse areas including program optimization and code generation, constraint programming, circuit testing, and theoretical biology. Efficient algorithms for this problem operate in the intraprocedural case where all flowgraph paths are valid. In the interprocedural case, which appears in the setting of whole-program analysis and optimization, however, there are path constraints that have to be taken into account. As a result, the most efficient algorithms for computing dominators cannot handle the interprocedural case. Unlike the intraprocedural dominators problem, the transitive reduction of the interprocedural dominance relation is not a tree but a directed acyclic graph. In this talk we discuss efficient algorithms for computing the interprocedural dominance relation.
Andrew V. Goldberg, Microsoft Research Silicon Valley
Highway Dimension: From Practice to Theory and Back
Computing driving directions has motivated many shortest path heuristics that answer queries on continental-scale networks, with tens of millions of intersections, in real time. The underlying algorithms are highly practical and intuitive, but until recently there was no theoretical explanation of their practical performance. We review some of these algorithms and give the first theoretical analysis for them on a non-trivial class of networks.
For our analysis, we introduce the notion of highway dimension. The analysis gives good bounds for networks with low highway dimension. Our analysis explores an unexpected relationship to VC-dimension, which leads to better algorithms.
We also show that the hub labeling algorithm achieves a better theoretical time bound. This motivates a heuristic implementation of this algorithm. Our experimenters show that the implementation outperforms the fastest previous codes, validating the theoretical prediction.
Compared to the SODA 2010 and ICALP 2011 papers, this talk contains new results, including an improved definition of highway dimension that is a strengthening of the doubling dimension, improved bounds, and a new analysis of the transit node algorithm.
Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck
Roberto Grossi, U. Pisa, Italy
Height-Partitioning of AVL Trees
We introduce and discuss the notion of height partitioning for an AVL tree in order to maintain it as a collection of linked complete binary trees: its tree topology and insertion algorithm are preserved, while the deletions are weak (logically mark as deleted and periodically rebuild). We describe how AVL trees can simultaneously attain several properties in this way: better memory allocation, space-efficient representation, cache obliviousness, and dynamization of static data structures. We show how to dynamically maintain the height partitioning of an AVL tree in logarithmic amortized time and constant average time per update. As a byproduct of our analysis, we can amortize with the same bounds, the cost of rebuilding the whole subtree of the critical node after performing its rotation(s), thus overcoming some limitations of exponential potential functions.
Joint work with M. Amani, A. Bernasconi, and L. Pagli.
Monika Henzinger, U. Wien, Austria
Breaking the O(n m) Barrier for Buechi Games and Maximal End-Component Decomposition
Computing the winning set for Buechi Games and computing the maximal end-component decomposition in graphs are central problems in computer aided verification. We present a simple technique that gives O(n^2)-time algorithms for both problems, improving a running time bound from 1991.
This is joint work with Krishnendu Chatterjee.
John Iacono, Polytechnic U., USA
The Power and Limitations of Static Binary Search Trees with Lazy Finger
A static binary search tree where every search starts from where the
previous one ends (lazy finger) is considered. Such a search method is
more powerful than that of the classic optimal static trees, where
every search starts from the root (root finger), and less powerful
than when rotations are allowed---where finding the best rotation
based tree is the topic of the dynamic optimality conjecture of
Sleator and Tarjan. The runtime of the classic root-finger tree can be
expressed in terms of the entropy of the distribution of the searches,
but we show that this is not the case for the optimal lazy finger
tree. A non-entropy based asymptotically-tight expression for the
runtime of the optimal lazy finger trees is derived, and a dynamic
programming-based method is presented to compute the optimal tree.
This is joint work with Prosenjit Bose, Karim Douïeb, Stefan Langerman.
Haim Kaplan, Tel-Aviv U., Israel
Incremental cycle detection
In the incremental cycle detection problem we maintain a directed acyclic graph under insertions of arcs and would like to detect the first insertion that closes a directed cycle.
I will describe a new technique for solving this problem.
Dynamic Graph Connectivity in Polynomial Expected Worst Case Time
The dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes which is undergoing a sequence of edge insertions and deletions, answer queries of the form Q(a,b): "Is there a path between nodes a and b?" While data structures for this problem with polylogarithmic amortized time per operation have been known since the mid-1990's, these data structures have Theta(n) worst case time. In fact, no previously known solution has worst case time per operation which is o(n^{1/2}). In this talk I'll explain a solution with worst case times O(log^4 n) per edge insertion, O(log^5 n) per edge deletion, and O(log n/log log n) per query. The answer to each query is correct if the answer is ``yes" and is correct with high probability if the answer is ``no".
This work is joint with Bruce Kapron and Ben Mountjoy.
Aleksander Madry, EPFL, Switzerland
TBA
Lasserre hierarchies of relaxations, applied to knapsack
Ian Munro, U. of Waterloo, Canada
Succinct data structures for representing equivalence classes
Given a partition of an n element set into equivalence classes,
we consider time-space trade-off for representing it to support the query
that asks whether two given elements are in the same equivalence class.
This has various applications including for testing whether two vertices
are in the same connected component in an undirected graph or in the
same strongly connected component in a directed graph.
We consider the problem in several situations.
- First we examine the problem of labeling nodes so that with no additional information, we can determine whether two labels come from the same class. A tight bound on the range of labels is determined.
- Next we consider the issue of labeling schemes where we assign distinct labels from the range 1,..,n, and determine the additional space necessary to respond to equivalence class queries.
- Efficient algorithms for responding to queries under this minimal label model are presented.
- Finally we discuss updating the labels after a sequence of class union operations.
This is joint work with Moshe Lewenstein and Venkatesh Raman
Multimodal Route Planning - An Overview
This talk gives an overview of recent approaches to location-to-location route planning for multimodal networks consisting of schedule-based public transit, (unrestricted) walking, driving, and cycling. We discuss modeling issues arising with each mode of transportation including specialties like in bicycle rental systems. We review recent algorithmic approaches to the problem such as preprocessing techniques that enable fast queries for interactive applications and conclude by discussing several open challenges.
Liam Roditty, Bar-Ilan U., Israel
Maintaining strongly connected components
We consider the problem of maintaining the strongly connected components (SCCs) of an $n$-nodes and $m$-edges directed graph that undergoes a sequence of edge deletions. Recently, in SODA 2011, {\L}\k{a}cki presented a deterministic algorithm that preprocess the graph in $O(mn)$ time and creates a data structure that maintains the SCCs of a graph under edge deletions with a total update time of $O(mn)$. The data structure answers strong connectivity queries in $O(1)$ time. The worst case update time after a single edge deletion might be as large as $O(mn)$. In this paper we reduce the preprocessing time and the worst case update time of {\L}\k{a}cki's data structure from $O(mn)$ to $O(m \log n)$. The query time and the total update time remain unchanged.
Jared Saia, U. of New Mexico, USA
Byzantine Agreement in Polynomial Expected Time
How can we build a reliable system out of unreliable parts? Byzantine agreement is fundamental to addressing this question. The Byzantine agreement problem is to devise an algorithm so that n agents, each with a private input can agree on a single common output that is equal to some agent's input. In the classic Byzantine agreement problem, communication is via asynchronous message-passing and the adversary is adaptive with full information. In particular, the adversary can adaptively determine which processors to corrupt and what strategy these processors should use as the algorithm proceeds; the scheduling of the delivery of messages is set by the adversary, so that the delays are unpredictable to the algorithm; and the adversary knows the states of all processors at any time, and is assumed to be computationally unbounded. Such an adversary is also known as strong.
We present a polynomial expected time algorithm to solve asynchronous Byzantine Agreement with a strong adversary that controls up to a constant fraction of the processors. This is the fi rst improvement in running time for this problem since Ben-Or's exponential expected time solution in 1983. Our algorithm is designed so that in order to thwart it, corrupted agents must engage in statistically deviant behavior that is detectable by individual agents. This suggests a new paradigm for secure distributed computing: the design of algorithms that force an attacker into behavior that is statistically deviant in a way that is computationally detectable.
Siddhartha Sen, Princeton U., USA
TBA
(Recursive) Cycle Separators in Planar Graphs
Divide-and-conquer algorithms for planar graphs usually exploit
separators, pioneered in seminal work of Lipton and Tarjan.
Many of the more recent planar graph algorithms (such as those for min
cut, max flow, shortest paths with negative lengths, or distance
oracles) use a more elaborate "combine" phase, exploiting non-crossing
properties. To run this combine phase efficiently, the separator is
required to correspond to a Jordan curve (as opposed to an arbitrary
set of points). Many recent planar graph algorithms therefore use
Miller's cycle separator algorithm, generally as a black box.
We shall discuss a new (and arguably simpler) cycle separator
algorithm, its implementations (both theoretical and in actual code),
and its application in a new algorithm that computes recursive cycle
separator decompositions in linear time.
Joint work with Philip N. Klein and Shay Mozes (STOC 2013), and Eli
Fox-Epstein, Shay Mozes, and Phitchaya Mangpo Phothilimthana, (ALENEX
2013)
Robert E. Tarjan, Princeton U. and HP, USA
Disjoint Set Union With Randomized Linking
A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naïve linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? New work of Ashish Goal, Sanjjev Khanna, Mikhail Kapralov, and the speaker shows that randomized linking is as efficient as linking by rank. This result provides theory that matches the experiments, since the experiments implicitly do randomized linking as a result of the way the inputs are generated.
Virginia Vassilevska Williams, UC Berkeley, USA
Approximating the graph diameter
I'll present efficient algorithms for approximating the diameter of a directed or undirected graph with nonnegative weights. The running time of the algorithms on sparse graphs with n vertices and n^{1+o(1)} edges is O(n^{2-eps}) for constant eps>0, that is they are polynomially faster than any algorithm computing
distance estimates for all pairs of nodes. The first algorithm runs in \tilde{O}(m\sqrt n} expected time for graphs with n vertices and m edges and returns an estimate E for the diameter D that satisfies D\geq E\geq 2D/3-W where W is the largest distance in the graph. The second algorithm is deterministic and runs in \tilde{O}(mn^{2/3} log W) time and returns an estimate E with D\geq E\geq 2D/3 when the weights are integers.
I'll also give evidence that these algorithms are optimal in the following sense: if there is an algorithm that runs in O(n^{2-eps}) time for some constant eps>0 on all undirected unweighted graphs with n^{1+o(1)} edges that returns an estimate E with D\geq E\geq (2/3+\delta)D for some constant \delta>0, then the Strong Exponential Time Hypothesis of Impagliazzo, Paturi and Zane is false.
Based on joint work with Liam Roditty and Shiri Chechik.
Search-Space Size in Contraction Hierarchies
Contraction hierarchies are a speed-up technique to improve the
performance of shortest-path computations, which works very well in
practice. Despite convincing practical results, there is still a
lack of theoretical explanation for this behavior.
In this talk, we present a theoretical framework for studying search
space sizes in contraction hierarchies. We prove the first bounds on
the size of search spaces that depend solely on structural parameters
of the input graph, that is, they are independent of the edge lengths. To
achieve this, we establish a connection with the well-studied
elimination game. Our bounds apply to graphs with treewidth k, and
to any minor-closed class of graphs that admits small separators. For
trees, we show that the maximum search space size can be minimized
efficiently, and the average size can be approximated efficiently
within a factor of 2.
We show that, under a worst-case assumption on the edge lengths, our
bounds are comparable to the recent results of Abraham et
al. (ICALP'11), whose analysis depends also on the edge
lengths. As a side result, we link their notion of highway
dimension (a parameter that is conjectured to be small, but is
unknown for all practical instances) with the notion of pathwidth.
This is the first relation of highway dimension with a well-known
graph parameter.
This is joint work with Reinhard Bauer, Tobias Columbus and Ignaz Rutter.
An Exact Combinatorial Algorithm for Graph Bisection
We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them.
Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. Besides introducing stronger lower bounds, we propose a new decomposition technique that contracts entire regions of the graph without losing optimality guarantees. In practice, our algorithm works particularly well on instances with relatively small minimum bisections, solving large real-world graphs (with tens of thousands to more than a million vertices) to optimality.
Joint work with Daniel Delling, Daniel Fleischman , Andrew Goldberg, and Ilya Razenshteyn.
Uri Zwick, Tel-Aviv U., Israel
A forward-backward single-source shortest paths algorithm
We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithms only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the out-going
and incoming adjacency lists of the vertices appear in non-decreasing order of weight. The running time of the algorithm on a complete directed graph on $n$ vertices with independent exponential edge weights is $O(n)$, with very high probability. This improves on the previously best result of $O(n\log n)$, which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms.
Joint work with David Wilson.