Finding K shortest looping paths in a traffic-light network

In this paper we consider a traffic-light network where every node in the network is associated with the constraint consisting of a repeated sequence of time windows. The constraint aims to simulate the operations of traffic-light control in an intersection of roads. With this kind of constraints in place, directions of routes when passing through the intersections can be formally modeled. The objective of this paper is to find the first K shortest looping paths in the traffic-light network. An algorithm of time complexity of O(rK²|V₁|³) is developed, where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.     

Finding idle machines in a workstation-based distributed system

The authors describe the design and performance of scheduling facilities for finding idle hosts in a workstation-based distributed system. They focus on the tradeoffs between centralized and decentralized architectures with respect to scalability, fault tolerance, and simplicity of design, as well as several implementation issues of interest when multicast communication is used. They conclude that the principal tradeoff between the two approaches is that a centralized architecture can be scaled to a significantly greater degree and can more easily monitor global system statistics whereas a decentralized architecture is simpler to implement     

Finding consistent global checkpoints in a distributed computation

Consistent global checkpoints have many uses in distributed computations. A central question in applications that use consistent global checkpoints is to determine whether a consistent global checkpoint that includes a given set of local checkpoints can exist. Netzer and Xu (1995) presented the necessary and sufficient conditions under which such a consistent global checkpoint can exist, but they did not explore what checkpoints could be constructed. In this paper, we prove exactly which local checkpoints can be used for constructing such consistent global checkpoints. We illustrate the use of our results with a simple and elegant algorithm to enumerate all such consistent global checkpoints     

Sorting a distributed file in a network

This paper presents a new algorithm based on Quicksort for sorting in place a distributed file in a message switching network. It discusses in detail the algorithmic aspects of the method and compares it to other possible approaches. The sort is analyzed and is shown to require, on the average, O(M·log(M)) messages and a total data traffic of O(N·log(M)) records for a file of size N fragmented over M stations. Arguments for the performance one may expect in practice, where N is much larger than M, are given. They are supported by results from a sequential simulation.     

Finding missing synchronization in a distributed computation using controlled re-execution

Correct distributed programs are hard to write. Not surprisingly, distributed systems are especially vulnerable to software faults. Testing and debugging is an important way to improve the reliability of distributed systems. A distributed debugger equipped with the mechanism to re-execute the traced computation in a controlled fashion can greatly facilitate the detection and localization of bugs. This approach gives rise to a general problem of predicate control, which takes a computation and a safety property specified on the computation as inputs, and produces a controlled computation, with added synchronization, that maintains the given safety property as output. We devise efficient control algorithms for two classes of useful predicates, namely region predicates and disjunctive predicates. For the former, we prove that the control algorithm is optimal in the sense that it guarantees maximum concurrency possible in the controlled computation. For the latter, we prove that our control algorithm generates the least number of synchronization dependencies and therefore has optimal message-complexity. Furthermore, we provide a necessary and sufficient condition under which it is possible to efficiently compute a minimal controlling synchronization for a general predicate. We also give an algorithm to compute such a synchronization under the condition provided.Received: 19 June 2002, Accepted: 7 November 2003, Published online: 1 March 2004Vijay K. Garg: Supported in part by the NSF Grants ECS-9907213, CCR-9988225, Texas Education Board Grant ARP-320, an Engineering Foundation Fellowship, and an IBM grant.A preliminary version of the results in this paper first appeared in [15].     

Finding the K shortest hyperpaths

The K shortest paths problem has been extensively studied for many years. Efficient methods have been devised, and many practical applications are known. Shortest hyperpath models have been proposed for several problems in different areas, for example in relation with routing in dynamic networks. However, the K shortest hyperpaths problem has not yet been investigated.In this paper we present procedures for finding the K shortest hyperpaths in a directed hypergraph. This is done by extending existing algorithms for K shortest loopless paths. Computational experiments on the proposed procedures are performed, and applications in transportation, planning and combinatorial optimization are discussed.     

Finding strongly connected components in distributed graphs

The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver.     

Finding a suitable checkpoint and recovery protocol for a distributed application

Checkpoint and recovery protocols are commonly used in distributed applications for providing fault tolerance. The performance of a checkpoint and recovery protocol is judged by the amount of computation it can save against the amount of overhead it incurs. This performance depends on different system and application characteristics, as well as protocol specific parameters. Hence, no single checkpoint and recovery protocol works equally well for all applications, and given a distributed application and a system it will run on, it is important to choose a protocol that will give the best performance for that system and application. In this paper, we present a scheme to automatically identify a suitable checkpoint and recovery protocol for a given distributed application running on a given system. The scheme involves a novel technique for finding the similarity between the communication pattern of two distributed applications that is of independent interest also. The similarity measure is based on a graph similarity problem. We present a heuristic for the graph similarity problem. Extensive experimental results are shown both for the graph similarity heuristic and the automatic identification scheme to show that an appropriate checkpoint and recovery protocol can be chosen automatically for a given application.     

Automatic resource allocation in a distributed camera network

In this paper, we present a hierarchical smart resource coordination and reconfiguration framework for distributed systems. We view the coordination problem as one of context aware resource reconfiguration. The fundamental unit in this hierarchy is a Fault Containment Unit (FCU) that provides run-time fault-tolerance by deciding on the best alternative course of action when a failure occurs. FCUs are composed hierarchically and are responsible for dynamically reconfiguring failing FCUs at lower levels. When such a reconfiguration is not possible, FCUs propagate the failure upward for resolution. We evaluate the effectiveness of our framework in a people tracking application using a network of cameras. The task for our multi-camera network is to allocate pairs of cameras that localize a subject optimally given the current run-time context. The system automatically derives policies for switching between camera pairs that enable robust tracking while being attentive to certain performance measures. Our approach is unique in that we model the dynamics in the scene and the camera network configuration steers the policies to provide robust tracking.     

Finding iterative roots with a spiking neural network

In recent years, both multilayer perceptrons and networks of spiking neurons have been used in applications ranging from detailed models of specific cortical areas to image processing. A more challenging application is to find solutions to functional equations in order to gain insights to underlying phenomena. Finding the roots of real valued monotonically increasing function mappings is the solution to a particular class of functional equation. Furthermore, spiking neural network approaches in solving problems described by functional equations, may be an useful tool to provide important insights to how different regions of the brain may co-ordinate signaling within and between modalities, thus providing a possible basis to construct a theory of brain function. In this letter, we present for the first time a spiking neural network architecture based on integrate-and-fire units and delays, that is capable of calculating the functional or iterative root of nonlinear functions, by solving a particular class of functional equation.     

The evolution of a distributed processing network

Current trends in information systems technology increase the advantages of developing an increasingly complex distributed processing capacity. Distributed processing networks (DPNs) are expected to evolve gradually from centralized systems into more complex configurations. The introduction of major changes in organizational Structure, such as those precipitated by mergers or acquisitions, also require rapid changes to the DPN. This paper describes four distributed processing configurations. It then presents a case: the evolution of the DPN in a large corporate bank and holding company. This case illustrates configuration changes over the life cycle of the DPN of the bank and provides insight into the process of planning for DPN change. A tendency to return toward centralization is noted in this case; this may cause practitioners to rethink their own DPN growth plans.     

Queuing network model of uniformly distributed arrivals in a distributed supply chain using subcontracting

In this paper, a supply chain (four-input three-stage queuing network) receives uniformly distributed orders from clients. An input order is represented by two stochastic variables, occurrence time and the quantity of items to be delivered. The objective of this work is to compute the minimum response time, and thus the average number of items (optimum capacity) that can be delivered with this response time. Performance measures such as average queue lengths, average response times, and average waiting times of the jobs in the supply chain, and in the equivalent single-server network are derived, plotted and discussed.     

Interfacing a serial bus microcomputer to a distributed network

Special nuclear material in long-term storage in a vault is an attractive target for a diverter. A serial bus data acquisition network has been implemented utilizing single-component microcomputers. The distributed network enables constant surveillance of this material utilizing a variety of sensors. The serial bus protocol includes broadcast commands, network control, microcomputer diagnostics and data collection.A single-component microcomputer collects data from a Geiger-Müller tube that monitors γ emissions and from a scale that monitors the total weight of the container and contents. A network of the microcomputer shelf monitors reports the acquired data to a minicomputer for analysis, alarm if necessary and storage. One network consisting of approximately 100 monitors has been collecting data for over 1 year. The objective of this research program has been to develop a reliable inexpensive monitor network and associated data-processing equipment capable of real-time monitoring.     

Securing the distributed word processing network

There has been little concern for the security of stand-alone and shared-logic word processor systems although the threats are there and the loss from breaches of security can be very expensive. Word processors usually store processed information rather than data and modification or destruction of a document can lead to poor or delayed decisions. Inherent controls of paper-based systems are lost when the typing function is automated. Word processing networks are particularly vulnerable with reliance placed on the software system to secure documents. The weakest configuration in distributed word processing systems is in moderate size networks which cannot justify sophisticated hardware to support sophisticated operating systems and security software. Therefore, either additional physical security for each terminal or a more sophisticated authorization routine must be provided. The first is nearly impossible and the second rarely exists on these systems. As the trend toward hard disks for these units continues, the best solution may be the inclusion of a cryptographic routine.     

Convergence testing on a distributed network of processors

The termination of iterative algorithms on a distributed network of transputers is an important issue with the increasing usage of parallel computers.

In this paper we analyse the computational and communication costs of performing the convergence tests on the solution of the Laplace Equation on a two dimensional region,.i.e., the unit square.

Finally a strategy of terminating the iteration without convergence testing is demonstrated.     

Modeling and distributed simulation of a broadband-ISDN network

A distributed approach to communication network simulation using a network of workstations configured as a loosely coupled parallel processor to model and simulate the broadband integrated services digital network (B-ISDN) is proposed. In a loosely coupled parallel processor system, a number of concurrently executable processors communicate asynchronously using explicit messages over high-speed links. Since this architecture is similar to that of B-ISDN networks, it constitutes a realistic testbed for their modeling and simulation. The authors describe an implementation of this approach on 50 Sun workstations at Brown University. Performance results, based on representative B-ISDN networks and realistic traffic models, indicate that the distributed approach is efficient and accurate     

Using structural information for distributed recommendation in a social network

Social networks are social structures that depict relational structure of different entities. The most important entities are usually located in strategic locations within the network. Users from such positions play important roles in spreading the information. The purpose of this research is to make a connection between, information related to structural positions of entities and individuals advice selection criteria in a friendship or trust network. We explore a technique used to consider both frequency of interactions and social influence of the users. We show, in our model, that individual positions within a network structure can be treated as a useful source of information in a recommendation exchange process. We then implement our model as a trust-based exchange mechanism in NetLogo, which is a multi-agent programmable modeling environment. The experimental results demonstrate that structural position of entities can indeed retain significant information about the whole network. Utilizing social influence of entities leads to an increase in overall utility of the system.     

从不确定图中发现K紧密子图

由蛋白质交互网络、社会网络及无线通信网络构成的图中存在许多不确定性。如何高效获取不确定图中有价值的信息,如蛋白质网络中关键的功能集团、社会网络中适于投放广告的团体及通信网络中应重点维护的区域等,具有重要的现实意义。从理论上证明了在不确定图中发现最紧密子图问题具有NP-Hard复杂性;基于树搜索策略提出了通过枚举解空间及剪枝获得最优解的算法TreeClose;针对树搜索算法TreeClose在处理大图时空间复杂度过高的问题,提出了基于贪心思想的2-近似算法GreedyClose。实验结果表明,通过上述算法可以高效快速地在不确定图中发现紧密子图,从而解决在实际应用中遇到的各种问题。     

分布式网络环境下实体行为信任的评估方法

随着分布式网络的发展,网络的资源环境变得越来越复杂和难以预测,使得越来越多的应用需要建立信任,特别是在本来互不相识的实体之间建立信任。主要给出了较全面反映信任特性的信任计算方法,首次给出了证据更新的计算方法,在此基础上给出了基于客观证据的直接信任、推荐信任和推荐者自身信任更新的计算公式,并在计算中增加了可信度因子,使得通过计算得到的信任自包含可信度;提出了同构推荐者和非同构推荐者的概念和基于这两者的不同的信任计算方法,提高了信任评估的可信度;论述了信任推荐的4种拓扑结构及其计算方法。最后分析了计算方法体现出信任的主观性、动态性、非传递性和受历史影响等特性。方法具有实用、防欺骗和可扩展特点,可直接用来指导实际网络的信任计算。