Randomized Consensus in Expected O(n^2) Total Work using Single-Writer Registers

James Aspnes

A new weak shared coin protocol yields a randomized wait-free shared-memory consensus protocol that uses an optimal expected total work with single-writer registers despite asynchrony and process crashes. Previously, no protocol was known that achieved this bound without using multi-writer registers.

Guest: James Aspnes
Host: Yvonne-Anne Pignolet

Black Hole Search with Finite Automata Scattered in a Synchronous Torus

Jeremie Chalopin, Shantanu Das, Arnaud Labourel and Euripides Markou

We consider the problem of locating a black hole in synchronous anonymous networks using finite-state agents. A black hole is a harmful node in the network that destroys any agent visiting that node without leaving any trace. The objective is to locate the black hole without destroying too many agents. This is difficult to achieve when the agents are initially scattered in the network and are unaware of the location of each other. Previous studies for black hole search used more powerful models where the agents had non-constant memory, were labelled with distinct identifiers and could either write messages on the nodes of the network or mark the edges of the network. In contrast, we solve the problem using a small team of finite-state agents each carrying a constant number of identical tokens that could be placed on the nodes of the network. Thus, all resources used in our algorithms are independent of the network size. We restrict our attention to oriented torus networks and first show that no team of finite-state agents can solve the problem in such networks, when the tokens are not movable. In case the agents are equipped with movable tokens, we determine lower bounds on thenumber of agents and tokens required for solving the problem in torus networks of arbitrary size. Further, we present a deterministic solution to the black hole search problem for oriented torus networks, using the minimum number of agents and tokens, thus providing matching upper bounds for the problem.

Guest: Jeremie Chalopin
Host: Zvi Lotker

Misleading Stars: What Cannot Be Measured in the Internet?

Yvonne Anne Pignolet, Stefan Schmid, Gilles Tredan

Traceroute measurements are one of our main instruments to shed light onto the structure and properties of today’s complex networks such as the Internet. This paper studies the feasibility and infeasibility of inferring the network topology given traceroute data from a worst-case perspective, i.e., without any probabilistic assumptions on, e.g., the nodes’ degree distribution. We attend to a scenario where some of the routers are anonymous, and propose two fundamental axioms that model two basic assumptions on the traceroute data: (1) each trace corresponds to a real path in the network, and (2) the routing paths are at most a factor 1/alpha off the shortest paths, for some parameter alpha in (0,1]. In contrast to existing literature that focuses on the cardinality of the set of (often only minimal) inferrable topologies, we argue that a large number of possible topologies alone is often unproblematic, as long as the networks have a similar structure. We hence seek to characterize the set of topologies inferred with our axioms. We introduce the notion of star graphs whose colorings capture the differences among inferred topologies; it also allows us to construct inferred topologies explicitly. We find that in general, inferrable topologies can differ significantly in many important aspects, such as the nodes’ distances or the number of triangles. These negative results are complemented by a discussion of a scenario where the trace set is best possible, i.e., “complete”. It turns out that while some properties such as the node degrees are still hard to measure, a complete trace set can help to determine global properties such as the connectivity.

Guest: Stefan Schmid
Host: Zvi Lotker

Fast and Scalable Rendezvousing

Yehuda Afek, Michael Hakimi and Adam Morrison

In an asymmetric rendezvous system, such as an unfair synchronous queue and an elimination array, threads of two types, consumers and producers, show up and are matched, each with a unique thread of the other type. Here we present a new highly scalable, high throughput asymmetric rendezvous system that outperforms prior synchronous queue and elimination array implementations under both symmetric and asymmetric workloads (more operations of one type than the other). It is a fast matching machine. Consequently, we also present a highly scalable and competitive stack implementation

Guest: Yehuda Afek
Host: Zvi Lotker

The Complexity of Data Aggregation in Directed Networks

Fabian Kuhn and Rotem Oshman

We study problems of data aggregation, such as approximate counting and computing the minimum input value, in synchronous directed networks with bounded message bandwidth B = Ω(log n). In undirected networks of diameter D, many such problems can easily be solved in O(D) rounds, using O(log n)-size messages. We show that for directed networks this is not the case: when the bandwidth B is small, several classical data aggregation problems have a time complexity that depends polynomially on the size of the network, even when the diameter of the network is constant.

Guest: Rotem Oshman
Host: Chen Avin

Physical Expander in Virtual Tree Overlay

Taisuke Izumi, Maria Gradinariu Potop-Butucaru and Mathieu Valero

In this paper, we propose a new distributed construction of constant-degree expanders motivated by their application in P2P overlay networks and in particular in the design of robust tree overlays. Our key result can be stated as follows. Consider a complete binary tree T and construct a random pairing Π between leaf nodes and internal nodes. We prove that the graph GΠ obtained from T by contracting all pairs (leaf-internal nodes) achieves a constant node expansion with high probability. In the context of P2P overlays our result can be interpreted as follows: if each physical node participating to the tree overlay manages a random pair that couples one virtual internal node and one virtual leaf node then the physical-node layer exhibits a constant expansion with high probability. We encompass the difficulty of obtaining the random tree virtualization by proposing a local, self-organizing and churn resilient uniformly-random pairing algorithm with O(log2 n) running time. Our algorithm has the merit to not modify the original tree overlay (we just control the mapping between physical nodes and virtual nodes). Therefore, our scheme is general and can be easilly extended to a large class of overlays.

Guest: Taisuke Izumi
Host: Chen Avin

Locality and checkability in wait-free computing

Pierre Fraigniaud, Sergio Rajsbaum and Corentin Travers

This paper studies  notions of locality that are inherent to the specification of a
distributed task and independent of the computing environment, in a shared
memory wait-free system.
A  task T =(I,O,D) is checkable if there exists a wait-free distributed algorithm that, given s in I and t in O,  determines whether t in D(s), i.e., if t is a valid output for s according to
the specification D of T. Determining whether a projection-closed task is
wait-free solvable remains undecidable, demonstrating the richness of this
class. A locality property called projection-closed is identified,  that completely characterizes tasks that are wait-free  checkable.
A stronger notion of locality considers tasks  where the outputs look identically to the inputs at every vertex (input value of  a process). A task T =(I,O,D)  is said to be locality-preserving} if  O is a  covering complex of I. This topological property yields obstacles for wait-free  solvability different in nature from the classical agreement impossibility
results. On the other hand, locality-preserving tasks are projection-closed and
therefore always wait-free checkable.  A classification of locality-preserving
tasks in term of their relative computational power is provided.
A correspondence between locality-preserving tasks and subgroups of the edgepath
group of an input complex shows the existence of  hierarchies of  locality-preserving tasks, each one containing at the top the universal task  (induced by the universal covering complex), and at the bottom the trivial identity task.
Guest: Pierre Fraigniaud
Host: Merav Parter

Oblivious Collaboration

Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial and Benny Sudakov.

Communication is a crucial ingredient in every kind of collaborative work. But what is the least possible amount of communication required for a given task? We formalize
this question by introducing a new framework for distributed computation, called
oblivious protocols.
We investigate the power of this model by considering two concrete examples, the musical chairs task MC(n,m) and the well-known Renaming problem. The MC(n,m) game is played by n players (processors) with $m$ chairs. Players can occupy chairs, and the game terminates as soon as each player occupies a unique chair. Thus we say that player P is in conflict if some other player Q is occupying the same chair, i.e., termination means there are no conflicts. By known results from distributed computing, if m <= 2n-2, no strategy of the players can guarantee termination. However, there
is a protocol with m = 2n-1 chairs that always terminates. Here we consider an
oblivious protocol where in every time step the only communication is this: an
adversarial scheduler chooses an arbitrary nonempty set of players, and for each
of them provides only one bit of information, specifying whether the player is
currently in conflict or not. A player notified not to be in conflict halts and
never changes its chair, whereas a player notified to be in conflict changes its
chair according to its deterministic program. Remarkably, even with this minimal
communication termination can be guaranteed with only m=2n-1 chairs. Likewise,
we obtain an oblivious protocol for the Renaming problem whose name-space is
small as that of the optimal nonoblivious distributed protocol.
Other aspects suggest themselves, such as the efficiency
(program length) of our protocols. We make substantial progress here as well,
though many interesting questions remain open.

Guest: Eli Gafni
Host: Merav Parter

On Approximate Distance Labels and Routing Schemes with Affine Stretch

Ittai Abraham and Cyril Gavoille


For every integral parameter k > 1, given an unweighted
graph G, we construct in polynomial time, for each vertex u, a distance label
L(u) of size O(n^(2/(2k-1))). For any u,v in G, given L(u),L(v) we can return in
time O(k) an affine approximation h(u,v) on the distance d(u,v) between u and v
in G such that d(u,v) <= h(u,v) <= (2k-2)d(u,v) +1. Hence we say that our
distance label scheme has affine stretch of (2k-2)d+1.  For k=2 our construction
is comparable to the O(n^(5/3)) size, 2d+1 affine stretch of the distance oracle
of Patrascu and Roditty (FOCS’10), it incurs a o(log(n)) storage overhead while
providing the benefits of a distance label.

For any k>1, given a restriction of o(n^(1+1/(k-1))) on
the total size of the data structure, our construction provides distance
labels with affine stretch of (2k-2)d+1 which is better than the stretch (2k-1)d
scheme of Thorup and Zwick (J. ACM’05).

Our second contribution is a compact routing scheme with
poly-logarithmic addresses that provides affine stretch guarantees. With
O(n^(3/(3k-2)))-bit routing tables we obtain affine stretch of (4k-6)d+1, for
any k>1.

Given a restriction of o(n^(1/(k-1))) on the table size,
our  routing scheme provides affine stretch which is better than the stretch
(4k-5)d routing scheme of Thorup and Zwick (SPAA’01).

Guest: Ittai Abraham

Host:  Merav Parter


Parsimonious Flooding in Geometric Random-Walks

Andrea Clementi and Riccardo Silvestri

We study the information spreading yielded by the (Parsimonious) 1-Flooding
Protocol} in geometric Mobile Ad-Hoc Networks. We consider n agents on a convex
plane region of diameter D performing independent random walks with move radius
\rho. At any time step, every active agent $v$ informs every non-informed agent
which is within distance R from v (R>0 is the transmission radius). An agent
is only active at the time step immediately after the one in which has been
informed and, after that, she is removed. At the initial time step, a source
agent is informed and we look at the \emph{completion time} of the protocol,
i.e., the first time step (if any) in which all agents are informed. This random
process is equivalent to the well-known Susceptible-Infective-Removed (SIR)
infection process in Mathematical Epidemiology. No analytical results are
available for this random process over any explicit mobility model. The presence
of removed agents makes this process much more complex than the (standard)
flooding. We prove optimal bounds on the completion time depending on the
parameters n, D, R, and rho. The obtained bounds hold with high probability. We
remark that our method of analysis provides a clear picture of the dynamic shape
of the information spreading (or infection wave) over the time.
end of abstract.
Guest: Andrea Clementi

Host:  Merav Parter