Erciyes - Distributed Graph Algorithms for Computer Networks
Here you can read online Erciyes - Distributed Graph Algorithms for Computer Networks full text of the book (entire story) in english for free. Download pdf and epub, get meaning, cover and reviews about this ebook. City: London, year: 2013, publisher: Imprint, Springer, Springer London, genre: Computer. Description of the work, (preface) as well as reviews are available. Best literature library LitArk.com created for fans of good reading and offers a wide selection of genres:
Romance novel
Science fiction
Adventure
Detective
Science
History
Home and family
Prose
Art
Politics
Computer
Non-fiction
Religion
Business
Children
Humor
Choose a favorite category and find really read worthwhile books. Enjoy immersion in the world of imagination, feel the emotions of the characters or learn something new for yourself, make an fascinating discovery.
Distributed Graph Algorithms for Computer Networks: summary, description and annotation
We offer to read an annotation, description, summary or preface (depends on what the author of the book "Distributed Graph Algorithms for Computer Networks" wrote himself). If you haven't found the necessary information about the book — write in the comments, we will try to find it.
Graph theory is an invaluable tool for the designer of algorithms for distributed systems. This hands-on textbook/reference presents a comprehensive review of key distributed graph algorithms for computer network applications, with a particular emphasis on practical implementation. Each chapter opens with a concise introduction to a specific problem, supporting the theory with numerous examples, before providing a list of relevant algorithms. These algorithms are described in detail from conceptual basis to pseudocode, complete with graph templates for the stepwise implementation of the algorithm, followed by its analysis. The chapters then conclude with summarizing notes and programming exercises. Topics and features: Introduces a range of fundamental graph algorithms, covering spanning trees, graph traversal algorithms, routing algorithms, and self-stabilization Reviews graph-theoretical distributed approximation algorithms with applications in ad hoc wireless networks Describes in detail the implementation of each algorithm, with extensive use of supporting examples, and discusses their concrete network applications Examines key graph-theoretical algorithm concepts, such as dominating sets, and parameters for mobility and energy levels of nodes in wireless ad hoc networks, and provides a contemporary survey of each topic Presents a simple simulator, developed to run distributed algorithms Provides practical exercises at the end of each chapter This classroom-tested and easy-to-follow textbook is essential reading for all graduate students and researchers interested in discrete mathematics, algorithms and computer networks. Prof. Dr. Kayhan Erciye is the Rector and a member of the Computer Engineering Department at Izmir University, Turkey.;Introduction -- Part I: Fundamental Algorithms -- Graphs -- The Computational Model -- Spanning Tree Construction -- Graph Traversals -- Minimal Spanning Trees -- Routing -- Self-Stabilization -- Part II: Graph Theoretical Algorithms -- Vertex Coloring -- Maximal Independent Sets -- Dominating Sets -- Matching -- Vertex Cover -- Part III: Ad Hoc Wireless Networks -- Introduction -- Topology Control -- Ad Hoc Routing -- Sensor Network Applications -- ASSIST: A Simulator to Develop Distributed Algorithms -- Pseudocode Conventions -- ASSIST Code -- Applications Using ASSIST.
Erciyes: author's other books
Who wrote Distributed Graph Algorithms for Computer Networks? Find out the surname, the name of the author of the book and a list of all author's works by series.
Rassul Bairamkulov
Gabriel Valiente
R. M. R. Lewis
Amy E. Hodler
Amy E. Hodler
Robert Sedgewick
Distributed Graph Algorithms for Computer Networks — read online for free the complete book (whole text) full work
Below is the text of the book, divided by pages. System saving the place of the last page read, allows you to conveniently read the book "Distributed Graph Algorithms for Computer Networks" online for free, without having to search again every time where you left off. Put a bookmark, and you can go to the page where you finished reading at any time.
Light
Font size:
↓
↑
Reset
Interval:
↓
↑
Bookmark:
Make
K. Erciyes Computer Communications and Networks Distributed Graph Algorithms for Computer Networks 2013 10.1007/978-1-4471-5173-9_1 Springer-Verlag London 2013
1. Introduction
K. Erciyes 1
(1)
Computer Engineering Department, Izmir University, Uckuyular, Izmir, Turkey
Abstract
A distributed system consists of a set of computational nodes connected by a communication network that cooperate to accomplish common tasks. In this chapter, we will review the benefits of using a distributed system, the architecture of a distributed system, and the challenges facing the designers.
1.1 Distributed Systems
The basic requirements from a distributed system are that the nodes should be autonomous so that they can work independently; the network should be connected, that is, any node should have a communication link directly or indirectly to any other node; and there should be a coordination mechanism for the nodes to cooperate to achieve common goals.
There are a number of benefits to be gained by utilizing distributed systems. One of the obvious advantages of using a distributed system is resource sharing . Access to a central resource has two disadvantages as this central site becomes a bottleneck for communications and also is a single point of failure. Distributing the resources such as the database and peripherals over a network overcomes these problems.
Resources and computation can be replicated at various sites providing fault tolerance as a replica may be substituted in the case of the dysfunctioning of a node. This type of fault tolerance is an important reason to employ distributed systems. It is also possible for the application to be inherently distributed such as bank transaction systems and airline reservation systems where employment of distributed systems is inevitable.
A distributed system can be modeled as a graph G ( V , E ) conveniently where V is the set of vertices and E is the set of edges of G . The computing nodes of the distributed system are represented by the vertices of the graph, and an edge exists between the nodes if there is a communication link between them. Figure displays a graph that represents a distributed system consisting of nodes numbered 1,,10. The first thing that may be noticed is that the graph is connected, providing a communication path between any pair of nodes. Many nodes are not directly connected to each other; therefore, they have to rely on their neighbor nodes to communicate with the other nodes of the network. 
Fig. 1.1
A graph representing a distributed system
We will use graphs to represent distributed systems and show the execution of a distributed algorithm in these graphs frequently. In this chapter, we will first describe platforms and models for distributed computing in Sects.. Finally, we conclude by the organization of the book.
1.2 Distributed Computing Platforms
Due to the recent technological advancements, in the last few decades, we have witnessed diverse distributed system platforms such as the Grid, The Cloud, mobile ad hoc networks, and wireless sensor networks that are described below.
1.2.1 The Grid
The Grid consists of loosely coupled, heterogeneous, and geographically dispersed computing elements that are connected by a network acting together to perform large tasks []. These computationally intensive scientific tasks may include various applications such as seismic analysis, drug discovery, and bioinformatics problems. Grid computing provides effective usage of the unused processing power and results in decreased completion time for a task due to parallelization.
The size of a grid varies from a small network of workstations in a corporation to thousands of nodes across many networks and nations. Grids require general software libraries called the middleware to accomplish coordination among a large number of nodes that comprise them. Resource discovery is the process of finding the location of the required resources such as the database tables in the Grid [] is prototyping a computational grid for infrastructure and an access grid for people.
1.2.2 Cloud Computing
The cloud computing evolved from grid computing with the aim to deliver the computing as a service to the users by extending the object-oriented programming paradigm. Cloud computing provides computation, software applications, data access, data management, and storage for resources without requiring cloud users to know the location and other details of the computing infrastructure []. Grid computing may be included in the cloud or not depending on the type of application and users. Cloud computing and grid computing aim at scalability, and both use load balancing to accomplish scalability. In grid computing, a single task is divided into smaller tasks that are run on a number of processors to effectively use the available computing power, whereas in cloud computing, service offered to users is not restricted to processing power and includes website hosting, database support, etc. Cloud computing, in general, offers more services than the Grid.
1.2.3 Mobile Ad hoc Networks
A wireless ad hoc network is a decentralized network consisting of wireless nodes that do not rely on a predefined infrastructure such as routers or access points. Instead, each node participates in routing by forwarding data to other nodes regarding dynamically changing network topology. A mobile ad hoc network ( MANET ) is a network without any fixed structure formed for a purpose by mobile devices connected by wireless communication links. Each node of a MANET moves independently, forming a dynamic network that changes its topology continuously. Nodes of a MANET must be able to route any messages not destined to them; therefore, each node functions as a router. Examples of MANETs are the disaster relief operations, military networks, and vehicular ad hoc networks.
1.2.4 Wireless Sensor Networks
A wireless sensor network ( WSN ) consists of many small nodes of computing elements, each equipped with sensing and wireless communication capabilities. These networks can obtain data about their environment and transfer this data to a central node using multi-hop communication to be analyzed further. The WSNs have large application spectrum such as habitat monitoring, military surveillance, and target tracking []. WSNs form a large-scale distributed system and require scalable distributed algorithms to solve problems such as data aggregation, topology control, and routing.
1.3 Models
The basic models of a distributed system are the message passing and shared-memory models. In the message passing model, nodes of the distributed system communicate by messages only. Messages are communicated in rounds in synchronous message passing, where messages sent in round k are delivered to all recipients before messages in round k +1 can be transferred. In asynchronous message passing, however, messages are assumed to eventually reach the destinations after unknown delays. Analyzing asynchronous message passing algorithms is more difficult than synchronous ones due to the uncertainties involved.
In shared-memory models, processes communicate by reading and writing to shared memory. Synchronization is an important issue also in shared-memory systems. Distributed shared-memory systems implement shared memory model over the message passing model to use the available shared memory software modules conveniently. Our analysis in this book is confined to message-passing distributed systems without any shared memory in general, except for some self-stabilizing algorithms, where it will be assumed that a process can read the values of the registers of its neighbors.
Light
Font size:
↓
↑
Reset
Interval:
↓
↑
Bookmark:
Make
Similar books «Distributed Graph Algorithms for Computer Networks»
Look at similar books to Distributed Graph Algorithms for Computer Networks. We have selected literature similar in name and meaning in the hope of providing readers with more options to find new, interesting, not yet read works.
Rassul Bairamkulov
Gabriel Valiente
R. M. R. Lewis
Amy E. Hodler
Amy E. Hodler
Robert Sedgewick
Reviews about «Distributed Graph Algorithms for Computer Networks»
Discussion, reviews of the book Distributed Graph Algorithms for Computer Networks and just readers' own opinions. Leave your comments, write what you think about the work, its meaning or the main characters. Specify what exactly you liked and what you didn't like, and why you think so.