Search

We study network coordination problems, as captured by the setting of generalized network design (Emek et al., STOC 2018), in the face of uncertainty resulting from partial information that the network users hold regarding the actions of their peers. This uncertainty is formalized using Alon et al.'s Bayesian ignorance framework (TCS 2012). While the approach of Alon et al. is purely combinatorial, the current paper takes into account computational considerations: Our main technical contribution is the development of (strongly) polynomial time algorithms for local decision making in the face of Bayesian uncertainty., Comment: 25 pages, 0 figure. An extended abstract of this paper is to appear in the 27th Annual European Symposium on Algorithms (ESA 2019)

In a generalized network design (GND) problem, a set of resources are assigned to multiple communication requests. Each request contributes its weight to the resources it uses and the total load on a resource is then translated to the cost it incurs via a resource specific cost function. For example, a request may be to establish a virtual circuit, thus contributing to the load on each edge in the circuit. Motivated by energy efficiency applications, recently, there is a growing interest in GND using cost functions that exhibit (dis)economies of scale ((D)oS), namely, cost functions that appear subadditive for small loads and superadditive for larger loads. The current paper advances the existing literature on approximation algorithms for GND problems with (D)oS cost functions in various aspects: (1) we present a generic approximation framework that yields approximation results for a much wider family of requests in both directed and undirected graphs; (2) our framework allows for unrelated weights, thus providing the first non-trivial approximation for the problem of scheduling unrelated parallel machines with (D)oS cost functions; (3) our framework is fully combinatorial and runs in strongly polynomial time; (4) the family of (D)oS cost functions considered in the current paper is more general than the one considered in the existing literature, providing a more accurate abstraction for practical energy conservation scenarios; and (5) we obtain the first approximation ratio for GND with (D)oS cost functions that depends only on the parameters of the resources' technology and does not grow with the number of resources, the number of requests, or their weights. The design of our framework relies heavily on Roughgarden's smoothness toolbox (JACM 2015), thus demonstrating the possible usefulness of this toolbox in the area of approximation algorithms., Comment: 39 pages, 1 figure. An extended abstract of this paper is to appear in the 50th Annual ACM Symposium on the Theory of Computing (STOC 2018)

It was suggested that a programmable matter system (composed of multiple computationally weak mobile particles) should remain connected at all times since otherwise, reconnection is difficult and may be impossible. At the same time, it was not clear that allowing the system to disconnect carried a significant advantage in terms of time complexity. We demonstrate for a fundamental task, that of leader election, an algorithm where the system disconnects and then reconnects automatically in a non-trivial way (particles can move far away from their former neighbors and later reconnect to others). Moreover, the runtime of the temporarily disconnecting deterministic leader election algorithm is linear in the diameter. Hence, the disconnecting -- reconnecting algorithm is as fast as previous randomized algorithms. When comparing to previous deterministic algorithms, we note that some of the previous work assumed weaker schedulers. Still, the runtime of all the previous deterministic algorithms that did not assume special shapes of the particle system (shapes with no holes) was at least quadratic in $n$, where $n$ is the number of particles in the system. (Moreover, the new algorithm is even faster in some parameters than the deterministic algorithms that did assume special initial shapes.) Since leader election is an important module in algorithms for various other tasks, the presented algorithm can be useful for speeding up other algorithms under the assumption of a strong scheduler. This leaves open the question: "can a deterministic algorithm be as fast as the randomized ones also under weaker schedulers?", PODC 2021

To find a maximum number of communication requests that can be satisfied concurrently, is a fundamental network scheduling problem. In this work we investigate the problem of finding a maximum number of multicast requests that can be scheduled simultaneously in a tree network in which the edges and links have heterogeneous bandwidth limitations.This problem generalizes two problems studied in the literature: maximum k-colorable subgraph in chordal graphs, maximum multi-commodity flow in trees. The problem is NP-hard and admits a 1.585-approximation in the special case of homogeneous bandwidth limitations.We first show that the problem is harder to approximate when the bandwidth limitations are heterogeneous, i.e. vary from link to link and from node to node. We then generalize of a classical algorithm and obtain an M-approximation where M is the maximum number of leaves of the communication subtrees. Surprisingly, variants of the same algorithm, are used in the literature at least four times to solve related problems. There exists a polynomial-time algorithm for the special case of unicast requests and star topology. We generalize this result and relax the second requirement so that the set of unicast requests share a common vertex with no restriction on the tree topology.

Self-stabilizing algorithms recover from sever faults, such as inconsistent initialization. Traditionally, when designing a self-stabilizing message-passing algorithm, the main goal was to reduce the time until stabilization. The message cost was neglected. In this work, we strive to reduce the number of messages sent on the average per time period. As a tool, we present a stabilizing module that can message-efficiently determine when a task (from a wide family of tasks) is terminated. False positive detection is possible, but only when faults occurred. This module can then be used in the transformation of non self-stabilizing algorithms into self-stabilizing ones.

A new \emph{spanner} construction algorithm is presented, working under the \emph{LOCAL} model with unique edge IDs. Given an $n$-node communication graph, a spanner with a constant stretch and $O (n^{1 + \varepsilon})$ edges (for an arbitrarily small constant $\varepsilon > 0$) is constructed in a constant number of rounds sending $O (n^{1 + \varepsilon})$ messages whp. Consequently, we conclude that every $t$-round LOCAL algorithm can be transformed into an $O (t)$-round LOCAL algorithm that sends $O (t \cdot n^{1 + \varepsilon})$ messages whp. This improves upon all previous message-reduction schemes for LOCAL algorithms that incur a $\log^{\Omega (1)} n$ blow-up of the round complexity., Comment: Appeared at International Symposium on Distributed Computing (DISC) 2019

This study was carried in the context of the development of technologies for a cloud that uses an optical network for internal communication. The problem addressed in this paper deals with dispatching jobs - units of work, to be performed by machines on the cloud. Sending (or migrating) a job to a machine involves establishing a lightpath (a la circuit switching); this incurs a significant setup cost, but while it exists, the lightpath's capacity is very high. Hence, moving one job is about as expensive as moving a set of jobs over the same lightpath. Our goal is to develop online network dispatching algorithms for a work conserving job scheduling. That is, consider a set of jobs the dispatcher is responsible for their executions on some set $S_{M}$ of machines. Any machine in the network may join or (when not executing a job) leave $S_{M}$ according to decisions made outside the scope of this paper. Whenever a machine joins the set or is in the set and has just finished executing a job, it issues a request for a new job to perform and the dispatcher must send this machine a job that has not been executed yet (if such exists). Every machine can perform any of the jobs, and each job is performed on a single machine. The main algorithmic challenge in this context boils down to the following questions: How many jobs should we send to a requesting machine (or to some intermediate storage to be distributed from there)? From the storage on which machine should these jobs be taken? The algorithms developed here are shown to be efficient in reducing the costs of establishing lightpaths. As opposed to related algorithms for delivering consumable resources (in other contexts), we prove that our online algorithms are fully competitive. We present randomized online algorithms for two different settings: in the first it is assumed that each message requires establishing a lightpath and thus, incurs a setup cost; in the second, we distinguish between messages that carry job sets and small control messages sent by the algorithm, where the latter type of messages is assumed to be sent over a designated (non-optical) control plane at a negligible cost. Our algorithms are quite simple, though the analysis turns out to be rather involved. They are designed (and rigorously analyzed) for a general architecture, but would be especially efficient in fat tree architectures - the common choice in many data centers.

The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. We consider two problems in this model: (Δ+l)-vertex coloring and maximal independent set (MIS), for a network of unknown size $n$ and unknown maximum degree Δ. Solving these problems allows to overcome communication interferences, and to break symmetry, a core component of many distributed protocols. The presented results apply to general graphs, but are efficient in graphs with low edge density (sparse graphs), such as bounded degree graphs, planar graphs and graphs of bounded arboricity. We present O(Δ2 log n + Δ3) time deterministic uniform MIS and coloring protocols, which are asymptotically time optimal for bounded degree graphs. Furthermore, we devise O(a2 log2 n+a3log n) time MIS and coloring protocols, as well as O(a2 Δ 2 log2 n + a3 Δ 3 log n) time 2-hop MIS and 2-hop coloring protocols, where $a$ is the arboricity of the communication graph. Building upon the 2-hop coloring protocols, we show how the strong CONGEST model can be simulated and by using this simulation we obtain an O ( $a$ ) -coloring protocol. No results about coloring with less than Δ + 1 colors were known up to now in the beeping model.

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most “obvious” complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of Ω( m ) messages, where m is the number of edges in the network, and Ω( D ) time, where D is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even Ω( n ), where n is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that D and n were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every D , m , and n , and hold even if D , m , and n are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an O ( m ) messages algorithm. An O ( D ) time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an Ω( m ) message lower bound for randomized broadcast algorithms. An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

This paper investigates the message complexity of distributed information spreading in adversarial dynamic networks. While distributed computations in dynamic networks have been studied intensively over the last years, almost all of the existing work solely focuses on the time complexity of distributed algorithms. In information spreading, the goal is to spread k tokens of information to every node on an n-node network. We consider the amortized (average) message complexity of spreading a token, assuming that the number of tokens is large. In a static network, this basic problem can be solved using (asymptotically optimal) O(n) amortized messages per token. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. We present two sets of results depending on how nodes send messages to their neighbors: 1. Local broadcast: We show a tight lower bound of Ω(n^2) on the number of amortized local broadcasts, which is matched by the naive flooding algorithm. The lower bound holds for randomized algorithms against a strongly adaptive adversary. 2. Unicast: We study the message complexity as a function of the number of dynamic changes in the network. To facilitate this, we introduce adversary-competitive message complexity as a natural complexity measure for analyzing dynamic networks: The adversary pays a unit cost for every topological change and the message cost of an algorithm is determined as the actual number of messages sent minus the total cost of the adversary. Under this model, we give a deterministic algorithm that obtains an optimal amortized message complexity of O(n) if the number of tokens k is sufficiently large. We also present a randomized algorithm that achieves subquadratic amortized message complexity for much smaller k under an oblivious adversary.

“Stable marriage” refers to a particular matching with constraints having a wide variety of applications in different domains (two-sided markets, Cloud computing, college admissions, etc.). Most of the studies on this problem performed up to now were for centralized and synchronous settings assuming initialization. We consider a distributed and asynchronous context, without initialization (i.e., in a self-stabilizing manner, tolerating any transient fault) and with some confidentiality requirements. The single already known self-stabilizing solution in Laveau et al. (SSS’ 2017), based on Ackerman et al.’s algorithm (SICOMP’ 2011), stabilizes in \(O(n^4)\) moves (activation of a single node). We improve on this previous result considerably by presenting a solution with \(O(n^2)\) steps, relying on the idea of Gale and Shapley’s algorithm (AMM 1962), which takes also \(O(n^2)\) moves, but in a centralized synchronous context. Moreover it is not self-sabilizing solution and a corruption cannot be repaired locally, as noticed by Knuth (1976).

By presenting a message-efficient snap-stabilizing quiescence detection algorithm, we also facilitate a transformer that converts non self-stabilizing algorithms into self-stabilizing ones. We propose a message-efficient snap-stabilizing ongoing quiescence detection algorithm. (Notice that by definition it is also self-stabilizing and can detect termination.) This algorithm works for diffusing computations. We are not aware of any other self-stabilizing or snap-stabilizing ongoing quiescence or termination detection algorithm.

Developing self-stabilizing solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an automatic transformer for algorithms in an extended population protocol model . Population protocols is a model that was introduced recently for networks with a large number of resource-limited mobile agents. We use a variant of this model. First, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication “speed”, which is reflected by their cover times . Second, we assume the existence of a special agent with an unbounded memory, the base station . The automatic transformer takes as an input an algorithm solving a static problem (and meeting some additional rather natural requirements) and outputs a self-stabilizing algorithm for the same problem. The transformer is built using a re-execution approach (the technique consisting of executing an algorithm repeatedly in order to obtain its self-stabilizing version). We show that in the model we use, a transformer based on such an approach is impossible without the assumption of an unbounded memory agent.

We initiate the study of error confinement in distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior, and only temporarily. The external behavior of all other nodes must remain impeccable, even though their internal state may be affected. Error confinement is impossible if an adversary is allowed to inflict arbitrary transient faults on the system, since the faults might completely wipe out input values. We introduce a new fault tolerance measure we call agility, which quantifies the strength of an algorithm that disseminate information, against state corrupting faults.We study the basic problem of broadcast, and propose algorithms that guarantee error confinement with optimal agility to within a constant factor, even in asynchronous networks when the topology is unknown. These algorithms can serve as building blocks in more general reactive systems. Previous results in exploring locality in reactive systems were not error confined, and relied on the assumption (not used in current paper) that the errors hitting each node are probabilistic, such that a faulty node itself, or its neighbor, can detect the node faulty.The main algorithm uses the novel core bootstrapping technique, that seems inherent for voting in reactive networks; its analysis leads to an interesting combinatorial problem. The technique and the analysis may be of independent interest

Shared counters are among the most basic coordination structures in distributed computing. Known implementations of shared counters are either blocking, non-linearizable, or have a sequential bottleneck. We present the first counter algorithm that is both linearizable, non-blocking, and can provably achieve high throughput in k-synchronous executions—executions in which process speeds vary by at most a constant factor k. The algorithm is based on a novel variation of the software combining paradigm that we call bounded-wait combining (BWC). It can thus be used to obtain implementations, possessing the same properties, of any object that supports combinable operations, such as a stack or a queue. Unlike previous combining algorithms where processes may have to wait for each other indefinitely, in the BWC algorithm, a process only waits for other processes for a bounded period of time and then “takes destiny in its own hands”. In order to reason rigorously about the parallelism attainable by our algorithm, we define a novel metric for measuring the throughput of shared objects, which we believe is interesting in its own right. We use this metric to prove that our algorithm achieves throughput of Ω(N/ log N) in k-synchronous executions, where N is the number of processes that can participate in the algorithm. Our algorithm uses two tools that we believe may prove useful for obtaining highly parallel non-blocking implementation of additional objects. The first are “synchronous locks”, locks that are respected by processes only in k-synchronous executions and are disregarded otherwise; the second are “pseduo-transactions”—a weakening of regular transactions that allows higher parallelism.

In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The amortized (on the number of topological changes) message complexity is O ( V ), where V is the number of nodes in the network. The message size used by the algorithm is O (log |ID|) where |ID| is the size of the name space of the nodes. Typically, log |ID| = O (log V ). Previous algorithms that adapt to dynamic networks involved Ω ( E ) messages per topological change—inherently paying for re-computation of the tree from scratch. Spanning trees are essential components in many distributed algorithms. Some examples include broadcast (dissemination of messages to all network nodes), multicast, reset (general adaptation of static algorithms to dynamic networks), routing, termination detection , and more. Thus, our efficient maintenance of a spanning tree implies the improvement of algorithms for these tasks. Our results are obtained using a novel technique to save communication. A node uses information received in the past in order to deduce present information from the fact that certain messages were NOT sent by the node's neighbor. This technique is one of our main contributions.

" How well connected is the network? " This is one of the most fundamental questions one would ask when facing the challenge of designing a communication network. Three major notions of connectivity have been considered in the literature, but in the context of traditional (single-layer) networks, they turn out to be equivalent. This paper introduces a model for studying the three notions of connectivity in multi-layer networks. Using this model, it is easy to demonstrate that in multi-layer networks the three notions may differ dramatically. Unfortunately, in contrast to the single-layer case, where the values of the three connectivity notions can be computed efficiently, it has been recently shown in the context of WDM networks (results that can be easily translated to our model) that the values of two of these notions of connectivity are hard to compute or even approximate in multi-layer networks. The current paper shed some positive light into the multi-layer connectivity topic: we show that the value of the third connectivity notion can be computed in polynomial time and develop an approximation for the construction of well connected overlay networks., Comment: Structural Information and Communication Complexity - 19th International Colloquium, 2012, Jun 2012, Reykjavik, Iceland. 2015

A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local "pulse counter" that simulates the global clock in a synchronous network. In this paper, we present a time-optimal self-stabilizing scheme for such a synchronizer, assuming unbounded counters. We give a simple rule by which each node can compute its pulse number as a function of its neighbors' pulse numbers. We also show that some of the popular correction functions for phase clock synchronization are not self-stabilizing in asynchronous networks. Using our rule, the counters stabilize in time bounded by the diameter of the network, without invoking global operations. We argue that the use of unbounded counters can be justified by the availability of memory for counters that are large enough to be practically unbounded and by the existence of reset protocols that can be used to restart the counters in some rare cases where faults will make this necessary.

The resource discovery problem arises in the context of peer to peer (P2P) networks, where at any point of time a peer may be placed at or removed from any location over a general purpose network (e.g., an Internet site). A node (peer) can communicate with another node directly if and only if it knows a certain routing information to that other node. Hence, a critical task is for the peers to convey this routing information to each other. The problem was formalized by Harchol-Balter et al. and the specific P2P application they had in mind was the logical networks G0 of servers placed by Akamai at various Internet sites. The routing information needed for a node to reach another peer is that peer's identifier (e.g., IP address). A logical directed edge represents the fact that the peer at the tail of the edge knows the IP address of the one at its head. The problem is to compute the connected components in the underlying graph of G0 (namely, the undirected graph obtained from G0 by removing edge directionality). A number of algorithms were developed in Harchol-Balter et al. for this problem in the model of a synchronous network over a weakly connected directed graph. That is, the assumption was that some clock delivers pulses to every node every time unit at the same time, and a message delivery takes one time unit. The best of these algorithms was randomized. Subsequently, a deterministic algorithm for the problem on synchronous networks with improved complexity was presented in a paper by Kutten et al. The current paper extends the deterministic algorithm of Kutten et al. to the environment of asynchronous networks, where no clock pulses are assumed, and the message delivery time may vary and is not known. We managed to maintain complexities similar to those of the synchronous algorithm of Kutten et al. (translated to the asynchronous model). These are lower than the complexities that would be needed to synchronize the system. The main technical difficulty in a directed, weakly connected system is to ensure that nodes take steps that are consistent with each other, even if their knowledge about each other is not symmetric. Here, this task is further complicated by the fact that there is no timeout mechanism (which does exist in synchronous systems) to assist in ensuring consistency. In particular, as opposed to the case in synchronous systems, an asynchronous algorithm cannot first transform every directed edge to be bidirectional and second, apply an algorithm for bidirectional graph. Thus, our result takes another step towards representing the actual setting in a realistic manner.

International audience; This paper demonstrates the usefulness of distributed local verification of proofs, as a tool for the design of self-stabilizing algorithms.In particular, it introduces a somewhat generalized notion of distributed local proofs, and utilizes it for improving the time complexity significantly, while maintaining space optimality. As a result, we show that optimizing the memory size carries at most a small cost in terms of time, in the context of Minimum Spanning Tree (MST). That is, we present algorithms that are both time and space efficient for both constructing an MST and for verifying it.This involves several parts that may be considered contributions in themselves.First, we generalize the notion of local proofs, trading off the time complexity for memory efficiency. This adds a dimension to the study of distributed local proofs, which has been gaining attention recently. Specifically, we design a (self-stabilizing) proof labeling scheme which is memory optimal (i.e., $O(\log n)$ bits per node), and whose time complexity is $O(\log ^2 n)$ in synchronous networks, or $O(\Delta \log ^3 n)$ time in asynchronous ones, where $\Delta$ is the maximum degree of nodes. This answers an open problem posed by Awerbuch and Varghese (FOCS 1991). We also show that $\Omega(\log n)$ time is necessary, even in synchronous networks. Another property is that if $f$ faults occurred, then, within the requireddetection time above, they are detected by some node in the $O(f\log n)$ locality of each of the faults.Second, we show how to enhance a known transformer that makes input/output algorithms self-stabilizing. It now takes as input an efficient construction algorithm and an efficient self-stabilizing proof labeling scheme, and produces an efficient self-stabilizing algorithm. When used for MST, the transformer produces a memory optimal self-stabilizing algorithm, whose time complexity, namely, $O(n)$, is significantly better even than that of previous algorithms. (The time complexity of previous MST algorithms that used $\Omega(\log^2 n)$ memory bits per node was $O(n^2)$, and the time for optimal space algorithms was $O(n|E|)$.) Inherited from our proof labelling scheme, our self-stabilising MST construction algorithm also has the following two properties: (1) if faults occur after the construction ended, then they are detected by some nodes within $O(\log ^2 n)$ time in synchronous networks, or within $O(\Delta \log ^3 n)$ time in asynchronous ones, and (2) if $f$ faults occurred, then, within the required detection time above, they are detected within the $O(f\log n)$ locality of each of the faults. We also show how to improve the above two properties, at the expense of some increase in the memory.

Multicast services, assisted by special hardware, are being considered as a part of high-speed wide-area networks (WANs) in order to support new generations of multiuser applications. This paper describes an application multicast service for high-speed WANs which is capable of exploiting multicast hardware. Indeed, this research was conducted in context of the spanning tree hardware structure of PARIS and of plaNET, the pioneering broadband experimental networks that predated ATM. The results of this research were also included in IBM's ATM, called Networking BroadBand Services (NBBS).We achieve modularity and low cost by assigning to distinct components the separate problems of: 1) naming groups; 2) finding group members in a network; 3) configuring multicast hardware; and 4) delivering multicast messages in sequence. This modularity enables, for example, both the multicast to a group to which the user initiates the joining (formed by using 1 and 2 above), on one hand, and to groups computed by the source on the other hand. We give the overall organization of our service and then describe in detail the methods used to solve the first two of the subproblems.

In the CONGEST model, a communications network is an undirected graph whose $n$ nodes are processors and whose $m$ edges are the communications links between processors. At any given time step, a message of size $O(\log n)$ may be sent by each node to each of its neighbors. We show for the synchronous model: If all nodes start in the same round, and each node knows its ID and the ID's of its neighbors, or in the case of MST, the distinct weights of its incident edges and knows $n$, then there are Monte Carlo algorithms which succeed w.h.p. to determine a minimum spanning forest (MST) and a spanning forest (ST) using $O(n \log^2 n/\log\log n)$ messages for MST and $O(n \log n )$ messages for ST, resp. These results contradict the "folk theorem" noted in Awerbuch, et.al., JACM 1990 that the distributed construction of a broadcast tree requires $\Omega(m)$ messages. This lower bound has been shown there and in other papers for some CONGEST models; our protocol demonstrates the limits of these models. A dynamic distributed network is one which undergoes online edge insertions or deletions. We also show how to repair an MST or ST in a dynamic network with asynchronous communication. An edge deletion can be processed in $O(n\log n /\log \log n)$ expected messages in the MST, and $O(n)$ expected messages for the ST problem, while an edge insertion uses $O(n)$ messages in the worst case. We call this "impromptu" updating as we assume that between processing of edge updates there is no preprocessing or storage of additional information. Previous algorithms for this problem that use an amortized $o(m)$ messages per update require substantial preprocessing and additional local storage between updates.

We study the classical problem of assigning unique identifiers to identical concurrent processes. In this paper, we consider the asynchronous shared memory model, and the correctness requirement is that upon termination of the algorithm, the processes must have unique IDs always. Our results include tight characterization of the problem in several respects. We call a protocol solving this task Las Vegas if it has finite expected termination time. Our main positive result is the first Las-Vegas protocol that solves the problem. The protocol terminates in O(logn) expected asychronous rounds, using O(n) shared memory space, where n is the number of participating processes. The new protocol improves on all previous solutions simultaneously in running time (exponentially), probability of termination (to 1), and space requirement. The protocol works under the assumption that the asynchronous schedule is oblivious, i.e., independent of the actual unfolding execution. On the negative side, we show that there is no finite-state Las-Vegas protocol for the problem if the schedule may depend on the history of the shared memory (an adaptive schedule). We also show that any Las-Vegas protocol must know n in advance (which implies that crash faults cannot be tolerated) and that the running time is ?(logn). For the case of an arbitrary (nonoblivious) adversarial schedule, we present a Las-Vegas protocol that uses O(n) unbounded registers. For the read-modify-write model, we present a constant-space deterministic algorithm.

In most communication networks, pairs of processors communicate by sending messages over a path connecting them. We present communication-efficient protocols that quickly detect and locate any failure along the path. Whenever there is excessive delay in forwarding messages along the path, the protocols detect a failure (even when the delay is caused by maliciously programmed processors). The protocols ensure optimal time for either message delivery or failure detection. We observe that the actual delivery time $\delta$ of a message over a link is usually much smaller than the a priori known upper bound D on that delivery time. The main contribution of this paper is the way to model and take advantage of this observation. We introduce the notion of asynchronously early-terminating protocols, as well as protocols that are asynchronously early-terminating, i.e., time optimal in both worst case and typical cases. More precisely, we present a time complexity measure according to which one evaluates protocols both in terms of $D$ and $\delta$. We observe that asynchronously early termination is a form of competitiveness. The protocols presented here are asynchronously early terminating since they are time optimal both in terms of $D$ and of $\delta$. Previous communication-efficient solutions were slow in the case where $\delta \ll D$. We observe that this is the most typical case. It is suggested that the time complexity measure introduced, as well as the notion of asynchronously early-terminating, can be useful when evaluating protocols for other tasks in communication networks. The model introduced can be a useful step towards a formal analysis of real-time systems. Our protocols have O(n log n) worst-case communication complexity. We show that this is the best possible for protocols that send immediately any acknowledgment they ever send. Then we show an early-terminating protocol which uses timing and delay to reduce the communication complexity in the typical executions where the number of failures is small and $\delta \ll D$. In such executions, its message complexity is linear, as is the complexity of nonfault tolerant protocols.

Traditional broadcast protocols are inappropriate for the high-speed networks of the future. Such protocols are limited by the speed of software processing, which becomes a bottleneck as network speeds increase. This paper presents broadcast protocols that are appropriate for high-speed networks, and are tolerant of failures involving the loss of messages. The protocols are based primarily on the simple hardware functions present in a high-speed network node. This leads to message delivery at hardware speeds. In the unlikely event of a failure, software intervention is required to guarantee the timely termination of the protocol; however, this software processing does not interfere with message delivery.

As communication networks grow, existing fault handling tools that involveglobalmeasures such as global time-outs or reset procedures become increasingly unaffordable, since their cost grows with the size of the network. Rather, for a fault handling mechanism to scale to large networks, its cost must depend only on the number of failed nodes (which, thanks to today's technology, grows much more slowly than the networks). Moreover, it should allow the nonfaulty regions of the networks to continue their operation even during the recovery of the faulty parts. This paper introduces the conceptsfault localityandfault-locally mendableproblems, which are problems for which there are correction algorithms (applied after faults) whose cost depends only on the (unknown) number of faults. We show thatanyinput-output problem is fault-locally mendable. The solution involves a novel technique combining data structures and “local votes” among nodes, which may be of interest in itself.

This paper proposes algorithms for allocating wavelengths to connections (lightpaths) in optical wavelength division multiplexed networks, predominantly for ring topologies. A worst-case model is considered, where no blocking of lightpaths is allowed, and there are no assumptions made on the traffic arrival and holding times. The traffic is characterized only by its load L, which is the maximum number of lightpaths that can be present on any link, assuming no blocking. A dynamic traffic model is considered where requests to set up lightpaths arrive over time and, must be accommodated without rerouting existing lightpaths, and lightpaths may be terminated over time as well. For networks without wavelength conversion, we show that at least 0.5Llog/sub 2/N wavelengths are required by any dynamic algorithm for rings of N nodes and present an algorithm that uses at most Llog/sub 2/N+L wavelengths for rings and 2(L-1)log/sub 2/N for trees. We also study the worst-case behavior of the well-known first-fit algorithm, and show that it requires at most 2.52Llog/sub 2/N+5L wavelengths (small variants of these constants are proven as well). When limited wavelength conversion is allowed, we first show how to use expanders to insure no blocking in arbitrary topologies. Then, we present conversion patterns for rings with conversion degree d=2, which require Llog/sub 2/L+4L or 2Llog/sub 2/log/sub 2/L+4L wavelengths, thereby eliminating the dependence (that exists without wavelength conversion) between the number of wavelengths and N. We also consider different traffic models where lightpath setup requests arrive over time, but once set up, lightpaths are never taken down. For this model, the number of wavelengths needed is shown to be only max{0,L-d}+L for a conversion degree of d.

This work is concerned with the problem of broadcasting a large message efficiently when each processor has partial prior knowledge about the contents of the broadcast message. The partial information held by the processors might be out of date or otherwise erroneous, and consequently, different processors may hold conflicting information. Tight bounds are established for broadcast under such conditions, and applications of the broadcast protocol to other distributed computing problems are discussed.

We present algorithms for distributed verification and silent-stabilization of a DFS(Depth First Search) spanning tree of a connected network. Computing and maintaining such a DFS tree is an important task, e.g., for constructing efficient routing schemes. Our algorithm improves upon previous work in various ways. Comparable previous work has space and time complexities of O(nlogΔ) bits per node and O(nD) respectively, where Δ is the highest degree of a node, n is the number of nodes and D is the diameter of the network. In contrast, our algorithm has a space complexity of O(logn) bits per node, which is optimal for silent-stabilizing spanning trees and runs in O(n) time. In addition, our solution is modular since it utilizes the distributed verification algorithm as an independent subtask of the overall solution. It is possible to use the verification algorithm as a stand alone task or as a subtask in another algorithm. To demonstrate the simplicity of constructing efficient DFS algorithms using the modular approach, we also present a (non-silent) self-stabilizing DFS token circulation algorithm for general networks based on our silent-stabilizing DFS tree. The complexities of this token circulation algorithm are comparable to the known ones.

The difference between the speed of the actions of different processes is typically considered as an obstacle that makes the achievement of cooperative goals more difficult. In this work, we aim to highlight potential benefits of such asynchrony phenomena to tasks involving symmetry breaking. Specifically, in this paper, identical except for their speeds mobile agents are placed at arbitrary locations on a continuous cycle of length n and use their speed difference in order to rendezvous fast. We normalize the speed of the slower agent to be 1, and fix the speed of the faster agent to be some ci¾?>i¾?1. An agent does not know whether it is the slower agent or the faster one. The straightforward distributed-race DR algorithm is the one in which both agents simply start walking until rendezvous is achieved. It is easy to show that, in the worst case, the rendezvous time of DR is n/ci¾?-i¾?1. Note that in the interesting case, where c is very close to 1 e.g., ci¾?=i¾?1i¾?+i¾?1/n k , this bound becomes huge. Our first result is a lower bound showing that, up to a multiplicative factor of 2, this bound is unavoidable, even in a model that allows agents to leave arbitrary marks the white board model, even assuming sense of direction, and even assuming n and c are known to agents. That is, we show that under such assumptions, the rendezvous time of any algorithm is at least $\frac{n}{2c-1}$ if ci¾?≤i¾?3 and slightly larger specifically, $\frac{n}{c+1}$ if ci¾?>i¾?3. We then manage to construct an algorithm that precisely matches the lower bound for the case ci¾?≤i¾?2, and almost matches it when ci¾?>i¾?2. Moreover, our algorithm performs under weaker assumptions than those stated above, as it does not assume sense of direction, and it allows agents to leave only a single mark a pebble and only at the place where they start the execution. Finally, we investigate the setting in which no marks can be used at all, and show tight bounds for ci¾?≤i¾?2, and almost tight bounds for ci¾?>i¾?2.

A new paradigm for the design of self-stabilizing distributed algorithms, called local detection , is introduced. The essence of the paradigm is in defining a local condition based on the state of a processor and its immediate neighborhood such that the system is in a globally legal state if and only if the local condition is satisfied at all the nodes. In this work we also extend the model of self-stabilizing networks traditionally assuming memory failure to include the model of dynamic networks (assuming edge failures and recoveries). We apply the paradigm to the extended model which we call “dynamic self-stabilizing networks”. Without loss of generality, we present the results in the least restrictive shared memory model of read/write atomicity, to which end we construct basic information transfer primitives. Using local detection, we develop deterministic and randomized self-stabilizing algorithms that maintain a rooted spanning tree in a general network whose topology changes dynamically. The deterministic algorithm assumes unique identities while the randomized assumes an anonymous network. The algorithms use a constant number of memory words per edge in each node; and both the size of memory words and of messages is the number of bits necessary to represent a node identity (typically O (log n ) bits where n is the size of the network). These algorithms provide for the easy construction of self-stabilizing protocols for numerous tasks: reset, routing, topology-update and self-stabilization transformers that automatically self-stabilize existing protocols for which local detection conditions can be defined.

In this paper we study the problem of on-linecall controlin a communication network, namely, the problem of accepting or rejecting an incoming call (a request for a connection between two points in a network) without having the knowledge of future calls. The problem is a part of the more general problem of bandwidth allocation and management. Intuition suggests that knowledge of future call arrivals can be crucial to the performance of the system. In this paper, however, we present preemptive deterministic on-line call control algorithms. We use competitive analysis to measure their performance?i.e., we compare our algorithms to their off-line, clairvoyant counterparts?and prove optimality for some of them. We consider two specific networks, a line of nodes and a single edge, and investigate a variety of cases concerning thevalueof the calls. The value is accrued only if the call terminates successfully; otherwise?if the call is rejected, or prematurely terminated?no value is gained. The performance of the algorithm is then measured by the cumulative value achieved, when given a sequence of calls. The variety of call value criteria that we study?constant; proportional to the length of the call's route; proportional to its holding time?captures many of the natural cost assignments to network services.

Afek, Awerbuch, Plotkin, and Saks identified an important fundamental problem inherent to distributed networks, which they called the Resource Controller problem. Consider, first, the problem in which one node (called the "root") is required to estimate the number of events that occurred all over the network. This counting problem can be viewed as a useful variant of the heavily studied and used task of topology update (that deals with collecting all remote information). The Resource Controller problem generalizes the counting problem: such remote events are considered as requests, and the counting node, i.e., the "root", also issues permits for the requests. That way, the number of request granted can be controlled (bounded).An efficient Resource Controller was constructed in the paper by Afek et al., which can operate on a dynamic network assuming that the network is spanned by a tree that may only grow, and only by allowing leaves to join the tree. In contrast, the Resource Controller presented here can operate under a more general dynamic model, allowing the spanning tree of the network to undergo both insertions and deletions of both leaves and internal nodes. Despite the more dynamic network model we allow, the message complexity of our controller is always at most the message complexity of the more restricted controller.All the applications for the controller of Afek et al. apply also for our controller. Moreover, with the same message complexity, our controller can handle these applications under the more general dynamic model mentioned above. In particular, under the more general dynamic model, the new controller can be transformed into an efficient size-estimation protocol, i.e., a protocol allowing the root to maintain a constant estimation of the number of nodes in the dynamically changing network. Informally, the resulted new size-estimation protocol uses O(log2n) amortized message complexity per topological change (assuming that the number of changes in the network size is "not too small"), where n is the current number of nodes in the network. In addition, with the same message complexity (as that of the size-estimation protocol), the new controller can be used to solve the name-assignment problem by assigning and maintaining unique log n+O(1)-bit identifiers for the nodes of the dynamic network.The new size-estimation protocol can be used for other applications, not mentioned in the paper by Afek et al.. Specifically, it can be used to extend many existing labeling schemes supporting different queries (e.g routing, ancestry, etc.) so that these schemes can now operate correctly also under more general models. These extensions maintain the same asymptotic sizes of the corresponding labels (or routing tables) of the original schemes and incur only a relatively low extra additive cost to the message complexity of the corresponding original schemes.

This paper presents an improved and time-optimal selfstabilizing 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.

We study the problem of distributed verification in the mobile agent model. The problem of distributed verification in a network using local checking has been studied previously. In the local verification model, each node of the network must decide on a yes or no answer based on the knowledge of its immediate neighborhood and the global answer is obtained by a conjunction of the local answers. The efficiency of such a verification process is determined by the sizes of the proofs i.e. labels that must be assigned to the nodes to enable local verification of some global property. On the other hand, in the mobile agent model, verification is performed by an agent that is allowed to move from node to node of the graph, reading the labels of visited nodes in order to verify the required property. In this case, minimizing the memory of the agent is the primary objective. We study the space complexity of performing mobile verification in terms of memory of each agent as well as the number of agents required globally in networks of size n. In the case of a solitary agent, logarithmic memory is both necessary and sufficient for solving certain graph-based verification problems (even in the family of trees). For a team of at least two agents, the space complexity of most verification problems (including the well-studied MST verification) is reduced to O(loglogn), while a team of at least three agents even with constant size memory each, is sufficient to solve all graph-based verification problems. We also study the effect of randomization and show that one agent with O(loglogn) bits of memory and the ability to flip coins is as powerful as two deterministic agent having the similar memory limitations.

In a cognitive radio network, a Primary User PU may vacate a channel for intermissions of an unknown length. A substantial amount of research has been devoted to minimizing the disturbance a Secondary User SU may cause the PU. We take another step and optimize the throughput of an SU, even when assuming that the disturbance to the PU is indeed avoided using those other methods. We suggest new optimization parameters the lengths of SU packets. That is, the SU fills up the intermission with consecutive packets. Each packet is associated with some fixed overhead. Hence, using a larger number of smaller packets increases the overhead ratio for each SU packet. On the other hand, it reduces the loss of throughput the SU suffers with the loss of a packet in a collision at the end of the intermission. As opposed to previous studies, we optimize also the case where the distribution of the channel intermission is unknown. That is, we develop optimal competitive protocols. Those seek to minimize the ratio of the SU's profit compared to a hypothetical optimal algorithm that knows the intermission length in advance. We show how to compute the optimal present packets' sizes for the case that the distribution is known for a general distribution. Finally, we show several interesting properties of the optimal solutions for several popular distributions.

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) takes only \(O(\sqrt{n}\log^{3/2} n)\) messages to elect a unique leader (with high probability). This algorithm is then extended to solve leader election on any connected non-bipartite n-node graph G in O(τ(G)) time and \(O(\tau(G)\sqrt{n}\log^{3/2} n)\) messages, where τ(G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader election algorithms. Finally, an almost-tight lower bound is presented for randomized leader election, showing that \(\Omega(\sqrt n)\) messages are needed for any O(1) time leader election algorithm which succeeds with high probability. It is also shown that Ω(n 1/3) messages are needed by any leader election algorithm that succeeds with high probability, regardless of the number of the rounds. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

A control architecture for a high-speed packet-switched network is described. The architecture was designed and implemented as part of the PARIS (subsequently plaNET and BBNS) networking project at IBM. This high bandwidth network for integrated communication (data, voice, video) is currently operational as a laboratory prototype. It will also be deployed within the AURORA Testbed that is part of the NSF/DARPA gigabit networking program. The high bandwidth dictates the need for specialized hardware to support faster packet handling for both point-to-point and multicast connections. A faster and more efficient network control is also required in order to support the increased number of connections and their changing requirements with time. The new network control architecture presented exploits specialized hardware, thereby enabling tasks to be performed faster and with less computation overhead. In particular, since control information can be distributed quickly using hardware packet handling mechanisms, decisions can be made based upon more complete and accurate information. In some respects, this has the effect of having the benefits of centralized control (e.g., easier bandwidth resource allocation to connections), while retaining the fault tolerance and scalability of a distributed architecture. >

An essential function for achieving security in computer networks is reliable authentication of communicating parties and network components. Such authentication typically relies on exchanges of cryptographic messages between the involved parties, which in turn implies that these parties be able to acquire shared secret keys or certified public keys. Provision of authentication and key distribution functions in the primitive and resource-constrained environments of low-function networking mechanisms, portable, or wireless devices presents challenges in terms of resource usage, system management, ease of use, efficiency, and flexibility that are beyond the capabilities of previous designs such as Kerberos or X.509. This paper presents a family of light-weight authentication and key distribution protocols suitable for use in the low layers of network architectures. All the protocols are built around a common two-way authentication protocol. The paper argues that key distribution may require substantially different approaches in different network environments and shows that the proposed family of protocols offers a flexible palette of compatible solutions addressing many different networking scenarios. The mechanisms are minimal in cryptographic processing and message size, yet they are strong enough to meet the needs of secure key distribution for network entity authentication. The protocols presented have been implemented as part of comprehensive security subsystem prototype called KryptoKnight. >

The Dynamic Content Distribution problem addresses the trade-off between storage and delivery costs in modern virtual Content Delivery Networks (CDNs). That is, a video file can be stored in multiple places so that the request of each user is served from a location that is near by to the user. This minimizes the delivery costs, but is associated with a storage cost. This problem is NP-hard even in grid networks. In this paper, we present a constant factor approximation algorithm for grid networks. We also present an O(logδ)-competitive algorithm, where δ is the normalized diameter of the network, for general networks with general metrics. We show a matching lower bound by using a reduction from online undirected Steiner tree. Our algorithms use a rather intuitive approach that has an elegant representation in geometric terms.

Algorithms for the group testing problem when there is no a priori information on the number of defective items are considered. The efficiency criterion used is the competitive ratio, which is the ratio of the number of tests required by an algorithm when there is no a priori information on the number of defective items, to the number of tests required by an optimal algorithm when the number of defective items is known in advance. A new algorithm is presented, and it is shown that the competitive ratio of this algorithm is 2. This result is an improvement over a previous algorithm due to Du and Hwang (1990) the competitive ratio of which is 2.75. It also proves a conjecture made by Du and Hwang. A new application of group testing techniques for high-speed network is discussed.

This paper demonstrates the usefulness of distributed local verification of proofs, as a tool for the design of algorithms. In particular, it introduces a somewhat generalized notion of distributed local proofs, and utilizes it for improving the memory size complexity, while obtaining time efficiency too.As a result, we show that optimizing the memory size carries at most a small cost in terms of time, in the context of Minimum Spanning Tree (MST). That is, we present algorithms that are both time and space efficient for constructing an MST, for verifying it, and for detecting the location of the faults. This involves several steps that may be considered contributions in themselves.First, we generalize the notion of local proofs, trading off the locality (or, really, the time complexity) for memory efficiency. This adds a dimension to the study of distributed local proofs, that has been gaining attention recently.Second, as opposed to previous studies that presented only the labels verification part of a proof labeling schemes, we present here also a space and time efficient distributed self stabilizing marker algorithm to generates those labels. This presents proof labeling schemes as an algorithmic tool.Finally, we show how to enhance a known transformer that makes input/output algorithms self stabilizing. It now takes as input an efficient construction algorithm and an efficient self stabilizing proof labeling scheme, and produces an efficient self stabilizing algorithm.When used for MST, the transformer produces a memory optimal (i.e., O(log n) bits per node) self stabilizing algorithm, whose time complexity, namely, O(n), is significantly better even than that of previous algorithms that where not space optimal. (The time complexity of previous MST algorithms that used ©(log2n) memory bits per node was O(n2), and the time for optimal space algorithms was O(n|E|).)Our MST algorithm also has the important property that, if faults occur after the construction ended, then they are detected by some nodes within O(log2n) time in synchronous networks, or within O(? log2n) time in asynchronous ones. This property is inherited from the specific proof labeling scheme we construct. It answers an open problem posed by Awerbuch and Varghese (FOCS 1991). We also show that ©(log n) time is necessary if the memory size is restricted to O(log n) bits, even in synchronous networks.Another property is that if f faults occurred, then, within the required detection time above, they are detected by some node in the O(f log n) locality of each of the faults. We also show how to improve the above detection time and locality, at the expense of some increase in the memory.

The aim of this invited talk is to try to stimulate research in the interesting and promising research direction of distributed verification. This distributed bears some similarities to the task of solving decision problems in the context of sequential computing. There, the study of decision problems proved very fruitful in establishing structured foundations for the theory. There are some signs that the study of distributed verification may be fruitful for the theory of distributed computing too.

A traditional distributed system was, usually, designed by some centralized manufacturer and owned by some central owner. On the other hand, many modern distributed systems (e.g., many Peer to Peer (P2P) networks) are formed when people team up to pool their resources together to form such a system. We aim to initiate an investigation into the way people make a distributed decision on the composition of such a system, with the goal of realizing high values. Intuitively, we look at settings in which, by teaming up, a node increases its utility, however, it also pays a cost that often (as mentioned later) increases with the size of the system. The right balance is achieved by the right size system.

International audience; Population protocols are a model presented recently for networks with a very large, possibly unknown number of mobile agents having small memory. This model has certain advantages over alternative models (such as DTN) for such networks. However, it was shown that the computational power of this model is limited to semi-linear predicates only. Hence, various extensions were suggested. We present a model that enhances the original model of population protocols by introducing a (weak) notion of speed of the agents. This enhancement allows us to design fast converging protocols with only weak requirements (for example, suppose that there are different types of agents, say agents attached to sick animals and to healthy animals, two meeting agents just need to be able to estimate which of them is faster, e.g., using their types, but not to actually know the speeds of their types). Then, using the new model, we study the gathering problem, in which there is an unknown number of anonymous agents that have values they should deliver to a base station (without replications). We develop efficient protocols step by step searching for an optimal solution and adapting to the size of the available memory. The protocols are simple, though their analysis is somewhat involved. We also present a more involved result - a lower bound on the length of the worst execution for any protocol. Our proofs introduce several techniques that may prove useful also in future studies of time in population protocols.

Most self-stabilizing protocols rely on checking every neighbor of a node continuously to detect failures. Such protocols have a high communication cost, especially in dense graphs. Conceivably, one can check neighbors less often, reducing the amount of communication per round. However, delaying the checking delays the fault detection and the stabilization, and therefore has the potential of increasing the total amount of communication overhead until stabilization. In this paper, we strive to reduce "after stabilization" overhead, without increasing the "before stabilization" overhead. For that, we investigate the potential effect of randomization on the communication efficiency of self-stabilizing protocols. We present randomized low communication self-stabilizing algorithms for several major tasks, namely, spanning tree construction, distributed reset, and unison. We study this approach in a complete graph, since there the communication overhead of checking seems the highest when one strives for protocols that are also fast.

Shared counters are the key to solving a variety of coordination problems on multiprocessor machines, such as barrier synchronization and index distribution. It is desired that they, like shared objects in general, be robust, linearizable and scalable. We present the first linearizable and wait-free shared counter algorithm that achieves high throughput without a-priori knowledge about the system's level of asynchrony. Our algorithm can be easily adapted to any other combinable objects as well, such as stacks and queues. In particular, in an N-process execution E, our algorithm achieves high throughput of Ω(N/φE2 log2 φElogN), where φE is E's level of asynchrony. Moreover, our algorithm stands any constant number of faults. If E contains a constant number of faults, then our algorithm still achieves high throughput of Ω(N/φ′E2 log2 φ′E logN), where φ′E bounds the relative speeds of any two processes, at a time that both of them participated in E and none of them failed. Our algorithm can be viewed as an adaptive version of the Bounded-Wait-Combining (BWC) prior art algorithm. BWC receives as an input an argument φ as a (supposed) upper bound of φE, and achieves optimal throughput if φ = φE. However, if the given φ happens to be lower than the actual φE, or much greater than φE, then the throughput of BWC degraded significantly. Moreover, whereas BWC is only lock-free, our algorithm is more robust, since it is wait-free. To achieve high throughput and wait-freedom, we present a method that guarantees (for some common kind of procedures) the procedure's successful termination in a bounded time, regardless of shared memory contention. This method may prove useful by itself, for other problems

We present a model for asynchronous mobile agent networks that takes into account the notion of speed of the agents. Then, we study the gathering problem (GP), in which an unknown number of anonymous agents have constant values they must deliver (only once) to a non mobile agent, the base station.

Developing self-stabilizing solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. This remark holds for a large variety of models. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an automatic transformer for algorithms in population protocols model . This model introduced recently for networks with a large number of resource-limited mobile agents. For our purposes, we use a variant of this model. Mainly, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication "speed" and considered through the notion of cover time . The automatic transformer takes as an input an algorithm solving a static problem and outputs a self-stabilizing algorithm for the same problem. We prove that our transformer is correct and we analyze its stabilization complexity.