# On the Design and Analysis of Parallel
and Distributed Algorithms

1. Rajendra Purohit, K R Chowdhary 2. S D Purohit
1\. Dept. of CSE, Jodhpur Institute of Engineeering and Technology, Jodhpur
2\. Dept. of HEAS (Mathematics), RTU, Kota
Email: 1<EMAIL_ADDRESS><EMAIL_ADDRESS>2.
<EMAIL_ADDRESS>
###### Abstract

Arrival of multicore systems has enforced a new scenario in computing, the
parallel and distributed algorithms are fast replacing the older sequential
algorithms, with many challenges of these techniques. The distributed
algorithms provide distributed processing using distributed file systems and
processing units, while network is modeled as minimum cost spanning tree. On
the other hand, the parallel processing chooses different language platforms,
data parallel vs. parallel programming, and GPUs. Processing units, memory
elements and storage are connected through dynamic distributed networks in the
form of spanning trees. The article presents foundational algorithms,
analysis, and efficiency considerations.

###### Index Terms:

Distributed algorithm, parallel algorithm, distributed file system, graphic
processing unit, spanning tree, algorithm analysis, trust management, data
parallle computing, parallel programming.

##  I Introduction

This Paper explains the foundational algorithms as well as their design and
analysis for parallel processing as well as those used in distributed
processing using graphs. The type of algorithms are governed by the nature of
data, which are huge in size (bigdata) as well they are distributed
geographically. This nature of data enforces to have processing to be
enormously fast – that leads to parallel processing – fortunately the multi-
core systems are common, and the parallel algorithms can explore the full
power of these processors.

The other aspect of data is that they are not collected/created and stored at
a geographic location, rather it is distributed in nature. This requires that
processors be also distributed, with coordination to such an extent that it
does not limit the scalability of the entire system.

In addition to distributing the processing, there is need of trust management
in the distributed system, which is mathematically proven.

The parallelism is basically two types – parallel programming, where sections
of a program or different programs are run in parallel, or there is data-
parallel programming – assign an individual data element to a separate logical
core for processing.

Graphic processing units (GPUs) are common for parallel processing, while for
distributed processing, it requires to provide least cost path between
distributed processing units, such that average distance of communication as
small as possible. In such a system, if there are thousand steps in a typical
algorithm, and it run in distributed manner using thousand processing units,
ideally it will complete the job in single step. To connect all geographically
distributed components, it requires to construct as minimum cost path without
any loops, called spanning tree. Thus, the design and analysis part of
distributed and parallel processing needs construction of spanning-tree. This
paper presents the study, design and analysis of some sequential and parallel
minimum spanning-tree construction algorithms.

##  II Distributed Algorithms

In the present era of Internet, there has been a enormous in crease of volume
of data to be processed, called big data, and we are witnessing a continuous
increase of computational power that produces an overwhelming flow of data
which has called for a paradigm shift in the computing architecture as well as
large-scale data processing methods.

It is important to evaluate the performance of distributed systems and the
corresponding algorithms. One of the measure is efficiency of distributed
algorithms, and the significant part of it is the running time, that is, the
number of rounds of distributed communication.

Many fundamental network problems such as minimum spanning tree, shortest
paths, etc., are addressed in computing the efficiency of distributed network.
In particular, there has been much attempts to design very fast distributed
approximation algorithms which are even faster at the cost of producing
suboptimal solutions, for many of these problems. Such algorithms are useful
for large-scale resource-constrained and dynamic networks where running time
is crucial [2].

Almost all the distributed algorithms are modeled in the form of Graph
Algorithms. The Analysis of graphical data is computationally expensive, as
most real-world networks can contain millions of nodes and edges – need for
efficient search and classification algorithms is common when they are
deployed on the higher-dimensional data structures. Many of the graph
algorithms can be implemented using matrix-based computing making use of GPUs
(Graphics Processing Units) and always outperform the CPUs for graph analysis
tasks, e.g., triangles counting.

One of the essential graph algorithms for NPUs (Network processing units) is
shortest-path finding [5]. For any graph $G(V,E)$, where $V$ is set of
vertices and $E$ is set of edges, goal of a community detection task is to
identify subsets of $V$ that can be considered “related.” This problem is
encountered in many scientific fields where structured, relational data is
generated, and in social networks where people are related due to certain
common attributes. Many algorithms exist for solving such problems, and there
is wide use of interacting spin systems in solving community detection
problems, which have been shown to be resolution-limit free.

##  III Distributed File System

A file system provides long-term storage by implementing files-named objects
that exist from their explicit creation time until their explicit destruction,
and are not effected due to temporary failures in the system. In distributed
network and distributed processing, a distributed implementation of classical
time-shared model of file system is used, called DFS (distributed file
system), where multiple users share files and storage resources.

Structure of DFS comprises service, server and client. The processes invokes
services through a set of operations through the client interface. A file
system provides file services to clients, like, create and delete files,
read/write into files. In a DFS, the clients, servers and storage devices are
dispersed among the machines in a distributed manner. Hence, the service
activity has to be carried out across the network instead of a centralized
data repository. However, the concrete configurations and implementations
vary. A DFS can be implemented as part of a distributed system, or
alternatively by a software layer whose task is to manage communication
between conventional operating system and the file system. The overall storage
space managed by a DFS consists of different and remotely located devices.

The file naming convention in DFS is Unix like hierarchical file system, i.e.,
host:local-name. Remote file systems are joined to create a global name
structure, often by mount mechanism, e.g.,

$\displaystyle mount~{}~{}$ $\displaystyle/dev/sda1~{}~{}/$ $\displaystyle
mount~{}~{}$ $\displaystyle/dev/sda2~{}~{}/home$ $\displaystyle mount~{}~{}$
$\displaystyle/dev/sda3~{}~{}/home/data$

where $sda1$, $sda2$, $sda3$ are physical volumes which appear as root, /home,
and /home/data directories, respectively. All the mount operations are
recorded by the operating system kernel in a mount table, like $/etc/fstab$ in
Unix, which is redirect name lookup to the appropriate file systems. All the
read-writes to shared files are transparently visible to all the clients.

The other scheme for file-system is NFS (network file system), which uses RPC
(remote procedure call) that defines the protocols functionality. Here, a
server file may be mounted locally, e.g., $server1:/usr/shared$ over the
client $client:/usr/local$. The original directory $/usr/local$ is not visible
any more.

A DFS, where instead of being local and available only for access to limited
local users, is made available for access to users globally through a DFS,
provides access and updating globally through the users distributed
geographically. While having this facility it should also provide all the
features, like, consistency, security, availability, scalability, and
efficiency. One such file system is Google File System (GFS) [6].

##  IV Trust management in Distributed Systems

The distributed systems are designed to allow transactions that can cross
domains and organizations, where all the domains cannot be trusted at the same
level. Even within the same domain, users’ trustworthiness can differ. A
flexible and general-purpose trust management system can maintain current and
consistent trustworthiness information for the different entities in a
distributed system [7].

One of the standard models for describing trust and trust establishment is
public-key cryptography. When a user generates a public/private key pair, it
registers its pubic CA (certifying authority) and has the CA certify it. If
the same CA certifies two users and they want to communicate securely, they
need only exchange their certificates. If different CAs certify two users,
they must confirm from higher-level CAs, which certify their CAs. This
constructs a hierarchical structure of CAs.

In a distributed recommendation-based trust model, users propose conditional
transition of trust, which hypothesizes that trust is transitive under some
conditions. For example, if user/system $A$ trusts $B$, and $B$ trusts $C$, we
cannot simply conclude that $A$ trusts $C$, because trust generally is not
transitive. We can only conclude that $A$ trusts $C$ if the following
conditions holds true:

  * -

$B$ recommends its trust in $C$ to $A$ explicitly;

  * -

$A$ trusts $B$ as a recommender; and

  * -

$A$ judges $B$’s recommendation and decide how much it will trust $C$,
irrespective of $B$’s trust in $C$.

This trust model’s motivation comes from human society, where human beings get
to know each other via direct interaction and through a grapevine
communication111Gleaning information from places other than the official
source of relationships. The same is true in distributed systems. In a large
distributed system, every entity cannot obtain first-hand information about
all other entities. As an option, entities can rely on second-hand information
or recommendations. However, because recommendations have an uncertainty or
risk, entities need to know how to cope with second-hand information.

The distributed trust models follow asymmetrical trust, which assumes either
of two types of trust relationships: direct trust and recommender trust. The
model categorizes a trust relationship between two entities in terms of
different interactions. The direct trust relationship is peer-to-process.
However, the distributed processes use recommendation protocol. Following
example illustrates the computation of trust worthiness of recommendation.

Example 1.: Consider that an entity $A$ needs a service from entity $D$ (say
car service). $A$ knows nothing about the quality of $D$’s service, so $A$
asks $B$ for a recommendation with respect to the car service category,
assuming that $A$ trusts $B$’s recommendation within this category. When $B$
receives this request and finds that it does not know $D$ either, $B$ forwards
$A$’s request to $C$, which has $D$’s trustworthiness information within the
car service category. Then $C$ sends a reply to $A$ with $D$’s trust value.
The path $A\times B\times C\times D$ is the recommendation path.

Following formula calculates the trust value ($tv_{T}$) from the returned
values :

$tv_{T}=[rtv(1)/4]\times[rtv(2)/4]\times...\\\
\times[rtv(i)/4]\times...\times[rtv(n)/4]\times tv(T),$ (1)

where $rtv(i)$ is the trust value of the $i$th recommender in the
recommendation path, $tv(T)$ is the trust value of target $T$ returned by the
last recommender, and $tv_{T}$ is the calculated trust value of target $T$.
$\Box$

##  V Data-parallel Computing

The ultimate objective of parallel computing is to provide high performance.
Although often it’s just to ensure that software is doing precisely what it is
supposed to, there are many cases where it is vital to get down to the basic
characteristics of the processor. Until recently, performance improvement was
not difficult. Processors just kept getting faster. Waiting about a year for
the customer’s hardware to be upgraded was a valid optimization strategy. In
most new systems, however, individual processors don’t get much faster;
systems just get more of these processors.

Though in the beginning, coding paradigms were targets for multiple-processor
cores, but the data-parallel paradigm is a new approach which is easier to
code and easier to implement at processor manufacturing stage.

Although the rate at which the processor-performance grows is phenomenal, and
it is only limited by the fundamental laws of physics. By 2003, the laws of
physics (power and heat) had put an end to growth in clock speed,
consequently, the silicon area requirements for increasingly sophisticated ILP
(instruction-level parallelism) schemes (branch prediction, speculative
execution, etc.) became prohibitive. Today the only remaining basis for
performance improvement is gate count [4]. Recognizing these facts,
manufacturing processes got restructured to stop pushing clock rate, but
focused on gate count, which allows for more cores. However, the real benefits
comes only when software becomes capable of scaling across all those new
cores. This is the challenge that performance software faces in the coming
years.

###  V-A Parallel Programming

Parallel programming is a challenging, and goes against many features in the
high level programming languages, e.g., we deprecate the use of GOTO
statements in most languages, however parallel execution is like having them
randomly sprinkled throughout the code during execution. The assumptions about
order of execution in the code that are mastered by programmers in their early
education no longer apply.

The single-threaded von Neumann model is easy to comprehend because it is
based on deterministic processing. The parallel code is subject to errors such
as and live-lock, race conditions, etc., that can become extremely subtle and
difficult to discover, because a bug may not repeat, and it is highly
nondeterministic in nature. These issues are so severe that despite decades of
effort and dozens of different approaches, none has really gained significant
adoption.

In the following, we present some standard terms and analysis for parallel
execution.

###### Definition 1

Speedup. Speedup of a parallel algorithm running on $P$ processors is the
running time of the fastest known serial algorithm running on a single
processor of a $P$-processor computer divided by the running time of the
parallel algorithm running on the same $P$-processor computer using all $P$
processors. $\Box$

###### Definition 2

Efficiency. Efficiency of a parallel algorithm running on $P$ processors is
the speed-up of the algorithm divided by the number of processors, $P$. $\Box$

Efficiency is a measure of how much a parallel algorithm takes advantage of
the parallelism of the problem.

An equally subtle challenge is performance scaling. Amdahl’s law states that
the maximum speedup attainable by parallelism is the reciprocal of the
proportion of code that is not parallelizable. If $10$ percent of a given code
base is not parallel, it is not possible to attain even tenfold speedup even
on an infinite number of processors.

###### Definition 3

Amdahl’s Law: Given that $f$ is a fraction of operations in a computation that
are perfectly sequential, maximum speedup achievable by parallel computer with
$P$ processors for this computation is:

$S_{max}(P)=\frac{1}{(f+\frac{(1-f)}{P})},$ (2)

where $S_{max}(P)$ is maximum speedup. $\Box$

Example 2. Considering that $20$ percent of the instructions in a particular
parallel algorithm are sequential in nature. An implementation of it is run on
a parallel computer with $16$ processors. Here $f=0.2$ and $P=16$, so the
maximum speed-up is $1/(0.2+0.8/16)$ or $4.0$. The maximum efficiency would be
$4.0/16=0.25$. If $P=100$, the maximum speedup is $1/(0.2+0.8/100)$ or only
$4.807$, and maximum efficiency would be $4.807/100=0.048$. $\Box$

The above example shows that arbitrary increase in number of processors
decrease the efficiency! However, this example may be a useful guideline, but
how much of the code ultimately runs in parallel is very difficult to predict.
Serialization of the code may arise unexpectedly as a result of contention for
a shared resource or when there is need to access too many distant memory
locations, as each instruction executed must commit to data to avoid any data
inconsistency for the remaining processing.

The traditional methods of parallel programming (thread control via locks,
message-passing interface, etc.) often have limited scaling ability because
these mechanisms can require serialization phases that actually increase with
core count [11]. If each core has to synchronize with a single core, that
produces a linear growth in serial code, but if each core has to synchronize
with all other cores, there can be a combinatoric increase in serialization.

There is a more fundamental issue with performance scaling. A common approach
in multicore parallel programming for games is to start with top-down
breakdown where relatively isolated codes are assigned to separate cores, but
there is problem when number of subsystems in the code base is reached to
maximum. Because restructuring of code at this level can be pervasive, and it
often requires a major rewrite to break out subsystems at the next finer
level, and again for each hardware generation. Due to all these reasons, the
transition of a major code base to parallel paradigms can be time consuming.

In fact, often the rate of core-count growth may outstrip our ability to adapt
to it, i.e., to adopt the practice of writing the code to take advantage of so
many cores. Thus, need to look for a new paradigm ideally one that scales with
core count but without requiring restructuring of the application
architecture. It is about choosing a paradigm that operates well and scales
with an increasing number of cores without requiring code changes.

###  V-B Data-parallel Programming

The difficulty multicore systems is of finding enough subsystem tasks to
assign to these cores. On the other side, the data-parallel approach simply to
assigns an individual data element to a separate logical core for processing.
Instead of breaking code down by subsystems, data-parallel system looks for
fine-grained inner loops within each subsystem and parallelize these loops.
For some tasks, there may be thousands to millions of data elements, enabling
assignment to thousands of cores. For example, a modern GPU can support
hundreds of ALUs (arithmetic logic units) with hundreds of threads per ALU for
nearly $10,000$ data elements on the die at once.

The concept of data-parallel processors began with the efforts to create wider
and wider vector machines. This has created a variety of fine-grained or data-
parallel programming environments. Many of these have achieved recent
visibility by supporting GPUs.

  * •

Older languages (C*, MPL, Co-Array Fortran). Several languages have been
developed for fine-grained parallel programming and vector processing. Many
add only a very small difference in syntax from well-known programming
languages. Few of them support a variety of platforms and they may not be
available commercially or be supported long term as far as updates,
documentation, and materials.

  * •

New languages (XMT-C, CUDA, CAL). These languages are developed by the
hardware manufacturers and therefore they are well supported. They are also
very close to current C++ programming models syntactically.

  * •

Array-based languages (RapidMind, Acceleware, Microsoft Accelerator). These
languages are based on array data types, the algorithms converted to these
languages result in shorter, clearer, and faster code. The challenge of
restructuring design concepts into array paradigms is a barrier to adoption of
these languages due to the high level of the requirement of high level of
abstraction.

  * •

Graphics APIs (OpenGL, Direct3D). Recent research in GPGPU (general-purpose
computing on graphics processing units) has found that while the initial ramp-
up of using graphics APIs can be difficult, they do provide a direct mapping
to hardware that enables very specific optimizations, as well as access to
hardware features that other approaches may not allow.

##  VI Graphic Processing Units

The recent decades in the processor design have led to an increasingly
heterogeneous computing environment – the multicores were commonly used in
conjunction with accelerators such as Graphics Processing Units (GPUs).
Consequently, the parallelism together with heterogeneity resulted in
programming a challenging work, as it required the knowledge of every new
language, and also of every new architectures, for developing applications.
Despite the advancements in compilation, auto-parallelization, and auto-
tuning, the programmers have to deal with low-level languages such as OpnCL
and CUDA [8].

This dramatic shift was an inevitable consequence of consumer demand for
video-games, advances in manufacturing technology, and the exploitation of the
inherent parallelism in the feed-forward graphics pipeline. Today, the raw
computational power of a GPU dwarfs that of the most powerful CPU, and the gap
is steadily widening.

Presently, the GPUs have in fact moved away from the traditional fixed-
function 3D graphics pipeline toward a flexible general-purpose computational
engine. Today, GPUs can implement many parallel algorithms directly using
graphics hardware, that are well-suited to leverage all the underlying
computational horsepower, and often achieves tremendous speedups. Truly, the
GPU is the first widely deployed commodity desktop parallel computer [9].

The GPUs have evolved from a hardwired implementation of the graphics pipeline
into a programmable computational unit where fixed-function units for
transforming vertices and texturing pixels have been subsumed by a unified
grid of processors. This evolution has evolved over a long time and it has
gradually replaced the individual pipeline stages with large number of
programmable units.

The highly parallel nature of workload of real-time computer graphics demands
high arithmetic throughput and streaming memory bandwidth but at the same time
it tolerates considerable latency in an individual computation. This is
because the final images are only displayed every $16$ milli-secs. These
workload characteristics have reshaped the GPU architecture, whereas CPUs are
optimized for low latency, while GPUs are optimized for high throughput.

###  VI-A GPUs as Data-parallel Machines

A GPU typically has a single array of processors that perform the
computational work of each stage in conjunction with specialized hardware.
After polygon-vertex processing, a specialized hardware interpolator unit is
used to turn each polygon into pixels for the pixel-processing stage. This
unit can be thought of as an address generator. At the end of the pipeline,
another specialized unit blends completed pixels into the image buffer. This
hardware is often useful in accumulating results into a destination array.
Further, all processing stages have access to a dedicated texture-sampling
unit that performs linearly interpolated reads on 1D, 2D, or 3D source arrays
in a variety of data-element formats.

A GPU’s memory subsystem is designed for higher I/O latency to achieve
increased throughput, which assumes only very limited data reuse (locality in
read/write access), featuring small input and output caches designed more as
FIFO (first in, first out) buffers than as mechanisms to avoid round-trips to
memory.

There are interesting algorithms for GPU processing. For example, compacting
an array of variable-length records is a task that has a data-parallel
implementation on the parallel prefix sum or scan. The prefix-sum algorithm
computes the sum of all previous array elements (i.e., the first output
element in a row $r$ is $r_{0}$, while the second is $o_{1}=r_{0}+r_{1}$, and
the $n$th output element is $o_{n}=r_{0}+r_{1}+...+r_{n-1})$. Using this, a
list of record sizes can be accumulated to compute the absolute addresses
where each record element is to be written. Then all the writes can occur
completely in parallel.

###  VI-B Making Data-parallel

How to make the data parallel? Before starting to write the code, one should
ensure that the known data are data-parallel cases. There are library routines
available for accelerating common tasks using data-parallel hardware. Most
data-parallel programming environments include such libraries as a convenient
way for users to begin adopting their technology.

For writing custom data-parallel code, the process is similar to a localized
optimization effort. One can adopt data-parallel programming incrementally,
since it is possible to identify and optimize the key inner loops one at a
time, without disturbing the larger-scale structure of the code base.
Following are the basic steps for converting a code to the data-parallel
model:

  1. 1.

Identify a key task that looks data-parallel,

  2. 2.

Identify a data-parallel algorithm for this task,

  3. 3.

Select a data-parallel programming environment,

  4. 4.

Implement code,

  5. 5.

Evaluate performance scaling rate,

  6. 6.

repeat from step 1 required .

For identification of task that look parallel, we look for a segment of code
that does not rely greatly on cross communication between data elements, or
conversely, a set of data elements, that can be processed without requiring
too much knowledge of each other. Also, look for the data-access patterns that
be regularized, as opposed to arbitrary/random (e.g., linear arrays, as
opposed to sparse-tree data structures). While searching for candidates to
parallelize, one can evaluate performance potential via Amdahl,s law, and
check if the total performance change. If there is not significant
improvement, going through the effort of parallelizing will not pay off.

##  VII Spanning Trees

A spanning tree of a graph is just a subgraph that contains all the vertices
and is a tree. A graph may have many spanning trees; for instance, the
complete graph with three vertices [Fig. 1(a)] has three spanning trees, shown
in Fig. 1(b).

Figure 1: (a) Graph with three vertices, (b) Spanning Trees for the Graph
shown in (a)

If edges of the graph have weights proportional to their lengths, then weight
of a spanning tree is the sum of the weights of its edges that makes the
spanning tree. Obviously, different trees have different weights. The problem
is to find the minimum-length (minimum weight) spanning tree. This problem can
be solved through different approaches and there are several algorithms,
depending on the assumptions made [1]. If there is a path visiting some
vertices more than once, one can always drop some edges to get a tree.
Therefore, in general the minimum-cost spanning tree (MST) weight is less than
the total spanning tree weight, because it is minimization over a strictly
larger set. One of the problems in spanning tree is to find the minimum-cost
spanning tree.

Consider that seven computers $\\{a,b,c,d,e,f,g\\}$ are connected in the
manner shown in Fig. 2(a) making vertices set $V$ of a small laboratory
network such that a computer is able to communicate with one or more other
computers.

Figure 2: (a) A Graph, (b) The minimum-cost Spanning Trees for the Graph shown
in (a) [1]

The problem to be solved is to retain all the computers connected and remove
certain links in the network such that the total cost for constructing all the
links is minimum, that is, some path exists from every computer to every other
computer. This new network consists of all the vertices of Fig. 2(a), but the
edges are subset of original. It is called minimum-cost spanning tree of the
original graph, and is shown in Fig. 2(b). For a spanning tree to exist, it is
necessary that the graph is connected.

A simple, though inefficient approach, can be to find all the spanning trees,
and then find the minimum-cost tree out of those. The minimum-cost is the one
having least sum of weights of arcs constructing the tree. A better idea is to
find some key property of the MST that guarantees that some edge is part of
it, and use this property to build up the MST by adding single edge at a time.
The construction of such an optimal spanning tree can be accomplished by using
the algorithm developed by Joseph Kruskal – called Kruskal’s algorithm, and
Robert Prim – called Prim’s algorithm.

Like Dijkstra,s shortest path algorithm, these algorithms are greedy, as each
of them uses at each step an optimal choice (here minimal) out of the
available data. If that choice is minimal, locally as well as globally, then
the algorithm will lead to an optimal tree.

###  VII-A Kruskal’s Algorithm

Assume that $G=(V,E)$ is an undirected loop-free connected graph where
$|V|=n$, and each edge $(a,b)$ is assigned a positive real number,
corresponding to its weight $wt(a,b)$. Assume that minimum-cost spanning tree
corresponding to $G$ is $G^{\prime}=(V^{\prime},E^{\prime})$, since vertices
in both the graphs are same, hence, $V=V^{\prime}$. To begin with, we set
$E^{\prime}$ equal to null ($\phi$). The algorithm (shown as Algorithm 1)
picks up smallest weight edge from $E$ and adds it into the set $E^{\prime}$
provided that this addition does not create a loop. This process is repeated
until $G^{\prime}$ becomes a connected graph, i.e., all the vertices become
connected, resulting to a spanning tree [1].

Algorithm 1 Kruskal-algorithm (Input: Graph $G=(V,E)$, Output: Spanning tree
$G^{\prime}=(V^{\prime},E^{\prime})$)

1: $V^{\prime}=V$

2: $E^{\prime}=\phi$

3: $G^{\prime}=(V^{\prime},E^{\prime})$

4: while $G^{\prime}$ is not connected do

5: select the smallest edge $(a,b)\in E-E^{\prime}$ such that adding $(a,b)$
in $E^{\prime}$ does not create cycle in $G^{\prime}$

6: if such $(a,b)$ exists then

7: $E^{\prime}=E^{\prime}\cup\\{(a,b)\\}$

8: end if

9: end while

10: end

The above algorithm is greedy since it selects from the remaining edges in
$G$, an edge of minimal weight that does not add a cycle when it is added into
$G^{\prime}$.

#### Analysis

Considering that there are $n$ vertices in the graph. Hence there can be at
the worst $n^{2}$ number of edges, i.e., from each vertex to every vertex,
including to itself. Total number of edges to be selected in MST is $n-1$. To
select these edges to be of minimum weights, all the edges are assumed to be
in a heap, which will require $(n-1)\log n^{2}$ time. This gives a time
complexity $O(n\log n)$. However, this computation is for a single memory
system, and not for distributed system.

###  VII-B Prim’s Algorithm

This algorithm was discovered in 1930 by mathematician Vojtech Jarnik and
later independently by the computer scientist Robert Clay Prim in 1957 and
rediscovered by Dijkstra in 1959. The Prim’s algorithm finds a minimum
spanning tree for a connected weighted graph. If the graph is not connected
then it will give a minimum spanning tree for one of the connected components.
The algorithm 2 is Prim’s algorithm [1].

The Prim’s algorithm (shown as Algorithm 2), also called Dijkastra-Jarnik-prim
Algorithm, runs in time $O(m\log n)$ time. It grows with one edge at a time.
Initially, $T$ is an arbitrary vertex. In each step of this algorithm, $T$ is
augmented with the least-cost edge $(x,y)$ such that $x\in T$ and $y\notin T$.
By the cut property, all the edges added to $T$ are in MSF (minimum spanning
forest). The MSF problem asks for a spanning acyclic subgraph of $G$ having
the least total weight. It is assumed that input graph is connected.

Algorithm 2 Prim’s-algorithm (Input: Graph $G=(V,E)$, Output: Spanning tree
$T=(V_{T},E_{T})$)

1: % Create Tree $T=(V_{T},E_{T})$ with arbitrarily chosen single vertex from
graph $G=(V,E)$

2: Let $E^{\prime}=E$, $E_{T}=\phi$, $V_{T}=\\{u\\}$ {$u\in V$ is an arbitrary
vertex }

3: while $|V_{T}|<|V|$ do

4: remove $(u,v)\in E^{\prime}$ of minimum weight such that $u\in V_{T}$ but
$v\notin V_{T}$, and addition of $(u,v)$ does not create a cycle in $T$

5: $V_{T}=V_{T}\cup\\{v\\}$

6: $E_{T}=E_{T}\cup\\{(u,v)\\}$

7: end while

8: end

#### Analysis

In Prim’s algorithm, one always chooses the minimum edge whose one vertex is
in the already constructed tree and other is outside, and it’s addition should
not create a cycle in the MST constructed so far. Choosing minimum can be done
by keeping all the edges of original graph $G=(V,E)$ in a priority queue or in
a heap. Since number of edges for $|V|=n$ can be at the worst $n^{2}$, it will
take $(n-1)\log n^{2}$ time like in Kruskal’s Algorithm. Since number of
choices are limited to only the edges connecting from the vertices present in
the so far constructed tree, it will reduce the figure $n-1$ but not $n^{2}$.
This improves the average-case performance of Prim’s algorithm but note the
worst-case, when compared with Kruskal’s algorithm.

Two commonly used algorithms for the classical minimum spanning tree problem
are Prim’s algorithm and Kruskal’s algorithm. However, it is difficult to
apply these two algorithms in the distributed message-passing model. The main
challenges are:

  * •

Both Prim’s algorithm and Kruskal’s algorithm require processing one node or
vertex at a time, making it difficult to make them run in parallel. E.g.,
Kruskal’s algorithm processes edges in turn, and not to add an edge in the MST
that would form a cycle with edges already chosen.

  * •

Both these algorithms require processes to know the state of the whole graph,
which is very difficult to discover in the message-passing model.

##  VIII Minimum spanning tree algorithms for Distributed Systems

The message-passing model is one of the most commonly used models in
distributed computing. In this model, each process is modeled as a node of an
undirected graph $G=(V,E)$, where $V$ is set of vertices and $E$ is set of
edges. The communication channel between two processes is an edge of the
graph. Fig. 3 shows a graph that represents a distributed processing network.

Figure 3: A distributed network with minimum spanning Tree

The distributed minimum spanning tree (MST) problem involves the construction
of a minimum spanning tree by a distributed algorithm, in a network where
nodes communicate by message passing. It is radically different from the
classical sequential problem, although the most basic approach resembles
Borůvka’s algorithm, also called Sollin’s algorithm, which is the earliest
known MST algorithm [3]. This algorithm is simple: It proceeds in a sequence
of stages, and in each stage, or Borůvka step, it identifies a forest $F$
consisting of minimum-weight edge incident to each vertex in the graph $G$,
then forms the graph $G_{1}=G-F$ as input to the next stage. Here $G-F$
denotes the graph derived from $G$ by contracting the edges in $F$. Each
Borůvka step takes linear time, and since the number of vertices is reduced by
at least half in each step, Borůvka’s algorithm takes $O(m\log n)$ time, where
$m$ is number of edges and $n$ is number of vertices.

Efforts to find the minimum spanning tree of a weighted, connected, undirected
graph in parallel have focused on the three classical algorithms: Sollin’s
[1977] algorithm, the Prim-Dijkstra algorithm [1980], and Kruskal’s [1983]
algorithm [10].

The Table I shows the summary of comparison of these algorithms. The terms
Systolic array222In parallel computer architectures, a systolic array is a
homogeneous network of tightly coupled data processing units (DPUs) called
cells or nodes., SIMD, Tree, MIMD stand for multiprocessor architectures.

TABLE I: Parallel Minimum spanning Tree Algorithms Method | Architecture | year | Complexity | No. of
---|---|---|---|---
|  |  |  | Processors
Kruskal | Systolic Array | 1972 | $O(n^{2})$ | $n^{2}$
Sollin(1) | SIMD | 1977 | $O(\log^{2}n)$ | $n^{2}/\log n$
Prim-Dijkstra | Tree | 1980 | $O(n\log n)$ | $n/\log n$
Sollin(2) | SIMD | 1982 | $O(\log n)$ | $n^{3}$
Kruskal(2) | MIMD | 1983 | $O(\log m)$ | $m$

#### Parallel Algorithm

Sollin’s algorithm (Sollin(2) in table I) is the most obvious algorithm for
investigation. This algorithm starts with a forest of $n$ isolated vertices,
with every vertex regarded as a tree. In an iteration, the algorithm
simultaneously determines for each tree in the forest the smallest edge
joining any given vertex in that tree to a vertex in some other tree. All such
edges are added to the forest, the exception is that no two trees are joined
by more than one edge. (Ties that cause a cycle, are resolved arbitrarily.)
This process continues until there is only one tree in the forest – the
minimum spanning tree.

Since the number of trees is reduced by a factor of at least two in each
iteration, Sollin’s algorithm requires at most $\log n$ iterations to find the
minimum spanning tree [10]. An optimal algorithm uses a procedure called
Boruvka2. This procedure executes two Borůvka steps on input graph $G$ and
returns the contracted graph $G^{\prime}$ as well as the edge set $F$. Fig. 4
shows the performance MSP construction using Borůvka’s algorithm and its
improved algorithm (split) for graphs of 1000, 3000 and 5000 nodes. These
graphs show the performance in time as a function of number of threads (the
parallel processing elements). The Boruvka2 algorithm distinctly outperforms
the Boruvka algorithm.

(a) 1000 nodes MSP

(b) 3000 nodes MSP

(c) 5000 nodes MSP

Figure 4: Results for construction of MST in a parallel System

For distributed MST, algorithms are based on message-passing model. The
algorithm begins by finding the minimum-weight edge incident to each vertex of
the graph, and adding all of those edges to the forest. Then, it repeats a
similar process of finding the minimum-weight edge from each tree constructed
so far to a different tree, and adding all of those edges to the forest.

Each repetition of this process reduces the number of trees, within each
connected component of the graph, to at most half of this former value, so
after logarithmically many repetitions the process finishes. When it does, the
set of edges it has added forms the minimum spanning forest.

#### Running of Distributed parallel MST Algorithm

The Fig. 5 shows the Running a Distributed Algorithm in steps:

  1. 1.

It shows the initial forest of trees: $\\{A\\},\\{B\\},\\{D\\},\\{C\\},$
$\\{E\\},\\{F\\},\\{G\\}$, in the form of isolated vertices.

  2. 2.

LOOP: Simultaneously determine for each tree ($A$ to $G$) smallest edge
originating in a tree and joins to a vertex in some other tree.

$\displaystyle\\{A\\},\\{B\\},\\{D\\},\\{C\\},\\{E\\},\\{F\\},\\{G\\}$
$\displaystyle\Rightarrow\\{(A,B,1)\\},\\{(B,A,1)\\},\\{(C,B,1)\\},\\{(D,A,1)\\},$
$\displaystyle\text{\hskip
85.35826pt}\\{(G,F,1)\\},\\{(E,F,1)\\},\\{(F,E,1)\\}$
$\displaystyle\Rightarrow\\{(A,B,1),(C,B,1),(D,A,1),(D,F,2)\\},\\{(G,F,1)\\},$
$\displaystyle\text{\hskip 142.26378pt}\\{(F,E,1),(F,D,2)\\}$
$\displaystyle\Rightarrow\\{(A,B),(C,B),(D,A),(D,F)(G,F),(F,E)\\}$

(a) Step 1

(b) Step 2

(c) Step 3

Figure 5: Borůvka’s algorithm results for construction of MST in a parallel
processing system

In the above steps of parallel MST algorithm, the terms $(X,Y,1)$ indicates
that these are added in first step of MST construction, while $(X,Y,2)$ means
that these edges are added in 2nd step. The third step is joining of two MSPs
through a single edge. Thus, as per Sollin(2) algorithm, the number of steps
are $\log 7\approx 3$, and as per Kruskal(2), for edges $m=11$, the number of
steps are $\log 11\approx 3$. However, these complexities are asymptotic.

Following are some applications of MSTs in distributed processing:

  * -

Single-linkage clustering (a method of hierarchical clustering),

  * -

Graph-theoretic clustering,

  * -

Clustering gene expression data,

  * -

Constructing trees for broadcasting in computer networks,

  * -

Distributed Ledger Technologies (DLTs) and blockchain systems.

##  IX Conclusion

Analysis and design of algorithms of parallel and distributed systems have
been presented in this article. Most bigdata are distributed in nature,
maintained through distributed file systems, and consequently, they require
distributed algorithms for their processing. Graphs are common tools for
modeling distributed algorithms, with nodes as processors and links between
them as communication links. These links when joined, provide the
communication paths between processors. The shortest path is achieved through
distributed minimum spanning tree algorithms, while the trust management is
through public key cryptography.

This article has provided the analysis about speedup in parallel processing,
and has suggested how to achieve optimum throughput through parallel
processing, for a given set of processors. The parallelism can be obtained
either through parallel programming or through data-parallel programming. For
high throughput, GUPs are common. The article has given an analysis of
parallel spanning-tree algorithm, comparison of various minimum spanning-tree
distributed algorithms, and presented the results of simulation of MST
construction using Borůvka’s algorithm.

## References

  * [1] Chowdhary, K. R. (2015). Fundamentals of discrete mathematical structures. PHI Learning Pvt. Ltd.
  * [2] Das Sarma, A., Nanongkai, D., Pandurangan, G. and Tetali, P., 2013. Distributed random walks. Journal of the ACM (JACM), 60(1), pp.1-31.
  * [3] Boruvka, O. (1926). O jistém problému minimálním, Práce Mor. Prırodved. Spol. v Brne (Acta Societ. Scienc. Natur. Moravicae), Vol. 3, No. 3, 37-58.
  * [4] Chas. Boyd. 2008. Data-Parallel Computing: Data parallelism is a key concept in leveraging the power of today’s manycore GPUs. Queue 6, 2 (March/April 2008), 30–39. https://doi.org/10.1145/1365490.1365499
  * [5] Dijkstra, E.W. A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959) and DOI at https://doi.org/10.1007/BF01386390.
  * [6] Ghemawat, S., Gobioff, H. and Leung, S.-T. (2003) The Google File System. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, 29–43 and DOI at https://doi.org/10.1145/945445.945450.
  * [7] Li, Huaizhi, and Mukesh Singhal. ”Trust management in distributed systems.” Computer 40, no. 2 (2007): 45-53.
  * [8] Cedric Nugteren and Henk Corporaal. 2014. Bones: An Automatic Skeleton-Based C-to-CUDA Compiler for GPUs. ACM Trans. Archit. Code Optim. 11, 4, Article 35 (January 2015), 25 pages. https://doi.org/10.1145/2665079
  * [9] Luebke, David, and Greg Humphreys. ”How gpus work.” Computer 40, no. 2 (2007): 96-100.
  * [10] Quinn, Michael J., and Narsingh Deo. ”Parallel graph algorithms.” ACM Computing Surveys (CSUR) 16, no. 3 (1984): 319-348.
  * [11] Silberschatz, A., Galvin, P. B., & Gagne, G. (2010). Operating system concepts with Java. John Wiley & Sons Software.


CECS-PHY-10/15

Accelerating black hole in 2+1 dimensions
and 3+1 black (st)ring
Marco<EMAIL_ADDRESS>

Instituto de Física,
Pontificia Universidad Católica de Valparaíso
and
Centro de Estudios Científicos (CECS), Valdivia,
Chile

Abstract

A C-metric type solution for general relativity with cosmological constant is
presented in 2+1 dimensions. It is interpreted as a three-dimensional black
hole accelerated by a strut. Positive values of the cosmological constant are
admissible too.
Some embeddings of this metric in the 3+1 space-time are considered:
accelerating BTZ black string and a black ring where the gravitational force
is sustained by the acceleration.

##  1 Introduction

Beside the fact that general relativity in three space-time dimensions is
trivial, because the lack of dynamical degrees of freedom, still it admits
black holes solutions. In fact the static and rotating black hole in 2+1
dimension is very well known as remarkably discovered by Bañados, Teitelboim
and Zanelli (BTZ) in [1]. Also well known is the charged and the electro-
rotating flavours [2]. Taking inspiration from the four dimensional C-metric
(for references see [3], [4] and [5]), we are here interested to apply
acceleration to the three dimensional black hole (section 2). This is done
with the motivation that such acceleration, and the physical object that
produce it, could play an important role in 3+1 general relativity solutions
with non-trivial topology, as shown in section 3. Our supposition is based on
analogy with the five dimensional case, as explained in [6]: to forge a black
ring one has to bend a string built with the cross product of a line and a
Schwarzschild black hole, and then balance the gravitational self attraction
which makes the string self collide. If one would do so in four dimensions,
the natural candidate to start with is the cross product of a line and the
three dimensional black hole, thus the cosmological constant is necessary.
Cosmological constant is also prominent in introducing a length scale to
obtain different scales for the radius and the thickness of the ring. In [6]
the absence of black (st)rings in vacuum 4D general relativity is attributed
to the lack of such a scale.

##  2 Accelerating black hole in 2+1 dimensions

We begin considering the Einstein-Hilbert action for standard general
relativity, with generic cosmological constant $\Lambda$, in three
dimensions111We have set, for convenience, the gravitational constant $G=1/8$:

$I[g_{\mu\nu}]=\frac{1}{2\pi}\int d^{3}x\sqrt{-g}(R-2\Lambda)$ (2.1)

Extremization of the action with respect the metric $g_{\mu\nu}$ yields the
Einstein field equations:

$R_{\mu\nu}-\frac{1}{2}R\ g_{\mu\nu}+\Lambda g_{\mu\nu}=0$ (2.2)

Being inspired by the four dimensional C-metric [5], we start proposing a
similar ansatz but in $2+1$ dimensions:

$ds^{2}=\frac{1}{(1+\alpha
r\cos\theta)^{2}}\left[-f(r)dt^{2}+\frac{dr^{2}}{f(r)}+\frac{r^{2}d\theta^{2}}{g(\theta)}\right]$
(2.3)

a general solution for (2.2) in terms of the unknown functions $f(r)$ and
$g(\theta)$ can be find:

$f(r)=c_{0}+c_{1}\ r+c_{2}\ r^{2}\ \ ,\qquad
g(\theta)=\frac{c_{0}\alpha^{2}\cos^{2}(\theta)-c_{1}\alpha\cos(\theta)+c_{2}+\Lambda}{\alpha^{2}(\cos^{2}(\theta)-1)}$
(2.4)

Where $c_{0},c_{1},c_{2}$ are arbitrary integration constant. This metric
describes locally a constant curvature space-time: $R^{\mu\nu}_{\ \
\rho\sigma}=\Lambda\ (\delta^{\mu}_{\ \rho}\delta^{\nu}_{\
\sigma}-\delta^{\mu}_{\ \sigma}\delta^{\nu}_{\ \rho})$. In order to have a
significant $\alpha\rightarrow 0$ limit we select a particular metric
choosing, from (2.4), the following integration constants:

$c_{0}=1-m\quad,\qquad c_{1}=0\quad,\qquad c_{2}=\alpha^{2}(m-1)-\Lambda$

After rescaling the $\theta$ coordinate one obtains the solution:

$\displaystyle ds^{2}=\frac{1}{\left[1+\alpha
r\cos\left(\theta\sqrt{1-m}\right)\right]^{2}}\bigg{\\{}$
$\displaystyle-\Big{[}1-m+r^{2}\big{[}\alpha^{2}(m-1)-\Lambda\big{]}\Big{]}dt^{2}$
(2.5)
$\displaystyle+\frac{dr^{2}}{1-m+r^{2}\big{[}\alpha^{2}(m-1)-\Lambda\big{]}}+r^{2}d\theta^{2}\bigg{\\}}$

The coordinates $(t,r,\theta)$ are chosen to be polar, so their range is
$-\infty<t<\infty$, $r\geq 0$, $-\pi\leq\theta\leq\pi$; since $\theta$ is an
angular coordinate, the points $\theta=-\pi$ and $\theta=\pi$ can be
considered identified. Other choises for the coordinate ranges and
identification are possible and give rise to different spacetime geometries;
our choice is motivated by the will to model an accelerating 2+1 black hole.
In fact when the parameter $\alpha$ is imposed to be null one has:

$ds^{2}=-\big{(}1-m-\Lambda\ r^{2}\big{)}dt^{2}+\frac{dr^{2}}{1-m-\Lambda\
r^{2}}+r^{2}d\theta^{2}$ (2.6)

which is precisely the static BTZ black hole metric in the gauge where the
ground state is the (A)dS space-time. We prefer this form of the metric
respect to the one of [1] because when the mass222Computed respect to the
(A)dS background, as done for instance in [7] $m\rightarrow 0$ one does
recover from (2.6), not just an asymptotically (A)dS space-time as in [1], but
exactly the standard vacuum (A)dS space-time. Similarly this is what happens
in 3+1 (or higher) dimension, for instance to the Schwarzschild-(A)dS black
hole. The fact that in this gauge when $m\in[0,1)$ naked singularity occurs
(while black holes for $m\in[1,\infty)$) it’s a typical feature of Chern-
Simons gravity or odd-dimensional Lovelock theories, such is three-dimensional
general relativity.333Recently $m\in[0,1)$ states of the black hole spectrum
were physically dignified as topological defects in [8], representing
particles in $AdS_{3}$ (see also [9]) .

The metric (2.5) describes, for $m\geq 1$ an accelerating black hole whose
event horizon is located at:

$r_{h}=\sqrt{\frac{m-1}{\alpha^{2}(m-1)-\Lambda}}$

A physical interpretation to the $\alpha$ parameter can be given, following
the argument of [3] and [4]. Usually, as for the 3+1 C-metric, one considers
the weak field limit of the solution (2.5), that is $m\rightarrow 0$:

$ds^{2}=\frac{1}{\big{[}1+\alpha
r\cos(\theta)\big{]}^{2}}\left\\{-\big{[}1-r^{2}(\alpha^{2}+\Lambda)\big{]}dt^{2}+\frac{dr^{2}}{1-r^{2}(\alpha^{2}+\Lambda)}+r^{2}d\theta^{2}\right\\}$
(2.7)

The weak field limit is usefull because, in this case, black holes can be
considered as test particles and cease to deform the spacetime and inertial
frames around them.444A metric similar to (2.7) is studied by [10] in the case
of null cosmological constant. The 3D timelike worldlines $x^{\mu}(\lambda)$
of an observer with $r=\bar{r}=constant$ and $\theta=0$ can be obtained by the
property $u_{\mu}u^{\mu}=-1$ of the 3-velocity defined by
$u^{\mu}=dx^{\mu}/d\lambda$:

$x^{\mu}(\lambda)=\left[\frac{1+\alpha\bar{r}\cos(\theta)}{\sqrt{1-\bar{r}^{2}(\alpha^{2}+\Lambda)}}\lambda,\bar{r},0\right]\
\ \ ;$

where $\lambda$ is the proper time of the observer. Then the magnitude $a$ of
the 3-acceleration, $a^{\mu}=(\nabla_{\nu}u^{\mu})u^{\nu}$, for this kind of
observer results

$|a|=\sqrt{a_{\mu}a^{\mu}}\ \Big{|}_{\bar{r}=0}=\alpha$ (2.8)

Since $a_{\mu}u^{\mu}=0$, the value $|a|$ is also the magnitude of the
2-acceleration in the rest frame of the observer. From eq. (2.8) we achieve
the conclusion that the origin of the metric (2.7), $\bar{r}=0$ is being
accelerated with an uniform acceleration whose value is precisely given by the
constant $\alpha$, so (2.7) is nothing but the accelerating (A)dS space-time.
Outside of the weak field limit similar results can also be obtained:
$a_{\mu}a^{\mu}\ |_{\bar{r}=0}=\alpha^{2}\ (1-m)$ for $m\neq 1$, while
$a_{\mu}a^{\mu}\ |_{\bar{r}=0}=-\Lambda$ for $m=1$.
Thus now we can interpret the BTZ metric (2.6) as the non-accelerating limit
of the (2.5). Thanks to this limit the parameter $m$ which appears in (2.5)
can be interpreted as the mass parameter of our solution. Of course in case of
non null acceleration this does not coincide with the mass of the metric
(2.5), but is somehow related to the mass. Actually is not clear how to
compute energy in this class of accelerating space-time, neither in standard
3+1 dimensions, because of the non trivial asymptotic. So usually in the
literature (see [5]) the mass value is estimated by thermodynamical argument
as follows: The first law of black hole thermodynamics states that
$dM=TdS=\frac{k}{8\pi G}dA$; while the surface gravity $k$ is defined by
$k^{2}=-\frac{1}{2}\nabla^{\mu}\chi^{\nu}\nabla_{\mu}\chi_{\nu}$ where
$\chi^{\mu}$ is the killing vector $\partial_{t}$:

$k=r_{h}\left[(m-1)\alpha^{2}-\Lambda\right]\bigg{|}_{m=1+\frac{\Lambda
r_{h}^{2}}{r_{h}^{2}\alpha^{2}-1}}=\frac{\Lambda
r_{h}}{r_{h}^{2}\alpha^{2}-1}$

The area of the accelerating black hole horizon $A$ is given by:

$A=\int_{-\pi}^{\pi}\sqrt{g_{\theta\theta}}\>\bigg{|}_{\\!\\!\begin{array}[]{l}\scriptscriptstyle
r=r_{h}\\\\[-3.61664pt] \scriptscriptstyle t=\hbox{\tiny
const.}\end{array}}\\!\\!\\!\\!\ d\theta\ =\
\frac{4}{\sqrt{\Lambda}}\arctan\left[\sqrt{\frac{\alpha r_{h}-1}{\alpha
r_{h}+1}}\tanh\left(\frac{\pi}{2}\sqrt{\frac{\Lambda
r_{h}^{2}}{r_{h}^{2}\alpha^{2}-1}}\right)\right]$ (2.9)

So the mass estimation is, up to a integration constant:

$M=\int
dM=\int\frac{2\sqrt{\Lambda}}{\pi(\alpha^{2}r_{h}^{2}-1)^{3/2}}\frac{\alpha
r_{h}\sinh\left(\pi\sqrt{\frac{\Lambda
r_{h}^{2}}{\alpha^{2}r_{h}^{2}-1}}\right)-\pi\sqrt{\frac{\Lambda
r_{h}^{2}}{\alpha^{2}r_{h}^{2}-1}}}{1+\alpha
r_{h}\cosh\left(\pi\sqrt{\frac{\Lambda
r_{h}^{2}}{\alpha^{2}r_{h}^{2}-1}}\right)}dr_{h}$

For small values of the acceleration parameter $\alpha<<1$, thus, in practice
we restrict only to the $\Lambda<0$ sector, this integral can be evaluated:

$M=-\Lambda r_{h}^{2}+2\alpha\left[\frac{r_{h}}{\pi^{2}}\cos\left(\pi
r_{h}\sqrt{\Lambda}\right)+\frac{\Lambda\pi^{2}r_{h}^{2}-1}{\sqrt{\Lambda}\pi^{3}}\sin\left(\pi
r_{h}\sqrt{\Lambda}\right)\right]+O(\alpha^{2})$

Evidently in case of null acceleration this results is coherent with the BTZ
one: $M[r_{h}]=m[r_{h}]+k_{0}$. Note that the integration constant $k_{0}$ is
background dependent, $k_{0}=0$ for the AdS background.
The main difference of this three dimensional accelerating black hole,
compared with the four dimensional C-metric, is the absence of a pure
acceleration horizon. In fact the effect of the acceleration merges with the
cosmological constant pressure to give an unique event horizon. This happens
because also the standard three dimensional event horizon is just that of an
accelerated observer, until one identifies $\theta$ as an angular coordinate
[1]. The peculiar combination between $\Lambda$ and $\alpha$ has the
remarkable consequence that also positive values for the cosmological constant
are admissible in order to get a black hole configuration. This is something
unexpected since even a no-go theorem (see [11]) is found to justify the lack
of a 2+1 black hole, in standard general relativity, for positive cosmological
constant. In our case the no-go theorem is circumvented in one of the
hypothesis of regularity of the horizon: the horizon of the accelerating
solution (2.5) is continuous but not smooth as required in [11]. It is worth
to note that the Riemannian curvature tensor remains locally constant
everywhere, but in fact in $\theta=\pm\pi$ the metric is not differentiable
because of an angular singularity, a common feature which characterises this
kind of accelerating black holes. Here the singularity is not a conical one
due to a standard deficit angle as the four dimensional case, this may appear
as another difference. But it is just because otherwise in one dimension less
there would be no room for a strut or a string.

Figure 1: Polar plot ($\bar{r},\theta$) of $\bar{r}=$constant radial curves
embedded in the plane $\mathbb{E}^{2}$. When $\bar{r}=r_{h}$ they illustrate
horizon deformations for various values of the mass: $m=0$, $0<m<1$, $m=1$ and
$m>1$.

In figure 1 are polar plotted the shapes of the horizon, for various values of
the mass parameter $m$, as embedded in the two dimensional euclidean plane
$\mathbb{E}^{2}$. Note that the sharp vertex occurring for $0<m<1$ and $m>1$
is an artifact of the embedding, in the real curved space-time there are no
sharp vertexes. In fact the two vectors normal to the horizon in $\theta=\pi$
and $\theta=-\pi$, denoted by $n^{\mu}_{(\pm)}$, are parallels:
$n^{\mu}_{(+)}\ n_{(-)\mu}=1$. Nevertheless the angular singularity in the
conformal factor persist as pointed out by the undifferenciability of the
metric in $\theta=\pm\pi$ (for $m\neq 0,1$). It is usually associated to the
presence of a semi-infinite cosmic string, or a strut, which is pulling the
black hole along the $\theta=\pi$ axis. In this picture the tension of the
string $\tau$ is responsible for the acceleration of the 2+1 dimensional black
hole. Thanks to the Israel junction condition it is possible to compute the
strength of the strut’s force, geometrically due by a jump in the extrinsic
curvature $\mathcal{K}_{\mu\nu}$:

$\big{[}\mathcal{K}_{\mu\nu}\big{]}^{\theta=\pi}_{\theta=-\pi}-h_{\mu\nu}\big{[}\mathcal{K}\big{]}^{\theta=\pi}_{\theta=-\pi}=-\pi
h_{\mu\nu}\tau$ (2.10)

where $h_{\mu\nu}$ is the induced metric on the $\theta=\pm\pi$ surface,
$\mathcal{K}=\mathcal{K}_{\mu\nu}h^{\mu\nu}$ and the tension is

$\tau=-2\alpha\ \sqrt{m-1}\ \sinh(\pi\sqrt{m-1}).$

The negativity of $\tau$ indicate that we are dealing with a strut that is
pushing the black hole, rather than a pulling string. As can be read from the
metric (2.5) or perceived from figure 1, the strut tension $\tau$ vanishes for
$m=0,1$, where the metric acquire regularity. The metric (2.5) is supported by
the surface stress-energy tensor that can be extract from (2.10) and, for sake
of precision, it should be better added in the equation of motion (2.2).
The casual structure and the Carter-Penrose diagram is similar to the BTZ one,
although now the casual singularity in $r=0$ has an acceleration $\alpha$.
A rotating and accelerating metric can be obtained by an improper boost in the
($t,\theta$) plane of (2.5) as explained in [2]. Since in three dimensions
there is no room for rotating around the strut axis as in four dimensions, the
only way to pursue rotation is have the strut rotate with the black hole. As
expected that metric reduces to the (2.5) when the rotation is null, while it
reduces to the rotating BTZ metric when the acceleration parameter vanish.
Since the metric (2.5) remains finite for $r\rightarrow\infty$ one may also
think to extend the spacetime also in the negative $r$ sector in order to
reach the conformal infinity for $r=-1/(\alpha\cosh(\theta\sqrt{m-1}))$. This
can be done in general for $\Lambda>0$. While for $\Lambda<0$, depending also
on the reciprocal values of the parameters $\Lambda,m$ and the angular
direction $\theta$, one may encounter another killing horizon corresponding to
the negative root of the $f(r)$ function before the conformal infinity. But
here we are not interested in that. Instead we are more interested on the
possible embeddings of this metric in the $3+1$ dimensional space time, as
presented in the next section.

##  3 Embeddings in 3+1

###  3.1 Accelerating BTZ black string

The most direct embedding in 3+1 dimensions of the 2+1 solution (2.5) is
obtained in the spirit of [12]. A string like object can be written by a
warped product of the three dimensional metric and a line element $dz$:

$\displaystyle ds^{2}=\frac{\cos^{2}(z)}{\left[1+\alpha
r\cos\left(\theta\sqrt{1-m}\right)\right]^{2}}\bigg{\\{}$
$\displaystyle-\left[1-m+r^{2}\left(\alpha^{2}(m-1)-\frac{\Lambda}{3}\right)\right]dt^{2}+$
(3.1)
$\displaystyle+\frac{dr^{2}}{1-m+r^{2}\left(\alpha^{2}(m-1)-\frac{\Lambda}{3}\right)}+r^{2}d\theta^{2}\bigg{\\}}\
+\ \frac{3}{\Lambda}\ dz^{2}$

To preserve the correct metric signature $(-,+,+,+)$ the z coordinate have to
be rotated to the imaginary plane when dealing with negative cosmological
constant: $z\rightsquigarrow iz$. The standard BTZ black string of [12] is
precisely recovered from (3.1) in the limit of $\alpha=0$ (of course in that
case just negative cosmological constant can be considered). But the periodic
dependence on the $z$ coordinate, for positive $\Lambda$ (and $\alpha\neq 0$),
suggests that in this case the string singularity can be though of closed
type. Thus the horizon’s topology has a toroidal geometric structure, but with
a couple of points in $z=\pm\pi/2$ where the horizon throat shrinks to
zero555Alternatively is possible to achieve the spherical topology, for
$\Lambda>0$, considering $-\pi/2<z<\pi$; the casual singularity would be a
$\pi$-length segment along the $z$-axes.. Anyway many other features are
shared between the static and accelerating black string. For instance the
space-time curvature still remains trivially constant as the 2+1-dimensional
case: $R^{\mu\nu}_{\ \ \rho\sigma}=\Lambda/3\ (\delta^{\mu}_{\
\rho}\delta^{\nu}_{\ \sigma}-\delta^{\mu}_{\ \sigma}\delta^{\nu}_{\ \rho})$.
In this case the acceleration is provided by a two space dimensions membrane,
which results a semi-infinite plane, at least for negative $\Lambda$.

###  3.2 Black Ring

Our main interest is in topological non-trivial solution, so we consider an
ansatz with toroidal base manifold, finally. Not the one of constant curvature
obtained by identification of a flat rectangle edges, but rather a doughnut
embedded in the full 3+1 space-time, whose metric and curvature is giving,
thinking $r$ and $t$ constant, as follows:

$ds^{2}=r^{2}d\theta^{2}+\left[R_{0}+r\cos\left(\theta\sqrt{1-m}\right)\right]^{2}d\phi^{2}\
,\qquad R^{\theta\phi}_{\ \
\theta\phi}=\frac{(1-m)\cos\left(\theta\sqrt{1-m}\right)}{r\left[R_{0}+r\cos\left(\theta\sqrt{1-m}\right)\right]}$

When $m\neq 0\neq 1$, but still $\theta=\pm\pi$ identified, the circular
section of the torus is deformed, respect to the smooth $m=0,m=1$ cases, in a
drop or a cardioid shaped section (see figure 1). Using this base manifold
with generic $m$ and the acceleration conformal factor of the previous section
2 one can obtain a ring-like solution of Einstein equations (2.2):

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle\frac{1}{\left[1+\alpha
r\cos\left(\theta\sqrt{1-m}\right)\right]^{2}}\bigg{\\{}-\left[1-m+r^{2}\left[\alpha^{2}(m-1)-\frac{\Lambda}{3}\right]\right]dt^{2}+$
$\displaystyle+$
$\displaystyle\frac{dr^{2}}{1-m+r^{2}\left[\alpha^{2}(m-1)-\frac{\Lambda}{3}\right]}+r^{2}d\theta^{2}+\big{[}R_{0}+r\cos(\theta\sqrt{1-m})\big{]}^{2}d\phi^{2}\bigg{\\}}$

where the bigger radius of the torus $R_{0}$ is related to the acceleration
and mass parameter in this way:

$R_{0}=\frac{\alpha(m-1)}{\alpha^{2}(m-1)-\Lambda/3}=\alpha r_{0}^{2}$

It is evident that the acceleration plays a fundamental role in the
topological structure of the solution: when the acceleration parameter
decreases also the radius of the torus $R_{0}$ shrinks until it vanishes for
$\alpha=0$; in the latter case local spherical symmetry in the base manifold
is achieved (while globally one has a portion of $(A)dS_{4}$). So, from a
physical point of view, the acceleration sustains and balances the
gravitational attraction of the ring singularity, providing an equilibrium
configuration (whose stability is unclear).

Figure 2: “Accelerating” black ring horizon embedded in $E^{3}$

Considering a $\phi$-constant slice of (3.2) one has exactly the accelerating
black hole in 2+1 of section 2, modulo the dimensional rescaling of the
cosmological constant.
The topology of the horizon, located at $r_{0}$, can be confirmed with the
help of the Gauss-Bonnet theorem. It is simple to compute the Euler
characteristic when the mass parameter gives smooth 2-surface for constant
time and radius, that is $m=0$ and $m=1$. For different values of $m$ one has
to take into account the correction to the Gauss-Bonnet theorem due to the
sharp edge, which is given by the Gibbons-Hawking term. This involves the jump
on the trace of the extrinsic curvature $\mathcal{\bar{K}}$ and the induced
metric $\bar{h}$ on the circular sharp edge. Consider the surface
$\mathcal{S}$ described by the two dimensional metric obtained by (3.2) fixing
$r=\bar{r}=$const and $t=$const, whose embedding in the three dimensional
euclidean space $E^{3}$ is portrayed in figure 2:

$d\bar{s}^{2}=\frac{1}{\left[1+\alpha\bar{r}\cos\left(\theta\sqrt{1-m}\right)\right]^{2}}\left\\{\bar{r}^{2}d\theta^{2}+\big{[}R_{0}+\bar{r}\cos(\theta\sqrt{1-m})\big{]}^{2}d\phi^{2}\right\\}$

Its Euler characteristic is null:

$\displaystyle\chi(\mathcal{S})$ $\displaystyle=$
$\displaystyle\frac{1}{4\pi}\left(\int_{\mathcal{S}}\sqrt{\bar{g}}\ \bar{R}\
d\theta\ d\phi\ +2\int_{-\pi}^{\pi}\left[\sqrt{\bar{h}}\
\bar{\mathcal{K}}\right]^{\theta=\pi}_{\theta=-\pi}\ d\phi\right)=$
$\displaystyle=$ $\displaystyle\frac{\alpha
R_{0}-1}{4\pi}\sqrt{1-m}\int_{-\pi}^{\pi}d\phi\int_{-\pi}^{\pi}\frac{\cos(\theta\sqrt{1-m})+\bar{r}\alpha}{[1+\alpha\bar{r}\cos(\theta\sqrt{1-m})]^{2}}d\theta$
$\displaystyle-$ $\displaystyle\frac{\alpha
R_{0}-1}{2\pi}\int_{-\pi}^{\pi}\frac{2\sin(\pi\sqrt{1-m})}{1+\alpha\bar{r}\cos(\pi\sqrt{1-m})}\
d\phi\ \ =\ 0$

so, since $\chi(\mathcal{S})=2-2g$, the genus of $\mathcal{S}$ is 1: toroidal
topology $S^{1}\times S^{1}$. Observe that the irregularity on the horizon can
be cast also in the external part of the torus, as happens in the 5D static
ring [13].
The causal singularity is located along $r=0$, forming a circle in the $\phi$
direction. It’s a naked singularity with a cosmological horizon for
$m\in(0,1)$ while a black hole type for $m>1$. Coordinate $r$ is not a
standard polar radius but rather the distance from the ring singularity. Of
course in order to have a proper black ring torus horizon the parameters of
the metric are somewhat constrained to assure that the ring radius is larger
than the ring thickness, $R_{0}\geq r_{0}$: $0\leq\Lambda\leq
3(m-1)\alpha^{2}$. Note that in the null cosmological constant case we can
have just a plump horn ring with $R_{0}=r_{0}$, as expected in [6], because a
lack of the lengh scale furnished by $\Lambda$. It’s not anymore possible tune
the acceleration parameter $\alpha$ to make one radius arbitrary larger than
the other one. While in the other limiting case, that is
$\Lambda=3(m-1)\alpha^{2}$, $R_{0}$ grows to infinity. To have a well behaved
coordinate’s set and an Hausdorff manifold, the range of $r$ have to be
restricted when $|\theta|>\pi/2$ to $r\geq-R_{0}/\cos(\theta\sqrt{1-m})$. That
fact is maybe clearer in toroidal coordinates (3.3) but, on the other hand,
this coordinates patch makes the physical interpretation of the metric (3.2)
more opaque. Anyway to get the the metric (3.2) in the usual ring coordinate
just rename $y=-1/\alpha r$, $x=\cos(\theta\sqrt{1-m})$ and rescale time:

$\displaystyle ds^{2}=\frac{1}{\alpha^{2}(y-x)^{2}}\bigg{\\{}$
$\displaystyle-$
$\displaystyle\left[(y^{2}-1)(1-m)-\frac{\Lambda}{3\alpha^{2}}\right]dt^{2}+\frac{dy^{2}}{(y^{2}-1)(1-m)-\frac{\Lambda}{3\alpha^{2}}}+$
(3.3) $\displaystyle+$
$\displaystyle\frac{dx^{2}}{(1-x^{2})(1-m)}+\left(\alpha R_{0}\
y-x\right)^{2}d\phi^{2}\bigg{\\}}$

This form of the solution may be of some utility for those people interested
in finding a (A)dS ring five or in higher dimensions.

Overall this metric (3.2) or (3.3) is again locally (A)dS again despite the
fact that the base manifold is not of constant curvature. However note that
this behaviour is conceptually different from the topology of the accelerating
black string (3.1), where the toroidal topology is archived by means of the
identification on the fourth coordinate, when $\Lambda>0$. That identification
forced a topology change in the whole universe, which is not here the case.

##  4 Comments and Conclusions

In this paper a C-metric type solution for 2+1 general relativity with
cosmological constant is presented. It is analysed following the standard
four-dimensional techniques: in the weak field approximation the extra
parameter $\alpha$ is found to be the acceleration of an observer in the
origin of coordinates. When $\alpha$ parameter vanishes the usual static BTZ
black hole is recovered. Thus the metric (2.5) is interpreted as an
accelerating three-dimensional black hole, for certain range of the mass
parameters: $m>1$. The acceleration is provided by a one-space-dimensional
semi-infinite strut whose tension is proportional to the jump in the extrinsic
curvature. For $0\leq m<1$ the same solution represents an accelerating naked
singularity with a cosmological horizon pulled by a string. A remarkable fact
is that black hole configurations are admissible even for positive
cosmological constant (whenever is smaller than a certain amount of
acceleration: $\Lambda<\alpha^{2}(m-1)$). This because the pushing effect of
the strut arithmetically adds to the acceleration provided by the cosmological
constant.
Moreover a couple of embeddings of this metric in the 3+1 dimension are
considered. First an accelerating (by a two space dimension membrane) black
string, whose horizon topology depends on the sign of the cosmological
constant: cylindrical or toroidal for negative or positive $\Lambda$
respectively. Again the standard BTZ black string is retrieved when
$\alpha=0$. Lastly it is proposed a ring singularity covered by a toroidal
horizon where the gravitational force is balanced by the acceleration supplied
by a disk (or puncured plane in case of external irregularity) that, in fact,
sustains the ring. Each $\phi$-constant slice represents an accelerating black
hole of one dimension less. Up to the author knowledge this is, though not
regular, the first analytical black ring solution in four dimensions and also
the first not asymptotically flat in any dimensions.
For future perspective would be very interesting counterweight the
gravitational attraction, instead of the acceleration only, by a smoother
centrifugal effect due to the angular momentum. This may provide a regular
horizon such as been done in five dimension by Emparan and Reall passing from
an irregular static ring in [13] to a regular rotating one in [14]. The case
of null acceleration implies only negative cosmological constant, so the
Hawking topology censorship theorem can be avoided. Nevertheless the presence
of the cosmological constant preclude the use of standard generating solutions
techniques.

## Acknowledgements

I would like to thank Eloy Ayon Beato, Fabrizio Canfora, Fiorenza de Micheli,
Dietmar Klemm, Julio Oliva, Souya Ray, David Tempo, Steve Willison and Jorge
Zanelli for fruitful discussions. I’m deeply indebted to Hideki Maeda for his
continuous encouragement, suggestions and comments, without his help this work
just wouldn’t have risen.
This work has been partially funded by the Fondecyt grant 1100755 and by the
Conicyt grant “Southern Theoretical Physics Laboratory” ACT-91. The Centro de
Estudios Científicos (CECS) is funded by the Chilean Government through the
Centers of Excellence Base Financing Program of Conicyt. CECS is also
supported by a group of private companies which at present includes
Antofagasta Minerals, Arauco, Empresas CMPC, Indura, Naviera Ultragas and
Telefónica del Sur.

## References

  * [1] M. Banados, M. Henneaux, C. Teitelboim and J. Zanelli, “Geometry of the (2+1) black hole,” Phys. Rev. D 48 (1993) 1506 [arXiv:gr-qc/9302012]
  * [2] C. Martinez, C. Teitelboim and J. Zanelli, “Charged rotating black hole in three spacetime dimensions,” Phys. Rev. D 61, 104013 (2000) [arXiv:hep-th/9912259].
  * [3] J. Podolsky and J. B. Griffiths, “Uniformly accelerating black holes in a de Sitter universe,” Phys. Rev. D 63 (2001) 024006 [arXiv:gr-qc/0010109].
J. Podolsky, “Accelerating black holes in anti-de Sitter universe,” Czech. J.
Phys. 52 (2002) 1 [arXiv:gr-qc/0202033].

  * [4] O. J. C. Dias and J. P. S. Lemos, “Pair of accelerated black holes in anti-de Sitter background: The AdS C-metric,” Phys. Rev. D 67 (2003) 064001 [arXiv:hep-th/0210065].
  * [5] J. B. Griffiths, P. Krtous and J. Podolsky, “Interpreting the C-metric,” Class. Quant. Grav. 23 (2006) 6745 [arXiv:gr-qc/0609056].
  * [6] R. Emparan and H. S. Reall, “Black Holes in Higher Dimensions,” Living Rev. Rel. 11 (2008) 6 [arXiv:0801.3471 [hep-th]]
  * [7] S. Deser and B. Tekin, “Energy in generic higher curvature gravity theories,” Phys. Rev. D 67 (2003) 084009 [arXiv:hep-th/0212292].
  * [8] O. Miskovic and J. Zanelli, “On the negative spectrum of the 2+1 black hole,” Phys. Rev. D 79 (2009) 105011 [arXiv:0904.0475 [hep-th]].
  * [9] A. R. Steif,“Time-Symmetric Initial Data for Multi-Body Solutions in Three Dimensions,” Phys. Rev. D 53 (1996) 5527 [arXiv:gr-qc/9511053].
  * [10] M. M. Anber, “AdS4/CFT3+Gravity for Accelerating Conical Singularities,” JHEP 0811 (2008) 026 [arXiv:0809.2789 [hep-th]]
  * [11] D. Ida, “No black hole theorem in three-dimensional gravity,” Phys. Rev. Lett. 85 (2000) 3758 [arXiv:gr-qc/0005129].
  * [12] R. Emparan, G. T. Horowitz and R. C. Myers, “Exact description of black holes on branes. II: Comparison with BTZ black holes and black strings,” JHEP 0001 (2000) 021 [arXiv:hep-th/9912135].
  * [13] R. Emparan and H. S. Reall, “Generalized Weyl solutions,” Phys. Rev. D 65 (2002) 084025 [arXiv:hep-th/0110258].
  * [14] R. Emparan and H. S. Reall, “A rotating black ring in five dimensions,” Phys. Rev. Lett. 88 (2002) 101101 [arXiv:hep-th/0110260].