Search

Communication in networks suffers if a link fails. When the links are edges of a tree that has been chosen from an underlying graph of all possible links, a broken link even disconnects the network. Most often, the link is restored rapidly. A good policy to deal with this sort of transient link failures is swap rerouting, where the temporarily broken link is replaced by a single swap link from the underlying graph. A rapid replacement of a broken link by a swap link is only possible if all swap links have been precomputed. The selection of high quality swap links is essential; it must follow the same objective as the originally chosen communication subnetwork. We are interested in a minimum diameter tree in a graph with edge weights (so as to minimize the maximum travel time of messages). Hence, each swap link must minimize (among all possible swaps) the diameter of the tree that results from swapping. We propose a distributed algorithm that efficiently computes all of these swap links, and we explain how to route messages across swap edges with a compact routing scheme. [ABSTRACT FROM AUTHOR]

We examine the problem of detecting nested temporal predicates given the execution trace of a distributed program. We present a technique that allows efficient detection of a reasonably large class of predicates which we call the Basic Temporal Logic or BTL. Examples of valid BTL predicates are nested temporal predicates based on local variables with arbitrary negations, disjunctions, conjunctions and the possibly (EF or $\Diamond$) and invariant(AG or $\Box$) temporal operators. We introduce the concept of a basis, a compact representation of all global cuts which satisfy the predicate. We present an algorithm to compute a basis of a computation given any BTL predicate and prove that its time complexity is polynomial with respect to the number of processes and events in the trace although it is not polynomial in the size of the formula. We do not know of any other technique which detects a similar class of predicates with a time complexity that is polynomial in the number of processes and events in the system. We have implemented a predicate detection toolkit based on our algorithm that accepts offline traces from any distributed program. [ABSTRACT FROM AUTHOR]

The timestamp problem captures a fundamental aspect of asynchronous distributed computing. It allows processes to label events throughout the system with timestamps that provide information about the real-time ordering of those events. We consider the space complexity of wait-free implementations of timestamps from shared read-write registers in a system of n processes. We prove an $\Omega(\sqrt{n})$ lower bound on the number of registers required. If the timestamps are elements of a nowhere dense set, for example the integers, we prove a stronger, and tight, lower bound of n. However, if timestamps are not from a nowhere dense set, this bound can be beaten; we give an algorithm that uses n − 1 (single-writer) registers. We also consider the special case of anonymous algorithms, where processes do not have unique identifiers. We prove anonymous timestamp algorithms require n registers. We give an algorithm to prove that this lower bound is tight. This is the first anonymous algorithm that uses a finite number of registers. Although this algorithm is wait-free, its step complexity is not bounded. We also present an algorithm that uses O(n2) registers and has bounded step complexity. [ABSTRACT FROM AUTHOR]

Let consider n autonomous mobile robots that can move in a two dimensional plane. The gathering problem is one of the most fundamental tasks of autonomous mobile robots. In short, given a set of robots with arbitrary initial locations, gathering must make all robots meet in finite time at a point that is not predefined. In this paper, we study about the feasibility of gathering by mobile robots that have φ-absolute error dynamic compasses. While the direction of each local coordinate system is fixed in usual systems, the dynamic compass model allows the angle difference between a local coordinate system and the global coordinate system to vary with time in the range of [0, φ]. This paper proposes a semi-synchronous gathering algorithm for n robots with (π/2 − ε)-absolute error dynamic compasses, where ε is an arbitrary small constant larger than zero. To the best of our knowledge, the proposed algorithm is the first one that considers both inaccurate compass models and more than two robots. We also show the optimality of our algorithm. It is proved that for any φ ≥ π/2, there is no algorithm to gather two robots with φ-absolute error dynamic compasses. [ABSTRACT FROM AUTHOR]

Eventual failure detectors, such as Ω or $\Diamond$P, can make arbitrarily many mistakes before they start providing correct information. This paper shows that any detector implementable in a purely asynchronous system can be implemented as a function of only the order of most-recently heard-from processes. The finiteness of this representation means that eventual failure detectors can be enumerated and their relative strengths tested automatically. The results for systems with two and three processes are presented. Implementability can also be modelled as a game between Prover and Disprover. This approach not only speeds up automatic implementability testing, but also results in shorter and more intuitive proofs. I use this technique to identify the new weakest failure detector anti-Ω and prove its properties. Anti-Ω outputs process ids and, while not necessarily stabilizing, it ensures that some correct process is eventually never output. [ABSTRACT FROM AUTHOR]

Three well studied progress conditions for implementing concurrent algorithms without locking are, obstruction-freedom, non-blocking and wait-freedom. Obstruction-freedom is weaker than non-blocking which, in turn, is weaker than wait-freedom. While obstruction-freedom and non-blocking have the potential to significantly improve the performance of concurrent applications, wait-freedom (although desirable) imposes too much overhead upon the implementation. In [5], Fich, Luchangco, Moir, and Shavit have presented an interesting transformation that converts any obstruction-free algorithm into a wait-free algorithm when analyzed in the unknown-bound semi-synchronous model. The FLMS transformation uses n atomic single-writer registers, n atomic multi-writer registers and a single fetch-and-increment object, where n is the number of processes. We define a time complexity measure for analyzing such transformations, and prove that the time complexity of the FLMS transformation is exponential in the number of processes n. This leads naturally to the question of whether the time and/or space complexity of the FLMS transformation can be improved by relaxing the wait-freedom progress condition. We present several efficient transformations that convert any obstruction-free algorithm into a non-blocking algorithm when analyzed in the unknown-bound semi-synchronous model. All our transformations have O(1) time complexity. One transformation uses n atomic single-writer registers and a single compare-and-swap object; another transformation uses only a single compare-and-swap object which is assumed to support also a read operation. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the number of ADMs in optical networks. All previous theoretical studies of this problem dealt with the off-line case, where all the lightpaths are given in advance. In a real-life situation, the requests (lightpaths) arrive at the network on-line, and we have to assign them wavelengths so as to minimize the switching cost. This study is thus of great importance in the theory of optical networks. We present an on-line algorithm for the problem, and show its competitive ratio to be $\frac{7}{4}$. We show that this result is best possible in general. Moreover, we show that even for the ring topology network there is no on-line algorithm with competitive ratio better than $\frac{7}{4}$. We show that on path topology the competitive ratio of the algorithm is $\frac{3}{2}$. This is optimal for this topology. The lower bound on ring topology does not hold when the ring is of bounded size. We analyze the triangle topology and show a tight bound of $\frac{5}{3}$ for it. The analyzes of the upper bounds, as well as those for the lower bounds, are all using a variety of proof techniques, which are of interest by their own, and which might prove helpful in future research on the topic. [ABSTRACT FROM AUTHOR]

Byzantine-fault-tolerant service protocols like Q/U and FaB Paxos that optimistically order requests can provide increased efficiency and fault scalability. However, these protocols require n ≥ 5b+ 1 servers (where b is the maximum number of faults tolerated), owing to their use of opaque Byzantine quorum systems; this is 2b more servers than required by some non-optimistic protocols. In this paper, we present a family of probabilistic opaque Byzantine quorum systems that require substantially fewer servers. Our analysis is novel in that it assumes Byzantine clients, anticipating that a faulty client may seek quorums that maximize the probability of error. Using this as motivation, we present an optional, novel protocol that allows probabilistic quorum systems to tolerate Byzantine clients. The protocol requires only one additional round of interaction between the client and the servers, and this round may be amortized over multiple operations. We consider actual error probabilities introduced by the probabilistic approach for concrete configurations of opaque quorum systems, and prove that the probability of error vanishes with as few as n > 3.15 b servers as n and b grow. [ABSTRACT FROM AUTHOR]

The paper considers broadcasting protocols in radio networks with known topology that are efficient in both time and energy. The radio network is modelled as an undirected graph G = (V,E) where V = n. It is assumed that during execution of the communication task every node in V is allowed to transmit at most once. Under this assumption it is shown that any radio broadcast protocol requires $D+\Omega(\sqrt{n-D})$ transmission rounds, where D is the diameter of G. This lower bound is complemented with an efficient construction of a deterministic protocol that accomplishes broadcasting in $D+O(\sqrt{n}\log n)$ rounds. Moreover, if we allow each node to transmit at most k times, the lower bound D + Ω((n − D)1/(2k)) on the number of transmission rounds holds. We also provide a randomised protocol that accomplishes broadcasting in D + O(kn1/(k − 2)log2n) rounds. The paper concludes with a discussion of several other strategies for energy efficient radio broadcasting and a number of open problems in the area. [ABSTRACT FROM AUTHOR]

In contrast to peer-to-peer file sharing, live streaming based on peer-to-peer technology is still awaiting its breakthrough. This may be due to the additional challenges live streaming faces, e.g., the need to meet real-time playback deadlines, or the increased demands on robustness under churn. This paper presents and evaluates novel neighbor selection and data distribution schemes for peer-to-peer live streaming. Concretely, in order to distribute data efficiently and with minimal delay, our algorithms combine low-latency push operations along a structured overlay with the flexibility of pull operations. The protocols ensure that all peers are able to obtain the required data blocks of a live stream in time, and that due to the loop-free dissemination paths, the overhead is low. [ABSTRACT FROM AUTHOR]

Consider a network whose inputs change rapidly, or are subject to frequent faults. This is expected often to be the case in the foreseen huge sensor networks. Suppose, that an algorithm is required to output the majority value of the inputs. To address such networks, it is desirable to be able to stabilize the output fast, and to give guarantees on the outputs even before stabilization, even if additional changes occur. We bound the instability of the outputs (the number of times the output changes) of majority consensus algorithms even before the final stabilization. We show that the instability can be traded off with their time adaptvity (how fast they are required to stabilize the output if f faults occurred). First, for the extreme point of the trade-off, we achieve instability that is optimal for the class of algorithms that are optimal in their output time adaptivity. This is done for various known versions of majority consensus problem. The optimal instability for this case is Ω(logf) and is shown to be O(logf) for most versions and O(logn) in some cases. Previous such algorithms did not have such a guarantee on the behaviour of the output before its final stabilization (and their instability was Ω(n)). We also explain how to adapt the results for other points in the trade off. The output stabilization in previous algorithms was adaptive only if the faults ceased for O(Diam) time. An additional result in this paper uses adaptations of some previous tools, as well as the new tools developed here for bounding the instability, in order to remove this limitation that is undesirable when changes are frequent. [ABSTRACT FROM AUTHOR]

We study replacement algorithms for non-uniform access caches that are used in distributed storage systems. Considering access latencies as major costs of data management in such a system, we show that the total cost of any replacement algorithm is bounded by the total costs of evicted blocks plus the total cost of the optimal off-line algorithm (OPT). We propose two off-line heuristics: MIN-d and MIN-cod, as well as an on-line algorithm: HD-cod, which can be run efficiently and perform well at the same time. Our simulation results with Storage Performance Council (SPC)'s storage server traces show that: (1) for off-line workloads, MIN-cod performs as well as OPT in some cases, all is at most three times worse in all test case; (2) for on-line workloads, HD-cod performs closely to the best algorithms in all cases, and is the single algorithm that performs well in all test cases, including the optimal on-line algorithm (Landlord). Our study suggests that the essential issue to be considered be the trade-off between the costs of victim blocks and the total number of evictions in order to effectively optimize both efficiency and performance of distributed storage cache replacement algorithms. [ABSTRACT FROM AUTHOR]

Weak fairness guarantees that continuously enabled actions are executed infinitely often. Strong fairness, on the other hand, guarantees that actions that are enabled infinitely often (but not necessarily continuously) are executed infinitely often. In this paper, we present a distributed algorithm for scheduling actions for execution. Assuming weak fairness for the execution of this algorithm, the schedule it provides is strongly fair. Furthermore, this algorithm is maximal in that it is capable of generating any strongly fair schedule. This algorithm is the first strongly-fair scheduling algorithm that is both distributed and maximal. [ABSTRACT FROM AUTHOR]

We study the impact of faulty processors on the communication cost of distributed algorithms in a message-passing model. The system is synchronous but prone to various kinds of processor failures: crashes, message omissions, (authenticated) Byzantine faults. One of the basic communication tasks, called fault-tolerant gossip, or gossip for short, is to exchange the initial values among all non-faulty processors. In this paper we address the question if there is a gossip algorithm which is both fault-tolerant, fast and communication-efficient? We answer this question in affirmative in the model allowing only crash failures, and in some sense negatively when the other kinds of failures may occur. More precisely, in an execution by n processors when f of them are faulty, each non-faulty processor contributes a constant to the message complexity, each crashed processor contributes Θ(fε) (ε> 0 could be an arbitrarily small constant independent from n,f but dependent on the algorithm), each omission (or authenticated Byzantine) processor contributes Θ(t), and each—even potential—Byzantine failure results in additional Θ(n) messages sent. [ABSTRACT FROM AUTHOR]

Many recommend planning for the worst and hoping for the best. In this paper we devise efficient indulgent consensus algorithms that can tolerate crash failures and arbitrarily long periods of asynchrony, and yet perform (asymptotically) optimally in well-behaved, synchronous executions with few failures. We present two such algorithms: In synchronous executions, the first has optimal message complexity, using only O(n) messages, but runs in superlinear time of O(n1 + ε). The second has a message complexity of , but has an optimal running time, completing in O(f) rounds in synchronous executions with at most f failures. Both of these results improve significantly over the most message-efficient of previous indulgent consensus algorithms which have a message complexity of at least Ω(n2) in well-behaved executions. [ABSTRACT FROM AUTHOR]

This paper presents an efficient scheme maintaining a separator decomposition representation in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, the scheme uses relatively low message complexity. In particular, if the initial dynamic tree contains just the root, then the scheme incurs an O(log3n) amortized message complexity per topology change, where n is the current number of nodes in the tree. As a separator decomposition is a fundamental decomposition of trees used extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for constructing dynamic versions to these algorithms. The paper then shows how to use our dynamic separator decomposition to construct rather efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme. Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models, which maintain optimal labels, up to a multiplicative factor of O(loglogn). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance labeling schemes. [ABSTRACT FROM AUTHOR]

We study adaptive routing algorithms in a round-based model. Suppose we are given a network equipped with load-dependent latency functions on the edges and a set of commodities each of which is defined by a collection of paths (represented by a DAG) and a flow rate. Each commodity is controlled by an agent which aims at balancing its traffic among its paths such that all used paths have the same latency. Such an allocation is called a Wardrop equilibrium. In recent work, it was shown that an infinite population of users each of which carries an infinitesimal amount of traffic can attain approximate equilibria in a distributed and concurrent fashion quickly. Interestingly, the convergence time is independent of the underlying graph and depends only mildly on the latency functions. Unfortunately, a direct simulation of this process requires to maintain an exponential number of variables, one for each path. The focus of this work lies on the distributed and efficient computation of the adaptation rules by a finite number of agents. In order to guarantee a polynomial running time, every agent computes a randomised path decomposition in every communication round. Based on this decomposition, agents remove flow from paths with high latency and reassign it proportionally to all paths. This way, our algorithm can handle exponentially large path collections in polynomial time. [ABSTRACT FROM AUTHOR]

This paper studies the impact of omission failures on asynchronous distributed systems with crash-stop failures. We provide two different transformations for algorithms, failure detectors, and problem specifications, one of which is weakest failure detector preserving. We prove that our transformation of failure detector Ω [1] is the weakest failure detector for consensus in environments with crash-stop and permanent omission failures and a majority of correct processes. Our results help to use the power of the well-understood crash-stop model to automatically derive solutions for the general omission model, which has recently raised interest for being noticeably applicable for security problems in distributed environments equipped with security modules such as smartcards [2,3,4]. [ABSTRACT FROM AUTHOR]

Consider a distributed network of n nodes that is connected to a global source of "beats". All nodes receive the "beats" simultaneously, and operate in lock-step. A scheme that produces a "pulse" every Cycle beats is shown. That is, the nodes agree on "special beats", which are spaced Cycle beats apart. Given such a scheme, a clock synchronization algorithm is built. The "pulsing" scheme is self-stabilized despite any transient faults and the continuous presence of up to $f < \frac{n}{3}$Byzantin nodes. Therefore, the clock synchronization built on top of the "pulse" is highly fault tolerant. In addition, a highly fault tolerant general stabilizer algorithm is constructed on top of the "pulse" mechanism. Previous clock synchronization solutions, operating in the exact same model as this one, either support $f < \frac{n}{4}$ and converge in linear time, or support $f < \frac{n}{3}$ and have exponential convergence time that also depends on the value of max-clock (the clock wrap around value). The proposed scheme combines the best of both worlds: it converges in linear time that is independent of max-clock and is tolerant to up to $f < \frac {n}{3}$Byzantin nodes. Moreover, considering problems in a self-stabilizing, Byzantin tolerant environment that require nodes to know the global state (clock synchronization, token circulation, agreement, etc.), the work presented here is the first protocol to operate in a network that is not fully connected. [ABSTRACT FROM AUTHOR]

We study oblivious deterministic gossip algorithms for multi-channel radio networks with a malicious adversary. In a multi-channel network, each of the n processes in the system must choose, in each round, one of the c channels of the system on which to participate. Assuming the adversary can disrupt one channel per round, preventing communication on that channel, we establish a tight bound of $\max\left(\Theta\left(\frac{(1-\epsilon)n}{c-1} + \log_c{n}\right), \Theta\left(\frac{n(1-\epsilon)}{\epsilon c^2}\right)\right)$ on the number of rounds needed to solve the ε-gossip problem, a parameterized generalization of the all-to-all gossip problem that requires (1 − ε)n of the "rumors" to be successfully disseminated. Underlying our lower bound proof lies an interesting connection between ε-gossip and extremal graph theory. Specifically, we make use of Turán's theorem, a seminal result in extremal combinatorics, to reason about an adversary's optimal strategy for disrupting an algorithm of a given duration. We then show how to generalize our upper bound to cope with an adversary that can simultaneously disrupt t < c channels. Our generalization makes use of selectors: a combinatorial tool that guarantees that any subset of processes will be "selected" by some set in the selector. We prove this generalized algorithm optimal if a maximum number of values is to be gossiped. We conclude by extending our algorithm to tolerate traditional Byzantine corruption faults. [ABSTRACT FROM AUTHOR]

Distributed storage algorithms implement the abstraction of a shared register over distributed base objects. We study a specific class of storage algorithms, which we call amnesic: these have the pragmatic property that old values written in the implemented register might be eventually forgotten, i.e., they are not permanently kept in the storage and might be overwritten in the base objects by more recent values. This paper precisely captures this property and argues that most storage algorithms are amnesic. We establish a fundamental impossibility of an amnesic storage algorithm to implement a robust register abstraction over a set of base objects of which at least one can fail arbitrarily, even if only in a responsive manner, unless readers are allowed to write to the base objects. Our impossibility helps justify the assumptions made by practical robust storage algorithms. We also derive from this impossibility the first sharp distinction between safe and regular registers. Namely, we show that, if readers do not write, then no amnesic algorithm can implement a regular register using safe registers. [ABSTRACT FROM AUTHOR]

We give a distributed approximation algorithm for the vertex-packing problem in unit-disk graphs. Given a graph H, the algorithm finds in a unit-disk graph G a collection of pairwise disjoint copies of H of size which is approximately equal to the packing number of H in G. The algorithm is deterministic and runs in a poly-logarithmic number of rounds in the message passing model. [ABSTRACT FROM AUTHOR]

In this paper, we propose the partition approach and define several new classes of partitioned failure detectors weaker than existing failure detectors for the k-set agreement problem in both the shared-memory model and the message-passing model. In the shared-memory model with n + 1 processes, for any 2 ≤ k ≤ n, we first propose a partitioned failure detector ΠΩk that solves k-set agreement with shared read/write registers and is strictly weaker than Ωk, which was conjectured to be the weakest failure detector for k-set agreement in the shared-memory model [19]. We then propose a series of partitioned failure detectors that can solve n-set agreement, yet they are strictly weaker than Υ [10], the weakest failure detector ever found before our work to circumvent any asynchronous impossible problems in the shared-memory model. We also define two new families of partitioned failure detectors in the message-passing model that are strictly weaker than the existing ones for k-set agreement. Our results demonstrate that the partition approach opens a new dimension for weakening failure detectors related to set agreement, and it is an effective approach to check whether a failure detector is the weakest one or not for set agreement. So far, all previous candidates for the weakest failure detectors of set agreement have been disproved by the partitioned failure detectors. [ABSTRACT FROM AUTHOR]

We present the first optimally resilient, bounded, wait-free implementation of a distributed atomic register, tolerating Byzantine readers and (up to one-third of) Byzantine servers, without the use of unproven cryptographic primitives or requiring communication among servers. Unlike previous (non-optimal) solutions, the sizes of messages sent to writers depend only on the actual number of active readers and not on the total number of readers in the system. With a novel use of secret sharing techniques combined with write back throttling we present the first solution to tolerate Byzantine readers information theoretically, without the use of cryptographic techniques based on unproven number-theoretic assumptions. [ABSTRACT FROM AUTHOR]

The paper presents a deterministic distributed algorithm that given an n node unweighted graph constructs an O(n3/2) edge 3-spanner for it in O(logn) time. This algorithm is then extended into a deterministic algorithm for computing an O(kn1 + 1/k) edge O(k)-spanner in 2O(k)logk − 1n time for every integer parameter $k \geqslant 1$. This establishes that the problem of the deterministic construction of a linear (in k) stretch spanner with few edges can be solved in the distributed setting in polylogarithmic time. The paper also investigates the distributed construction of sparse spanners with almost pure additive stretch (1 + ε,β), i.e., such that the distance in the spanner is at most 1 + ε times the original distance plus β. It is shown, for every ε> 0, that in O(ε− 1logn) time one can deterministically construct a spanner with O(n3/2) edges that is both a 3-spanner and a (1 + ε,8logn)-spanner. Furthermore, it is shown that in $n^{O(1/\sqrt{\log n})} + O(1/\epsilon)$ time one can deterministically construct a spanner with O(n3/2) edges which is both a 3-spanner and a (1 + ε,4)-spanner. This algorithm can be transformed into a Las Vegas randomized algorithm with guarantees on the stretch and time, running in O(ε− 1 + logn) expected time. [ABSTRACT FROM AUTHOR]

A group of identical mobile agents moving asynchronously among the nodes of an anonymous network have to gather together in a single node of the graph. This problem known as the (asynchronous anonymous multi-agent) rendezvous problem has been studied extensively but only for networks that are safe or fault-free. In this paper, we consider the case when some of the edges in the network are dangerous or faulty such that any agent travelling along one of these edges would be destroyed. The objective is to minimize the number of agents that are destroyed and achieve rendezvous of all the surviving agents. We determine under what conditions this is possible and present algorithms for achieving rendezvous in such cases. Our algorithms are for arbitrary networks with an arbitrary number of dangerous channels; thus our model is a generalization of the case where all the dangerous channels lead to single node, called the Black Hole. We do not assume prior knowledge of the network topology; In fact, we show that knowledge of only a "tight" bound on the network size is sufficient for solving the problem, whenever it is solvable. [ABSTRACT FROM AUTHOR]

This paper presents an improved and time-optimal self-stabilizing algorithm for a major task in distributed computing- a rooted spanning tree construction. Our solution is decentralized ("truly distributed"), uses a bounded memory and is not based on the assumption that either n (the number of nodes), or diam (the actual diameter of the network), or an existence of cycles in the network are known. The algorithm assumes asynchronous and reliable FIFO message passing and unique identifiers, and works in dynamic networks and for any network topology. One of the previous time-optimal algorithms for this task was designed for a model with coarse-grained atomic operations and can be shown not to work properly for the totally asynchronous model (with just "read" or "receive" atomicity, and "write" or "send" atomicity). We revised the algorithm and proved it for a more realistic model of totally asynchronous networks. The state in the presented algorithm does not stabilize until long after the required output does. For such an algorithm, an increased asynchrony poses much increased hardness in the proof. [ABSTRACT FROM AUTHOR]

We introduce the problem of load-distance balancing in assigning users of a delay-sensitive networked application to servers. We model the service delay experienced by a user as a sum of a network-incurred delay, which depends on its network distance from the server, and a server-incurred delay, stemming from the load on the server. The problem is to minimize the maximum service delay among all users. We address the challenge of finding a near-optimal assignment in a scalable distributed manner. The key to achieving scalability is using local solutions, whereby each server only communicates with a few close servers. Note, however, that the attainable locality of a solution depends on the workload - when some area in the network is congested, obtaining a near-optimal cost may require offloading users to remote servers, whereas when the network load is uniform, a purely local assignment may suffice. We present algorithms that exploit the opportunity to provide a local solution when possible, and thus have communication costs and stabilization times that vary according to the network congestion. We evaluate our algorithms with a detailed simulation case study of their application in assigning hosts to Internet gateways in an urban wireless mesh network (WMN). [ABSTRACT FROM AUTHOR]

Distributed computing must adapt its techniques to networks of mobile agents. Indeed, we are facing new problems like the small size of memory and the lack of computational power. In this paper, we extend the results of Angluin et al (see [4,3,2,1]) by finding self-stabilizing algorithms to count the number of agents in the network. We focus on two different models of communication, with a fixed base station or with pairwise interactions. In both models we decide if there exist algorithms (probabilistic, deterministic, with k-fair adversary) to solve the self-stabilizing counting problem. [ABSTRACT FROM AUTHOR]

We present a model of a mobile ad-hoc network in which nodes can move arbitrarily on the plane with some bounded speed. We show that without any assumption on some topological stability, it is impossible to solve the geocast problem despite connectivity and no matter how slowly the nodes move. Even if each node maintains a stable connection with each of its neighbours for some period of time, it is impossible to solve geocast if nodes move too fast. Additionally, we give a tradeoff lower bound which shows that the faster the nodes can move, the more costly it would be to solve the geocast problem. Finally, for the one-dimensional case of the mobile ad-hoc network, we provide an algorithm for geocasting and we prove its correctness given exact bounds on the speed of movement. [ABSTRACT FROM AUTHOR]

We consider the problem of designing scalable and robust information systems based on multiple servers that can survive even massive denial-of-service (DoS) attacks. More precisely, we are focusing on designing a scalable distributed hash table (DHT) that is robust against so-called past insider attacks. In a past insider attack, an adversary knows everything about the system up to some time point t0 not known to the system. After t0, the adversary can attack the system with a massive DoS attack in which it can block a constant fraction of the servers of its choice. Yet, the system should be able to survive such an attack in a sense that for any set of lookup requests, one per non-blocked (i.e., non-DoS attacked) server, every lookup request to a data item that was last updated aftert0 can be served by the system, and processing all the requests just needs polylogarithmic time and work at every server. We show that such a system can be designed. [ABSTRACT FROM AUTHOR]

We describe and analyze a 3-state one-way population protocol for approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an initial configuration of x's, y's and blanks that contains at least one non-blank, the goal is for the agents to reach consensus on one of the values x or y. Additionally, the value chosen should be the majority non-blank initial value, provided it exceeds the minority by a sufficient margin. We prove that with high probability n agents reach consensus in O(n logn) interactions and the value chosen is the majority provided that its initial margin is at least $\omega(\sqrt{n \log n})$. This protocol has the additional property of tolerating Byzantine behavior in $o(\sqrt{n})$ of the agents, making it the first known population protocol that tolerates Byzantine agents. Turning to the register machine construction from [2], we apply the 3-state approximate majority protocol and other techniques to speed up the per-step parallel time overhead of the simulation from O(log4n) to O(log2n). To increase the robustness of the phase clock at the heart of the register machine, we describe a consensus version of the phase clock and present encouraging simulation results; its analysis remains an open problem. [ABSTRACT FROM AUTHOR]

We consider the task of waking up an anonymous ad hoc radio network from a single source, by a deterministic algorithm. In the beginning only the source is awake and has to wake up other nodes by disseminating messages throughout the network. Nodes of the network do not know its topology and they do not have distinct labels. In such networks some nodes are impossible to reach. A node in a network is accessible if it can be woken up by some (possibly network-dependent) deterministic algorithm. A deterministic wakeup algorithm for ad hoc networks is universal if it wakes up all accessible nodes in all networks. We study the question of the existence of such a universal wakeup algorithm. For synchronous communication we design a universal wakeup algorithm, and for asynchronous communication we show that no such algorithm exists. [ABSTRACT FROM AUTHOR]

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous tree network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given tree and given starting node we are interested in the fastest possible black hole search by two agents. For arbitrary trees we give a 5/3-approximation algorithm for this problem. We give optimal black hole search algorithms for two "extreme" classes of trees: the class of lines and the class of trees in which any internal node (including the root which is the starting node) has at least 2 children. Keywords: algorithm, black hole, mobile agent, tree. [ABSTRACT FROM AUTHOR]

Encryption is a fundamental building block for computer and communications technologies. Existing encryption methods depend for their security on unproven assumptions. We propose a new model, the Limited Access model for enabling a simple and practical provably unbreakable encryption scheme. A voluntary distributed network of thousands of computers each maintain and update random pages, and act as Page Server Nodes. A Sender and Receiver share a random key K. They use K to randomly select the same PSNs and download the same random pages. These are employed in groups of say 30 pages to extract One Time Pads common to S and R. Under reasonable assumptions of an Adversary's inability to monitor all PSNs, and easy ways for S and R to evade monitoring while downloading pages, Hyper Encryption is clearly unbreakable. The system has been completely implemented. [ABSTRACT FROM AUTHOR]

DISC 2006 marked the 20th anniversary of the DISC conferences. We list below the special events that took place during DISC 2006, together with some information and perspectives on the past and future of DISC. [ABSTRACT FROM AUTHOR]

We characterize Perfectly Secure Message Transmission (PSMT) between two nodes S and R in directed wire model, assuming that n wires are directed from S to R (also termed as top band) and u wires are directed from R to S (also termed as bottom band). A mixed adversary (tb, tf ) controls tb wires in Byzantine fashion and tf in fail-stop fashion among these u+n wires with unbounded computing power. S wishes to send a message m from a finite field $\mathbb{F}$ in a perfectly secure manner to R such that the adversary gets no information whatsoever on m, though he has unbounded computing power. Our characterization is the first ever characterization for PSMT considering mixed adversary and reveals more fault tolerance than the existing results [1]. Our protocols terminates in constant number of phases, performs polynomial computation and have polynomial communication complexity. [ABSTRACT FROM AUTHOR]

There is a proliferation of models for distributed computing, consisting of both shared memory and message passing paradigms. Different communities adopt different variants as the "standard" model for their research setting. Since subtle changes in the communication model can result in significant changes to the solvability/unsolvability or to the complexity of various problems, it becomes imperative to understand the relationships between the many models. The situation becomes even more complicated when additional requirements such as fault-tolerance are added to the mix. This motivates us to determine exactly under what circumstances a program designed for one model and delivering some set of additional guarantees can be converted into an "equivalent" programs for a different model while delivering comparable guarantees. Once these relationships are understood, they can be exploited in system design. [ABSTRACT FROM AUTHOR]

Distributed Greedy Coloring is an interesting and intuitive variation of the standard Coloring problem. It still consists in coloring in a distributed setting each node of a given graph in such a way that two adjacent nodes do not get the same color, but it adds a further constraint. Given an order among the colors, a coloring is said to be greedy if there does not exist a node for which its associated color can be replaced by a color of lower position in this order without violating the coloring property. We provide lower and upper bounds for this problem in Linial's model and we relate them to other well-known problems, namely Coloring, Maximal Independent Set (MIS), and Largest First Coloring. Whereas the best known upper bound for Coloring, MIS, and Greedy Coloring are the same, we prove a lower bound which is strong in the sense that it now makes a difference between Greedy Coloring and MIS. [ABSTRACT FROM AUTHOR]

In the deferred update technique for database replication, a number of database replicas are used to implement a single serializable database interface. Its main idea consists in executing all operations of a transaction initially on a single database replica. Transactions that do not change the database state can commit locally to the replica they executed, but other transactions must be globally certified and, if committed, have their update operations submitted to all replicas. Despite its wide use, we are not aware of any work that explored the inherent limitations and characteristics of deferred update database replication, ours being the first attempt in this direction. [ABSTRACT FROM AUTHOR]

In the standard message passing models it is assumed that the identity of a sender is known to the receiver. In practice, this often is not the case, due to impersonation attacks by malicious adversaries. Various impersonation attack schemes have been extensively investigated in the context of network security or cryptography, in particular for peep-to-peer and sensor networks [4,5]. Here, we study this problem in the context of distributed computing theory. [ABSTRACT FROM AUTHOR]

We describe a distributed algorithm for convex constrained optimization in networks without any consistent naming infrastructure. The algorithm produces an approximately feasible and near-optimal solution in time polynomial in the network size, the inverse of the permitted error, and a measure of curvature variation in the dual optimization problem. It blends, in a novel way, gossip-based information spreading, iterative gradient ascent, and the barrier method from the design of interior-point algorithms. [ABSTRACT FROM AUTHOR]

Fault-tolerant systems often require a means by which independent processes or processors can arrive at an exact mutual agreement of some kind. The work announced in this note studies the continuous consensus problem, which is a general tool for enabling actions that are performed at the same time at different sites of the system to be consistent with one another (e.g., mutual exlusion, firing squad etc). Suppose that we are interested in maintaining a simultaneously consistent view regarding a set of events E in the system. These are applicationdependent, but will typically record inputs that processes receive at various times, values that certain variables have at a given time, and faulty behavior in the form of failed or inconsistent message deliveries. A continuous consensus (CC) protocol maintains at all times k ≥ 0 a coreMi[k] of events of ε at every site i. In every run of this protocol the following three properties are required to hold, for all nonfaulty processes i and j. [ABSTRACT FROM AUTHOR]

This brief announcement focuses on interoperability of software transactions with ad hoc nonblocking algorithms. Specifically, we modify arbitrary nonblocking operations so that (1) they can be used both inside and outside transactions, (2) external uses serialize with transactions, and (3) internal uses succeed if and only if the surrounding transaction commits. Interoperability enables seemless integration with legacy code, atomic composition of nonblocking operations, and the equivalent of hand-optimized, closed nested transactions. [ABSTRACT FROM AUTHOR]

Recently, we challenged the belief that randomized Byzantine agreement protocols are inefficient, by designing, implementing and assessing the performance of a stack of protocols of that type [3]. That assessment lead us to a set of properties desirable for Byzantine asynchronous binary consensus protocols: (1) Strong validity . if all correct processes propose the same value v, the decision is v (values proposed by Byzantine processes are often useless); (2) Asynchrony . no time assumptions are made (systems are often prone to arbitrary delays); (3) Decentralization . there is no leader (leader elections have a great impact on performance); (4) Optimal resilience - n ≥ 3f +1 processes to tolerate f Byzantine (extra processes are costly); (5) Optimal message complexity . O(n2) (high impact on throughput); (6) Signature freedom (high impact of signatures based on public-key cryptography on the performance); (7) Early decision . in "nice" runs the protocol should decide in a few communication steps (good latency in the "normal" case). [ABSTRACT FROM AUTHOR]

In many large-scale distributed systems the users have only incomplete information about the system. We outline game theoretic approaches that are used to model such incomplete information settings. [ABSTRACT FROM AUTHOR]

After presenting a personal view of distributed computing (of course, being personal, this view is partial and questionable), this invited talk will address distributed computing problems that have recently received attention in the literature. For each of them, the talk presents the problem, results from the community, results from the author (and his co-authors), and questions that remain open. The following are among the topics covered in the talk. [ABSTRACT FROM AUTHOR]

As broadcasting is one of the primary functions in radio networks, fast algorithms for performing it are of considerable interest. A radio network consists of stations that can act at any a given time step either as transmitters or as receivers. Given a deployment of the stations, the reception conditions can be modeled by a graph, where the existence of an edge between two nodes indicates that transmissions of one of them can reach the other, i.e., these nodes can communicate directly. The message transmitted by a node in given time step is delivered in the same time step to all of its neighbors in the graph. A node acting as a receiver in a given step will successfully receive a message if and only if exactly one of its neighbors transmits in that step. If two or more neighbors of a node transmit simultaneously, then a collision occurs and none of the messages is heard by the node in that step. [ABSTRACT FROM AUTHOR]

I first became involved in Distributed Computing Theory around 1978 or 1979, as a new professor at Georgia Tech. Looking back at my first few years in the field, approximately 1979-1982, I see that they were tremendously exciting, productive, and fun. I collaborated with, and learned from, many leaders of the field, including Mike Fischer, Jim Burns, Michael Merritt, Gary Peterson, Danny Dolev, and Leslie Lamport. Results that emerged during that time included space lower bounds for mutual exclusion; definition of the k-exclusion problem, with associated lower bounds and algorithms; the Burns-Lynch lower bound on the number of registers needed for mutual exclusion; fast network-wide resource allocation algorithms; the Lynch-Fischer semantic model for distributed systems (a precursor to I/O automata); early work on proof techniques for distributed algorithms; lower bounds on the number of rounds for Byzantine agreement; definition of the approximate agreement problem and associated algorithms; and finally, the Fischer-Lynch-Paterson impossibility result for consensus. In this talk, I will review this early work, trying to explain how we were thinking at the time, and how the ideas in these projects influenced later work. [ABSTRACT FROM AUTHOR]

A guided tour through the labyrinth of my thoughts, from the Bakery Algorithm to arbiter-free marked graphs. This exercise in egotism is by invitation of the DISC 20th Anniversary Committee. I take no responsibility for the choice of topic. [ABSTRACT FROM AUTHOR]