A workflow model based on parallelism for distributed organizations

Distribution has become an increasingly common characteristic for modern service and production companies. Enterprises nowadays rely on distribution of their operations for provision of their supplies, labor, and for selling their products in dynamic global markets. Much of today enterprises efforts to cope with global markets are being directed towards the finding of effective collaboration means among their operations and partners. This research proposes a model for assisting distributed enterprises in modeling their operations by optimizing and integrating their workflow to accomplish the collaborative objective. The method developed, called the distributed parallel integration evaluation model (DPIEM) models the workflow in the distributed enterprise based on three integration scenarios. DPIEM minimizes the integrated tasks total cost by adding as many parallel servers per task as possible. The method was tested for a case of distributed assembly of two part-types. A total of eight scenarios for the case were analyzed, yielding the recommended number of parallel servers per integrated task. For comparison, each scenario was also simulated with the TIE parallel-computer environment. The TIE simulation results corroborate the DPIEM recommendation based on the lowest total cost for the case analyzed.     

Combinatorial algorithms for distributed graph coloring

Numerous problems in Theoretical Computer Science can be solved very efficiently using powerful algebraic constructions. Computing shortest paths, constructing expanders, and proving the PCP Theorem, are just few examples of this phenomenon. The quest for combinatorial algorithms that do not use heavy algebraic machinery, but are roughly as efficient, has become a central field of study in this area. Combinatorial algorithms are often simpler than their algebraic counterparts. Moreover, in many cases, combinatorial algorithms and proofs provide additional understanding of studied problems. In this paper we initiate the study of combinatorial algorithms for Distributed Graph Coloring problems. In a distributed setting a communication network is modeled by a graph $G=(V,E)$ of maximum degree $\varDelta $ . The vertices of $G$ host the processors, and communication is performed over the edges of $G$ . The goal of distributed vertex coloring is to color $V$ with $(\varDelta + 1)$ colors such that any two neighbors are colored with distinct colors. Currently, efficient algorithms for vertex coloring that require $O(\varDelta + \log ^* n)$ time are based on the algebraic algorithm of Linial (SIAM J Comput 21(1):193–201, 1992) that employs set-systems. The best currently-known combinatorial set-system free algorithm, due to Goldberg et al. (SIAM J Discret Math 1(4):434–446, 1988), requires $O(\varDelta ^2+\log ^*n)$ time. We significantly improve over this by devising a combinatorial $(\varDelta + 1)$ -coloring algorithm that runs in $O(\varDelta + \log ^* n)$ time. This exactly matches the running time of the best-known algebraic algorithm. In addition, we devise a tradeoff for computing $O(\varDelta \cdot t)$ -coloring in $O(\varDelta /t + \log ^* n)$ time, for almost the entire range $1 < t < \varDelta $ . We also compute a Maximal Independent Set in $O(\varDelta + \log ^* n)$ time on general graphs, and in $O(\log n/ \log \log n)$ time on graphs of bounded arboricity. Prior to our work, these results could be only achieved using algebraic techniques. We believe that our algorithms are more suitable for real-life networks with limited resources, such as sensor networks.     

A distributed Prolog system with AND parallelism

Design details and benchmark results are given for a Prolog interpreter that can be executed across a network by using message passing to implement AND-parallelism. The system is simple and easy to use, yet significantly speeds up existing programs. The system hardware is a group of Sun 3/50 workstations connected to a 10-Mb/s Ethernet. The number of machines actually used by the system is determined when it is initialized. The benchmark programs to test the system are a Prolog compiler, a recursive Fibonacci program, an implementation of the standard quicksort algorithm, and a simple chess program     

A graph theoretical approach to determine a join reducer sequencein distributed query processing

Semijoin has traditionally been relied upon to reduce the cost of data transmission for distributed query processing. However, judiciously applying join operations as reducers can lead to further reduction in the amount of data transmission required. In view of this fact, we explore the approach of using join operations as reducers in distributed query processing. We first show that the problem of determining a sequence of join operations for a query can be transformed to that of finding a specific type of set of cuts to the corresponding query graph, where a cut to a graph is a partition of nodes in that graph. Then, in light of this concept, we prove that the problem of determining the optimal sequence of join operations for a given query graph is of exponential complexity, thus justifying the necessity of applying heuristic approaches to solve this problem. By mapping the problem of determining a sequence of join reducers into the one of finding a set of cuts, we develop (for tree and general query graphs, respectively) efficient heuristic algorithms to determine a join reducer sequence for distributed query processing. The algorithms developed are based on the concept of divide and conquer and are of polynomial time complexity. Simulation is performed to evaluate these algorithms     

Partitioning functions for stateful data parallelism in stream processing

In this paper, we study partitioning functions for stream processing systems that employ stateful data parallelism to improve application throughput. In particular, we develop partitioning functions that are effective under workloads where the domain of the partitioning key is large and its value distribution is skewed. We define various desirable properties for partitioning functions, ranging from balance properties such as memory, processing, and communication balance, structural properties such as compactness and fast lookup, and adaptation properties such as fast computation and minimal migration. We introduce a partitioning function structure that is compact and develop several associated heuristic construction techniques that exhibit good balance and low migration cost under skewed workloads. We provide experimental results that compare our partitioning functions to more traditional approaches such as uniform and consistent hashing, under different workload and application characteristics, and show superior performance.     

A distributed graph algorithm for the detection of local cycles andknots

In this paper, a distributed cycle/knot detection algorithm for general graphs is presented. The algorithm distinguishes between cycles and knots and is the first algorithm to our knowledge which does so. It is especially relevant to an application such as parallel simulation in which 1) cycles and knots can arise frequently 2) the size of the graph is very large, and 3) it is necessary to know if a given node is in a cycle or a knot. It requires less communication than previous algorithms-2m vs. (at least) (4m) for the Chandy and Misra algorithm, where m is the number of links in the graph. It requires O (nlog (n)) bits of memory, where n is the number of nodes. The algorithm differs from the classical diffusing computation methods through its use of incomplete search messages to speed up the computation. We introduce a marking scheme in order to identify strongly connected subcomponents of the graph which cannot reach the initiator of the algorithm. This allows us to distinguish between the case in which the initiator is in a cycle (only) or is in a knot     

分布式数据库中查询处理的新方法研究

在分布式数据库系统中,由于数据的分布和冗余,使得分布式查询处理增加了许多新的内容和复杂性,通过分析现有分布式数据库查询处理技术,根据应用实际提出一种新的查询处理方法,该方法通过将常用查询结果存储在本地来减少查询时的数据传输量,从而缩短了响应时间.实验证明了该方法是有效的.     

A distributed approach for graph mining in massive networks

We propose a novel distributed algorithm for mining frequent subgraphs from a single, very large, labeled network. Our approach is the first distributed method to mine a massive input graph that is too large to fit in the memory of any individual compute node. The input graph thus has to be partitioned among the nodes, which can lead to potential false negatives. Furthermore, for scalable performance it is crucial to minimize the communication among the compute nodes. Our algorithm, DistGraph, ensures that there are no false negatives, and uses a set of optimizations and efficient collective communication operations to minimize information exchange. To our knowledge DistGraph is the first approach demonstrated to scale to graphs with over a billion vertices and edges. Scalability results on up to 2048 IBM Blue Gene/Q compute nodes, with 16 cores each, show very good speedup.     

An efficient distributed algorithm for detection of knots and cycles in a distributed graph

Knot detection in a distributed graph is an important problem and finds applications in deadlock detection in several areas such as store-and-forward networks, distributed simulation, and distributed database systems. This paper presents an efficient distributed algorithm to detect if a node is part of a knot in a distributed graph. The algorithm requires 2e messages and a delay of 2(d+1) message hops to detect if a node in a distributed graph is in a knot (here, e is the number of edges in the reachable part of the distributed graph and d is its diameter). A significant advantage of this algorithm is that it not only detects if a node is involved in a knot, but also finds exactly which nodes are involved in the knot. Moreover, if the node is not involved in a knot, but is only involved in a cycle, then it finds the nodes that are in a cycle with that node. We illustrate the working of the algorithm with examples. The paper ends with a discussion on how the information about the nodes involved in the knot can be used for deadlock resolution and also on the performance of the algorithm.     

Program graph allocation in distributed multicomputers

Data-flow multiprocessors have been shown to be a very efficient solution to the problem of multiprocessor schedulability. Recent research has demonstrated the critical importance of the proper allocation of program partitions to Processing Elements. We first describe in this paper several heuristic algorithms which have been used for program allocation. We then describe the layered approach to the problem of allocation (syntax directed and graph partitioning). A parallel approach to simulated annealing is used to perform allocation at the data-flow graph level. It is also shown how the results apply to the allocation problem in the Hughes Data-Flow Machine. Finally, simulation results indicate the validity of the solutions.     

ViWoSG: A distributed scene graph of ultramassive distributed virtual environments

An ultra-massive distributed virtual environment generally consists of ultra-massive terrain data and a large quantity of objects and their attribute data, such as 2D/3D geometric models, audio/video, images, vectors, characteristics, etc. In this paper, we propose a novel method for constructing distributed scene graphs with high extensibility. Thismethod can support high concurrent interaction of clients and implement various tasks such as editing, querying, accessing and motion controlling. Some application experiments are performed to demonstrate its efficiency and soundness. Supported by the National Basic Research Program of China (Grant No. 2004CB719403), the National High-Tech Research & Development Program of China (Grant Nos. 2006AA01Z334, 2007AA01Z318, 2009AA01Z324), the National Natural Science Foundation of China (Grant Nos. 60573151, 60703062, 60833007), and the Marine 908-03-01-10 Project     

A framework for data-flow distributed processing

A framework for data-flow distributed processing is established through the definition of a data-flow model and a set of language constructs for concurrent programming. The proposed approach is based on the following characteristics: i) the exploitation of parallelism at the operation level leads to the efficient and natural exploitation of parallelism at the program level, and ii) parallelism, communication, nondeterminism and history sensitivity are primitive concepts. The aim of the defined data-flow constructs is to enhance modularity and parallelism of programs. Two structuring levels are introduced, called «modules» and «frames», to permit both symmetric and asymmetric communication. Single assignment and guarded commands are employed inside modules. Examples of tipical programming problems, including shared resources management, are given together with a short account of a distributed data-flow architecture able to support data-flow distributed processing efficiently.     

Instruction-level distributed processing

Shifts in hardware and software technology will soon force designers to look at microarchitectures that process instruction streams in a highly distributed fashion     

Availability analysis for the design of distributed processing networks

This paper presents an analytical model for evaluating the availability of distributed processing systems. The model, which is based on a well-known probability formula, has been implemented in FORTRAN and used for the design of a real-time distributed processing system that requires high availability. It is applied to a sample distributed processing system to illustrate its usefulness and to provide good insight into the design of highly available distributed processing systems. Effects of homogeneous/heterogeneous clustering and standby spare are illustrated. The concept of availability threshold where the distributed system may gain or lose availability over the individual processor availability is introduced. It has proven to be a valuable tool for the tradeoffs in the allocation of system requirements. The concluding remarks summarize the lessons learned and suggest cost-effective ways to achieve higher availability for the design of distributed processing systems.     

Partitioning dynamic graph asynchronously with distributed FENNEL

Graph partitioning is important in distributed graph processing. Classical method such as METIS works well on relatively small graphs, but hard to scale for huge, dynamic graphs. Streaming graph partitioning algorithms overcome this issue by processing those graphs as streams. Among these algorithms, FENNEL achieves better edge cut ratio, even close to METIS, but consumes less memory and is significantly faster. On the other hand, graph partitioning may also benefit from distributed graph processing. However, to deploy FENNEL on a cluster, it is important to avoid quality loss and keep efficiency high. The direct implementation of this idea yields a synchronous model and a star-shaped network, which limits both scalability and efficiency. Targeting these two problems, we propose an asynchronous model, combined with a dedicated tree-shaped map-reduce network which is prevail in systems such as Apache Hadoop and Spark, to form AsyncFENNEL (asynchronous FENNEL). We theoretically prove that, the impact on partition quality brought by asynchronous model can be kept as minimal. We test AsyncFENNEL with various synthetic and real-world graphs, the comparison between synchronous and asynchronous models shows that, for streamed natural graphs, AsyncFENNEL can improve performance significantly (above 300% with 8 workers/partitions) with negligible loss on edge cut ratio. However, more worker nodes will introduce a heavier network traffic and reduce efficiency. The proposed tree-shaped map-reduce network can mitigate that impact and increase the performance in that case.     

Partial evaluation technique for distributed image processing

In this paper, a partial evaluation technique to reduce communication costs of distributed image processing is presented. It combines application of incomplete structures and partial evaluation together with classical program optimization such as constant-propagation, loop unrolling and dead-code elimination. Through a detailed performance analysis, we establish conditions under which the technique is beneficial. Andrei Tchernykh received his Ph.D. degree in computer science from the Institute of Precise Mechanics and Computer Technology of the Russian Academy of Sciences (RAS), Russia in 1986. From 1975 to 1995 he was with the Institute of Precise Mechanics and Computer Technology of the RAS, Scientific Computer Center of the RAS, and at Institute for High Performance Computer Systems of the RAS, Moscow, Russia. Since 1995 he has been working at Computer Science Department at the CICESE Research Center, Ensenada, Baja California, Mexico. His main interests include cluster and Grid computing, incomplete information processing, and on-line scheduling. Vitaly Kober obtained his MS degree in Applied Mathematics from the Air-Space University of Samara (Russia) in 1984, and his PhD degree in 1992 and Doctoral degree in 2004 in Image Processing from the Institute of Information Transmission Problems, Russian Academy of Sciences. Now he is a titular researcher at the Centro de Investigation Cientifica y de Educatión Superior de Ensenada (Cicese), México. His research interests include signal and image processing, pattern recognition. Alfredo Cristóbal-Salas received his Ph.D. degree in computer science from the Computer Science Department at the CICESE Research Center, Ensenada, Baja California, México. Now he is a researcher at School of Chemistry Sciences and Engineering, University of Baja California, Tijuana, B.C. Mexico His main interests include cluster and Grid computing, incomplete information processing, and online scheduling. Iosif A. Ovseevich graduated from the Moscow Electrotechnical Institute of Telecommunications. Received candidate’s degree in 1953 and doctoral degree in information theory in 1972. At present he is Emeritus Professor at the Institute of Information Transmission Problems of the Russian Academy of Sciences. His research interests include information theory, signal processing, and expert systems. He is a Member of IEEE, Popov Radio Society.     

A system framework for open distributed processing

Emerging distributed applications increasingly require adequate tools and techniques for system- and application-level management. The integration of both aspects in an overall system framework is an important issue. This paper presents such a framework supporting advanced distributed applications in the context of the evolving Open Distributed Processing reference model. For system-level communication, an efficient subsystem providing advanced service capabilities is presented to cope with the increasing diversity of application service requirements. For application-level processing, a distributed object-based environment is offered. It implements location-independent invocation and object mobility and provides a high level of distribution transparency. The approach is augmented with tools and techniques for managing an overall application configuration.