Catálogo de publicaciones - libros

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

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 or as . 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 occurs and none of the messages is heard by the node in that step.

After presenting a 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.

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.

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 ’s, ’s and blanks that contains at least one non-blank, the goal is for the agents to reach consensus on one of the values or . 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 agents reach consensus in ( log) interactions and the value chosen is the majority provided that its initial margin is at least . This protocol has the additional property of tolerating Byzantine behavior in 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 (log) to (log). 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.

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 about the system up to some time point not known to the system. After , 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 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 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.

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.

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.

We introduce the problem of 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 solutions, whereby each server only communicates with a few close servers. Note, however, that the attainable locality of a solution depends on the – 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).

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 based on the assumption that either (the number of nodes), or (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.