We consider discrete, iterative load balancing via matchings on arbitrary graphs. Initially each node holds a certain number of tokens, defining the load of the node, and the objective is to redistribute the tokens such that eventually each node has approximately the same number of tokens. We present results for a general class of simple local balancing schemes where the tokens are balanced via matchings. In each round the process averages the tokens of any two matched nodes. If the sum of their tokens is odd, the node to receive the one excess token is selected at random. Our class covers three popular models: in the matching model a new matching is generated randomly in each round, in the balancing circuit model a fixed sequence of matchings is applied periodically, and in the asynchronous model the load is balanced over a randomly chosen edge.

We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given n anonymous agents, and the goal is to assign each agent a unique rank in {1,…,n}. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well.Ranking requires at least n states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only n+O(logn) states. Our protocol stabilizes in O(n2logn) interactions w.h.p. and in expectation, using n + O(log2n) states in total. Our stabilization time is asymptotically optimal (see Burman et al., PODC ’21). In comparison to the currently best known ranking protocol by Burman et al., which requires n + Ω(n) states, our result exponentially improves the number of overhead states.

Small-world networks are attractive for the efficient routing they provide, requiring only a low link density. They have hence also been considered for the design of distributed systems, such as peer-to-peer networks. However, existing small-world network designs are oblivious to the actual traffic they serve. In this paper, we initiate the study of demand-aware small-world networks. In particular, we extend the Kleinberg graph model, by allowing the nodes to choose the distribution of long-range links according to the traffic demand. We present a formal analysis of the weighted route lengths for the important case of clustered demands. We show both in theory and in simulations, using real-world traffic workloads, that demand-aware small-world graphs can significantly outperform their demand-oblivious counterparts.

We revisit the majority problem in the population protocol communication model, as first studied by Angluin et al. (Distributed Computing 2008). We consider a more general version of this problem known as plurality consensus, which has already been studied intensively in the literature. In this problem, each node in a system of n nodes, has initially one of k different opinions, and they need to agree on the (relative) majority opinion. In particular, we consider the important and intensively studied model of Undecided State Dynamics.

The article presents optimization techniques for two Python-based large-scale social sciences applications: SN (Social Network) Simulator and KPM (Kernel Polynomial Method). These applications use MPI technology to transfer data between computing processes, which in the regular implementation leads to load imbalance and performance degradation. To avoid this effect, we propose a 2-stage optimization. In the first step, the order of tasks is changed, and in the second step, the tasks are divided into smaller ones for easier allocation. In addition, we focus on mitigating performance and memory bottlenecks using modern ccNUMA systems with multiple NUMA domains. As part of the performance analysis, the limitations of communication in data traffic between and within the processor were revealed and resolved through appropriate data allocation. Benchmarking was carried out, examining various environments, including vendors of traditional x86-64 and ARM-based processors for HPC.

We consider the plurality consensus problem for population protocols. Here, n anonymous agents start each with one of k opinions. Their goal is to agree on the initially most frequent opinion (the plurality opinion) via random, pairwise interactions. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1.

We consider the plurality consensus problem for n agents. Initially, each agent has one of k opinions. Agents choose random interaction partners and revise their state according to a fixed transition function, depending on their own state and the state of the interaction partners. The goal is to reach a configuration in which all agents agree on the same opinion. If there is initially a sufficiently large bias towards some opinions one of them should prevail. In this paper we consider a synchronized variant of the undecided state dynamics where the agents use so-called phase clocks. The phase clocks divide the time in overlapping phases. Each phase consists of a decision and a boosting part. In the decision part, any agent that encounters an agent with a different opinion becomes undecided. In the boosting part, undecided agents adopt the first opinion they encounter. We consider this dynamics both in the sequential population model and the parallel gossip model. In the population model agents interact in randomly chosen pairs, one pair per time step. The runtime is measured in parallel time (number of interactions divided by n). We show that our protocol reaches consensus (w.h.p.) in O(log2 n) parallel time, providing the first polylogarithmic result for k > 2 (w.h.p.) in this model. If there is an initial bias of , then (w.h.p.) that opinion wins. The gossip model assumes parallel rounds. During each round every agent is allowed to communicate with one randomly chosen agent. Here it is known that consensus can be reached fast (in polylogarithmic time) if there is a bias of order towards one opinion [Ghaffari and Parter, PODC'16; Berenbrink et al., ICALP'16]. Without any assumption on the bias, fast consensus has only been shown for k = 2 for the unsynchronized version of the undecided state dynamics [Clementi et al., MFCS'18]. To account for the yet unsolved general case, we show that the synchronized variant of the undecided state dynamics reaches consensus (w.h.p.) in time O(log2 n) for every initial configuration. Again, we guarantee that if there is an initial bias of , then (w.h.p.) that opinion wins. A simple extension of our protocol in the gossip model yields a dynamics that does not depend on n or k, is anonymous, and has (w.h.p.) runtime O(log2 n). This solves an open problem formulated by Becchetti et al. [Distributed Computing, 2017].

Online social networks are a dominant medium in everyday life to stay in contact with friends and to share information. In Twitter, users can connect with other users by following them, who in turn can follow back. In recent years, researchers studied several properties of social networks and designed random graph models to describe them. Many of these approaches either focus on the generation of undirected graphs or on the creation of directed graphs without modeling the dependencies between reciprocal (i.e., two directed edges of opposite direction between two nodes) and directed edges. We propose an approach to generate directed social network graphs that creates reciprocal and directed edges and considers the correlation between the respective degree sequences.

Most modern communication networks include fast rerouting mechanisms, implemented entirely in the data plane, to quickly recover connectivity after link failures. By relying on local failure information only, these data plane mechanisms provide very fast reaction times, but at the same time introduce an algorithmic challenge in case of multiple link failures: failover routes need to be robust to additional but locally unknown failures downstream. This paper presents local fast rerouting algorithms which not only provide a high degree of resilience against multiple link failures, but also ensure a low congestion on the resulting failover paths. We consider a randomized approach and focus on networks which are highly connected before the failures occur. Our main contribution are three simple algorithms which come with provable guarantees and provide interesting resilience-load tradeoffs, significantly outperforming any deterministic fast rerouting algorithm with high probability.

To ensure high availability, datacenter networks must rely on local fast rerouting mechanisms that allow routers to quickly react to link failures, in a fully decentralized manner. However, configuring these mechanisms to provide a high resilience against multiple failures while avoiding congestion along failover routes is algorithmically challenging, as the rerouting rules can only depend on local failure information and must be defined ahead of time. This paper presents a randomized local fast rerouting algorithm for Clos networks, the predominant datacenter topologies. Given a graph $G=(V,E)$ describing a Clos topology, our algorithm defines local routing rules for each node $v\in V$, which only depend on the packet's destination and are conditioned on the incident link failures. We prove that as long as number of failures at each node does not exceed a certain bound, our algorithm achieves an asymptotically minimal congestion up to polyloglog factors along failover paths. Our lower bounds are developed under some natural routing assumptions.

Abstract Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in Proceedings of the 2015 ACM symposium on principles of distributed computing, Donostia-San Sebastián, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population size n), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.

We study distributed plurality consensus among n nodes, each of which initially holds one of k opinions. The goal is to eventually agree on the initially dominant opinion. We consider an asynchronous communication model in which each node is equipped with a random clock. Whenever the clock of a node ticks, it may open communication channels to a constant number of other nodes, chosen uniformly at random or from a list of constantly many addresses acquired in previous steps. The tick rates and the delays for establishing communication channels (channel delays) follow some probability distribution. Once a channel is established, communication between nodes can be performed instantaneously. We consider distributions for the waiting times between ticks and channel delays that have constant mean and the so-called positive aging property. In this setting, asynchronous plurality consensus is fast: if the initial bias between the largest and second largest opinion is at least [EQUATION] log n , then after O (log log α k · log k + log log n ) time all but a 1/polylog n fraction of nodes have the initial plurality opinion. Here α denotes the initial ratio between the largest and second largest opinion. After additional O (log n ) steps all nodes have the same opinion w.h.p., and this result is tight. If additionally the distributions satisfy a certain density property, which is common in many well-known distributions, we show that consensus is reached in O (log log α k + log log n ) time for all but n /polylog n nodes, w.h.p. This implies that for a large range of initial configurations partial consensus can be reached significantly faster in this asynchronous communication model than in the synchronous setting. To obtain these results, we first assume the existence of a designated base station and later present fully distributed algorithms. Additionally, we derive tail bounds on the Pólya-Eggenberger distribution, which might be of independent interest.

Most modern communication networks include fast rerouting mechanisms, implemented entirely in the data plane, to quickly recover connectivity after link failures. By relying on local failure information only, these data plane mechanisms provide very fast reaction times, but at the same time introduce an algorithmic challenge in case of multiple link failures: failover routes need to be robust to additional but locally unknown failures downstream. This paper presents local fast rerouting algorithms which not only provide a high degree of resilience against multiple link failures, but also ensure a low congestion on the resulting failover paths. We consider a randomized approach and focus on networks which are highly connected before the failures occur. Our main contribution are three simple algorithms which come with provable guarantees and provide interesting resilience-load tradeoffs, significantly outperforming any deterministic fast rerouting algorithm with high probability.

A population protocol can be viewed as a sequence of pairwise interactions of $n$ agents (nodes). During one interaction, two agents selected uniformly at random update their states by applying a specified deterministic transition function. In a long run, the whole system should stabilize at the correct output property. The main performance objectives in designing population protocols are small number of states per agent and fast stabilization time. We present a fast population protocol for the exact-majority problem which uses $Θ(\log n)$ states (per agent) and stabilizes in $O(\log^{5/3} n)$ parallel time (i.e., $O(n\log^{5/3} n)$ interactions) in expectation and with high probability. Alistarh et al. [SODA 2018] showed that any exact-majority protocol which stabilizes in expected $O(n^{1-ε})$ parallel time, for any constant $ε> 0$, requires $Ω(\log n)$ states. They also showed an $O(\log^2 n)$-time protocol with $O(\log n)$ states, the currently fastest exact-majority protocol with polylogarithmic number of states. The standard design framework for majority protocols is based on $O(\log n)$ phases and requires that all nodes are well synchronized within each phase, leading naturally to upper bounds of the order of at least $\log^2 n$ because of $Θ(\log n)$ synchronization time per phase. We show how this framework can be tightened with {\em weak synchronization} to break the $O(\log^2 n)$ upper bound of previous protocols.

We study consensus processes on the complete graph of n nodes. Initially, each node supports one up to n different opinions. Nodes randomly and in parallel sample the opinions of constantly many nodes. Based on these samples, they use an update rule to change their own opinion. The goal is to reach consensus, a configuration where all nodes support the same opinion.

We consider the model of population protocols, which can be viewed as a sequence of random pairwise interactions of n agents (nodes). During each interaction, two agents v and w selected uniformly at random update their states on the basis of their current states, and the whole system should in long run converge towards a desired global final configuration. We study population protocols for two problems: the leader election and the exact majority voting. Both protocols use Θ(log2 n) states per agent and run in O(log2 n) rounds (the number of interactions divided by n), w.h.p. and in expectation, improving on the running time of the Θ(log2 n)-state protocols proposed recently by Alistarh et al. [SODA 2017]. Our protocols are based on the idea of agents counting their local interactions and rely on the probabilistic fact that the uniform random selection would limit the divergence of the individual counts.

We consider distributed plurality consensus on a complete graph of size n with k initial opinions in the following asynchronous communication model. Each node is equipped with a random Poisson clock with parameter lambda=1. Whenever a node's clock ticks, it samples some neighbors uniformly at random and adjusts its opinion according to the sample.

In this paper we consider a wide class of discrete diffusion load balancing algorithms. The problem is defined as follows. We are given an interconnection network and a number of load items, which are arbitrarily distributed among the nodes of the network. The goal is to redistribute the load in iterative discrete steps such that at the end each node has (almost) the same number of items. In diffusion load balancing, nodes are only allowed to balance their load with their direct neighbors. We show three main results. Firstly, we present a general framework for randomly rounding the flow generated by continuous diffusion schemes over the edges of a graph in order to obtain corresponding discrete schemes. Compared to the results of Rabani, Sinclair, and Wanka, FOCS'98, which are only valid w.r.t. The class of homogeneous first order schemes, our framework can be used to analyze a larger class of diffusion algorithms, such as algorithms for heterogeneous networks and second order schemes. Secondly, we bound the deviation between randomized second order schemes and their continuous counterparts. Finally, we provide a bound for the minimum initial load in a network that is sufficient to prevent the occurrence of negative load at a node during the execution of second order diffusion schemes. Our theoretical results are complemented with extensive simulations on different graph classes. We show empirically that second order schemes, which are usually much faster than first order schemes, will not balance the load completely on a number of networks within reasonable time. However, the maximum load difference at the end seems to be bounded by a constant value, which can be further decreased if first order scheme is applied once this value is achieved by second order scheme.

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n, and loose if m > n. In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O(log n) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = (1 + ϵ) · n and constant ϵ, they achieve a step complexity of O(log log n). In this paper we consider tight as well as loose renaming and introduce randomized algorithms that achieve their tasks with high probability. The model assumed is the asynchronous shared memory model against an adaptive adversary. Our algorithm for loose renaming maps n processes to a name space of size m = (1+2/(log n)ℓ)·n = (1+o(1))·n performing O(ℓ · (log logn)2) test-and-set operations. In the case of tight renaming, we present a protocol that assigns n processes to n names with step complexity O(log n), but without the overhead and impracticality of the AKS network. This algorithm utilizes modern hardware features in form of a counting device which is also described in the paper. This device may have the potential to speed up other distributed algorithms as well.

Information dissemination is a fundamental problem in parallel and distributed computing. In its simplest variant, known as the broadcasting problem, a single message has to be spread among all nodes of a graph. A prominent communication protocol for this problem is based on the socalled random phone call model (Karp et al., FOCS 2000). In each step, every node opens a communication channel to a randomly chosen neighbor, which can then be used for bidirectional communication. Motivated by replicated databases and peer-to-peer networks, Berenbrink et al., ICALP 2010, considered the so-called gossiping problem in the random phone call model. There, each node starts with its own message and all messages have to be disseminated to all nodes in the network. They showed that any O(log n)-time algorithm in complete graphs requires Ω(log n) message transmissions per node to complete gossiping, with high probability, while it is known that in the case of broadcasting the average number of message transmissions per node is O(log log n). Furthermore, they explored different possibilities on how to reduce the communication overhead of randomized gossiping in complete graphs. It is known that the O(nloglogn) bound on the number of message transmissions produced by randomized broadcasting in complete graphs cannot be achieved in sparse graphs even if they have best expansion and connectivity properties. In this paper, we analyze whether a similar influence of the graph density also holds w.r.t. the performance of gossiping. We study analytically and empirically the communication overhead generated by gossiping algorithms w.r.t. the random phone call model in random graphs and also consider simple modifications of the random phone call model in these graphs. Our results indicate that, unlike in broadcasting, there seems to be no significant difference between the performance of randomized gossiping in complete graphs and sparse random graphs. Furthermore, our simulations illustrate that by tuning the parameters of our algorithms, we can significantly reduce the communication overhead compared to the traditional push-pull approach in the graphs we consider.

In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues a random walk through the graph. Let $G=(V,E)$ be an undirected and connected graph with $n$ vertices and $m$ edges. The coalescence time, $C(n)$, is the expected time for all particles to coalesce, when initially one particle is located at each vertex. We study the problem of bounding the coalescence time for general connected graphs and prove that $C(n) = O\big(\frac{1}{1-\lambda_2}\big(\log^{4} n + \frac{n}{\nu}\big)\big)$. Here $\lambda_2$ is the second eigenvalue of the transition matrix of the random walk. To avoid problems arising from, e.g., lack of coalescence on bipartite graphs, we assume the random walk can be made lazy if required. The value of $\nu$ is given by $\nu= \sum_{v\in V} d^2(v)/(d^2n)$, where $d(v)$ is the degree of vertex $v$, and $d=2m/n$ is the average degree. The parameter $\nu$ is an indicator of the variability of vertex degrees: $1 \le \nu = O(n)$, with $\nu=1$ for regular graphs. Our general bound on $C(n)$ holds for all connected graphs. This implies, for example, that $C(n)=O(n/(1-\lambda_2))$ for $d$-regular graphs with expansion parameterized by the eigenvalue gap $1-\lambda_2$. The bound on $C(n)$ given above is sublinear for some classes of graphs with skewed degree distributions. In the voter model, initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. Let ${\mathbf{E}} (C_{{\mbox{\boldmath$v$}}})$ be the expected time for voting to complete, that is, for a unique opinion to emerge. A system of coalescing particles, where initially one particle is located at each vertex, corresponds to the voter model in that $\mathbf{E}(C_{{\mbox{\boldmath$v$}}})=C(n)$. Thus our result stated above for $C(n)$ also gives general bounds for $\mathbf{E}(C_{{\mbox{\boldmath$v$}}})$.

In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues the random walk through the graph. Coalescing random walks can be used to achieve consensus in distributed networks, and is the basis of the self-stabilizing mutual exclusion algorithm of Israeli and Jalfon [14].

Epidemic processes are widely used to design efficient distributed algorithms with applications in various research fields. In this paper, we consider a dynamic epidemic process in a certain (idealistic) urban environment modeled by a complete graph. The epidemic is spread among $n$ agents, which move from one node to another according to a power law distribution that describes the so called attractiveness of the corresponding locations in the urban environment. If two agents meet at some node, then a possible infection may be transmitted from one agent to the other.

We consider the problem of diffusion-based load balancing on a distributed network with n processors. If the load is arbitrarily divisible, then the convergence is fairly well captured in terms of the second largest eigenvalue of the diffusion matrix. As for many applications load can not be arbitrarily divided, we consider a model where load consists of indivisible, unit-size tokens. Quantifying by how much this integrality assumption worsens the efficiency of load balancing algorithms is a natural question which has been posed by many authors [9, 15, 16, 6, 19, 17].

We consider the following marking process (rw-rand) made by a random walk on an undirected graph G. Upon arrival at a vertex v, it marks v if unmarked and otherwise it marks a randomly chosen unmarked neighbor of v. We also consider a variant of this process called rw-r-rank. Here each vertex is assigned a global random rank first and then in each step, the walk marks the lowest ranked unmarked neighbor of the currently visited vertex. Depending on the degree and the expansion of the graph, we prove several upper bounds on the time required by these processes to mark all vertices. For instance, if G is a hypercube or random graph, our processes mark all vertices in time O(n), significantly speeding up the Θ(n log n)-cover time of standard random walks.

A Random Geometric Graph (RGG) in two dimensions is constructed by distributing n nodes independently and uniformly at random in and creating edges between every pair of nodes having Euclidean distance at most r, for some prescribed r. We analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that with probability 1 – (n−1) this algorithm informs every node in the largest connected component of an RGG within rounds. This holds for any value of r larger than the critical value for the emergence of a connected component with Ω(n) nodes. In order to prove this result, we show that for any two nodes sufficiently distant from each other in , the length of the shortest path between them in the RGG, when such a path exists, is only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest connected component of an RGG is , which surprisingly has been an open problem so far.

We introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs the intuition of Chandra et al. (1997) that ``the cover time of the graph is an appropriate metric for the performance of certain kinds of randomized broadcast algorithms''. In more detail, our results are as follows: \begin{itemize} \item For any graph $G=(V,E)$ of size $n$ and minimum degree $\delta$, we have $\mathcal{R}(G)= \mathcal{O}(\frac{|E|}{\delta} \cdot \log n)$, where $\mathcal{R}(G)$ denotes the quotient of the cover time and broadcast time. This bound is tight for binary trees and tight up to logarithmic factors for many graphs including hypercubes, expanders and lollipop graphs. \item For any $\delta$-regular (or almost $\delta$-regular) graph $G$ it holds that $\mathcal{R}(G) = \Omega(\frac{\delta^2}{n} \cdot \frac{1}{\log n})$. Together with our upper bound on $\mathcal{R}(G)$, this lower bound strongly confirms the intuition of Chandra et al.~for graphs with minimum degree $\Theta(n)$, since then the cover time equals the broadcast time multiplied by $n$ (neglecting logarithmic factors). \item Conversely, for any $\delta$ we construct almost $\delta$-regular graphs that satisfy $\mathcal{R}(G) = \mathcal{O}(\max \{ \sqrt{n},\delta \} \cdot \log^2 n)$. Since any regular expander satisfies $\mathcal{R}(G) = \Theta(n)$, the strong relationship given above does not hold if $\delta$ is polynomially smaller than $n$. \end{itemize} Our bounds also demonstrate that the relationship between cover time and broadcast time is much stronger than the known relationships between any of them and the mixing time (or the closely related spectral gap).

We consider broadcasting in random d-regular graphs by using a simple modification of the so-called random phone call model introduced by Karp et al. [19]. In the phone call model every time step each node calls on a randomly chosen neighbour to establish a communication channel with this node. The communication channels can then be used to transmit messages in both directions. We show that, if we allow every node to choose four distinct neighbours instead of one, then the average number of message transmissions per node decreases exponentially. Formally, we present a broadcasting algorithm that has time complexity O(log n) and uses O(n log log n) transmissions per message. In contrast, we show for the standard model that every distributed and address-oblivious algorithm that broadcasts a message in time O(log n) needs Ω(n log n/ log d) message transmissions. Our algorithm can efficiently handle limited communication failures, only requires rough estimates of the number of nodes, and is robust against limited changes in the size of the network. Our results have applications in peer-to-peer networks and replicated databases.

Broadcasting algorithms have a various range of applications in different fields of computer science. In this paper we analyze the number of message transmissions generated by efficient randomized broadcasting algorithms in random-like networks. We mainly consider the classical random graph model, i.e., a graph Gp with n nodes in which any two arbitrary nodes are connected with probability p, independently. For these graphs, we present an efficient broadcasting algorithm based on the random phone call model introduced by Karp et al. [21], and show that the total number of message transmissions generated by this algorithm is bounded by an asymptotically optimal value in almost all connected random graphs. More precisely, we show that if p ≥ logδ n/n for some constant δ > 2, then we are able to broadcast any information r in a random graph Gp of size n in O(log n) steps by using at most O(n max{log log n, log n/ log d}) transmissions related to r, where d = pn denotes the expected average degree in Gp. We also show that for these kind of graphs there is a a matching lower bound on the number of transmissions generated by any efficient broadcasting algorithm which works within the limits of the random phone call model. Please note that the main result holds with probability 1-1/nΩ(1), even if n and d are unknown to the nodes of the graph.The algorithm we present in this paper is based on a simple communication model [21], is scalable, and robust. It can efficiently handle restricted communication failures and certain changes in the size of the network, and can also be extended to certain types of truncated power law graphs based on the models of [1, 2, 5]. In addition, our methods and results might be useful for further research on this field.

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. We propose here several time efficient, centralized as well as fully distributed procedures for the broadcasting problem in random radio networks. In particular we show how to perform a centralized broadcast in a random graph Gp=(V,E) of size n=|V| and expected average degree d=pn in time O(ln n/lnd+lnd). Later we present a randomized distributed broadcasting algorithm with the running time O(ln n). In both cases we show that the presented algorithms are asymptotically optimal by deriving lower bounds on the complexity of radio broadcasting in random graphs. In these proofs we determine some structural properties in random graphs which may be of independent interest. We should note here that the results of this paper hold with probability 1-o(1/n).

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.