Dagstuhl Publishing
http://www.dagstuhl.de
RSS feed announcing the latest publications published by Schloss Dagstuhlen-en2010-06-082010-06-08http://www.dagstuhl.de/rss.phpMixed Criticality on Multicore / Manycore Platforms (Dagstuhl Seminar 17131)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7362
This report provides an overview of the discussions, the program and the outcomes of the second Dagstuhl Seminar on Mixed Criticality onMulticore/Manycore Platforms. The seminar brought together researchers working on mixed criticality real-time applications, industrialists from the aerospace, railway, and automotive industries, and experts in certification.Tue, 17 Oct 2017 08:10:26 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7362Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7361
This report documents the program and the outcomes of Dagstuhl Seminar 17121 "Computational Complexity of Discrete Problems". The first section gives an overview of the topics covered and the organization of the meeting. Section 2 lists the talks given in alphabetical order. The last section contains the abstracts of the talks.Tue, 17 Oct 2017 08:09:24 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7361Front Matter, Table of Contents, Preface, Symposium Organization, Awards
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7962
Front Matter, Table of Contents, Preface, Symposium Organization, 2017 Edsger W. Dijkstra Prize in Distributed Computing, and 2017 Principles of Distributed Computing Doctoral Dissertation Award.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7962Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7963
In this paper we study the task of approach of two mobile agents having the same limited range of vision and moving asynchronously in the plane. This task consists in getting them in finite time within each other's range of vision. The agents execute the same deterministic algorithm and are assumed to have a compass showing the cardinal directions as well as a unit measure. On the other hand, they do not share any global coordinates system (like GPS), cannot communicate and have distinct labels. Each agent knows its label but does not know the label of the other agent or the initial position of the other agent relative to its own. The route of an agent is a sequence of segments that are subsequently traversed in order to achieve approach. For each agent, the computation of its route depends only on its algorithm and its label. An adversary chooses the initial positions of both agents in the plane and controls the way each of them moves along every segment of the routes, in particular by arbitrarily varying the speeds of the agents. Roughly speaking, the goal of the adversary is to prevent the agents from solving the task, or at least to ensure that the agents have covered as much distance as possible before seeing each other. A deterministic approach algorithm is a deterministic algorithm that always allows two agents with any distinct labels to solve the task of approach regardless of the choices and the behavior of the adversary. The cost of a complete execution of an approach algorithm is the length of both parts of route travelled by the agents until approach is completed.Let Delta and l be the initial distance separating the agents and the length of (the binary representation of) the shortest label, respectively. Assuming that Delta and l are unknown to both agents, does there exist a deterministic approach algorithm whose cost is polynomial in Delta and l?Actually the problem of approach in the plane reduces to the network problem of rendezvous in an infinite oriented grid, which consists in ensuring that both agents end up meeting at the same time at a node or on an edge of the grid. By designing such a rendezvous algorithm with appropriate properties, as we do in this paper, we provide a positive answer to the above question.Our result turns out to be an important step forward from a computational point of view, as the other algorithms allowing to solve the same problem either have an exponential cost in the initial separating distance and in the labels of the agents, or require each agent to know its starting position in a global system of coordinates, or only work under a much less powerful adversary.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7963Brief Announcement: Rapid Mixing of Local Dynamics on Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7964
In peer-to-peer networks, it is desirable that the logical topology of connections between the constituting nodes make a well-connected graph, i.e., a graph with low diameter and high expansion. At the same time, this graph should evolve only through local modifications. These requirements prompt the following question: are there local graph dynamics that i) create a well-connected graph in equilibrium, and ii) converge rapidly to this equilibrium?In this paper we provide an affirmative answer by exhibiting a local graph dynamic that mixes provably fast. Specifically, for a graph on N nodes, mixing has occurred after each node has performed O(polylog(N)) operations. This is in contrast with previous results, which required at least Omega(N polylog(N)) operations per node before the graph had properly mixed.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7964Recommenders: from the Lab to the Wild (Keynote Talk)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7965
Recommenders are ubiquitous on the Internet today: they tell you which book to read, which movie you should watch, predict your next holiday destination, give you advices on restaurants and hotels, they are even responsible for the posts that you see on your favorite social media and potentially greatly influence your friendship on social networks.While many approaches exist, collaborative filtering is one of the most popular approaches to build online recommenders that provide users with content that matches their interest. Interestingly, the very notion of users can be general and span actual humans or software applications. Recommenders come with many challenges beyond the quality of the recommendations. One of the most prominent ones is their ability to scale to a large number of users and a growing volume of data to provide real-time recommendations introducing many system challenges. Another challenge is related to privacy awareness: while recommenders rely on the very fact that users give away information about themselves, this potentially raises some privacy concerns.In this talk, I will focus on the challenges associated to building efficient, scalable and privacy-aware recommenders.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7965Brief Announcement: Distributed SplayNets
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7966
SplayNets are reconfigurable networks which adjust to the communication pattern over time. We present DiSplayNets, a distributed (concurrent and decentralized) implementation of SplayNets.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7966Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7967
Providing clean and efficient foundations and tools for reconfiguration is a crucial enabler for distributed system management today. This work takes a step towards developing such foundations. It considers classic fault-tolerant atomic objects emulated on top of a static set of fault-prone servers, and turns them into dynamic ones. The specification of a dynamic object extends the corresponding static (non-dynamic) one with an API for changing the underlying set of fault-prone servers. Thus, in a dynamic model, an object can start in some configuration and continue in a different one. Its liveness is preserved through the reconfigurations it undergoes, tolerating a versatile set of faults as it shifts from one configuration to another.In this paper we present a general abstraction for asynchronous reconfiguration, and exemplify its usefulness for building two dynamic objects: a read/write register and a max-register. We first define a dynamic model with a clean failure condition that allows an administrator to reconfigure the system and switch off a server once the reconfiguration operation removing it completes. We then define the Reconfiguration abstraction and show how it can be used to build dynamic registers and max-registers. Finally, we give an optimal asynchronous algorithm implementing the Reconfiguration abstraction, which in turn leads to the first asynchronous (consensus-free) dynamic register emulation with optimal complexity. More concretely, faced with n requests for configuration changes, the number of configurations that the dynamic register is implemented over is n; and the complexity of each client operation is O(n).Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7967Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7968
Non-volatile memory is expected to coexist with (or even displace) volatile DRAM for main memory in upcoming architectures. As a result, there is increasing interest in the problem of designing and specifying durable data structures that can recover from system crashes. Data-structures may be designed to satisfy stricter or weaker durability guarantees to provide a balance between the strength of the provided guarantees and performance overhead.This paper proposes three novel implementations of a concurrent lock-free queue. These implementations illustrate the algorithmic challenges in building persistent lock-free data structures with different levels of durability guarantees. We believe that by presenting these challenges, along with the proposed algorithmic designs, and the possible levels of durability guarantees, we can shed light on avenues for building a wide variety of durable data structures. We implemented the various designs and evaluate their performance overhead compared to a simple queue design for standard (volatile) memory.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7968Some Lower Bounds in Dynamic Networks with Oblivious Adversaries
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7969
This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel Omega(d + poly(m)) lower bounds on their time complexity (in rounds). Here d is the dynamic diameter of the dynamic network and m is the total number of nodes. Before this work, the only known lower bounds on these problems under oblivious adversaries were the trivial Omega(d) lower bounds. Our novel lower bounds are hence the first non-trivial lower bounds and also the first lower bounds with a poly(m) term. Our proof relies on a novel reduction from a certain two-party communication complexity problem. Our central proof technique is unique in the sense that we consider the communication complexity with a special leaker. The leaker helps Alice and Bob in the two-party problem, by disclosing to Alice and Bob certain "non-critical" information about the problem instance that they are solving.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7969Brief Announcement: Practical Synchronous Byzantine Consensus
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7970
This paper presents new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The PBFT state machine replication protocol tolerates f Byzantine faults in an asynchronous setting using n = 3f + 1 replicas. We improve the Byzantine fault tolerance to n = 2f + 1 by utilizing the synchrony assumption. Our protocol also solves synchronous authenticated Byzantine agreement in fewer expected rounds than the best existing solution (Katz and Koo, 2006).Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7970Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7971
We show that many techniques developed in the context of predicate detection are applicable to the stable marriage problem. The standard Gale-Shapley algorithm can be derived as a special case of detecting linear predicates. We also show that techniques in computation slicing can be used to represent the set of all constrained stable matchings.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7971Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7972
The Undecided-State Dynamics is a well-known protocol that achieves Consensus in distributed systems formed by a set of n anonymous nodes interacting via a communication network. We consider this dynamics in the parallel PULL communication model on the complete graph for the binary case, i.e., when every node can either support one of two possible colors or stay in the undecided state. Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color. A interesting open question here is whether this dynamics reaches consensus quickly, i.e. within a polylogarithmic number of rounds. In this paper we present an unconditional analysis of the Undecided-State Dynamics which answers to the above question in the affirmative. Our analysis shows that, starting from any initial configuration, the Undecided-State Dynamics reaches a monochromatic configuration within O(log^2 n) rounds, with high probability (w.h.p.). Moreover, we prove that if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color within O(log n) round, w.h.p. At the heart of our approach there is a new analysis of the symmetry-breaking phase that the process must perform in order to escape from (almost-)unbiased configurations. Previous symmetry-breaking analysis of consensus dynamics essentially concern sequential communication models (such as Population Protocols) and/or symmetric updated rules (such as majority rules).Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7972Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7973
Locally Checkable Labeling (LCL) problems include essentially all the classic problems of LOCAL distributed algorithms. In a recent enlightening revelation, Chang and Pettie [FOCS'17] showed that any LCL (on bounded degree graphs) that has an o(log n)-round randomized algorithm can be solved in T_(LLL)(n) rounds, which is the randomized complexity of solving (a relaxed variant of) the Lovasz Local Lemma (LLL) on bounded degree n-node graphs. Currently, the best known upper bound on T_(LLL)(n) is O(log n), by Chung, Pettie, and Su [PODC'14], while the best known lower bound is Omega(log log n), by Brandt et al. [STOC'16]. Chang and Pettie conjectured that there should be an O(log log n)-round algorithm (on bounded degree graphs).Making the first step of progress towards this conjecture, and providing a significant improvement on the algorithm of Chung et al. [PODC'14], we prove that T_(LLL)(n)= 2^O(sqrt(log log n)). Thus, any o(log n)-round randomized distributed algorithm for any LCL problem on bounded degree graphs can be automatically sped up to run in 2^O(sqrt(log log n)) rounds.Using this improvement and a number of other ideas, we also improve the complexity of a number of graph coloring problems (in arbitrary degree graphs) from the O(log n)-round results of Chung, Pettie and Su [PODC'14] to 2^O(sqrt(log log n)). These problems include defective coloring, frugal coloring, and list vertex-coloring.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7973Consistency Models with Global Operation Sequencing and their Composition
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7974
Modern distributed systems often achieve availability and scalability by providing consistency guarantees about the data they manage weaker than linearizability. We consider a class of such consistency models that, despite this weakening, guarantee that clients eventually agree on a global sequence of operations, while seeing a subsequence of this final sequence at any given point of time. Examples of such models include the classical Total Store Order (TSO) and recently proposed dual TSO, Global Sequence Protocol (GSP) and Ordered Sequential Consistency.We define a unified model, called Global Sequence Consistency (GSC), that has the above models as its special cases, and investigate its key properties. First, we propose a condition under which multiple objects each satisfying GSC can be composed so that the whole set of objects satisfies GSC. Second, we prove an interesting relationship between special cases of GSC - GSP, TSO and dual TSO: we show that clients that do not communicate out-of-band cannot tell the difference between these models. To obtain these results, we propose a novel axiomatic specification of GSC and prove its equivalence to the operational definition of the model.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7974Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7975
This paper addresses the cornerstone family of local problems in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions.Our main contribution is in providing tools for derandomizing solutions to local problems, when the n nodes can only send O(log n)-bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results.First, we show that in the Congested Clique model, which allows all-to-all communication, there is a deterministic maximal independent set (MIS) algorithm that runs in O(log^2 Delta) rounds, where Delta is the maximum degree. When Delta=O(n^(1/3)), the bound improves to O(log Delta).Adapting the above to the CONGEST model gives an O(D log^2 n)-round deterministic MIS algorithm, where D is the diameter of the graph. Apart from a previous unproven claim of a O(D log^3 n)-round algorithm, the only known deterministic solutions for the CONGEST model are a coloring-based O(Delta + log^* n)-round algorithm, where Delta is the maximal degree in the graph, and a 2^O(sqrt(log n log log n))-round algorithm, which is super-polylogarithmic in n.In addition, we deterministically construct a (2k-1)-spanner with O(kn^(1+1/k) log n) edges in O(k log n) rounds in the Congested Clique model. For comparison, in the more stringent CONGEST model, where the communication graph is identical to the input graph, the best deterministic algorithm for constructing a (2k-1)-spanner with O(kn^(1+1/k)) edges runs in O(n^(1-1/k)) rounds.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7975How Large Is Your Graph?
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7976
We consider the problem of estimating the graph size, where one is given only local access to the graph. We formally define a query model in which one starts with a seed node and is allowed to make queries about neighbours of nodes that have already been seen. In the case of undirected graphs, an estimator of Katzir et al. (2014) based on a sample from the stationary distribution pi uses O(1/||pi||_2 + d_avg) queries; we prove that this is tight. In addition, we establish this as a lower bound even when the algorithm is allowed to crawl the graph arbitrarily; the results of Katzir et al. give an upper bound that is worse by a multiplicative factor t_mix(1/n^4).The picture becomes significantly different in the case of directed graphs. We show that without strong assumptions on the graph structure, the number of nodes cannot be predicted to within a constant multiplicative factor without using a number of queries that are at least linear in the number of nodes; in particular, rapid mixing and small diameter, properties that most real-world networks exhibit, do not suffice. The question of interest is whether any algorithm can beat breadth-first search. We introduce a new parameter, generalising the well-studied conductance, such that if a suitable bound on it exists and is known to the algorithm, the number of queries required is sublinear in the number of edges; we show that this is tight.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7976Fast Plurality Consensus in Regular Expanders
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7977
In a voting process on a graph vertices revise their opinions in a distributed way based on the opinions of nearby vertices. The voting completes when the vertices reach consensus, that is, they all have the same opinion. The classic example is synchronous pull voting where at each step, each vertex adopts the opinion of a random neighbour. This very simple process, however, can be slow and the final opinion is not necessarily the one with the initial largest support. It was shown earlier that if there are initially only two opposing opinions, then both these drawbacks can be overcome by a synchronous two-sample voting, in which at each step each vertex considers its own opinion and the opinions of two random neighbours.If there are initially three or more opinions, a problem arises when there is no clear majority. One class of opinions may be largest (the plurality opinion), although its total size is less than that of two other opinions put together. We analyse the performance of the two-sample voting on d-regular graphs for this case. We show that, if the difference between the initial sizes A_1 and A_2 of the largest and second largest opinions is at least C n max{sqrt((log n)/A_1), lambda}, then the largest opinion wins in O((n log n)/A_1) steps with high probability. Here C is a suitable constant and lambda is the absolute second eigenvalue of transition matrix P=Adj(G)/d of a simple random walk on the graph G. Our bound generalizes the results of Becchetti et al. [SPAA 2014] for the related three-sample voting process on complete graphs. Our bound implies that if lambda = o(1), then the two-sample voting can consistently converge to the largest opinion, even if A_1 - A_2 = o(n). If lambda is constant, we show that the case A_1 - A_2 = o(n) can be dealt with by sampling using short random walks. Finally, we give a simple and efficient push voting algorithm for the case when there are a number of large opinions and any of them is acceptable as the final winning opinion.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7977Brief Announcement: Crash-Tolerant Consensus in Directed Graph Revisited
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7978
We revisit the problem of distributed consensus in directed graphs tolerating crash failures; we improve the round and communication complexity of the existing protocols. Moreover, we prove that our protocol requires the optimal number of communication rounds, required by any protocol belonging to a specific class of crash-tolerant consensus protocols in directed graphs.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7978Improved Distributed Degree Splitting and Edge Coloring
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7979
The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy.We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2+o(1))Delta-edge-coloring, improving on that of Ghaffari and Su.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7979Certification of Compact Low-Stretch Routing Schemes
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7980
On the one hand, the correctness of routing protocols in networks is an issue of utmost importance for guaranteeing the delivery of messages from any source to any target. On the other hand, a large collection of routing schemes have been proposed during the last two decades, with the objective of transmitting messages along short routes, while keeping the routing tables small. Regrettably, all these schemes share the property that an adversary may modify the content of the routing tables with the objective of, e.g., blocking the delivery of messages between some pairs of nodes, without being detected by any node.In this paper, we present a simple certification mechanism which enables the nodes to locally detect any alteration of their routing tables. In particular, we show how to locally verify the stretch 3 routing scheme by Thorup and Zwick [SPAA 2001] by adding certificates of ~O(sqrt(n)) bits at each node in n-node networks, that is, by keeping the memory size of the same order of magnitude as the original routing tables. We also propose a new name-independent routing scheme using routing tables of size ~O(sqrt(n)) bits. This new routing scheme can be locally verified using certificates on ~O(sqrt(n)) bits. Its stretch is 3 if using handshaking, and 5 otherwise.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7980Extending Hardware Transactional Memory Capacity via Rollback-Only Transactions and Suspend/Resume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7981
Transactional memory (TM) aims at simplifying concurrent programming via the familiar abstraction of atomic transactions. Recently, Intel and IBM have integrated hardware based TM (HTM) implementations in commodity processors, paving the way for the mainstream adoption of the TM paradigm. Yet, existing HTM implementations suffer from a crucial limitation, which hampers the adoption of HTM as a general technique for regulating concurrent access to shared memory: the inability to execute transactions whose working sets exceed the capacity of CPU caches. In this paper we propose P8TM, a novel approach that mitigates this limitation on IBM's POWER8 architecture by leveraging a key combination of techniques: uninstrumented read-only transactions, Rollback Only Transaction-based update transactions, HTM-friendly (software-based) read-set tracking, and self-tuning. P8TM can dynamically switch between different execution modes to best adapt to the nature of the transactions and the experienced abort patterns. In-depth evaluation with several benchmarks indicates that P8TM can achieve striking performance gains in workloads that stress the capacity limitations of HTM, while achieving performance on par with HTM even in unfavourable workloads.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7981Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7982
We present the first self-stabilizing algorithm for leader election in arbitrary topologies whose space complexity is O(max{log Delta, log log n}) bits per node, where n is the network size and Delta its degree. This complexity is sub-logarithmic in n when Delta = n^o(1).Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7982Meeting in a Polygon by Anonymous Oblivious Robots
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7983
The Meeting problem for k>=2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order sigma (where sigma=1 corresponds to no rotational symmetry), we prove that k=sigma+1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k=2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon's vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7983Three Notes on Distributed Property Testing
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7984
In this paper we present distributed property-testing algorithms for graph properties in the CONGEST model, with emphasis on testing subgraph-freeness. Testing a graph property P means distinguishing graphs G = (V,E) having property P from graphs that are epsilon-far from having it, meaning that epsilon|E| edges must be added or removed from G to obtain a graph satisfying P.We present a series of results, including:- Testing H-freeness in O(1/epsilon) rounds, for any constant-sized graph H containing an edge (u,v) such that any cycle in H contain either u or v (or both). This includes all connected graphs over five vertices except K_5. For triangles, we can do even better when epsilon is not too small.- A deterministic CONGEST protocol determining whether a graph contains a given tree as a subgraph in constant time.- For cliques K_s with s >= 5, we show that K_s-freeness can be tested in O(m^(1/2-1/(s-2)) epsilon^(-1/2-1/(s-2))) rounds, where m is the number of edges in the network graph.- We describe a general procedure for converting epsilon-testers with f(D) rounds, where D denotes the diameter of the graph, to work in O((log n)/epsilon)+f((log n)/epsilon) rounds, where n is the number of processors of the network. We then apply this procedure to obtain an epsilon-tester for testing whether a graph is bipartite and testing whether a graph is cycle-free. Moreover, for cycle-freeness, we obtain a corrector of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property.These protocols extend and improve previous results of [Censor-Hillel et al. 2016] and [Fraigniaud et al. 2016].Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7984Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7985
The Arrow protocol is a simple and elegant protocol to coordinate exclusive access to a shared object in a network. The protocol solves the underlying distributed queueing problem by using path reversal on a pre-computed spanning tree (or any other tree topology simulated on top of the given network).It is known that the Arrow protocol solves the problem with a competitive ratio of O(log D) on trees of diameter D. This implies a distributed queueing algorithm with competitive ratio O(s log D) for general networks with a spanning tree of diameter D and stretch s. In this work we show that when running the Arrow protocol on top of the well-known probabilistic tree embedding of Fakcharoenphol, Rao, and Talwar [STOC'03], we obtain a randomized distributed online queueing algorithm with expected competitive ratio O(log n) against an oblivious adversary even on general n-node network topologies. The result holds even if the queueing requests occur in an arbitrarily dynamic and concurrent fashion and even if communication is asynchronous. The main technical result of the paper shows that the competitive ratio of the Arrow protocol is constant on a special family of tree topologies, known as hierarchically well separated trees.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7985Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7986
We study distributed algorithms implemented in a simplified biologically inspired model for stochastic spiking neural networks. We focus on tradeoffs between computation time and network complexity, along with the role of noise and randomness in efficient neural computation.It is widely accepted that neural spike responses, and neural computation in general, is inherently stochastic. In recent work, we explored how this stochasticity could be leveraged to solve the 'winner-take-all' leader election task. Here, we focus on using randomness in neural algorithms for similarity testing and compression. In the most basic setting, given two n-length patterns of firing neurons, we wish to distinguish if the patterns are equal or epsilon-far from equal.Randomization allows us to solve this task with a very compact network, using O((sqrt(n) log n)/epsilon) auxiliary neurons, which is sublinear in the input size. At the heart of our solution is the design of a t-round neural random access memory, or indexing network, which we call a neuro-RAM. This module can be implemented with O(n/t) auxiliary neurons and is useful in many applications beyond similarity testing - e.g., we discuss its application to compression via random projection.Using a VC dimension-based argument, we show that the tradeoff between runtime and network size in our neuro-RAM is nearly optimal. To the best of our knowledge, we are the first to apply these techniques to stochastic spiking networks. Our result has several implications - since our neuro-RAM can be implemented with deterministic threshold gates, it demonstrates that, in contrast to similarity testing, randomness does not provide significant computational advantages for this problem. It also establishes a separation between our networks, which spike with a sigmoidal probability function, and well-studied deterministic sigmoidal networks, whose gates output real number values, and which can implement a neuro-RAM much more efficiently.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7986Brief Announcement: A Note on Hardness of Diameter Approximation
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7987
We revisit the hardness of approximating the diameter of a network. In the CONGEST model, ~Omega(n) rounds are necessary to compute the diameter [Frischknecht et al. SODA'12]. Abboud et al. [DISC 2016] extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer 1 <= l <= polylog(n) , distinguishing between networks of diameter 4l + 2 and 6l + 1 requires ~Omega(n) rounds. We slightly tighten this result by showing that even distinguishing between diameter 2l + 1 and 3l + 1 requires ~Omega(n) rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition. This is suited for teaching both the lower bound in the CONGEST model and the conditional lower bound in the RAM model.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7987Brief Announcement: Towards a Complexity Theory for the Congested Clique
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7988
The congested clique model of distributed computing has been receiving attention as a model for densely connected distributed systems. While there has been significant progress on the side of upper bounds, we have very little in terms of lower bounds for the congested clique; indeed, it is now know that proving explicit congested clique lower bounds is as difficult as proving circuit lower bounds. In this work, we use traditional complexity-theoretic tools to build a clearer picture of the complexity landscape of the congested clique, proving non-constructive lower bounds and studying the relationships between natural problems.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7988An Efficient Communication Abstraction for Dense Wireless Networks
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7989
In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which can be exploited to enable concurrent communication among multiple sender/receiver pairs. To simplify the development of these algorithms we describe a new communication abstraction called FadingMAC which exposes the benefits of this concurrent communication, but also hides the details of the underlying low-level radio signal behavior. This approach splits efforts between those who develop useful algorithms that run on the abstraction, and those who implement the abstraction in concrete low-level wireless models, or on real hardware.After defining FadingMAC, we describe and analyze an efficient implementation of the abstraction in a standard low-level SINR-style network model. We then describe solutions to the following problems that run on the abstraction: max, min, sum, and mean computed over input values; process renaming; consensus and leader election; and optimal packet scheduling. Combining our abstraction implementation with these applications that run on the abstraction, we obtain near-optimal solutions to these problems in our low-level SINR model - significantly advancing the known results for distributed algorithms in this setting. Of equal importance to these concrete bounds, however, is the general idea advanced by this paper: as wireless networks become more dense, both theoreticians and practitioners must explore new communication abstractions that can help tame this density.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7989Brief Announcement: On Connectivity in the Broadcast Congested Clique
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7990
Recently, very fast deterministic and randomized algorithms have been obtained for connectivity and minimum spanning tree in the unicast congested clique. In contrast, no solution faster than a simple parallel implementation of the Boruvka's algorithm has been known for both problems in the broadcast congested clique. In this announcement, we present the first sub-logarithmic deterministic algorithm for connected components in the broadcast congested clique.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7990Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7991
We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the n nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to fThu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7991Brief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic Networks
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7992
In this work we study the performance of asymptotic and approximate consensus algorithms in dynamic networks. The asymptotic consensus problem requires a set of agents to repeatedly set their outputs such that the outputs converge to a common value within the convex hull of initial values. This problem, and the related approximate consensus problem, are fundamental building blocks in distributed systems where exact consensus among agents is not required, e.g., man-made distributed control systems, and have applications in the analysis of natural distributed systems, such as flocking and opinion dynamics. We prove new nontrivial lower bounds on the contraction rates of asymptotic consensus algorithms, from which we deduce lower bounds on the time complexity of approximate consensus algorithms. In particular, the obtained bounds show optimality of asymptotic and approximate consensus algorithms presented in [Charron-Bost et al., ICALP'16] for certain classes of networks that include classical failure assumptions, and confine the search for optimal bounds in the general case.Central to our lower bound proofs is an extended notion of valency, the set of reachable limits of an asymptotic consensus algorithm starting from a given configuration. We further relate topological properties of valencies to the solvability of exact consensus, shedding some light on the relation of these three fundamental problems in dynamic networks.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7992Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7993
In this paper, we show that the protocol complex of a Byzantine synchronous system can remain (k-1)-connected for up to ceil(t/k) rounds, where t is the maximum number of Byzantine processes, and t >= k >= 1. This topological property implies that ceil(t/k) + 1 rounds are necessary to solve k-set agreement in Byzantine synchronous systems, compared to floor(t/k) + 1 rounds in synchronous crash-failure systems. We also show that our connectivity bound is tight as we indicate solutions to Byzantine k-set agreement in exactly ceil(t/k) + 1 synchronous rounds, at least when n is suitably large compared to t. In conclusion, we see how Byzantine failures can potentially require one extra round to solve k-set agreement, and, for n suitably large compared to t, at most that.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7993Which Broadcast Abstraction Captures k-Set Agreement?
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7994
It is well-known that consensus (one-set agreement) and total order broadcast are equivalent in asynchronous systems prone to process crash failures. Considering wait-free systems, this article addresses and answers the following question: which is the communication abstraction that "captures" k-set agreement? To this end, it introduces a new broadcast communication abstraction, called k-BO-Broadcast, which restricts the disagreement on the local deliveries of the messages that have been broadcast (1-BO-Broadcast boils down to total order broadcast). Hence, in this context, k=1 is not a special number, but only the first integer in an increasing integer sequence.This establishes a new "correspondence" between distributed agreement problems and communication abstractions, which enriches our understanding of the relations linking fundamental issues of fault-tolerant distributed computing.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7994Cost of Concurrency in Hybrid Transactional Memory
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7995
State-of-the-art software transactional memory (STM) implementations achieve good performance by carefully avoiding the overhead of incremental validation (i.e., re-reading previously read data items to avoid inconsistency) while still providing progressiveness (allowing transactional aborts only due to data conflicts). Hardware transactional memory (HTM) implementations promise even better performance, but offer no progress guarantees. Thus, they must be combined with STMs, leading to hybrid TMs (HyTMs) in which hardware transactions must be instrumented (i.e., access metadata) to detect contention with software transactions.We show that, unlike in progressive STMs, software transactions in progressive HyTMs cannot avoid incremental validation. In fact, this result holds even if hardware transactions can read metadata non-speculatively. We then present opaque HyTM algorithms providing progressiveness for a subset of transactions that are optimal in terms of hardware instrumentation. We explore the concurrency vs. hardware instrumentation vs. software validation trade-offs for these algorithms. Our experiments with Intel and IBM POWER8 HTMs seem to suggest that (i) the cost of concurrency also exists in practice, (ii) it is important to implement HyTMs that provide progressiveness for a maximal set of transactions without incurring high hardware instrumentation overhead or using global contending bottlenecks and (iii) there is no easy way to derive more efficient HyTMs by taking advantage of non-speculative accesses within hardware.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7995Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7996
We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question.Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires a near-quadratic number of rounds in the CONGEST model, as well as any algorithm for computing the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds.Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple linear lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a sub-linear complexity. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7996On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7997
We first prove that there are uncountably many objects with distinct computational powers. More precisely, we show that there is an uncountable set of objects such that for any two of them, at least one cannot be implemented from the other (and registers) in a wait-free manner. We then strengthen this result by showing that there are uncountably many linearizable objects with distinct computational powers. To do so, we prove that for all positive integers n and k, there is a linearizable object that is computationally equivalent to the k-set agreement task among n processes. To the best of our knowledge, these are the first linearizable objects proven to be computationally equivalent to set agreement tasks.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7997Brief Announcement: Fast Aggregation in Population Protocols
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7998
The coalescence protocol plays an important role in the population protocol model. The conceptual structure of the protocol is for two agents holding two non-zero values a, b respectively to take a transition (a,b) -> (a+b, 0), where + is an arbitrary commutative binary operation. Obviously, it eventually aggregates the sum of all initial values. In this paper, we present a fast coalescence protocol that converges in O(sqrt(n) log^2 n) parallel time with high probability in the model with an initial leader (equivalently, the model with a base station), which achieves an substantial speed-up compared with the naive implementation taking Omega(n) time.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7998Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7999
Direct-sum questions in (two-party) communication complexity ask whether two parties, Alice and Bob, can compute the value of a function f on l inputs (x_1,y_1),...,(x_l,y_l) more efficiently than by applying the best protocol for f, independently on each input (x_i,y_i). In spite of significant efforts to understand these questions (under various communication-complexity measures), the general question is still far from being well understood.In this paper, we offer a multiparty view of these questions: The direct-sum setting is just a two-player system with Alice having inputs x_1,...,x_l, Bob having inputs y_1,...,y_l and the desired output is f(x_1,y_1),...,f(x_l,y_l). The naive solution of solving the l problems independently, is modeled by a network with l (disconnected) pairs of players Alice i and Bob i, with inputs x_i,y_i respectively, and communication only within each pair. Then, we consider an intermediate ("star") model, where there is one Alice having l inputs x_1,...,x_l and l players Bob_1,...,Bob_l holding y_1,...,y_l, respectively (in fact, we consider few variants of this intermediate model, depending on whether communication between each Bob i and Alice is point-to-point or whether we allow broadcast). Our goal is to get a better understanding of the relation between the two extreme models (i.e., of the two-party direct-sum question). If, for instance, Alice and Bob can do better (for some complexity measure) than solving the l problems independently, we wish to understand what intermediate model already allows to do so (hereby understanding the "source" of such savings). If, on the other hand, we wish to prove that there is no better solution than solving the l problems independently, then our approach gives a way of breaking the task of proving such a statement into few (hopefully, easier) steps.We present several results of both types. Namely, for certain complexity measures, communication problems f and certain pairs of models, we can show gaps between the complexity of solving f on l instances in the two models in question; while, for certain other complexity measures and pairs of models, we can show that such gaps do not exist (for any communication problem f). For example, we prove that if only point-to-point communication is allowed in the intermediate "star" model, then significant savings are impossible in the public-coin randomized setting. On the other hand, in the private-coin randomized setting, if Alice is allowed to broadcast messages to all Bobs in the "star" network, then some savings are possible. While this approach does not lead yet to new results on the original two-party direct-sum question, we believe that our work gives new insights on the already-known direct-sum results, and may potentially lead to more such results in the future.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7999Recoverable FCFS Mutual Exclusion with Wait-Free Recovery
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8000
Traditional mutual exclusion locks are not resilient to failures: if there is a power outage, the memory is wiped out. Thus, when the system comes back on, the lock will have to be restored to the initial state, i.e., all processes are rolled back to the Remainder section and all variables are reset to their initial values. Recently, Golab and Ramaraju showed that we can improve this state of the art by exploiting the Non-Volatile RAM (NVRAM). They designed algorithms that, by maintaining shared variables in NVRAM, allow processes to recover from crashes on their own without a need for a global reset, even though a crash can wipe out the local memory of a process.We present a Recoverable Mutual Exclusion algorithm using the commonly supported CAS primitive. The main features of our algorithm are that it satisfies FCFS, it ensures that each process recovers in a wait-free manner, and in the absence of failures, it guarantees a worst-case Remote Memory Reference (RMR) complexity of O(lg n) on both Cache Coherent (CC) and Distributed Shared Memory (DSM) machines, where n is the number of processes for which the algorithm is designed. This bound matches the Omega(lg n) RMR lower bound by Attiya, Hendler, and Woelfel for Mutual Exclusion algorithms that use comparison primitives.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8000Brief Announcement: Shape Formation by Programmable Particles
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8001
Shape formation is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessellation of the plane, have constant memory, can only communicate with neighboring particles, and can only move from a grid node to an empty neighboring node; their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization.In this paper we provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of n particles. As a byproduct, if randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that n is large enough. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n^2) rounds and moves: this number of moves is also asymptotically optimal.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8001Improved Deterministic Distributed Matching via Rounding
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8002
We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts. The common denominator of these results is a deterministic distributed rounding method for certain linear programs, which is the first such rounding method, to our knowledge.A sampling of our end results is as follows.- An O(log^2 Delta log n)-round deterministic distributed algorithm for computing a maximal matching, in n-node graphs with maximum degree Delta. This is the first improvement in about 20 years over the celebrated O(log^4 n)-round algorithm of Hanckowiak, Karonski, and Panconesi [SODA'98, PODC'99].- A deterministic distributed algorithm for computing a (2+epsilon)-approximation of maximum matching in O(log^2 Delta log(1/epsilon) + log^* n) rounds. This is exponentially faster than the classic O(Delta + log^* n)-round 2-approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an epsilon-maximal matching which leaves only an epsilon-fraction of the edges on unmatched nodes.- An O(log^2 Delta log(1/epsilon) + log^* n)-round deterministic distributed algorithm for computing a (2+epsilon)-approximation of a maximum weighted matching, and also for the more general problem of maximum weighted b-matching. These improve over the O(log^4 n log_(1+epsilon) W)-round (6+epsilon)-approximation algorithm of Panconesi and Sozio [DIST'10], where W denotes the maximum normalized weight.- A deterministic local computation algorithm for a (2+epsilon)-approximation of maximum matching with 2^O(log^2 Delta) log^* n queries. This improves almost exponentially over the previous deterministic constant approximations which have query-complexity of 2^Omega(Delta log Delta) log^* n.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8002Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8003
We present a method for solving the shortest transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of (1 + epsilon) in undirected graphs with non-negative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes epsilon^(-3) polylog(n) iterations, and in each iteration it needs to solve an instance of the transshipment problem up to a multiplicative error of polylog(n), where n is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a careful white-box analysis, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve prior work by obtaining the following results:(1) Broadcast CONGEST model: (1 + epsilon)-approximate SSSP using ~O((sqrt(n) + D) epsilon^(-O(1))) rounds, where D is the (hop) diameter of the network.(2) Broadcast congested clique model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(epsilon^(-O(1))) rounds.(3) Multipass streaming model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(n) space and ~O(epsilon^(-O(1))) passes.The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative integer edge weights that are polynomially bounded in n; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs for traversing an edge in opposite directions, running times scale with the maximum ratio between the costs of both directions over all edges.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8003Hybrid Consensus: Efficient Consensus in the Permissionless Model
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8004
Consensus, or state machine replication is a foundational building block of distributed systems and modern cryptography. Consensus in the classical, "permissioned" setting has been extensively studied in the 30 years of distributed systems literature. Recent developments in Bitcoin and other decentralized cryptocurrencies popularized a new form of consensus in a "permissionless" setting, where anyone can join and leave dynamically, and there is no a-priori knowledge of the number of consensus nodes. So far, however, all known permissionless consensus protocols assume network synchrony, i.e., the protocol must know an upper bound of the network's delay, and transactions confirm slower than this a-priori upper bound.We initiate the study of the feasibilities and infeasibilities of achieving responsiveness in permissionless consensus. In a responsive protocol, the transaction confirmation time depends only on the actual network delay, but not on any a-priori known upper bound such as a synchronous round. Classical protocols in the partial synchronous and asynchronous models naturally achieve responsiveness, since the protocol does not even know any delay upper bound. Unfortunately, we show that in the permissionless setting, consensus is impossible in the asynchronous or partially synchronous models.On the positive side, we construct a protocol called Hybrid Consensus by combining classical-style and blockchain-style consensus. Hybrid Consensus shows that responsiveness is nonetheless possible to achieve in permissionless consensus (assuming proof-of-work) when 1) the protocol knows an upper bound on the network delay; 2) we allow a non-responsive warmup period after which transaction confirmation can become responsive; 3) honesty has some stickiness, i.e., it takes a short while for an adversary to corrupt a node or put it to sleep; and 4) less than 1/3 of the nodes are corrupt. We show that all these conditions are in fact necessary - if only one of them is violated, responsiveness would have been impossible. Our work makes a step forward in our understanding of the permissionless model and its differences and relations to classical consensus.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8004Recovering Shared Objects Without Stable Storage
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8005
This paper considers the problem of building fault-tolerant shared objects when processes can crash and recover but lose their persistent state on recovery. This Diskless Crash-Recovery (DCR) model matches the way many long-lived systems are built. We show that it presents new challenges, as operations that are recorded at a quorum may not persist after some of the processes in that quorum crash and then recover.To address this problem, we introduce the notion of crash-consistent quorums, where no recoveries happen during the quorum responses. We show that relying on crash-consistent quorums enables a recovery procedure that can recover all operations that successfully finished. Crash-consistent quorums can be easily identified using a mechanism we term the crash vector, which tracks the causal relationship between crashes, recoveries, and other operations.We apply crash-consistent quorums and crash vectors to build two storage primitives. We give a new algorithm for multi-writer, multi-reader atomic registers in the DCR model that guarantees safety under all conditions and termination under a natural condition. It improves on the best prior protocol for this problem by requiring fewer rounds, fewer nodes to participate in the quorum, and a less restrictive liveness condition. We also present a more efficient single-writer, single-reader atomic set - a virtual stable storage abstraction. It can be used to lift any existing algorithm from the traditional Crash-Recovery model to the DCR model. We examine a specific application, state machine replication, and show that existing diskless protocols can violate their correctness guarantees, while ours offers a general and correct solution.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8005Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8006
Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries.Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most (1+epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). We achieve a query complexity of O(poly(Delta/epsilon)n^(2/3)) (up to polylogarithmic factors in n) where Delta is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanner, i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of O(log n (Delta+log n)/epsilon) hops in the output that connects its endpoints.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8006Brief Announcement: The Synergy of Finite State Machines
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8007
What can be computed by a network of n randomized finite state machines communicating under the stone age model (a generalization of the beeping model’s communication scheme)? The inherent linear upper bound on the total space of the network implies that its global computational power is not larger than that of a randomized linear space Turing machine, but is this tight? The reported reseach answers this question affirmatively for bounded degree networks by introducing a stone age algorithm (operating under the most restrictive form of the model) that given a designated I/O node, constructs a tour in the network that enables the simulation of the Turing machine’s tape. To construct the tour, it is first shown how to 2-hop color the network concurrently with building a spanning tree with high probability.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8007Improved Deterministic Distributed Construction of Spanners
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8008
Graph spanners are fundamental graph structures with a wide range of applications in distributed networks. We consider a standard synchronous message passing model where in each round O(log n) bits can be transmitted over every edge (the CONGEST model).The state of the art of deterministic distributed spanner constructions suffers from large messages. The only exception is the work of Derbel et al., which computes an optimal-sized (2k-1)-spanner but uses O(n^(1-1/k)) rounds.In this paper, we significantly improve this bound. We present a deterministic distributed algorithm that given an unweighted n-vertex graph G = (V,E) and a parameter k > 2, constructs a (2k-1)-spanner with O(k n^(1+1/k)) edges within O(2^k n^(1/2 - 1/k)) rounds for every even k. For odd k, the number of rounds is O(2^k n^(1/2 - 1/(2k))). For the weighted case, we provide the first deterministic construction of a 3-spanner with O(n^(3/2)) edges that uses O(log n)-size messages and ~O(1) rounds. If the vertices have IDs in [1,Theta(n)], the spanner is computed in only 2 rounds!Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8008Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8009
In many lock-free algorithms, threads help one another, and each operation creates a descriptor that describes how other threads should help it. Allocating and reclaiming descriptors introduces significant space and time overhead. We introduce the first descriptor abstract data type (ADT), which captures the usage of descriptors by lock-free algorithms. We then develop a weak descriptor ADT which has weaker semantics, but can be implemented significantly more efficiently. We show how a large class of lock-free algorithms can be transformed to use weak descriptors, and demonstrate our technique by transforming several algorithms, including the leading k-compare-and-swap (k-CAS) algorithm. The original k-CAS algorithm allocates at least k+1 new descriptors per k-CAS. In contrast, our implementation allocates two descriptors per process, and each process simply reuses its two descriptors. Experiments on a variety of workloads show significant performance improvements over implementations that reclaim descriptors, and reductions of up to three orders of magnitude in peak memory usage.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8009Brief Announcement: Compact Topology of Shared-Memory Adversaries
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8010
The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8010Interactive Compression for Multi-Party Protocol
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8011
The field of compression studies the question of how many bits of communication are necessary to convey a given piece of data. For one-way communication between a sender and a receiver, the seminal work of Shannon and Huffman showed that the communication required is characterized by the entropy of the data; in recent years, there has been a great amount of interest in extending this line of research to interactive communication, where instead of a sender and a receiver we have two parties communication back-and-forth. In this paper we initiate the study of interactive compression for distributed multi-player protocols. We consider the classical shared blackboard model, where players take turns speaking, and each player's message is immediately seen by all the other players. We show that in the shared blackboard model with k players, one can compress protocols down to ~O(Ik), where I is the information content of the protocol and k is the number of players. We complement this result with an almost matching lower bound of ~Omega(Ik), which shows that a nearly-linear dependence on the number of players cannot be avoided.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8011Brief Announcement: Black-Box Concurrent Data Structures for NUMA Architectures
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8012
Recent work introduced a method to automatically produce concurrent data structures for NUMA architectures. We present a summary of that work.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8012Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8013
We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. The time (round) complexity of MIS (and ruling sets) have attracted much attention in the Local model. Indeed, recent results (Barenboim et al., FOCS 2012, Ghaffari SODA 2016) for the MIS problem have tried to break the long-standing O(log n)-round "barrier" achieved by Luby's algorithm, but these yield o(log n)-round complexity only when the maximum degree Delta is somewhat small relative to n. More importantly, these results apply only in the Local model. In fact, the best known time bound in the Congest model is still O(log n) (via Luby's algorithm) even for moderately small Delta (i.e., for Delta = Omega(log n) and Delta = o(n)). Furthermore, message complexity has been largely ignored in the context of local symmetry breaking. Luby's algorithm takes O(m) messages on m-edge graphs and this is the best known bound with respect to messages. Our work is motivated by the following central question: can we break the Theta(log n) time complexity barrier and the Theta(m) message complexity barrier in the Congest model for MIS or closely-related symmetry breaking problems?This paper presents progress towards this question for the distributed ruling set problem in the Congest model. A beta-ruling set is an independent set such that every node in the graph is at most beta hops from a node in the independent set. We present the following results:- Time Complexity: We show that we can break the O(log n) "barrier" for 2- and 3-ruling sets. We compute 3-ruling sets in O(log n/log log n) rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in O(log Delta (log n)^(1/2 + epsilon) + log n/log log n) rounds for any epsilon > 0, which is o(log n) for a wide range of Delta values (e.g., Delta = 2^(log n)^(1/2-epsilon)). These are the first 2- and 3-ruling set algorithms to improve over the O(log n)-round complexity of Luby's algorithm in the Congest model.- Message Complexity: We show an Omega(n^2) lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only O(n log^2 n) messages and runs in O(Delta log n) rounds. This is the first message-efficient algorithm known for ruling sets, which has message complexity nearly linear in n (which is optimal up to a polylogarithmic factor).Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8013Dalí: A Periodically Persistent Hash Map
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8014
Technology trends suggest that byte-addressable nonvolatile memory (NVM) will supplant many uses of DRAM over the coming decade, raising the prospect of inexpensive recovery from power failures and similar faults. Ensuring the consistency of persistent state remains nontrivial, however, in the presence of volatile caches; cached values can "leak" back to persistent memory in arbitrary order. To ensure consistency, existing persistent memory algorithms use expensive, explicit write-back instructions to force each value back to memory before performing a dependent write, thereby incurring significant run-time overhead.To reduce this overhead, we present a new design paradigm that we call periodic persistence. In a periodically persistent data structure, updates are made "in place," but can safely leak back to memory in any order, because only those updates that are known to be valid will be heeded during recovery. To guarantee forward progress, we periodically force a write-back of all dirty data in the cache, ensuring that all "sufficiently old" updates have indeed become persistent, at which point they become semantically visible to the recovery process.As an example of periodic persistence, we present a transactional hash map, Dalí, together with an informal proof of safety (buffered durable linearizability). Experiments with a prototype implementation suggest that periodic persistence can offer substantially better performance than either file-based or incrementally persistent (per-access write-back) alternatives.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8014Demand-Aware Network Designs of Bounded Degree
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8015
Traditionally, networks such as datacenter interconnects are designed to optimize worst-case performance under arbitrary traffic patterns. Such network designs can however be far from optimal when considering the actual workloads and traffic patterns which they serve. This insight led to the development of demand-aware datacenter interconnects which can be reconfigured depending on the workload.Motivated by these trends, this paper initiates the algorithmic study of demand-aware networks (DANs), and in particular the design of bounded-degree networks. The inputs to the network design problem are a discrete communication request distribution, D, defined over communicating pairs from the node set V, and a bound, d, on the maximum degree. In turn, our objective is to design an (undirected) demand-aware network N = (V,E) of bounded-degree d, which provides short routing paths between frequently communicating nodes distributed across N. In particular, the designed network should minimize the expected path length on N (with respect to D), which is a basic measure of the efficiency of the network.We show that this fundamental network design problem exhibits interesting connections to several classic combinatorial problems and to information theory. We derive a general lower bound based on the entropy of the communication pattern D, and present asymptotically optimal network-aware design algorithms for important distribution families, such as sparse distributions and distributions of locally bounded doubling dimensions.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8015Blockchain Consensus Protocols in the Wild (Keynote Talk)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8016
A blockchain is a distributed ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Consensus protocols for tolerating Byzantine faults have received renewed attention because they also address blockchain systems. This work discusses the process of assessing and gaining confidence in the resilience of a consensus protocols exposed to faults and adversarial nodes. We advocate to follow the established practice in cryptography and computer security, relying on public reviews, detailed models, and formal proofs; the designers of several practical systems appear to be unaware of this. Moreover, we review the consensus protocols in some prominent permissioned blockchain platforms with respect to their fault models and resilience against attacks.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8016Simple and Near-Optimal Distributed Coloring for Sparse Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8017
Graph coloring is one of the central problems in distributed graph algorithms. Much of the research on this topic has focused on coloring with Delta+1 colors, where Delta denotes the maximum degree. Using Delta+1 colors may be unsatisfactory in sparse graphs, where not all nodes have such a high degree; it would be more desirable to use a number of colors that improves with sparsity. A standard measure that captures sparsity is arboricity, which is the smallest number of forests into which the edges of the graph can be partitioned.We present simple randomized distributed algorithms that, with high probability, color any n-node alpha-arboricity graph:- using (2+epsilon)alpha colors, for constant epsilon>0, in O(log n) rounds, if alpha=Omega(log n log log n), or- using O(alpha log alpha) colors, in O(log n) rounds, or- using O(alpha) colors, in O(log n min{log log n, log alpha}) rounds.These algorithms are nearly-optimal, as it is known by results of Linial [FOCS'87] and Barenboim and Elkin [PODC'08] that coloring with Theta(alpha) colors, or even poly(alpha) colors, requires Omega(log_alpha n) rounds. The previously best-known O(log n)-time result was a deterministic algorithm due to Barenboim and Elkin [PODC'08], which uses Theta(alpha^2) colors. Barenboim and Elkin stated improving this number of colors as an open problem in their Distributed Graph Coloring Book.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8017Error-Sensitive Proof-Labeling Schemes
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8018
Proof-labeling schemes are known mechanisms providing nodes of networks with certificates that can be verified locally by distributed algorithms. Given a boolean predicate on network states, such schemes enable to check whether the predicate is satisfied by the actual state of the network, by having nodes interacting with their neighbors only. Proof-labeling schemes are typically designed for enforcing fault-tolerance, by making sure that if the current state of the network is illegal with respect to some given predicate, then at least one node will detect it. Such a node can raise an alarm, or launch a recovery procedure enabling the system to return to a legal state. In this paper, we introduce error-sensitive proof-labeling schemes. These are proof-labeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the edit-distance between the current state and the set of legal states. By using error-sensitive proof-labeling schemes, states which are far from satisfying the predicate will be detected by many nodes, enabling fast return to legality. We provide a structural characterization of the set of boolean predicates on network states for which there exist error-sensitive proof-labeling schemes. This characterization allows us to show that classical predicates such as, e.g., acyclicity, and leader admit error-sensitive proof-labeling schemes, while others like regular subgraphs don't. We also focus on compact error-sensitive proof-labeling schemes. In particular, we show that the known proof-labeling schemes for spanning tree and minimum spanning tree, using certificates on O(log n) bits, and on O(log^2 n) bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8018Near-Optimal Distributed DFS in Planar Graphs
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8019
We present a randomized distributed algorithm that computes a Depth-First Search (DFS) tree in ~O(D) rounds, in any planar network G=(V,E) with diameter D, with high probability. This is the first sublinear-time distributed DFS algorithm, improving on a three decades-old O(n) algorithm of Awerbuch (1985), which remains the best known for general graphs. Furthermore, this ~O(D) round complexity is nearly-optimal as Omega(D) is a trivial lower bound.A key technical ingredient in our results is the development of a distributed method for (recursively) computing a separator path, which is a path whose removal from the graph leaves connected components that are all a constant factor smaller. We believe that the general method we develop for computing path separators recursively might be of broader interest, and may provide the first step towards solving many other problems.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8019Brief Announcement: Towards Reduced Instruction Sets for Synchronization
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8020
Contrary to common belief, a recent work by Ellen, Gelashvili, Shavit, and Zhu has shown that computability does not require multicore architectures to support "strong" synchronization instructions like compare-and-swap, as opposed to combinations of "weaker" instructions like decrement and multiply. However, this is the status quo, and in turn, most efficient concurrent data-structures heavily rely on compare-and-swap (e.g. for swinging pointers).We show that this need not be the case, by designing and implementing a concurrent linearizable Log data-structure (also known as a History object), supporting two operations: append(item), which appends the item to the log, and get-log(), which returns the appended items so far, in order. Readers are wait-free and writers are lock-free, hence this data-structure can be used in a lock-free universal construction to implement any concurrent object with a given sequential specification. Our implementation uses atomic read, xor, decrement, and fetch-and-increment instructions supported on X86 architectures, and provides similar performance to a compare-and-swap-based solution on today's hardware. This raises a fundamental question about minimal set of synchronization instructions that the architectures have to support.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8020Phase Transitions and Emergent Phenomena in Random Structures and Algorithms (Keynote Talk)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8021
Markov chain Monte Carlo methods have become ubiquitous across science and engineering to model dynamics and explore large sets of configurations. The idea is to perform a random walk among the configurations so that even though only a very small part of the space is visited, samples will be drawn from a desirable distribution. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose, building on insights from statistical physics. One of the striking discoveries has been the realization that many natural Markov chains undergo phase transitions, whereby they change from being efficient to inefficient as some parameter of the system is modified, also revealing interesting properties of the underlying random structures.We will explore how phase transitions can provide valuable insights in three settings. First, they allow us to understand the limitations of certain classes of sampling algorithms, potentially leading to faster alternative approaches. Second, they reveal statistical properties of stationary distributions, giving insight into various interacting models. Example include colloids, or binary mixtures of molecules, segregation models, where individuals are more likely move when they are unhappy with their local demographics, and interacting particle systems from statistical physics. Last, they predict emergent phenomena that can be harnessed for the design of distributed algorithms for certain asynchronous models of programmable active matter. We will see how these three research threads are closely interrelated and inform one another.The talk will take a random walk through some of the results included in the references.Thu, 05 Oct 2017 10:29:09 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8021Databases on Future Hardware (Dagstuhl Seminar 17101)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7358
A number of physical limitations mandate radical changes in the way howwe build computing hard- and software, and there is broad consensus thata stronger interaction between hard- and software communities is neededto meet the ever-growing demand for application performance.Under this motivation, representatives from various hard- and softwarecommunities have met at the Dagstuhl seminar "Databases on FutureHardware" to discuss the implications in the context of databasesystems. The outcome of the seminar was not only a much betterunderstanding of each other's needs, constraints, and ways of thinking.Very importantly, the group identified topic areas that seem key for theongoing shift, together with suggestions on how the field could moveforward. During the seminar, it turned out that the future of databasesis not only a question of technology. Rather, economic considerationshave to be taken into account when building next-generation databaseengines.Sun, 01 Oct 2017 17:06:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7358Using Networks to Teach About Networks (Dagstuhl Seminar 17112)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7360
his report documents the program and the outcomes of Dagstuhl Seminar 17112 "Using Networks to Teach About Networks". The seminar brought together people with mixed backgrounds in order to exchange experiences gained with different approaches to teach computer networking. Despite the obvious question of what to teach, special attention was given to the questions of how to teach and which tools and infrastructures can be used effectively today for teaching purposes.Fri, 29 Sep 2017 08:44:23 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7360Game Theory in AI, Logic, and Algorithms (Dagstuhl Seminar 17111)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7960
This report documents the program and the outcomes of Dagstuhl Seminar 17111 "Game Theory in AI, Logic, and Algorithms". Fri, 29 Sep 2017 08:43:05 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7960Rethinking Productivity in Software Engineering (Dagstuhl Seminar 17102)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7359
This report documents the program and the outcomes of Dagstuhl Seminar 17102 "Rethinking Productivity in Software Engineering". In the following, we briefly summarize the goals and format of the of the seminar, before we provide insights and an outlook, including a few grand challenges, based on the results and statements collected during the seminar.Fri, 29 Sep 2017 08:36:51 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7359Front Matter, Table of Contents, Preface, Conference Organization
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7936
Front Matter, Table of Contents, Preface,Program Committee, List of AuthorsThu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7936Applying Attribute Grammars to Teach Linguistic Rules
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7937
An attribute grammar is a very well known formalism to describe computer languages but it can also be successfully used to describe linguistic phenomena. Since natural languages can also be expressed in grammars it is natural to describe rules using the same formalism. Linguistic teachers of the University Complutense of Madrid started using attribute grammars but they lack a tool that helps them to specify linguistic rules in a friendly and natural way. Therefore we propose a domain specific language (NLSdsl) carefully designed for non-programmers that will be implemented on an AnTLR based system.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7937Towards an Automated Test Bench Environment for Prolog Systems
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7938
Software testing and benchmarking is a key component of the software development process. Nowadays, a good practice in big software projects is the Continuous Integration (CI) software development technique. The key idea of CI is to let developers integrate their work as they produce it, instead of doing the integration at the end of each software module. In this paper, we extend a previous work on a benchmark suite for the Yap Prolog system and we propose a fully automated test bench environment for Prolog systems, named Yet Another Prolog Test Bench Environment (YAPTBE), aimed to assist developers in the development and CI of Prolog systems. YAPTBE is based on a cloud computing architecture and relies on the Jenkins framework and in a set of new Jenkins plugins to manage the underneath infrastructure. We present the key design and implementation aspects of YAPTBE and show its most important features, such as its graphical user interface and the automated process that builds and runs Prolog systems and benchmarks.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7938Generating Method Documentation Using Concrete Values from Executions
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7939
There exist multiple automated approaches of source code documentation generation. They often describe methods in abstract terms, using the words contained in the static source code or code excerpts from repositories. In this paper, we introduce DynamiDoc - a simple yet effective automated documentation approach based on dynamic analysis. It traces the program being executed and records string representations of concrete argument values, a return value, and a target object state before and after each method execution. Then for every concerned method, it generates documentation sentences containing examples, such as "When called on [3, 1.2] with element = 3, the object changed to [1.2]". A qualitative evaluation is performed, listing advantages and shortcomings of the approach.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7939Modelling Contiki-Based IoT Systems
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7940
In this paper, we investigate how model-driven engineering (MDE) of Internet of Things (IoT) systems and Wireless-Sensor Networks (WSN) can be supported and introduce a domain-specific metamodel for modeling such systems based on the well-known Contiki operating system. The unique lightweight thread structure of Contiki makes it more preferable in the implementation of new IoT systems instead of many other existing platforms. Although some MDE approaches exist for IoT systems and WSNs, currently there is no study which addresses the modelling according to the specifications of Contiki platform. The work presented in this paper aims at filling this gap and covers the development of both a modeling language syntax and a graphical modeling environment for the MDE of IoTs according to event-driven mechanism and protothread architecture of Contiki. Use of the proposed modeling language is demonstrated with including the development of an IoT system for forest fire detection.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7940Exercise Solution Check Specification Language for Interactive Programming Learning Environments
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7941
Automatic checking of the correctness of students' solutions of programming exercises for generating appropriate feedback is a necessary component of interactive programming learning environments. Although there are multiple ways of specifying such a check, ranging from mere string patterns to code written in general-purpose programming language, they all have their deficiencies, with the check specification being too verbose, too complicated, difficult to reuse, or very limited in its expressive capabilities. In this paper, a new language designed especially for this purpose is described. It provides both extension and replacement for RegEx-based pattern specification so that checks typical for programming exercise verification can be expressed in a concise and highly-readable manner.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7941Visualizing the Evaluation of Functional Programs for Debugging
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7942
In this position paper, we present a prototype of a visualizer for functional programs. Such programs, whose evaluation model is the reduction of an expression to a value through repeated application of rewriting rules, and which tend to make little or no use of mutable state, are amenable to visualization in the same fashion as simple mathematical expressions, with which every schoolchild is familiar. We show how such visualizations may be produced for the strict functional language OCaml, by direct interpretation of the abstract syntax tree and appropriate pretty-printing. We describe (and begin to address) the challenges of presenting such program traces in limited space and of identifying their essential elements, so that our methods will one day be practical for more than toy programs. We consider the problems posed by the parts of modern functional programming which are not purely functional such as mutable state, input/output and exceptions. We describe initial work on the use of such visualizations to address the problem of program debugging, which is our ultimate aim. Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7942A Survey on CSS Preprocessors
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7943
In the Web realm, the adoption of Cascading Style Sheets (CSS) is unanimous, being widely used for styling web documents. Despite their intensive use, this W3C specification was written for web designers with limit programming background. Thus, it lack several programming constructs, such as variables, conditional and repetitive blocks, and functions. This absence affects negatively code reuse, and consequently, the maintenance of the styling code. In the last decade, several languages (e.g. Sass, Less) appeared to extend CSS, defined as CSS preprocessors, with the ultimate goal to bring those missing constructs and to foster stylesheets structured programming. The paper provides an introductory survey on CSS Preprocessors. It gathers information on a specific set of preprocessors, categorizes them and compares their features regarding a set of predefined criteria such as: maturity, coverage and performance.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7943XML Parsing in JavaScript
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7944
With Web 2.0 the dynamic web got to a reality. With it, some new concepts arived, like the use of asynchronous calls to receive missing data to render a website, instead of requesting a full new page to the server. For this task, and in the recent years, developers use mostly the JSON format for the interchange of data, than XML. Nevertheless, XML is more suitable for some kind of data interchange but, and even if the web is based in SGML/XML standards, processing XML using directly JavaScript is tricky.In this document, a set of different approaches to parse XML with JavaScript will be described, and a new module, based on a set of translation functions, will be presented. At the end, a set of experiments will be discussed, trying to evaluate how versatile the proposed approach is.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7944Indexing XML Documents Using Tree Paths Automaton
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7945
An XML document can be viewed as a tree in a natural way. Processing tree data structures usually requires a pushdown automaton as a model of computation. Therefore, it is interesting that a finite automaton can be used to solve the XML index problem. In this paper, we attempt to support a significant fragment of XPath queries which may use any combination of child (i.e., /) and descendant-or-self (i.e., //) axis. A systematic approach to the construction of such XML index, which is a finite automaton called Tree Paths Automaton, is presented. Given an XML tree model T, the tree is first of all preprocessed by means of its linear fragments called string paths. Since only path queries are considered, the branching structure of the XML tree model can be omitted. For individual string paths, smaller Tree Paths Automata are built, and they are afterwards combined to form the index. The searching phase uses the index, reads an input query Q of size m, and computes the list of positions of all occurrences of Q in the tree T. The searching is performed in time O(m) and does not depend on the size of the XML document. Although the number of queries is clearly exponential in the number of nodes of the XML tree model, the size of the index seems to be, according to our experimental results, usually only about 2.5 times larger than the size of the original document. Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7945A REST Service for Poetry Generation
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7946
This paper describes a REST API developed on the top of PoeTryMe, a poetry generation platform. This API exposes several functionalities, from the production of full poems, to narrower tasks, having in mind their utility for poetry composition, including the acquisition of well-formed lines, or semantically-related words, possibly constrained by the number of syllables, rhyme, or polarity. Examples that illustrate the endpoints and what they can be used for are also revealed.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7946SOS - Simple Orchestration of Services
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7947
Nowadays, we continue to write redundant code which can often be reused from the Web. Reusing programming tasks is beneficial since it speeds up the process of creating applications and reduces the errors related with the task creation from scratch. At the same time, the demands of our applications are increasing, leading to a simple problem having to be solved through several tasks. With the advent of the cloud, there are countless Web services that proliferate on the Web. One solution for developers is to use these Web Services. However, the process of mastering and coordinating all these services manually is time-consuming and error-prone.This paper presents SOS, a Simple Orchestration of Services. The ultimate goal of this tool is to act as a service composer while promoting the separation of concerns for two typical actors in this realm: the developer and the business analyst. The developer must define a service as a SOS task based on a JSON schema and submit it in a Web specialized editor. The business analyst uses the SOS editor, in an interactive way, to chain the required tasks to solve a specific problem. Then, the developer, uses a a simple client API - a SOS engine wrapper - to load a SOS manifest and to iterate over all tasks, without the need to dominate any bureaucratic aspects related with HTTP clients and messages. As a case study, several tasks are instantiated and aggregated in order to generate a composite service for a mobile app whose goal is to give an translated description of a picture taken with a mobile phone.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7947Visualization of Ontology Evolution using OntoDiffGraph
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7948
Ontologies evolve with the passing of time due to improvements, corrections or changes in requirements that need to be made. In this paper we describe a thesis work aiming at the creation of a visualization technique with the objective of allowing the viewer to easily identify changes made in an ontology. With the use of a specification based on the already existing Visual Notation for OWL Ontologies (VOWL) it is possible to display the differences that exist between two versions of an ontology. The proposed approach will be implemented in an application, that is also discussed in the paper.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7948Socii: A Tool to Analyze and Visualize Dynamic Social Networks
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7949
Social media network analysis represents a major challenge for data scientists in every aspect, since the extraction all the way to the visualization. Despite representing a major technological challenge, social media data analysis has an additional motivation, that is the daily usage in every country across the planet, making Online Social Network (OSN) a universal tool for communication, such as radio or TV, but with the technological flavor of the 21st century. In the present article, we propose a system, called Socii, for social networks analysis and visualization, as part of an ongoing work under a master’s dissertation. This system overlaps two main scientific fields, sociology (more concisely social networks) and computer science. Socii aims at helping OSNs users to know and understand social structures through a user friendly interface. The system relies in four main principles, namely simplicity, accessibility, OSNs integration and contextual analysis.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7949Comparing and Combining Portuguese Lexical-Semantic Knowledge Bases
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7950
There are currently several lexical-semantic knowledge bases (LKBs) for Portuguese, developed by different teams and following different approaches. In this paper, the open Portuguese LKBs are briefly analysed, with a focus on size and overlapping contents, and new LKBs are created from their redundant information. Existing and new LKBs are then exploited in the performance of semantic analysis tasks and their performance is compared. Results confirm that, instead of selecting a single LKB to use, it is worth combining all the open Portuguese LKBs.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7950Information Extraction for Event Ranking
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7951
Search engines are evolving towards richer and stronger semantic approaches, focusing on entity-oriented tasks where knowledge bases have become fundamental. In order to support semantic search, search engines are increasingly reliant on robust information extraction systems. In fact, most modern search engines are already highly dependent on a well-curated knowledge base. Nevertheless, they still lack the ability to effectively and automatically take advantage of multiple heterogeneous data sources. Central tasks include harnessing the information locked within textual content by linking mentioned entities to a knowledge base, or the integration of multiple knowledge bases to answer natural language questions. Combining text and knowledge bases is frequently used to improve search results, but it can also be used for the query-independent ranking of entities like events. In this work, we present a complete information extraction pipeline for the Portuguese language, covering all stages from data acquisition to knowledge base population. We also describe a practical application of the automatically extracted information, to support the ranking of upcoming events displayed in the landing page of an institutional search engine, where space is limited to only three relevant events. We manually annotate a dataset of news, covering event announcements from multiple faculties and organic units of the institution. We then use it to train and evaluate the named entity recognition module of the pipeline. We rank events by taking advantage of identified entities, as well as partOf relations, in order to compute an entity popularity score, as well as an entity click score based on implicit feedback from clicks from the institutional search engine. We then combine these two scores with the number of days to the event, obtaining a final ranking for the three most relevant upcoming events.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7951A Method for Proper Noun Extraction in Kurdish
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7952
This paper suggests a method for proper noun identification in Kurdish texts. Kurdish proper nouns are not capitalized and they also assume other part-of-speech roles, which leads to a broad ambiguity that should be addressed in Kurdish proper noun recognition applications. Kurdish is also among less-resourced languages. We developed an application based on an architecture which includes a number of name lists, a set of rules, and a set of processes that recognizes Kurdish person names. This can help the study of Information Retrieval (IR) in Kurdish to advance and can also be used in Kurdish machine translation. We conducted several experiments which showed that the precision of the method is more than 95%, the recall is between 40% to 80%, and the F-measure is close to 60% to more than 80%. The reason for the low recall precision was because our name lists were not exhaustive enough to cover the vast majority of the Kurdish names.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7952Natural Transmission of Information Extraction Results to End-Users - A Proof-of-Concept Using Data-to-Text
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7953
Information Extraction from natural texts has a great potential in areas such as Tourism and can be of great assistance in transforming customers' comments in valuable information for Tourism operators, governments and customers. After extraction, information needs to be efficiently transmitted to end-users in a natural way. Systems should not, in general, send extracted information directly to end-users, such as hotel managers, as it can be difficult to read.Naturally, humans transmit and encode information using natural languages, such as Portuguese. The problem arising from the need of efficient and natural transmission of the information to end-user is how to encode it. The use of natural language generation (NLG) is a possible solution, for producing sentences, and, with them, texts.In this paper we address this, with a data-to-text system, a derivation of formal NLG systems that use data as input. The proposed system uses an aligned corpus, which was defined, collected and processed, in about approximately 3 weeks of work. To build the language model were used three different in-domain and out-of-domain corpora. The effects of this approach were evaluated, and results are presented.Automatic metrics, BLEU and Meteor, were used to evaluate the different systems, comparing their values with similar systems. Results show that expanding the corpus has a major positive effect in BLEU and Meteor scores and use of additional corpora (in-domain and out-of-domain) in training language model does not result in significantly different performance.The scores obtained, combined with their comparison with other systems performance and informal evaluation by humans of the sentences produced, give additional support for the capabilities of the translation based approach for fast development of data-to-text for new domains.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7953Adapting Speech Recognition in Augmented Reality for Mobile Devices in Outdoor Environments
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7954
This paper describes the process of integrating automatic speech recognition (ASR) into a mobile application and explores the benefits and challenges of integrating speech with augmented reality (AR) in outdoor environments. The augmented reality allows end-users to interact with the information displayed and perform tasks, while increasing the user’s perception about the real world by adding virtual information to it. Speech is the most natural way of communication: it allows hands-free interaction and may allow end-users to quickly and easily access a range of features available. Speech recognition technology is often available in most of the current mobile devices, but it often uses Internet to receive the corresponding transcript from remote servers, e.g., Google speech recognition. However, in some outdoor environments, Internet is not always available or may be offered at poor quality. We integrated an off-line automatic speech recognition module into an AR application for outdoor usage that does not require Internet. Currently, speech interaction is used within the application to access five different features, namely: to take a photo, shoot a film, communicate, messaging related tasks, and to request information, either geographic, biometric, or climatic. The application makes available solutions to manage and interact with the mobile device, offering good usability. We have compared the online and off-line speech recognition systems in order to assess their adequacy to the tasks. Both systems were tested under different conditions, commonly found in outdoor environments, such as: Internet access quality, presence of noise, and distractions.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7954Vocatives in Portuguese: Identification and Processing
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7955
This paper describes the most salient linguistic aspects of vocative constructions in Portuguese, with special reference to its European variety. Next, the paper presents the strategy followed for implementing this linguistic knowledge in a computational grammar of Portuguese, developed for the natural language processing chain STRING and using the XIP rule-based parser. Very precise and detailed linguistic descriptions can be implemented in this way.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7955Linear Operators in Information Retrieval
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7956
In this paper, we propose a pseudo-relevance feedback approach based on linear operators: vector space basis change and cross product. The aim of pseudo-relevance feedback methods based on vector space basis change IBM (Ideal Basis Method) is to optimally separate relevant and irrelevant documents. Whereas the aim of pseudo-relevance feedback method based on cross product AI (Absorption of irrelevance) is to effectively exploit irrelevant documents. We show how to combine IBM methods with AI methods. The combination methods IBM+AI are evaluated experimentally on two TREC collections (TREC-7 ad hoc and TREC-8 ad hoc). The experiments show that these methods improve previous works.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7956Enhancing Feedback to Students in Automated Diagram Assessment
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7957
Automated assessment is an essential part of eLearning. Although comparatively easy for multiple choice questions (MCQs), automated assessment is more challenging when exercises involve languages used in computer science. In this particular case, the assessment is more than just grading and must include feedback that leads to the improvement of the students' performance.This paper presents ongoing work to develop Kora, an automated diagram assessment tool with enhanced feedback, targeted to the multiple diagrammatic languages used in computer science. Kora builds on the experience gained with previous research, namely: a diagram assessment tool to compute differences between graphs; an IDE inspired web learning environment for computer science languages; and an extensible web diagram editor. Kora has several features to enhance feedback: it distinguishes syntactic and semantic errors, providing specialized feedback in each case; it provides progressive feedback disclosure, controlling the quality and quantity shown to each student after a submission; when possible, it integrates feedback within the diagram editor showing actual nodes and edges on the editor itself. Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7957An Emotional Word Analyzer for Portuguese
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7958
The analysis of sentiments, emotions and opinions in texts is increasingly important in the current digital world. The existing lexicons with emotional annotations for the Portuguese language are oriented to polarities, classifying words as positive, negative or neutral. To identify the emotional load intended by the author it is necessary also to categorize the emotions expressed by individual words.EmoSpell is an extension of a morphological analyzer with semantic annotations of the emotional value of words. It uses Jspell as the morphological analyzer and a new dictionary with emotional annotations. This dictionary incorporates the lexical base EMOTAIX.PT, which classifies words based on three different levels of emotions - global, specific and intermediate.This paper describes the generation of the EmoSpell dictionary using three sources, the Jspell Portuguese dictionary and the lexical bases EMOTAIX.PT and SentiLex-PT. Also, this paper details the web application and web service that exploit this dictionary. It presents also a validation of the proposed approach using a corpus of student texts with different emotional loads. The validation compares the analyses provided by EmoSpell with the mentioned emotional lexical bases on the ability to recognize emotional words and extract the dominant emotion from a text.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7958Towards Employing Informal Sketches and Diagrams in Software Development
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7959
Programmers write notes and draw informal sketches and diagrams. We hypothesize about understandability and helpfulness of these sketches and their deeper inclusion into software development process. We are leveraging the fact that we have a collection of such sketches affiliated to a commercial software system. We have the opportunity to study sketches that were created naturally, not intentionally for research purposes. The oldest sketch was created a year and a half ago and the most recent one a half a year ago. Our initial experiment shows that these sketches are pretty understandable even after some time - even for another person.Thu, 28 Sep 2017 13:46:17 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7959Search as Learning (Dagstuhl Seminar 17092)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7357
This report describes the program and the results of Dagstuhl Seminar 17092 "Search as Learning", which brought together 26 researchers from diverse research backgrounds. The motivation for the seminar stems from the fact that modern Web search engines are largely engineered and optimized to fulfill lookup tasks instead of complex search tasks. The latter though are an essential component of information discovery and learning. The 3-day seminar started with four perspective talks, providing four different views on the topic of search as learning: interactive information retrieval (IR), psychology, education and system-oriented IR. The remainder of the seminar centered around breakout groups leading to new views on the challenges andissues in search as learning, interspersed with research spotlight talks.Wed, 20 Sep 2017 08:02:49 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7357Computer Science Meets Ecology (Dagstuhl Seminar 17091)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7356
This report summarizes the program and main outcomes of the Dagstuhl Seminar 17091 entitled ``Computer Science Meets Ecolog''. Ecology is a discipline that poses many challenging problems involving big data collection, provenance and integration, as well as difficulties in data analysis, prediction and understanding. All these issues are precisely the arena where computer science is concerned. The seminar motivation was rooted in the belief that ecology could largely benefit from modern computer science. The seminar attracted scientists from both fields who discussed important topics in ecology (e.g. botany, animal science, biogeochemistry) and how to approach them with machine learning, computer vision, pattern recognition and data mining. A set of specific problems and techniques were treated, and the main building blocks were set up. The important topics of education, outreach, data and models accessibility were also touched upon. The seminar proposed a distinctive perspective by promoting cross-fertilization in a unique environment and a unique set of individuals.Wed, 20 Sep 2017 08:02:42 +0200http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7356