Transaction scheduling is crucial to efficiently allocate shared resources in a conflict-free manner in distributed systems. We investigate the efficient scheduling of transactions in a network of fog-cloud computing model, where transactions and their associated shared objects can move within the network. The schedule may require objects to move to transaction nodes, or the transactions to move to the object nodes. Moreover, the schedule may determine intermediate nodes where both objects and transactions meet. Our goal is to minimize the total combined cost of the schedule. We focus on networks of constant doubling dimension, which appear frequently in practice. We consider a batch problem where an arbitrary set of nodes has transactions that need to be scheduled. First, we consider a single shared object required by all the transactions and present a scheduling algorithm that gives an $O(\log n \cdot \log D)$ approximation of the optimal schedule, where $n$ is the number of nodes and $D$ is the diameter of the network. Later, we consider transactions accessing multiple shared objects (at most $k$ objects per transaction) and provide a scheduling algorithm that gives an $O(k \cdot \log n \cdot \log D)$ approximation. We also provide a fully distributed version of the scheduling algorithms where the nodes do not need global knowledge of transactions.

A phase clock is a basic synchronization mechanism that keeps distributed nodes closely synchronized to execute the same phase of a distributed algorithm. A phase clock is typically implemented with a local logical counter that keeps track of the current phase count. Phase clocks are particularly useful in population protocols for implementing leader election and majority selection. We study phase clocks that tolerate Byzantine faults. We show that there is a phase clock that tolerates up to f < n/3 faulty nodes, where n is the number of nodes, such that the gap of the local counter values is O(n²log n). The gap can be further lowered to O(log n) when f ≤ n/8. We also show that if f > n/3, then the gap grows to infinity as time increases. While analyzing phase clock we introduce novel techniques and bounds for balls into bins processes, which might be of independent interest. Using the phase clock, we obtain a majority selection population protocol that tolerates up to f faults and decides on the majority value in O(log² n) parallel time using poly-log states per node.

Sharding is a technique to speed up transaction processing in blockchains, where the n processing nodes in the blockchain are divided into s disjoint groups (shards) that can process transactions in parallel. We study dynamic scheduling problems on a shard graph G_s where transactions arrive online over time and are not known in advance. Each transaction may access at most k shards, and we denote by d the worst distance between a transaction and its accessing (destination) shards (the parameter d is unknown to the shards). To handle different values of d, we assume a locality sensitive decomposition of G_s into clusters of shards, where every cluster has a leader shard that schedules transactions for the cluster. We first examine the simpler case of the stateless model, where leaders are not aware of the current state of the transaction accounts, and we prove a O(d log² s ⋅ min{k, √s}) competitive ratio for latency. We then consider the stateful model, where leader shards gather the current state of accounts, and we prove a O(log s⋅ min{k, √s}+log² s) competitive ratio for latency. Each leader calculates the schedule in polynomial time for each transaction that it processes. We show that for any ε > 0, approximating the optimal schedule within a (min{k, √s})^{1 -ε} factor is NP-hard. Hence, our bound for the stateful model is within a poly-log factor from the best possibly achievable. To the best of our knowledge, this is the first work to establish provably efficient dynamic scheduling algorithms for blockchain sharding systems.

Sharding is used to improve the scalability and performance of blockchain systems. We investigate the stability of blockchain sharding, where transactions are continuously generated by an adversarial model. The system consists of n processing nodes that are divided into s shards. Following the paradigm of classical adversarial queuing theory, transactions are continuously received at injection rate ρ ≤ 1 and burstiness b > 0. We give an absolute upper bound max{2/k+1, 2⌊√2s⌋} on the maximum injection rate for which any scheduler could guarantee bounded queues and latency of transactions, where k is the number of shards that each transaction accesses. We next give a basic distributed scheduling algorithm for uniform systems where shards are equally close to each other. To guarantee stability, the injection rate is limited to ρ ≤ max{1/18k, 1/ ⌈18√s⌉}. We then provide a fully distributed scheduling algorithm for non-uniform systems where shards are arbitrarily far from each other. By using a hierarchical clustering of the shards, stability is guaranteed with injection rate ρ ≤ 1/(c1d log2 s) ⋅ max{1/k, 1/√s}, where d is the worst distance of any transaction to the shards it will access, and c1 is some positive constant. We also conduct simulations to evaluate the algorithms and measure the average queue sizes and latency throughout the system. To our knowledge, this is the first adversarial stability analysis of sharded blockchain systems.

Given a graph G, a classical problem in graph theory is the construction of a spanner H -- a sparse subgraph of G that closely approximates the distances between nodes in G. The distance stretch~α of H is the factor of how much the distances in H increase versus G. Here, we consider sparse spanner constructions that can also preserve the node congestion of routing problems in G. The congestion stretch β of H is the factor of how much the (smallest) congestion of a routing problem increases in H versus G. We introduce the notion of (α, β)-DC-spanner (i.e., a Distance-Congestion-spanner) that simultaneously controls the stretches for distance and congestion. We show that for expander graphs with n nodes, there is a (3, O(log n))-DC-spanner with O(n5/3) edges. We also examine Δ-regular graphs with Δ ≥ n2/3, where we show how to obtain a (3, O(√Δ ⋅ log n))-DC-spanner with O(n5/3 log2n) edges. Finally, we show that there is a graph such that any optimal size 3-distance spanner has Ω(n7/6) edges and is a (3, Ω(n1/6))-DC-spanner.

Nowadays, wireless local-area networks (WLANs) are widely deployed in residential and commercial areas. The coverage quality is essential to users. The full coverage appears to be one of the most crucial problems to be considered during the network and access-point/router deployment (placement). We formulate the light-of-sight (LoS) coverage problem using the visibility-graph framework. In this work, for arbitrary multiply-connected or simply-connected polygonal/prismatic fields-of-interest subject to an arbitrary link-range restriction, we investigate how the full LoS coverage can be achieved by a minimum number of access-points/routers. Based on the new mathematical lemmas we derive, we design a novel graph-theoretical approach accordingly. Our proposed new scheme can be deemed the first-ever systematic approach to the best of our knowledge. Our proposed new approach is also evaluated in terms of the coverage efficiency, the number of access-points/routers, and the peak link-distance ratio for full LoS coverage in comparison with the existing solution to the art gallery problem.

A spanning tree T of graph G is a $\rho$-approximate universal Steiner tree (UST) for root vertex r if, for any subset of vertices S containing r, the cost of the minimal subgraph of T connecting S is within a $\rho$ factor of the minimum cost tree connecting S in G. Busch et al. (FOCS 2012) showed that every graph admits $2^{O(\sqrt{\log n})}$-approximate USTs by showing that USTs are equivalent to strong sparse partition hierarchies (up to poly-logs). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions.We settle these open questions by giving polynomial-time algorithms for computing both $O\left(\log ^{7} n\right)$-approximate USTs and poly-logarithmic strong sparse partition hierarchies. We reduce the existence of these objects to the previously studied cluster aggregation problem and a class of well-separated point sets which we call dangling nets. For graphs with constant doubling dimension or constant pathwidth we obtain improved bounds by deriving $O(\log n)$-approximate USTs and $O(1)$ strong sparse partition hierarchies. Our doubling dimension result is tight up to second order terms.

Mosaic is a popular approach to provide privacy of data and image. However, the existing demosaicing techniques cannot accomplish efficient perfect-reconstruction. If the receiver wants to recover the original image, the extra transmission of the original subimage to be mosaicked is necessary, which consumes much channel resource and is therefore inefficient. In this paper, we propose a novel efficient recoverable cryptographic mosaic technique by permutations. A mosaic, or a privacy-protected subimage, can be constructed through either of the three permutations (Busch's, Wu's, and Sun's/Minmax). These three permutations are designed to maximize the objective function as the sum of the absolute row/column index-differences. This objective is related to the sum of the pixel-to-pixel cross-correlation by our pertinent theoretical study. To measure the effectiveness of the image-mosaicing methods, we propose two image-discrepancy measures, namely summed cross-correlation (SCC) and Kullback-Leibler divergence of discrete cosine transform (DCT-KLD). Compared to the big majority of random permutations for image-mosaicing, our proposed three permutation methods can achieve much better performances in terms of SCC. Nevertheless, the advantage of the three proposed permutation methods over random permutations is not obvious according to DCT-KLD.

Autonomous vehicles become more and more popular in our daily life. Mobile computing schemes to be installed on these vehicles have drawn a lot of recent research interest. In this paper, we address the important path-planning problem for autonomous vehicles. We introduce and formulate the novelpaintbrush coverage problem. We present a theoretical study on the minimum trajectory length of a paintbrush to cover an arbitrary convex region, which is derived as a function of the area of the region and the size of the cover. Three commonly-used patrolling/scouting methods, namely boustrophedon, spiral, and sector, are manifested in details as the potential solutions to the paintbrush coverage problem. The theoretical minimum trajectory lengths any algorithm can achieve are also demonstrated as the benchmarks for different shapes of regions.

We investigate scheduling algorithms for distributed transactional memory systems where transactions residing at nodes of a communication graph operate on shared, mobile objects. A transaction requests the objects it needs, executes once those objects have been assembled, and then sends the objects to other waiting transactions. We study scheduling algorithms with provable performance guarantees. Previously, only the offline batch scheduling setting was considered in the literature where transactions and the objects they access are known a priori. Minimizing execution time, even for the offline batch scheduling, is known to be NP-hard for arbitrary communication graphs. In this paper, we analyze for the very first time scheduling algorithms in the online dynamic scheduling setting where transactions and the objects they access are not known a priori and the transactions may arrive online over time. We provide efficient and near-optimal execution time schedules for dynamic scheduling in many specialized network architectures. The core of our technique is a method to convert offline schedules to online. We first describe a centralized scheduler which we then adapt it to a purely distributed scheduler. To our knowledge, these are the first attempts to obtain provably efficient online execution schedules for distributed transactional memory.

The coordination problems arising in a team of autonomous mobile robots have received a lot of attention in the distributed robotics community. Along those lines, we study in this paper the problem of coordinating autonomous mobile robots to reposition on a convex hull so that each robot sees all others. In particular, we consider non-transparent fat robots operating in the 2-dimensional plane. They are abstracted as unit discs and they make local decisions with vision being the only mean of coordination among them. We develop a (deterministic) distributed algorithm that solves the problem for a team of N ≥ 3 fat robots in O(N) time avoiding collisions under the semi-synchronous scheduler. The main idea is to enforce the robots to reach a configuration in which (i) the robots' centers form a convex hull; (ii) all robots are on the convex hull's boundary; and (iii) each robot can see all other robots. The result is achieved assuming some reasonable conditions on the input configuration and showing that starting from any input configuration that satisfies our conditions, robots reach such a configuration in linear time and terminate.

We propose a scalable, cycle-collecting, decentralized, reference counting garbage collector with partial tracing. The algorithm is based on the Brownbridge system but uses four different types of references to label edges. Memory usage is O (log n) bits per node, where n is the number of nodes in the graph. The algorithm assumes an asynchronous network model with a reliable reordering channel. It collects garbage in O (E a ) time, where E a is the number of edges in the in- duced subgraph. The algorithm uses termination detection to manage the distributed computation, a unique identifier to break the symmetry among multiple collectors, and a transaction-based approach when multiple collectors conflict. Unlike existing algorithms, ours is not centralized, does not require barriers, does not require migration of nodes, does not require back-pointers on every edge, and is stable against concurrent mutation.

We consider bottleneck congestion games in an arbitrary graph G where player strategies are flows in G . The player's objective is to select a flow that minimizes the maximum load on any edge, that is, minimize the bottleneck congestion. We consider splittable and unsplittable games with pure strategies. It has been an open problem for many years to determine whether it is possible to compute in polynomial time Nash equilibriums for bottleneck congestion games in arbitrary graphs. For splittable games we provide a polynomial time algorithm to compute a Nash equilibrium which is also a global optimum. The unsplittable game problem is known to be PLS-complete, and so we focus on approximate Nash equilibria where players are approximately stable. For uniform player demands we give an algorithm to compute a O(łog m)-approximate unsplittable equilibrium in polynomial time, where m is the number of edges. For non-uniform player demands we give an algorithm to compute a O(ζ łog(ζ m))-approximate unsplittable equilibrium in polynomial time, where ζ = O(1 + łog (dmax /dmin)) and dmax, dmin are the respective maximum and minimum player demands. To our knowledge, these are the first general results for efficiently computing equilibria of pure bottleneck congestion games in arbitrary graphs, both for the splittable and unsplittable cases.

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using colored lights (the robots with lights model). We study the fundamental problem of repositioning N autonomous robots on a plane sothat each robot is visible to all others (the Complete Visibility problem) on this model; a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. There exists an O(1) time, O(1) color algorithm for this problem in the semi-synchronous setting. In this paper, we provide the first O(log N) time, O(1) color algorithm for this problem in the asynchronous setting. This is a significant improvement over an O(N)-time translation of the semi-synchronous algorithm to the asynchronous setting. The proposed algorithm is collision-free - robots do not share positions and their paths do not cross.

We investigate scheduling algorithms for distributed transactional memory systems where transactions residing at nodes of a communication graph operate on shared, mobile objects. A transaction requests the objects it needs, executes once those objects have been assembled, and then possibly forwards those objects to other waiting transactions. Minimizing execution time in this model is known to be NP-hard for arbitrary communication graphs, and also hard to approximate within any factor smaller than the size of the graph. Nevertheless, networks on chips, multi-core systems, and clusters are not arbitrary. Here, we explore efficient execution schedules in specialized graphs likely to arise in practice: Clique, Line, Grid, Cluster, Hypercube, Butterfly, and Star. In most cases, when individual transactions request k objects, we obtain solutions close to a factor O(k) from optimal, yielding near-optimal solutions for constant k. These execution times approximate the TSP tour lengths of the objects in the graph. We show that for general networks, even for two objects (k=2), it is impossible to obtain execution time close to the objects' optimal TSP tour lengths, which is why it is useful to consider more realistic network models. To our knowledge, this is the first attempt to obtain provably fast schedules for distributed transactional memory.

We consider the distributed setting of $N$ autonomous mobile robots that operate in Look-Compute-Move cycles following the well-celebrated classic oblivious robots model. We study the fundamental problem where starting from an arbitrary initial configuration, N autonomous robots reposition themselves to a convex hull formation on the plane where each robot is visible to all others (the Complete Visibility problem). We assume obstructed visibility, where a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. We provide the first \cO(N) time algorithm for this problem in the fully synchronous setting. Our contribution is a significant improvement over the runtime of the only previously known algorithm for this problem which has a lower bound of \Omega(N^2). Our proposed algorithm is collision-free -- robots do not share positions and their paths do not cross.

We consider the fundamental problem of gathering a set of n robots in the Euclidean plane that have a physical extent and hence cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem with minimum time objective has applications in many real-world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (in Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science, 2011) gave a local greedy algorithm in a fully synchronous setting and proved that, for the discrete version of the problem where robots’ movements are restricted to the positions on an integral grid, their algorithm solves this problem in O ( nR ) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this article, we improve significantly the round complexity of their algorithm to R + 2 · ( n - 1) rounds. This round complexity is obtained in the following modified model: (1) the viewing range of the robots is increased to three hops and (2) robots can additionally move to the diagonally opposite corner to a grid cell in one step—that is, they can traverse the two corresponding grid edges in one time step. We also prove that there are initial configurations of n robots in this problem where at least R +(n-1)/2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + ( n - 1) rounds for the algorithm of Cord-Landwehr et al. These results altogether provide a tight runtime analysis of their algorithm.

Nowadays, the sufficient quality-of-service (QoS) provision for mobile applications remains a major challenge in any wireless network. Conventional sufficient QoS provision techniques using resource allocation, data scheduling, and cross-layer optimization have been proposed to tackle this problem. Nevertheless, due to the unpredictable nature of wireless channel conditions, the QoS improvements resulting from the aforementioned approaches are often unsatisfactory. In this paper, we would like to follow our previous concept, namely user-placement ushering (UPU), by use of the user's mobility. A mobile user can be relocated to an optimal, or at least a better place to boost the QoS for a particular application. Novel fast algorithms are devised here to usher (guide) the mobile user to an appropriate spot with sufficient QoS, which is nearby. We address the UPU problem to accommodate realistic complex indoor environments, where obstacles are present. Our simulation results have demonstrated that our new fast UPU algorithms are capable of finding new appropriate locations satisfying the required QoSs for different wireless network applications.

Current shared memory multi-core systems require powerful software and hardware techniques to support the performance parallel computation and consistency simultaneously. The use of transactional memory results in significant improvement of performance by avoiding thread synchronization and locks overhead. Also, transactions scheduling apparently influences the performance of transactional memory. In this paper, we study the fairness of transactions' scheduling using Lazy Snapshot Algorithm. The fairness of transactions' scheduling aims to balance between transactions types which are read-only and update transactions. Indeed, we support the fairness of the scheduling procedure by a machine learning technique. The machine learning techniques improve the fairness decisions according to transactions' history. The experiments in this paper show that the throughput of the Lazy Snapshot Algorithm is improved with a machine learning support. Indeed, our experiments show that the learning significantly affects the performance if the durations of update transactions are much longer than read-only ones. We also study several machine learning techniques to investigate the fairness decisions accuracy. In fact, K-Nearest Neighbor machine learning technique shows more accuracy and more suitability, for our problem, than Support Vector Machine Model and Hidden Markov Model.

We consider the group-communication maintenance problem between a set ofkmobile agents that are tracked by a static sensor network. We develop a scalable deterministic distributed algorithm for maintaining a Steiner tree of the agents so that group communication between them can be provided with the minimum total cost possible. The main idea is that our algorithm maintains a virtual tree of mobile agents that can be immediately converted to an actual Steiner tree at all times. Our algorithm achieves the Steiner tree with total length at mostO(logk) times the length of the optimal Steiner tree in the constant-doubling graph model. The total communication cost (the number of messages) to maintain the Steiner tree is onlyO(min{logn, logD}) times the optimal communication cost, wherenandD, respectively, are the number of nodes and the diameter of the constant-doubling network. We also develop improved algorithms for the mobilek-center, sparse-aggregation, and distributed-matching problems. Experimental evaluation results show the benefits of our algorithms compared to previous algorithms. These four problems are NP-hard and, to the best of our knowledge, our algorithms are the first near-optimal deterministic algorithms for maintaining approximate solutions to these important network problems with low maintenance costs in a distributed setting.

We consider the problem of repositioning N autonomous robots on a plane so that each robot is visible to all others (the Complete Visibility problem), a robot cannot see another robot if there is a third robot positioned between them on the straight line joining them. Robots communicate using collared lights. The computation is synchronous and each robot performs a look-compute-move during a round. Specifically, during a round a robot is permitted to observe the light and position of every robot visible to it. It may also perform an internal computation based on the observed lights and positions(including deciding on a new-collar for its own light), and possibly moving to a new position at the end of the round. The challenge posed by this model of computation stems from the fact that each robot has only a constant number of colours for its lights(symbols for communication) and no memory(except for the persistence of lights) between rounds. In this paper we first show that the best previously known algorithm for the complete visibility problem on this model runs in linear time in the worst case. We then present the first logarithmic time complexity algorithm for Complete Visibility. The model we assume use sterility, is fully-synchronous and allows robot paths to cross.

We consider the fundamental problem of gathering a set of n robots in the Euclidean plane which have a physical extent and hence they cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem has applications in many real world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (SOFSEM 2011) gave a local greedy algorithm in a synchronous setting and proved that, for the discrete version of the problem where robots movements are restricted to the positions on an integral grid, their algorithm solves this problem in O(nR) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this paper, we improve significantly the round complexity of their algorithm to R + 2 · (n - 1) rounds. We also prove that there are initial configurations of n robots in this problem where at least R + (n - 1) over 2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + (n - 1) rounds for the algorithm of Cord-Landwehr et al.. These results altogether provide a tight runtime analysis of their algorithm.

We consider scheduling problems in the data flow model of distributed transactional memory. Objects shared by transactions move from one network node to another by following network paths. We examine how the objects' transfer in the network affects the completion time of all transactions and the total communication cost. We show that there are problem instances for which there is no scheduling algorithm that can simultaneously minimize the completion time and communication cost. These instances reveal a trade-off, minimizing execution time implies high communication cost and vice versa. On the positive side, we provide scheduling algorithms which are independently communication cost near-optimal or execution time efficient.

We consider the group communication maintenance problem between a set of k mobile agents that are tracked by a static sensor network. We develop a scalable deterministic distributed algorithm for maintaining a Steiner tree of the agents so that group communication between them can be provided in the minimum cost possible. The main idea is that our algorithm maintains a virtual tree of mobile agents which can be immediately converted to an actual Steiner tree at all times. Our algorithm achieves the Steiner tree with total length at most O (log k) times the length of the minimum Steiner tree in the constant-doubling graph model. The total communication cost (messages) to maintain the Steiner tree is only O (min {log n, log D}) times the optimal communication cost, where n and D, respectively, are the number of nodes and the diameter of the network. We also develop improved algorithms for the k-center, sparse aggregation, and distributed matching problems. Experimental evaluation results show the benefits of our algorithms compared to previous algorithms. These four problems are NP-hard and, to the best of our knowledge, our algorithms are the first near-optimal deterministic algorithms for maintaining approximate solutions to these problems with low maintenance costs in a distributed setting.

This paper presents a new concurrent garbage collection algorithm based on two types of reference, strong and weak, to link the graph of objects. Strong references connect the roots to all the nodes in the graph but do not contain cycles. Weak references may, however, contain cycles.

We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph G and a root node r, we seek a single spanning tree T of minimum stretch, where the stretch of T is defined to be the maximum ratio, over all terminal sets X, of the cost of the minimal sub-tree TXof T that connects X to r to the cost of an optimal Steiner tree connecting X to r in G. Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. graphs with 2O(√log n)-stretch. We also give a polynomial time We provide a polynomial time UST construction for general polylog(n)-stretch construction for minor-free graphs. One basic building block of our algorithms is a hierarchy of graph partitions, each of which guarantees small strong diameter for each cluster and bounded neighbourhood intersections for each node. We show close connections between the problems of constructing USTs and building such graph partitions. Our construction of partition hierarchies for general graphs is based on an iterative cluster merging procedure, while the one for minor-free graphs is based on a separator theorem for such graphs and the solution to a cluster aggregation problem that may be of independent interest even for general graphs. To our knowledge, this is the first subpolynomial-stretch (o(nε) for any ε >; 0) UST construction for general graphs, and the first polylogarithmic-stretch UST construction for minor-free graphs.

We consider the problem of implementing transactional memory in large-scale distributed networked systems. We present and analyze Spiral, a novel distributed directory-based protocol for transactional memory. Spiral is designed for the data-flow distributed implementation of software transactional memory which supports three basic operations: publish, allowing a shared object to be inserted in the directory so that other nodes can find it; lookup, providing a read-only copy of the object to the requesting node; move, allowing the requesting node to write the object locally after the node gets it. The protocol runs on a hierarchical directory construction based on sparse covers, where clusters at each level are ordered to avoid race conditions while serving concurrent requests. Given a shared object the protocol maintains a directory path pointing to the object. The basic idea is to use “spiral” paths that grow outward to search for the directory path of the object in a bottom-up fashion. For general networks, this protocol guarantees an O(log2n · log D) approximation for move requests, where n is the number of nodes and D is the diameter of the network. It also guarantees polylog approximation for lookup requests. To the best of our knowledge, this is the first consistency protocol for distributed transactional memory that achieves poly-log approximation in general networks.

A classic optimization problem in network routing is to minimize C + D, where C is the maximum edge congestion and D is the maximum path length (also known as dilation). The problem of computing the optimal C* + D* is NP-complete even when either C* or D* is a small constant. We study routing games in general networks where each player i selfishly selects a path that minimizes Ci+ Dithe sum of congestion and dilation of the player's path. We first show that there are instances of this game without Nash equilibria. We then turn to the related quality of routing (QoR) games which always have Nash equilibria. QoR games represent networks with a small number of service classes where paths in different classes do not interfere with each other (with frequency or time division multiplexing). QoR games have O(log4n) price of anarchy when either C* or D* is a constant. Thus, Nash equilibria of QoR games give poly-log approximations to hard optimization problems.

We consider the problem of constructing a single spanning tree for the single-sink buy-at-bulk network design problem for doubling-dimension graphs. We compute a spanning tree to route a set of demands along a graph G to or from a designated sink node. The demands could be aggregated at (or symmetrically distributed to) intermediate edges where the fusion cost is specified by a nonnegative concave function f. We describe a novel approach for developing an oblivious spanning tree in the sense that it is independent of the number and location of data sources (or demands) and cost function at the edges. We present a deterministic, polynomial-time algorithm for constructing a spanning tree in low doubling-dimension graphs that guarantees a log3D-approximation over the optimal cost, where D is the diameter of the graph G. With a constant fusion-cost function, our spanning tree gives an O(log3D)-approximation for every Steiner tree that includes the sink. We also provide a Ω(log n) lower bound for any oblivious tree in low doubling-dimension graphs. To our knowledge, this is the first paper to propose a single spanning tree solution to the single-sink buy-at-bulk network design problem (as opposed to multiple overlay trees).

In the oblivious path selection problem, each packet in the network independently chooses a path, which is an important property if the routing algorithm is to be independent of the traffic distribution. The quality of the paths is determined by the congestion, C, the maximum number of paths crossing an edge, and the dilation, D, the maximum path length. So far, the oblivious algorithms studied in the literature have focused on minimizing the congestion while ignoring the dilation. An open problem is to give algorithms for networks in which C and D can be controlled simultaneously. Here, we solve this problem for the d-dimensional mesh. We present an oblivious algorithm for which C and D are both within O(d2) of the optimal. The algorithm uses randomization and we show that the number of random bits required per packet is within O(d) of the minimum number of random bits required by any algorithm that obtains the same congestion. For a fixed d, our algorithm is asymptotically optimal.

We consider the construction of sparse covers for planar graphs and other graphs that exclude a fixed minor. We present an algorithm that gives a cover for the γ-neighborhood of each node. For planar graphs, the cover has radius no more than 24γ-8 and degree (maximum cluster overlaps) no more than 18. For every n node graph that excludes a fixed minor, we present an algorithm that yields a cover with radius no more than 4γ and degree O(log n).

A packet-switching algorithm specifies the actions of the nodes in order to deliver packets in the network. A packet-switching algorithm is universal if it applies to any network topology and for any batch communication problem on the network. A long-standing open problem has concerned the existence of a universal packet-switching algorithm with near-optimal performance guarantees for the class of bufferless networks where the buffer size for packets in transit is zero. We give a positive answer to this question. In particular, we give a universal bufferless algorithm which is within a polylogarithmic factor from optimal for arbitrary batch problems: ${\cal T}=O\left({\cal T}^*\cdot \log^3(n+N)\right)$, where ${\cal T}$ is the packet delivery time of our algorithm, ${\cal T}^*$ is the optimal delivery time, n is the size of the network, and N is the number of packets. At the heart of our result is a new deterministic technique for constructing a universal bufferless algorithm by emulating a store-and-forward algorithm on a transformation of the network. The main idea is to replace packet buffering in the transformed network with packet circulation in regions of the original network. The cost of the emulation on the packet delivery time is proportional to the buffer sizes used by the store-and-forward algorithm. We obtain the advertised result by using a store-and-forward algorithm with logarithmic sized buffers. The resulting bufferless algorithm is constructive and can be implemented in a distributed way.

In both distributed counting and queuing, processors in a distributed system issue operations which are organized into a total order. In counting, each processor receives the rank of its operation in the total order, where as in queuing, a processor gets back the identity of its predecessor in the total order. Coordination applications such as totally ordered multicast can be solved using either distributed counting or queuing, and it would be very useful to definitively know which of counting or queuing is a harder problem. We conduct the first systematic study of the relative complexities of distributed counting and queuing in a concurrent setting. Our results show that concurrent counting is harder than concurrent queuing on a variety of processor interconnection topologies, including high diameter graphs such as the list and the mesh, and low diameter graphs such as the complete graph, perfect m-ary tree, and the hypercube. For all these topologies, we show that the concurrent delay complexity of a particular solution to queuing, the arrow protocol, is asymptotically smaller than a lower bound on the complexity of any solution to counting. As a consequence, we are able to definitively say that given a choice between applying counting or queuing to solve a distributed coordination problem, queuing is the better solution.

We study the problem of maintaining sketches of recent elements of a data stream. Motivated by applications involving network data, we consider streams that are asynchronous, in which the observed order of data is not the same as the time order in which the data was generated. The notion of recent elements of a stream is modeled by the sliding timestamp window, which is the set of elements with timestamps that are close to the current time. We design algorithms for maintaining sketches of all elements within the sliding timestamp window that can give provably accurate estimates of two basic aggregates, the sum and the median, of a stream of numbers. The space taken by the sketches, the time needed for querying the sketch, and the time for inserting new elements into the sketch are all polylog with respect to the maximum window size and the values of the data items in the window. Our sketches can be easily combined in a lossless and compact way, making them useful for distributed computations over data streams. Previous works on sketching recent elements of a data stream have all considered the more restrictive scenario of synchronous streams, where the observed order of data is the same as the time order in which the data was generated. Our notion of recency of elements is more general than that studied in previous work, and thus our sketches are more robust to network delays and asynchrony.

We study oblivious routing in which the packet paths are constructed independently of each other. We give a simple oblivious routing algorithm for geometric networks in which the nodes are embedded in the Euclidean plane. In our algorithm, a packet path is constructed by first choosing a random intermediate node in the space between the source and destination, and then the packet is sent to its destination through the intermediate node. We analyze the performance of the algorithm in terms of the stretch and congestion of the resulting paths. We show that the stretch is constant, and the congestion is near optimal when the network paths can be chosen to be close to the geodesic lines that connect the end points of the paths. We give applications of our general result to the mesh topology and uniformly distributed disc graphs. Previous oblivious routing algorithms with near optimal congestion use many intermediate nodes and do not control the stretch.

Link reversal algorithms provide a simple mechanism for routing in communication networks whose topology is frequently changing, such as in mobile ad hoc networks. A link reversal algorithm routes by imposing a direction on each network link such that the resulting graph is a destination oriented DAG. Whenever a node loses routes to the destination, it reacts by reversing some (or all) of its incident links. Link reversal algorithms have been studied experimentally and have been used in practical routing algorithms, including TORA [V. D. Park and M. S. Corson, A highly adaptive distributed routing algorithm for mobile wireless networks,in Proc. INFOCOM, IEEE, Los Alamitos, CA, 1997, pp. 1405--1413]. This paper presents the first formal performance analysis of link reversal algorithms. We study these algorithms in terms of work (number of node reversals) and the time needed until the network stabilizes to a state in which all the routes are reestablished. We focus on the full reversal algorithm and the partial reversal algorithm, both due to Gafni and Bertsekas [IEEE Trans. Comm.}, 29 (1981), pp. 11--18]; the first algorithm is simpler, while the latter has been found to be more efficient for typical cases. Our results are as follows: The full reversal algorithm requires O(n 2 ) work and time, where n is the number of nodes that have lost routes to the destination. This bound is tight in the worst case.The partial reversal algorithm requires O(n $\cdot$ a* + n 2 ) work and time, where a* is a nonnegative integral function of the initial state of the network. Further, for every nonnegative integer $\alpha$, there exists a network and an initial state with a*=$\alpha$, and with n nodes that have lost their paths to the destination, such that the partial reversal algorithm requires $\Omega(n\cdot {a^*} + n^2)$ work and time.There is an inherent lower bound on the worst-case performance of link reversal algorithms. There exist networks such that for every deterministic link reversal algorithm, there are initial states that require $\Omega(n^2)$ work and time to stabilize. Therefore, surprisingly, the full reversal algorithm is asymptotically optimal in the worst case, while the partial reversal algorithm is not, since a* can be arbitrarily larger than n.

Link reversal algorithms provide a simple mechanism for routing in mobile ad hoc networks. These algorithms maintain routes to any particular destination in the network, even when the network topology changes frequently. In link reversal, a node reverses its incident links whenever it loses routes to the destination. Link reversal algorithms have been studied experimentally and have been used in practical routing algorithms, including [8].This paper presents the first formal performance analysis of link reversal algorithms. We study these algorithms in terms of work (number of node reversals) and the time needed until the network stabilizes to a state in which all the routes are reestablished. We focus on the full reversal algorithm and the partial reversal algorithm, both due to Gafni and Berstekas [5]; the first algorithm is simpler, while the latter has been found to be more efficient for typical cases. Our results are as follows:(1) The full reversal algorithm requires O(n2) work and time, where n is the number of nodes which have lost the routes to the destination.(2) The partial reversal algorithm requires O(n • a* + n2) work and time, where a* is a non-negative integer which depends on the state of the network. This bound is tight in the worst case, for any a*.(3) There are networks such that for every deterministic link reversal algorithm, there are initial states which require requires ω(n2) work and time to stabilize. Therefore, surprisingly, the full reversal algorithm is asymptotically optimal in the worst case, while the partial reversal algorithm is not, since a* can grow arbitrarily large.

We study packet routing problems, in which we route a set of N packets on preselected paths with congestion C and dilation D. For store-and-forward routing, in which nodes have buffers for packets in transit, there are routing algorithms with performance that matches the lower bound Ω(C+D). Motivated from optical networks, we study the extreme case of hot-potato routing in which the nodes are bufferless. In hot-potato routing, packets may be unable to follow the preselected paths towards the destination nodes; thus it may take more time for packets to be routed. An interesting question is how much is the performance of routing algorithms affected from the absence of buffers.Here, we answer this question for the general class of leveled networks, in which the nodes are partitioned into L+1 distinct levels. We present a randomized hot-potato routing algorithm for leveled networks, which routes the packets in Õ(C + L) time with high probability. For routing problems with dilation O(L), this bound is within polylogarithmic factors from the lower bound Ω(C+L). Our algorithm demonstrates that the benefit from using buffers is no more than polylogarithmic; thus, hot-potato routing is an efficient way to route packets in leveled networks.Our algorithm is online, that is, routing decisions are taken at real time at each node, while packets are routed in the network. A novel characteristic of our algorithm is that during the course of routing, packets may deviate from their preselected paths. To our knowledge, this is the first hot-potato algorithm designed and analyzed, in terms of congestion and dilation, for arbitrary leveled networks.

We present the first dynamic hot-potato routing algorithm that does not require any form of explicit flow control: a node may inject a message into the network (n × n mesh) whenever a link is free. In the worst case, a node may have to wait an expected Ο(n) time before it has a free link. If destinations are chosen uniformly at random, this algorithm guarantees delivery in an expected Ο(n) time steps. Both measures are optimal up to a constant factor.

We present the first hot-potato routing algorithm for the n × n mesh whose running time on any "hard" (i.e., n)) "many-to-one" batch routing problem is, with high probability, within a polylogarithmic factor of optimal. For any instance I of a batch routing problem, there exists a well-known lower bound LBI based on maximum path length and maximum congestion. If LBI is n), our algorithm solves I with high probability in time O(LBI log 3 n). The algorithm is distributed and greedy, and it makes use of a new routing technique based on multi-bend paths, a departure from paths using a constant number of bends used in prior hot-potato algorithms.

We present the fist construction for sorting and counting networks of arbitrary width that uses both small depth and small constant factors.Let w be the product w = pe + + .p,,-l,

No abstract available.

Balancing networks, originally introduced by Aspnes et al.(Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 348-358, May 1991), represent a new class of distributed, low-contention data structures suitable for solving many fundamental multi-processor coordination problems that can be expressed asbalancing problems. In this work, we present a mathematical study of the combinatorial structure of balancing networks, and a variety of its applications. Our study identifies important combinatorialtransfer parametersof balancing networks. In turn, necessary and sufficient combinatorial conditions are established, expressed in terms of transfer parameters, which precisely characterize many important and well studied classes of balancing networks such ascounting networksandsmoothing networks. We propose these combinatorial conditions to be “balancing analogs” of the well knownZero-One principleholding forsorting networks Within the combinatorial framework we develop, our first application is in deriving combinatorial conditions, involving the transfer parameters, which precisely delimit the boundary between counting networks and sorting networks.

No abstract available.

No abstract available.

Article A combinatorial treatment of balancing networks Share on Authors: Costas Busch Department of Computer Science, University of Crete, Heraklion 71110, Greece and Institute of Computer Science, Foundation of Research and Technology, Heraklion 71110, Greece Department of Computer Science, University of Crete, Heraklion 71110, Greece and Institute of Computer Science, Foundation of Research and Technology, Heraklion 71110, GreeceView Profile , Marios Mavronicolas Institute of Computer Science, Foundation of Research and Technology, Greece and Department of Computer Science, University of Cyprus, Nicosia, Cyprus Institute of Computer Science, Foundation of Research and Technology, Greece and Department of Computer Science, University of Cyprus, Nicosia, CyprusView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 206–215https://doi.org/10.1145/197917.198092Online:14 August 1994Publication History 7citation146DownloadsMetricsTotal Citations7Total Downloads146Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access