We study the asymptotic behaviour of the distance to the first available parking slot in a recursive Manhattan street network endowed with a hyperfractal intensity structure, where slot-release events occur according to Poisson processes along the streets. We establish, by analysing the associated self-similar harmonic sums via Mellin-transform asymptotics [Flajolet et al., 1995], a power-law decay of the expected distance as the total intensity grows, with exponent equal to the inverse of the hyperfractal dimension. In particular, the scaling exponent depends only on the large-scale geometry of the network. We further prove that this exponent is robust under random multiplicative modulations of the street intensities: mild stochastic heterogeneity affects only the multiplicative constant. Similar scaling behaviour holds for the variance, the number of turns before parking, and for a jump-over variant of the search strategy.

The {balls-into-bins model} randomly allocates n sequential balls into n bins, as follows: each ball selects a set D of d ⩾ 2 bins, independently and uniformly at random, then the ball is allocated to a least-loaded bin from D (ties broken randomly). The maximum load is the maximum number of balls in any bin. In 1999, Azar et al. showed that, provided ties are broken randomly, after n balls have been placed the maximum load, is log_d log n + 𝒪(1), with high probability. We consider this popular paradigm in a dynamic environment where the bins are structured as a dynamic hypergraph. A dynamic hypergraph is a sequence of hypergraphs, say ℋ^(t), arriving over discrete times t = 1,2,…, such that the vertex set of ℋ^(t)’s is the set of n bins, but (hyper)edges may change over time. In our model, the t-th ball chooses an edge from ℋ^(t) uniformly at random, and then chooses a set D of d ⩾ 2 random bins from the selected edge. The ball is allocated to a least-loaded bin from D, with ties broken randomly. We quantify the dynamicity of the model by introducing the notion of pair visibility, which measures the number of rounds in which a pair of bins appears within a (hyper)edge. We prove that if, for some ε > 0, a dynamic hypergraph has pair visibility at most n^{1-ε}, and some mild additional conditions hold, then with high probability the process has maximum load 𝒪(log_dlog n). Our proof is based on a variation of the witness tree technique, which is of independent interest. The model can also be seen as an adversarial model where an adversary decides the structure of the possible sets of d bins available to each ball.

The asynchronous rumor spreading algorithm propagates a piece of information, the so-called rumor, in a network. Starting with a single informed node, each node is associated with an exponential time clock with rate 1 and calls a random neighbor in order to possibly exchange the rumor. A well-studied parameter associated with the algorithm is the spread time, which is the first time when all nodes of a network are informed with high probability1. We consider the spread time of the algorithm in any dynamic evolving network, [EQUATION], which is a sequence of n-node graphs with the same set of nodes exposed at discrete time step t = 0, 1. ... We establish upper bounds for the spread time in terms of graph conductance and diligence. For a given connected simple graph G = (V, E), the diligence of cut set [EQUATION] is defined as

This paper studies the fundamental communication properties of urban vehicle networks by exploiting the selfsimilarity and hierarchical organization of modern cities. We use an innovative model called “hyperfractal” that captures the selfsimilarities of both the traffic and vehicle locations but avoids the extremes of regularity and randomness. We use analytical tools to derive theoretical upper and lower bounds for the information propagation speed in an urban delay tolerant network (i.e., a network that is disconnected at all time, and thus uses a store-carryand-forward routing model). We prove that the average broadcast time behaves as n1-δtimes a slowly varying function, where δ depends on the precise fractal dimension. Furthermore, we show that the broadcast speedup is due in part to an interesting selfsimilar phenomenon, that we denote as information teleportation. This phenomenon arises as a consequence of the topology of the vehicle traffic, and triggers an acceleration of the broadcast time. We show that our model fits real cities where open traffic data sets are available. We present simulations confirming the validity of the bounds in multiple realistic settings, including scenarios with variable speed, using both QualNet and a discrete-event simulator in Matlab.

The goal of this paper is to increase our understanding of the fundamental communication properties in urban vehicle-to-vehicle mobile networks by exploiting the self-similarity and hierarchical organization of modern cities. We use an innovative model called “hyperfractal” that captures the self-similarities of both the traffic and vehicle locations, and yet avoids the extremes of regularity and randomness. We use analytical tools to derive matching theoretical upper and lower bounds for the information propagation speed in an urban delay tolerant network (i.e., a network that is disconnected at all time, and thus uses a store-carry-and-forward routing model). We prove that the average broadcast time behaves as n1-δ(times a slowly varying function), where δ depends on the precise fractal dimension. Furthermore, we show that the broadcast speedup is due in part to an interesting self-similar phenomenon, that we denote as information teleportation. This phenomenon arises as a consequence of the topology of the vehicle traffic, and triggers an acceleration of the broadcast time. We show that our model fits real cities where open traffic data sets are available. The study presents simulations that confirm the validity of the bounds in multiple realistic settings, including scenarios with variable speed.

A major challenge of running applications in clouds is to determine the right number of resources (virtual machines or VMs) to rent in terms of both performance and cost. Such a challenge becomes greater if the application requires to run across multiple resources. In this paper, we address the problem of scheduling scientific workflow applications. The structure of workflows, dictated by precedence/data dependencies, and the diversity of resources in clouds both at large scale make the resource provisioning and task scheduling very complex. To this end, we design the Resource Demand Aware Scheduling (RDAS) algorithm that schedules workflows based on their resource demands and priorities considering workflow structure. RDAS partitions workflows and allocates resources of possibly different capacities/types to the partitions in a “fair” manner such that their execution times do not vary significantly. RDAS turns resource and application heterogeneity (a major hindering factor in clouds) into an opportunity for optimizing resource provisioning for scientific workflows. Based on our experimental results, RDAS demonstrates its capacity of minimizing the overall workflow completion time (makespan) and in turn minimizing costs of the execution. In particular, RDAS outperforms three existing algorithms by 22%, 13% and 33%, on average, in terms of makespan, cost and the number of resources used, respectively.

Trees are a fundamental structure in algorithmics. In this paper, we study the transformation of an arbitrary binary tree S with n vertices into a completely balanced tree T via rotations , a widely studied elementary tree operation. Combining concepts on rotation distance and data structures, we give a basic algorithm that performs the transformation in Θ( n ) time and Θ(1) space, making at most 2 n − 2 log 2n rotations and improving on known previous results. The algorithm is then improved, exploiting particular properties of S . Finally, we show tighter upper bounds and obtain a close lower bound on the rotation distance between a zig-zag tree and a completely balanced tree. We also find the exact rotation distance of a particular almost balanced tree to a completely balanced tree, and thus show that their distance is quite large despite the similarity of the two trees.

We study the scaling properties of a georouting scheme in a wireless multi-hop network of n mobile nodes. Our aim is to increase the network capacity quasi-linearly with n, while keeping the average delay bounded. In our model, we consider mobile nodes moving according to an independent identically distributed random walk with velocity v and transmitting packets to randomly chosen fixed and known destinations. The average packet delivery delay of our scheme is of order 1/v, and it achieves network capacity of order (n/log n log logn). This shows a practical throughput-delay tradeoff, in particular when compared with the seminal result of Gupta and Kumar, which shows network capacity of order (n/log n)1/2and negligible delay and the groundbreaking result of Grossglauser and Tse, which achieves network capacity of order n but with an average delay of order √n/v. The foundation of our improved capacity and delay tradeoff relies on the fact that we use a mobility model that contains straight-line segments, a model that we consider more realistic than classic Brownian motions. We confirm the generality of our analytical results using simulations under various interference models.

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.

Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. Yet, connectivity can be achieved over time and space, leading to evaluate a given route both in terms of topological length or temporal length. The problem of measuring temporal distances in a social network was recently addressed through postprocessing contact traces like email data sets, in which all contacts are punctual in time (i.e., they have no duration). We focus on the distributed version of this problem and address the more general case that contacts can have arbitrary durations (i.e., be nonpunctual). Precisely, we ask whether each node in a network can track in real time how "out-of-dateâ it is with respect to every other. Although relatively straightforward with punctual contacts, this problem is substantially more complex with arbitrarily long contacts: consecutive hops of an optimal route may either be disconnected (intermittent connectedness of DTNs) or connected (i.e., the presence of links overlaps in time, implying a continuum of path opportunities). The problem is further complicated (and yet, more realistic) by the fact that we address continuous-time systems and nonnegligible message latencies (time to propagate a single message over a single link); however, this latency is assumed fixed and known. We demonstrate the problem is solvable in this general context by generalizing a time-measurement vector clock construct to the case of "nonpunctualâ causality, which results in a tool we call T-Clocks, of independent interest. The remainder of the paper shows how T-Clocks can be leveraged to solve concrete problems such as learning foremost broadcast trees (BTs), network backbones, or fastest broadcast trees in periodic DTNs.

We study the information propagation speed in multi-lane vehicle-to-vehicle networks such as roads or highways. We focus on the impact of time-varying radio ranges and of multiple lanes of vehicles, varying in speed and in density. We assess the existence of a vehicle density threshold under which information propagates on average at the fastest vehicle speed and above which information propagates dramatically faster. We first prove that no such phase transition occurs if there is only one lane, regardless of the density of vehicles, when one takes into account real-time radio communication range variations at the MAC layer. We then prove that, on the other hand, a phase transition exists as soon as there are multiple lanes with different vehicle speeds and appropriate densities. We characterize conditions under which the phase transition occurs and we derive bounds on the corresponding threshold as a simple relationship between the vehicle density on the fastest lane and the sum of densities on the other lanes. Our results intrinsically encompass a wide range of vehicular network scenarios, including one-way and two-way roads, as well as special cases such as road side units and/or parked cars being used as relays. We confirm our analytical results using simulations.

We study the scaling properties of a georouting scheme in a wireless multi-hop network of n mobile nodes. Our aim is to increase the network capacity quasi linearly with n while keeping the average delay bounded. In our model, mobile nodes move according to an i.i.d. random walk with velocity v and transmit packets to randomly chosen destinations. The average packet delivery delay of our scheme is of order 1/v and it achieves the network capacity of order n/(log n log log n). This shows a practical throughput-delay trade-off, in particular when compared with the seminal result of Gupta and Kumar which shows network capacity of order √(n/log n) and negligible delay and the groundbreaking result of Grossglauser and Tse which achieves network capacity of order n but with an average delay of order √n/v. The foundation of our improved capacity and delay trade-off relies on the fact that we use a mobility model that contains free space motion, a model that we consider more realistic than classic brownian motions. We confirm the generality of our analytical results using simulations under various interference models.

In this paper, we provide a full analysis of the information propagation speed in bidirectional vehicular delay tolerant networks such as roads or highways. The provided analysis shows that a phase transition occurs concerning the information propagation speed, with respect to the vehicle densities in each direction of the highway. We prove that under a certain threshold, information propagates on average at vehicle speed, while above this threshold, information propagates dramatically faster at a speed that increases quasi-exponentially when the vehicle density increases. We provide the exact expressions of the threshold and of the average information propagation speed near the threshold, in case of finite or infinite radio propagation speed. Furthermore, we investigate in detail the way information propagates under the threshold, and we prove that delay tolerant routing using cars moving on both directions provides a gain in propagation distance, which is bounded by a sublinear power law with respect to the elapsed time, in the referential of the moving cars. Combining these results, we thus obtain a complete picture of the way information propagates in vehicular networks on roads and highways, which may help designing and evaluating appropriate vehicular ad hoc networks routing protocols. We confirm our analytical results using simulations carried out in several environments (The One and Maple).

In this paper, we provide an analysis of the information propagation speed in bidirectional vehicular delay tolerant networks on highways. We show that a phase transition occurs concerning the information propagation speed, with respect to the vehicle densities in each direction of the highway. We prove that under a certain threshold, information propagates on average at vehicle speed, while above this threshold, information propagates dramatically faster at a speed that increase exponentially when vehicle density increases. We provide the exact expressions of the threshold and of the average propagation speed near the threshold. We show that under the threshold, the information propagates on a distance which is bounded by a sub-linear power law with respect to the elapsed time, in the referential of the moving cars. On the other hand, we show that information propagation speed grows quasi-exponentially with respect to vehicle densities in each direction of the highway, when the densities become large, above the threshold. We confirm our analytical results using simulations carried out in several environments.

Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. In most cases, however, a form of connectivity can be established over time and space. This particularity leads to consider the relevance of a given route not only in terms of hops (topological length), but also in terms of time (temporal length). The problem of measuring temporal distances between individuals in a social network was recently addressed, based on a posteriori analysis of interaction traces. This paper focuses on the distributed version of this problem, asking whether every node in a network can know precisely and in real time how out-of-date it is with respect to every other. Answering affirmatively is simple when contacts between the nodes are punctual, using the temporal adaptation of vector clocks provided in (Kossinets et al., 2008). It becomes more difficult when contacts have a duration and can overlap in time with each other. We demonstrate that the problem remains solvable with arbitrarily long contacts and non-instantaneous (though invariant and known) propagation delays on edges. This is done constructively by extending the temporal adaptation of vector clocks to non-punctual causality. The second part of the paper discusses how the knowledge of temporal lags could be used as a building block to solve more concrete problems, such as the construction of foremost broadcast trees or network backbones in periodically-varying DTNs.

We investigate the fundamental capacity limits of space-time journeys of information in mobile and Delay Tolerant Networks (DTNs), where information is either transmitted or carried by mobile nodes, using store-carry-forward routing. We define the capacity of a journey (i.e., a path in space and time, from a source to a destination) as the maximum amount of data that can be transferred from the source to the destination in the given journey. Combining a stochastic model (conveying all possible journeys) and an analysis of the durations of the nodes' encounters, we study the properties of journeys that maximize the space-time information propagation capacity, in bit-meters per second. More specifically, we provide theoretical lower and upper bounds on the information propagation speed, as a function of the journey capacity. In the particular case of random way-point-like models (i.e., when nodes move for a distance of the order of the network domain size before changing direction), we show that, for relatively large journey capacities, the information propagation speed is of the same order as the mobile node speed. This implies that, surprisingly, in sparse but large-scale mobile DTNs, the space-time information propagation capacity in bit-meters per second remains proportional to the mobile node speed and to the size of the transported data bundles, when the bundles are relatively large. We also verify that all our analytical bounds are accurate in several simulation scenarios.

The goal of this paper is to increase our understanding of the fundamental performance limits of mobile and Delay Tolerant Networks (DTNs), where end-to-end multihop paths may not exist and communication routes may only be available through time and mobility. We use analytical tools to derive generic theoretical upper bounds for the information propagation speed in large scale mobile and intermittently connected networks. In other words, we upper-bound the optimal performance, in terms of delay, that can be achieved using any routing algorithm. We then show how our analysis can be applied to specific mobility models to obtain specific analytical estimates. In particular, in 2-D networks, when nodes move at a maximum speed$v$and their density$\nu $is small (the network is sparse and asymptotically almost surely disconnected), we prove that the information propagation speed is upper bounded by$(1+O(\nu ^{2}))v$in random waypoint-like models, while it is upper bounded by$O(\sqrt {\nu v} v)$for other mobility models (random walk, Brownian motion). We also present simulations that confirm the validity of the bounds in these scenarios. Finally, we generalize our results to 1-D and 3-D networks.

The goal of this paper is to increase our understanding of the fundamental performance limits of mobile and delay tolerant networks (DTNs), where end-to-end multi-hop paths may not exist and communication routes may only be available through time and mobility. We use analytical tools to derive generic theoretical upper bounds for the information propagation speed in large scale mobile and intermittently connected networks. In other words, we upper-bound the optimal performance, in terms of delay, that can be achieved using any routing algorithm. We then show how our analysis can be applied to specific mobility and graph models to obtain specific analytical estimates. In particular, when nodes move at speed v and their density v is small (the network is sparse and surely disconnected), we prove that the information propagation speed is upper bounded by (1 + O(v2))v in the random way-point model, while it is upper bounded by O(radic(vv)v) for other mobility models (random walk, Brownian motion). We also present simulations that confirm the validity of the bounds in these scenarios.

We analyze the performance of epidemic routing in large-scale intermittently connected networks, under a random geometric graph model and for different mobility parameters (such as the random-waypoint, random walk and Brownian motion models). We derive a generic scaling law on the delay, which provides us with lower bounds: the average delay from a source to a destination and the average broadcast delay are both ¿ ((RN¿n)/vn), where n is the number of nodes in the network, vnthe maximum node speed, and Rnthe radio range.

Classical routing strategies for mobile ad hoc networks operate in a hop by hop "push mode" basis: packets are forwarded on pre-determined relay nodes, according to previously and independently established link performance metrics (e.g., using hellos or route discovery messages). Conversely, recent research has highlighted the interest in developing opportunistic routing schemes, operating in "pull mode": the next relay can be selected dynamically for each packet and each hop, on the basis of the actual network performance. This allows each packet to take advantage of the local pattern of transmissions at any time. The objective of such opportunistic routing schemes is to minimize the end-to-end delay required to carry a packet from the source to the destination. In this paper, we provide upper bounds on the packet propagation speed for opportunistic routing, in a realistic network model where link conditions are variable. We analyze the performance of various opportunistic routing strategies and we compare them with classical routing schemes. The analysis and the simulations show that opportunistic routing performs significantly better. We also investigate the effects of mobility and of random fading. Finally, we present numerical simulations that confirm the accuracy of our bounds.

Delay/disruption tolerant networks (DTNs) or intermittently connected mobile networks (ICNs) are mobile ad hoc networks where end-to-end multi-hop paths may not exist and communication routes may only be available through time and mobility. While most of the research is dedicated to the design of routing protocols, very few properties of such networks are known. In a recent paper [6], the authors provided analytical upper bounds for the information propagation speed in DTNs when they are modeled as two-dimensional Unit Disk Graphs. In this paper, we extend this study to other models by using analytical tools to derive theoretical upper-bounds of the information propagation speed. Firstly, we will present results for DTNs mapped in a space of dimension D, where D varies from 1 to 3. Secondly, we will depart from the Unit Disk Graph model to consider a more realistic model where a node captures a packet sent at distance r with probability p(r).

Classical routing strategies for mobile ad hoc networks forward packets on a pre-defined route (typically obtained by a shortest path routing protocol). Research has high-lighted the interest in developing opportunistic routing schemes, where the next relay is selected dynamically for each packet and each hop. This allows each packet to take advantage of the local pattern of transmissions at any time. The objective of such opportunistic routing schemes is to minimize the end-to-end delay required to carry a packet from the source to the destination. In this paper, we provide upper bounds on the packet propagation speed for opportunistic routing, in a realistic network model where link conditions are variable. We analyze the performance of various opportunistic routing strategies and we compare them with classical routing schemes. The analysis and simulations show that opportunistic routing performs significantly better. We also investigate the effects of mobility. Finally, we present numerical simulations that confirm the accuracy of our bounds.

For nodes of mobile ad hoc networks, energy is a scarce resource that can be quickly depleted by communications. Moreover, due to the nature of wireless communication medium, nodes can waste a substantial amount of energy by overhearing packets in their neighborhood, most of which may not be meant for them. The overall impact of overhearing is not well-studied: many of the schemes claiming to be energy-efficient neglect this cost by only focusing on energy costs due to local traffic. In this paper, we propose that nodes exploit overheard packets to gather awareness of current neighboring flows and adapt their local routing dynamically. By combining this awareness with battery-aware routing metrics, which includes the battery levels of the neighbors, we introduce various routing schemes that increase the network lifetime.

A simple, yet popular way to design energy-efficient routing for Mobile Ad Hoc Networks (MANET) is to use a virtual backbone that forms a minimum sized Connected Dominating Set (CDS) of the network topology. By minimising the number of forwarding nodes, it looks at extending the (battery-dependent) life-span of the network by minimising the number (and energy cost) of transmitting nodes. In this paper, we consider a more realistic model in which the energy cost of the receiving nodes (including nodes overhearing packets) is also taken into account, and show that current CDS algorithms may lead to backbones that are ineffective at minimising the overall energy cost during broadcast. We first prove that a (realistic) reception-aware model leads to a new NP-complete problem - we have coined this Connected Exact Cover - to reduce the energy drain due to the number of overheard receptions while broadcasting in MANET. This holds even if all nodes transmit at the same power. Then we introduce two algorithms, one centralised and one distributed, and show with several simulations that these algorithms generate virtual backbones that consume less energy during broadcasts compared to the best virtual backbone schemes known in the literature.

Numerous studies on energy-efficient routing for multihop ad hoc networks (MANET) look at extending battery life by minimizing the cost at the transmitting node. In this paper, we study the complexity of energy-efficient routing when the energy cost of receiving packets is also considered. We first prove that, surprisingly, even when all nodes transmit at the same power, finding a simple unicast path that guarantees enough remaining energy locally at each node in the network then becomes an NP-complete problem. Hence we propose several heuristics based on Dijkstra's shortest path algorithm in which we integrate the notion of remaining energy in order to satisfy flow requirements. We show with several simulations that these heuristics not only allow the computation of routes that save energy of nodes with low battery but also allow the network to handle more flows

A parameterized model of hyperclusters of processors-clusters of clusters of... of clusters of processors-is formulated under which a hypercluster enjoys generality along three orthogonal axes: (1) Its processors are heterogeneous: they may have different computational powers (speed of computation and memory access). (2) Its constituent clusters are interconnected via a hierarchy of networks of possibly differing bandwidths and speeds. (3) Its clusters at each level of the hierarchy are heterogeneous: they may differ in size. The model accounts for architectural details such as the bandwidths and transit costs of both networks and their ports. The algorithmic tractability of the model is demonstrated via broadcast and reduction algorithms, which are predictably efficient in general and actually optimal in special circumstances.

The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving therefore the O(m + n) previous known bound.

This paper analyzes the performance of portable distributed priority queues by examining the theoretical features required and comparing various implementations. In spite of intrinsic bottlenecks and induced hot-spots, we argue that tree topologies are attractive to manage the naturally centralized control required for the deletemin operation in order to detect the site which holds the item with the largest priority. We introduce an original perfect balancing to cope with the load variation due to the priority queue operations which continuously modify the overall number of items in the network. For comparison, we introduce the d -heap and the binomial distributed priority queue. The purpose of this experiment is to convey, through executions on a Cray-T3D and Meiko-T800, an understanding of the nature of distributed priority queues, the range of their concurrency and a comparison of their efficiency to reduce request latency. In particular, we show that the d -heap combines an adjustable degree with a small depth, which make it efficient in both theory and practice. The Message Passing Interface (MPI) provides the code with portability. © 1998 John Wiley & Sons, Ltd.

An extensive body of evidence exists of the impact that specific edge labelings have on the communication complexity of distributed problems. It has been long suspected that these very different labelings share a common property, named sense of direction. In spite of the large number of investigations, and of the obvious practical importance, a formal characterization of this property did not exist. In this paper, we finally provide a formal definition of sense of direction, making explicit the very specific relationship between three factors: the labeling, the topological structure, and the local view that an entity has of the system. In a way, sense of direction is the capability of a node in the system to use the labeling to translate the local view of its neighbors into its own. Using the formal definition as an observational platform, we describe several properties which allow the translation process to be possible beyond the immediate neighborhood. Finally, we identify four general classes of labelings and analyze their properties; these classes include all the labelings used in the literature. © 1998 John Wiley & Sons, Inc. Networks 32: 165–180, 1998

Loop networks (or Hamiltonian circulant graphs) are a popular class of fault-tolerant network topologies which include rings and complete graphs. For this class, the fundamental problem of leader election has been extensively studied, assuming either a fault-free system or an upper-bound on the number of link failures. We consider loop networks where an arbitrary number of links have failed and a processor can only detect the status of its incident links. We show that a leader election protocol In a faulty loop network requires only O(n log n) messages in the worst-case, where n is the number of processors. Moreover, we show that this is optimal. The proposed algorithm also detects network partitions. We also show that it provides an optimal solution for arbitrary nonfaulty networks with sense of direction.

We study the positive impact that the availability of Sense of Direction has on the message complexity of the election problem in arbitrary networks of processors. We present a /spl Theta/(n log n) solution; without sense of direction, this problem requires /spl Omega/(e+nlogn) messages where e is the number of communication links. This result confirms and extends the evidence on the impact of sense of direction which, up to now, was established only for specific classes of topologies. >