Abstract. A Nash equilibrium of a routing game is a stable state where no (randomizing) user could benefit from a unilateral deviation. We consider the simplest case of the parallel links network, where links are related. The Social Cost of a Nash equilibrium is the expected maximum latency. We seek the worst-case Nash equilibrium [E. Koutsoupias and C. H. Papadimitriou, Comput. Sci. Rev., 3 (2009), pp. 65–69], which maximizes Social Cost. We continue the study of the fully mixed Nash equilibrium conjecture, abbreviated as the FMNE Conjecture, stating that the worst-case Nash equilibrium is the fully mixed Nash equilibrium, where each user assigns strictly positive probability to every link. Through an extensive combinatorial analysis, we confirm the FMNE Conjecture for the two basic cases where there are either (i) two users on related links, or (ii) many users on two identical links.

We show exact values for the worst-case price of anarchy in weighted and unweighted (atomic unsplittable) congestion games, provided that all cost functions are bounded-degree polynomials with nonnegative coefficients. The given values also hold for weighted and unweighted network congestion games.

In this work we study weighted network congestion games with player-specific latency functions where selfish players wish to route their traffic through a shared network. We consider both the case of splittable and unsplittable traffic. Our main findings are as follows. For routing games on parallel links with linear latency functions, we introduce two new potential functions for unsplittable and for splittable traffic, respectively. We use these functions to derive results on the convergence to pure Nash equilibria and the computation of equilibria. For several generalizations of these routing games, we show that such potential functions do not exist. We prove tight upper and lower bounds on the price of anarchy for games with polynomial latency functions. All our results on the price of anarchy translate to general congestion games.

Graph partitioning requires the division of a graph's vertex set into k equally sized subsets such that some objective function is optimized. For many important ob jective functions, e. g., the number of edges incident to different partitions, the problem is MV-hard. Graph partitioning is an important task in many applications, so that a variety of algorithms and tools for its solution have been developed. Most state-of-the-art graph partitioning libraries use a variant of the Kernighan-Lin (KL) heuristic within a multilevel framework. While these libraries are very fast, their solutions do not always meet all requirements of the users. This includes the choice of the appropriate objective function and the shape of the computed partitions. Moreover, due to its sequential nature, the KL heuristic is not easy to parallelize. Thus, its use as a load balancer in parallel numerical applications requires complicated adaptations. That is why we have developed previously an inherently parallel algorithm, called BUBBLE-FOS/C (Meyerhenke et ah, IPDPS'06), which optimizes the partition shapes by a diffusive mechanism. Yet, it is too slow to be of real practical use, despite its high solution quality. In this paper, besides proving that BUBBLE-FOS/C converges towards a local optimum, we develop a much faster method for the improvement of partitionings. It is based on a different diffusive process, which is restricted to local areas of the graph and also contains a high degree of parallelism. By coupling this new technique with BUBBLE-FOS/C in a multilevel framework based on two different hierarchy construction methods, we obtain our new graph partitioning heuristic DibaP. Compared to BUBBLE-FOS/C, it shows a considerable acceleration, while retaining the positive properties of the slower algorithm. Experiments with popular benchmark graphs show an extremely good behavior. First, DibaP computes consistently better results - measured by the edge-cut and the number of boundary vertices in the summation and the maximum norm - than the state-of-the-art libraries METIS and JOSTLE. Second, with our new algorithm, we have improved the best known edge-cut values for a significant number of partitionings of six widely used benchmark graphs.

We propose a load balancing heuristic for parallel adaptive finite element method (FEM) simulations. In contrast to most existing approaches, the heuristic focuses on good partition shapes rather than on minimizing the classical edge-cut metric. By applying algebraic multigrid (AMG), we are able to speed up the two most time consuming calculations of the approach while maintaining its large amount of natural parallelism

In his seminal work Harsanyi [13] introduced an elegant approach to study non-cooperative games with incomplete information where the players are uncertain about some parameters. To model such games he introduced the Harsanyi transformation, which converts a game with incomplete information to a strategic game where players may have different types. In the resulting Bayesian game players' uncertainty about each others types is described by a probability distribution over all possible type profiles.In this work, we introduce a particular selfish routing game with incomplete information that we call Bayesian routing game. Here, n selfish users wish to assign their traffic to one of m links. Users do not know each others traffic. Following Harsanyi's approach, we introduce for each user a set of possible types.This paper presents a comprehensive collection of results for the Bayesian routing game.We prove, with help of a potential function, that every Bayesian routing game possesses a pure Bayesian Nash equilibrium. For the model of identical links and independent type distribution we give a polynomial time algorithm to compute a pure Bayesian Nash equilibrium.We study structural properties of fully mixed Bayesian Nash equilibria for the model of identical links and show that they maximize individual cost. In general there exists more than one fully mixed Bayesian Nash equilibrium. We characterize the class of fully mixed Bayesian Nash equilibria in the case of independent type distribution.We conclude with results on coordination ratio for the model of identical links for three social cost measures, that is, social cost as expected maximum congestion, sum of individual costs and maximum individual cost. For the latter two we are able to give (asymptotic) tight bounds using our results on fully mixed Bayesian Nash equilibria.To the best of our knowledge this is the first time that mixed Bayesian Nash equilibria have been studied in conjunction with social cost.

Graph partitioning is an important subproblem in many applications. To partition a graph into more than two parts, there exist two different commonly used approaches: Either the graph is partitioned directly into the desired amount of partitions or the graph is first split into two partitions that are then further divided recursively. It has been shown that even optimal recursive bisection can lead to solutions "very far from the optimal one". However, for "important graph classes" recursive bisection solutions are known to be "almost always" within a constant factor of the optimal one. Thus, the question arises how good recursive bisection performs in practice. In this paper we describe enhancements to the Party graph partitioning library which is based on the helpful-set bisection heuristic and present results of extensive tests undertaken with it. We thereby compare Party with the two state-of-the art libraries Metis and Jostle using a permutation based evaluation scheme. We show experimentally that there are indeed many cases where a recursive application of a good bisection heuristic is likely to find better solutions than up-to-date direct approaches.

We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to the correspondingly restricted problem of assigning n jobs to m parallel machines. In a pure Nash equilibrium, no user may improve its own individual cost (delay) by unilaterally switching to another link from its set of allowed links. As our main result, we introduce a polynomial time algorithm to compute from any given assignment a pure Nash equilibrium with non-increased makespan. The algorithm gradually changes a given assignment by pushing unsplittable user traffics through a network that is defined by the users and the links. Here, we use ideas from blocking flows. Furthermore, we use similar techniques as in the generic Preflow-Push algorithm to approximate a schedule with minimum makespan, gaining an improved approximation factor of 2 - 1/w1 for identical links, where w1 is the largest user traffic. We extend this result to related links, gaining an approximation factor of 2. Our approximation algorithms run in polynomial time. We close with tight upper bounds on the coordination ratio for pure Nash equilibria.

Diffusive schemes have been widely analyzed for parallel and distributed load balancing. It is well known that their convergence rates depend on the eigenvalues of some associated matrices and on the expansion properties of the underlying graphs. In the first part of this paper we make use of these relationships in order to obtain new spectral bounds on the edge and node expansion of graphs. We show that these new bounds are better than the classical bounds for several graph classes. In the second part of the paper, we consider the load balancing problem for indivisible unit size tokens. Since known diffusion schemes do not completely balance the load for such settings, we propose a randomized distributed algorithm based on Markov chains to reduce the load imbalance. We prove that this approach provides the best asymptotic result that can be achieved in l1- or l2-norm concerning the final load situation.

One of the fundamental properties of a graph is the number of distinct eigenvalues of its adjacency or Laplace matrix. Determining this number is of theoretical interest as well as of practical impact. Sparse graphs with small spectra exhibit excellent structural properties and can act as interconnection topologies. In this paper, for any n we present graphs, for which the product of their vertex degree and the number of different eigenvalues is small. It is known that load balancing can be performed on such graphs in a small number of steps.

When executing processes on parallel computer systems they encounter as a major bottleneck inter-processor communication. One way to address this problem is to minimize the communication between processes that are mapped to different processors. This translates to the k-partitioning problem of the corresponding process graph, where k is the number of processors. The classical spectral lower bound of ¦V¦ ÷ 2k Σ k i =1 λi for the k-section width of a graph is well-known. We show new relations between the structure and the eigen values of a graph and present a new method to get tighter lower bounds on the k-section width. This method makes use of the level structure defined by the k-section. We define some global expansion property and prove that for graphs with the same k-section width the spectral lower bound increases with this global expansion. We also present examples of graphs for which our new bounds are tight up to a constant factor.

Up to now, diffusive load balancing schemes have only been developed for homogeneous networks. We generalize existing diffusion schemes, in order to deal with heterogeneous networks. In these networks, every processor can have arbitrary computing power, and the load has to be balanced proportionally to these weights. The balancing flow that is calculated by the schemes for homogeneous networks is minimal with regard to the l 2 -norm and we prove this to hold true for the generalized schemes, too. By means of a number of experiments we demonstrate the usability of the generalized schemes on heterogeneous networks.

We design a general mathematical framework to analyze the properties of nearest neighbor balancing algorithms of the diffusion type. Within this framework we develop a new Optimal Polynomial Scheme (OPS) which we show to terminate within a finite number m of steps, where m only depends on the graph and not on the initial load distribution. We show that all existing diffusion load balancing algorithms, including OPS, determine a flow of load on the edges of the graph which is uniquely defined, independent of the method and minimal in the l2-norm. This result can also be extended to edge weighted graphs. The l2-minimality is achieved only if a diffusion algorithm is used as preprocessing and the real movement of load is performed in a second step. Thus, it is advisable to split the balancing process into the two steps of first determining a balancing flow and afterwards moving the load. We introduce the problem of scheduling a flow and present some first results on its complexity and the approximation quality of local greedy heuristics.

We present a parallel algorithm for static and dynamic partitioning of unstructured FEM-meshes. The method consists of two parts. First a fast but inaccurate sequential clustering is determined which is used, together with a simple mapping heuristic, to map the mesh initially onto the processors of a parallel system. The second part of the method uses a massively parallel algorithm to remap and optimize the mesh decomposition, taking several cost functions into account which reflect the characteristics of the underlying hardware and the requirements of the numerical solution method supposed to run after the decomposition. The parallel algorithm first calculates the number of nodes that have to be migrated between pairs of clusters in order to obtain an optimal load balancing. In a second step, nodes to be migrated are chosen according to cost functions optimizing the amount of necessary communication and the shapes of subdomains. The latter criterion is extremely important for the convergence behavior of certain numerical solution methods, especially for preconditioned conjugate gradient methods. The parallel parts of the method are implemented in C under Parix to run on the Parsytec GC systems. Results on up to 64 processors are presented and compared to those of other existing methods. © 1998 John Wiley & Sons, Ltd.

We consider the simulation of large cube-connected cycles (CCC) and large butterfly networks (BFN) on smaller ones, a problem that arises when algorithms designed for an architecture of an ideal size are to be executed on an existing architecture of a fixed size. We show that large CCCs and BFNs can be embedded into smaller networks of the same type with (a) dilation 2 and optimum load, (b) dilation 1 and optimum load in most cases, and (c) dilation 1 and nearly optimum load in all cases. Our results show that large CCCs and BFNs can be simulated very efficiently on smaller ones. Additionally, we implemented our algorithm for compressing CCCs and ran several experiments on a Transputer network, which showed that our technique also behaves very well from a practical point of view. © 1998 John Wiley & Sons, Inc. Networks 32: 47–65, 1998

Multistage networks (MIN) are used as interconnection structure in a large number of applications. Their performance is mainly determined by their communication throughput which, in most cases, has to be investigated by time-consuming simulations or approximated by simple models. In this paper, we investigate the steady state throughput of single buffered multistage interconnection networks using the so called relaxed blocking model, where a message is deleted, if the receiving buffer is occupied. We derive upper and lower bounds on the throughput of MINs of arbitrary height and show that the throughput of singlebuffered networks is an order of magnitude higher than the throughput of non-buffered MINs. In detail we show, that the throughput is \\Theta(n= p log n) if n is the size of the network. Because the time-dynamic of finite buffered MINs defies each marcov- or semi-marcov approach, we analyze the the equilibrium-situation of the network and give tight upper and lower bounds on t...

Abstract With nearest‐neighbor load‐balancing algorithms, a processor makes balancing decisions based on localized workload information and manages workload migrations within its neighborhood. The paper compares a couple of fairly well‐known nearest‐neighbor algorithms,the dimension‐exchange(DE) andthe diffusion(DF) methods and their several variants—the average dimension‐exchange (ADE), optimally tuned dimension‐exchange (ODE), local average diffusion (ADF) and optimally tuned diffusion (ODF). The measures of interest are their efficiency in driving any initial workload distribution to a uniform distribution and their ability in controlling the growth of the variance among the processors' workloads. The comparison is made with respect to both one‐port and all‐port communication architectures and in consideration of various implementation strategies including synchronous/asynchronous invocation policies and static/dynamic random workload behaviors. It turns out that the dimension‐exchange method outperforms the diffusion method in the one‐port communication model. In particular, the ODE algorithm is best suited for statically synchronous implementations of a load‐balancing process regardless of its underlying communication models. The strength of the diffusion method is in asynchronous implementations in the all‐port communication model; the ODF algorithm performs best in that case. The underlying communication networks considered assume the most popular topologies, the mesh and the torus and their special cases: the hypercube and thek‐aryn‐cube.

In this paper we study the overheads arising in our algorithm for distributed evaluation of Min/Max trees.The overheads are classified into search overhead, performance loss, and decrease of work load.Several mechanisms are investigated to cope with these overheads in order to achieve a high performance.We study a combination of local, medium range, and global load distribution strategies that does not only show a good behavior in terms of work load, but also has a positive influence on the search overhead.The efficient use of a virtual shared memorv.that is distributed among the processors, shows also a big 'contribution to the overal~performance of the system.A carefully restricted application of parallelism using an improved version of the Young Brothers Wait Concept (YBWC) leads to a perfect behavior for minimal Min/Max trees and to a quite low search overhead, if well ordered trees are searched.Well ordered trees const itute the most important case in practice, since a couple of move ordering mechanisms are known that achieve a nearly optimal move ordering in many applications.The resulting combination of the methods shows an efficiency better than any previous approach.Experiments carried out using 256 DeBruijn-connected Transputers result in a speedup of 142 even applying restricted timing constraints.With a system consisting of 1024 grid connected Transputers we obtain a speedup of 344.Moreover the algorithm shows a very good scalability, especially using interconnection networks with logarithmic diameter.The experiments have been carried out using a Min/Max search program that incorporates all important state-of-theart search techniques ( ZUGZWANG, current vice world champion in computer chess) and therefore makes sure, that no artificial or simplifying assumptions on the structure of the problem are made.

The overall efficiency of parallel algorithms is most decisively effected by the strategy applied for the mapping of workload. Strategies for balancing dynamically generated workload on a processor network which are also useful for practical applications have intensively been investigated by simulations and by direct applications. This paper presents the complete theoretical analysis of a dynamically distributed load balancing strategy. The algorithm is adaptive by nature and is therefore useful for a broad range of applications. A similar algorithmic principle has already been implemented for a number of applications in the areas of combinatorial optimization, parallel programming languages and graphical animation. The algorithm performed convincingly for all these applications. In our analysis we will prove that the expected number of packets on each processor varies only by a constant factor compared with that on any other processor, independent of the generation and consumption of ...

Article Simulating binary trees on X-trees (extended abstract) Share on Author: Burkhard Monien Dept. of Math. and Computer Science, University of Paderborn, 4790 Paderborn, Germany Dept. of Math. and Computer Science, University of Paderborn, 4790 Paderborn, GermanyView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 147–158https://doi.org/10.1145/113379.113393Online:01 June 1991Publication History 4citation215DownloadsMetricsTotal Citations4Total Downloads215Last 12 Months2Last 6 weeks0 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

Assume each processor in a network has some piece of information.We study how efficiently information can be spread in a communication network.Specifically, we investigate the number of rounds necessary to spread all the pieces of information to all processors.This problem is known as the "gossip" problem, and initially, the question was to determine the number of telephone calls necessary to achieve complete dissemination.In this paper we study the "telegraph comnmnication node", where in each round, each processor is active only via one of its links and the communication is one-way, i.e. each processor can either transmit or receive, but not both.For an even number of processors, we prove upper and lower bounds on the number of rounds needed for disseminating the information in this telegraph mode.The two bounds are related to Fibonacci numbers and differ by, at most, an additive constant of 1.Our lower bound technique uses elements from matrix theory, specifically matrix norms.These results show, for the first time, that in the two-way mode, information can be distributed faster than in the one-way mode.Similar techniques are applied to obtain upper and lower bounds on the number of rounds needed for gossip in other communication modes.We consider the (pR, qS)communication modes, where during each round each processor can receive information from at most p processors or can send information to at most q processors, but no processor can send and receive during the same round. ITechnion, Israel Institute

Bandwidth restrictions are considered on several NP-Complete problems, including the following problems: