This dissertation studies the theory of distributed computing. In the distributed setting, computation is carried out by multiple independent computational units. They communicate with neighbouring units and collectiv...
详细信息
This dissertation studies the theory of distributed computing. In the distributed setting, computation is carried out by multiple independent computational units. They communicate with neighbouring units and collectively solve a problem. Systems of this kind are widespread in the information society as well as in the natural world: prime examples include the Internet, multi- processor computer systems, the cells of a biological organism and human social networks. Therefore it is important to gain knowledge on the fundamental capabilities and limitations of distributed systems. Our work takes place in the context of deterministic and synchronous message-passing models of distributed computing. Such models abstract away some possible features of distributed systems, such as asynchrony, congestion and faults, while putting emphasis on the amount of communication needed between the units. The computational units are expected to solve a problem related to the structure of the underlying communication network. More specifically, we study the standard LOCAL model, the standard port-numbering model and several weaker variants of the latter. The contributions of this dissertation are two-fold. First, we give new methods for studying distributed computing by establishing a strong connection between several weak variants of the port-numbering model and corresponding variants of modal logic. This makes it possible to apply existing logical tools, such as bisimulation, to understand computation in the distributed setting. We also give a full characterisation of the relationships between the models of computing, which has implications on the side of mathematical logic. Second, we prove the existence of various new non-empty complexity classes. One of our results studies the relationship between time and space complexity, which is a relatively new topic in distributed computing research. We demonstrate the existence of a problem that can be solved in a constant amount of space in a
This paper considers the MapReduce-like coded distributed computing framework originally proposed by Li et al., which uses coding techniques when distributed computing servers exchange their computed intermediate valu...
详细信息
ISBN:
(数字)9781728182988
ISBN:
(纸本)9781728182995
This paper considers the MapReduce-like coded distributed computing framework originally proposed by Li et al., which uses coding techniques when distributed computing servers exchange their computed intermediate values, in order to reduce the overall traffic load. In their original model, servers are connected via an error-free common communication bus allowing broadcast transmissions. However, this assumption is one of the major limitations for practical implementations since real-world data centers may have network topologies far more involved than a single broadcast bus. We formulate a topological coded distributed computing problem, where the computing servers communicate with each other through some switch network. By using a special instance of fat-tree topologies, referred to as t-ary fat-tree proposed by Al-Fares et al. which can be built by some inexpensive switches, we propose a coded distributed computing scheme to achieve the optimal max-link communication load (defined as the maximum load over all links) over any network topology.
distributed computing provides user with reliable, flexible and dynamic computing and storage services by organizing many computer resources. It is also popular for high performance and resource sharing. The significa...
详细信息
ISBN:
(数字)9781728185736
ISBN:
(纸本)9781728185743
distributed computing provides user with reliable, flexible and dynamic computing and storage services by organizing many computer resources. It is also popular for high performance and resource sharing. The significance of billing for distributed computing is to correctly measure resource utilization and charge fees for the task on distributed computing. Many companies use distributed computing to build cloud computing platforms. To provide customers with more attractive products and better services, this paper proposes a billing system for distributed cloud computing. This system mainly includes two parts, information collection and billing calculation. In the information collection, the process on each node periodically collects resource utilization of the assigned task and transmits the information to other part. In the billing calculation, this part calculates the cost based on the information collected and stores the records. This system is helpful for services providers to get more reasonable billing and for customer to control cost.
Coded distributed computing (CDC) introduced by Li et. at. is an effective technique to trade computation load for communication load in a MapReduce framework. CDC achieves an optimal trade-off by duplicating map comp...
详细信息
ISBN:
(数字)9781728150895
ISBN:
(纸本)9781728150901
Coded distributed computing (CDC) introduced by Li et. at. is an effective technique to trade computation load for communication load in a MapReduce framework. CDC achieves an optimal trade-off by duplicating map computations at r computing nodes to yield multicasting opportunities such that r nodes are served simultaneously in the Shuffle phase. However, in general, the state-of-the-art CDC scheme is mainly designed only for homogeneous networks, where the computing nodes are assumed to have the same storage, computation and communication capabilities. In this work, we explore two approaches of heterogeneous CDC design. First, we study CDC schemes which operate on multiple, collaborating homogeneous computing networks. Second, we allow heterogeneous function assignment in the CDC design, where nodes are assigned a varying number of reduce functions. We propose an expandable heterogeneous CDC scheme where r-1 nodes are served simultaneously in the Shuffle phase. In comparison to the state-of-the-art homogeneous CDC scheme with an equivalent computation load, we find our newly proposed heterogeneous CDC scheme has a smaller communication load in some cases.
One of the main functions of distributed computing systems is the efficient distribution of resources between users and computing applications. The choice of a specific algorithm for managing resource allocation is us...
详细信息
ISBN:
(数字)9781728157610
ISBN:
(纸本)9781728157627
One of the main functions of distributed computing systems is the efficient distribution of resources between users and computing applications. The choice of a specific algorithm for managing resource allocation is usually determined by the class of tasks to be solved by the computer system and the goals to be achieved. An analysis of existing resource allocation control algorithms for traditional computing systems showed the limitations of using these methods in distributed systems, as a result of which significant delays can occur between task switching. Thus, the relevance of creating effective resource allocation control algorithms in distributed computing systems is substantiated. A functional mathematical model for estimating the workload of distributed systems based on determining the probability of downtime of a computing node is proposed. An algorithm for managing the distribution of resources based on genetic algorithms is developed.
Modern pace of Information and Communication Technologies (ICT) progress requires rapid development of completely new approaches to data processing. One of the most important criteria that should be taken into account...
详细信息
ISBN:
(数字)9781728171272
ISBN:
(纸本)9781728171289
Modern pace of Information and Communication Technologies (ICT) progress requires rapid development of completely new approaches to data processing. One of the most important criteria that should be taken into account in every computing system nowadays is its energy efficiency. Strict requirements to service availability and timeliness must be taken into account as well. In this paper new comprehensive energy efficient approach to workload processing in distributed computing environment is proposed. The goal of this approach is to get as close as possible to the energy-proportional computing model. Proposed approach combines the advantages of horizontal scaling and energy efficient scheduling taking into account individual power consumption characteristics of computing nodes and dynamicity of workload in modern computing systems. The efficiency of the proposed approach is proven using Matlab modeling.
The use of data is increasing steadily in the modern era of technology. That produced the term big data. Many companies are interested in analyzing this data, which amounts to several terabytes. The term distributed c...
详细信息
ISBN:
(数字)9781728196756
ISBN:
(纸本)9781728196763
The use of data is increasing steadily in the modern era of technology. That produced the term big data. Many companies are interested in analyzing this data, which amounts to several terabytes. The term distributed computing system appears as an effective technique for analyzing big data. Businesses have sought to use cloud resources to implement distributed computing in order to reduce costs and increase productivity. distributed computing system faces the hurdle of significant material cost for providing related equipment. To avoid the financial cost problem, researchers have developed frameworks and tools for implementing distributed computing operations by using the redundant resources of cloud computing. This paper presents the advantages and disadvantages of a distributed computing system as well as analyzes traditional systems of distributed computing and concludes with a survey of frameworks for using cloud computing resources to implement distributed computing system operations at a lower cost.
Cloud computing provides a flexible and cost-effective solution to big data applications. Data privacy, however, is a main concern. To avoid information leakage to a cloud service provider, a user may store portions o...
详细信息
ISBN:
(数字)9781728150895
ISBN:
(纸本)9781728150901
Cloud computing provides a flexible and cost-effective solution to big data applications. Data privacy, however, is a main concern. To avoid information leakage to a cloud service provider, a user may store portions of encoded data in multiple clouds and perform computing tasks in a distributed way. In this work, nested MDS codes and the criterion of perfect secrecy are adopted. The allocation of encoded data to be stored in heterogeneous clouds with different computing capability is formulated as an optimization problem, subject to data reliability and security constraints. The problem is shown to be feasible if and only if the storage budget is above a certain level. The tradeoff between minimum computation time and storage budget is analytically characterized, and the former is proved to be a piecewise-linear decreasing function of the latter. When the storage budget increases beyond a certain threshold, the optimal computation time levels off. Closed-form expressions of minimum computation time and optimal storage allocation are obtained. Numerical results show that the optimized allocation outperforms equal allocation significantly if the computing rates of different clouds have large variation.
The following topics are dealt with: cellular radio; telecommunication traffic; quality of service; resource allocation; learning (artificial intelligence); probability; 5G mobile communication; multi-access systems; ...
详细信息
ISBN:
(数字)9781728171272
ISBN:
(纸本)9781728171289
The following topics are dealt with: cellular radio; telecommunication traffic; quality of service; resource allocation; learning (artificial intelligence); probability; 5G mobile communication; multi-access systems; error statistics; and Long Term Evolution.
Digital image processing is an actual task in the digital communication systems, IP-telephony and video conferencing, in digital television, and video surveillance. Digital processing of large video images takes a lot...
详细信息
ISBN:
(数字)9781728173863
ISBN:
(纸本)9781728173870
Digital image processing is an actual task in the digital communication systems, IP-telephony and video conferencing, in digital television, and video surveillance. Digital processing of large video images takes a lot of time, especially if it happens in a real-time system. And, processing speed plays an important role in recognition of objects in video images received from IP-cameras in real time. This requires the use of modern technologies, and fast algorithms that increase the acceleration of digital image processing. Acceleration problems have not been fully resolved till present. Today's realities are such that the development of accelerated image processing programs requires a good knowledge of parallel and distributed computing. Both of these areas are united by the fact that both parallel and distributed software consists of several processes that together solve one common problem. This article proposes an accelerated method for the tasks of recognizing objects in video images received from IP-cameras using parallel and distributed computing technologies.
暂无评论