We consider the problems of online and stochastic packet queueing in a distributed system of n nodes with queues, where the communication between the nodes is done via a multiple access channel. In the online setting, in each round, an arbitrary number of packets can be injected to nodes’ queues. Two measures of performance are considered: the total number of packets in all queues, called the total load , and the maximum queue size, called the maximum load . We develop a deterministic distributed algorithm that is asymptotically optimal with respect to both complexity measures, in a competitive way. More precisely, the total load of our algorithm is bigger than the total load of any other algorithm, including centralized online solutions, by only an additive term of O ( n 2 ), whereas the maximum queue size of our algorithm is at most n times bigger than the maximum queue size of any other algorithm, with an extra additive O ( n ). The optimality for both measures is justified by proving the corresponding lower bounds, which also separates nearly exponentially distributed solutions from the centralized ones. Next, we show that our algorithm is also stochastically stable for any expected injection rate smaller or equal to 1. This is the first solution to the stochastic queueing problem on a multiple access channel that achieves such stability for the (highest possible) rate equal to 1.

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, n processes execute a concurrent program that occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource (also called a critical section), in such a way that at any time, there is at most one process accessing it. In our considerations, the shared resource is the shared communication channel itself (multiple access channel), and the main challenge arises because the channel is also the only mean of communication between these processes. We consider both the classic and a slightly weaker version of mutual exclusion, called $$\varepsilon $$ -mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most $$\varepsilon $$ . We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while the $$\varepsilon $$ -mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker $$\varepsilon $$ -exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.

Decentralized monitoring and alarming systems can be an attractive alternative to centralized architectures. Distributed sensor nodes (e.g., in the smart grid's distribution network) are closer to an observed event than a global and remote observer or controller. This improves the visibility and response time of the system. Moreover, in a distributed system, local problems may also be handled locally and without overloading the communication network. This paper studies alarming from a distributed computing perspective and for two fundamentally different scenarios: on-duty and off-duty. We model the alarming system as a sensor network consisting of a set of distributed nodes performing local measurements to sense events. In order to avoid false alarms, the sensor nodes cooperate and only escalate an event (i.e., raise an alarm) if the number of sensor nodes sensing an event exceeds a certain threshold. In the on-duty scenario, nodes not affected by the event can actively help in the communication process, while in the off-duty scenario, non-event nodes are inactive. We present and analyze algorithms that minimize the reaction time of the monitoring system while avoiding unnecessary message transmissions. We investigate time and message complexity tradeoffs in different settings, and also shed light on the optimality of our algorithms by deriving cost lower bounds for distributed alarming systems.

Request balancing is an important issue in P2P networks, as requests or accesses are typically not distributed evenly among the items. Some of the items may account for a large ratio of the overall requests, e.g., in case of extremely popular videos. In this paper, we present a combination of two approaches to overcome an uneven request distribution even if there is highly skewed traffic. These approaches, in combination with a new local routing scheme on the skewCCC network, are able to balance a skewCCC network by a factor of O(logN) faster than commonly used load balancing schemes.

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, $n$ processes perform a concurrent program which occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource in such a way that in any time there is at most one process accessing it. We consider both the classic and a slightly weaker version of mutual exclusion, called $\ep$-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most $\ep$. We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while $\ep$-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker $\ep$-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.

Peer-to-peer overlay networks have proven their efficiency for storing and retrieving data at large scale, but new services are required to take the actual performances of resources into account. In this paper, we describe a fully decentralized algorithm, called "dating service" meant to organize communications in a fully heterogeneous network, that ensures that communication capabilities of the nodes are not exceeded. We prove that with high probability, this service ensures that a constant fraction of all possible communications is organized. Interestingly enough, this property holds true even if a node is not able to choose another node uniformly at random. In particular, the dating service can be implemented over existing DHT-based systems. In order to illustrate the expressiveness and the usefulness of proposed service, we also present a possible practical application of the dating service. As an illustration, we propose an algorithm for rumor spreading that enables to broadcast a unit-size message to all the nodes of a P2P system in logarithmic number of steps with high probability.

Page migration is one of the fundamental subproblems in the framework of data management in networks. It occurs in a distributed network of processors sharing one indivisible memory page of size D, which is stored in one of the processors. During runtime, processors access unit size data items from the page, and the system is allowed to move the page from one processor to another in order to minimize the total communication cost.This problem was considered in the online setting numerous times by many researchers, and some online algorithms were proven to achieve a cost within a constant factor of the optimal offline solution. However, all results were achieved under the assumption that the communication costs between processors were fixed during the execution of the whole process.In this paper we consider a model in which the communication costs can change in each time step, but the pace of the changes is restricted. This is typical in mobile networks, and also models the dynamics of networks that are not exclusively dedicated to the page migration.If both changes of the network and the request sequence are given by some adversarial entity, we prove a tight bound on the competitive ratio of the problem. However, the size of this ratio motivates us to assume that the changes of communication costs are modeled by some stochastic process, and an adversary dictates only which processor issues a request. To analyze such a hybrid case, we introduce the notion of expected competitive ratio and prove that, for the case where constant number of processors perform a random walk on a torus or on a mesh of diameter √D, it is O(log2D).

In a (randomized) oblivious routing scheme the path chosen for a request between a source s and a target t is independent from the current traffic in the network. Hence, such a scheme consists of probability distributions over s-t paths for every source-target pair s,t in the network.In a recent result [11] it was shown that for any undirected network there is an oblivious routing scheme that achieves a polylogarithmic competitive ratio with respect to congestion. Subsequently, Azar et al. [4] gave a polynomial time algorithm that for a given network constructs the best oblivious routing scheme, i.e. the scheme that guarantees the best possible competitive ratio. Unfortunately, the latter result is based on the Ellipsoid algorithm; hence it is unpractical for large networks.In this paper we present a combinatorial algorithm for constructing an oblivious routing scheme that guarantees a competitive ratio of O(log4n) for undirected networks. Furthermore, our approach yields a proof for the existence of an oblivious routing scheme with competitive ratio O(log3n), which is much simpler than the original proof from [11].