The container stowage planning problem is known to be NP-hard and heuristic algorithms have been proposed. Conventionally, the efficiency of the stowage planning algorithms are improved by pruning or reducing the search space. We observe that constraint evaluation is the core of most algorithms. In addition, the order at which the constraints are evaluated can have significant impact on the efficiency of the constraint evaluation engine. We propose random sample model (RSM) and sequential sample model (SSM) for analysis of the problem. We present and evaluate seven strategies in optimizing the constraint evaluation engine. We show how to achieve the optimal constraint ordering with respect to RSM and SSM, respectively. However, the optimal ordering for SSM requires perfect information about the states of the constraint tests, which is impractical. We present an alternative strategy and show empirically that its efficiency is close to the optimal. Experiments show that, compared to a naïve ordering, an average of 2.74 times speed up in the evaluation engine can be achieved.Note to Practitioners—Automated stowage planning has become a trend as the number of mega-scale containerships being deployed has increased drastically over the past decade. Due to the nature of the problem, it is impractical to expect the best stowage plan within a limited amount of time, and hence, many heuristics have been devised to reduce the solution space. Many heuristics algorithms share a common core-repeatedly selecting a stowage slot and a container (selection mechanism) and evaluate whether all of the constraints are satisfied. To improve the efficiency, most studies aim to reduce the number of location-container pairs being considered. We consider an alternative approach that improves the efficiency of the constraint evaluation engine. Specifically, we show how to improve the efficiency by strategically reordering the sequence in which the constraints are evaluated. With the improvements on the efficiency, the stowage algorithm is one step closer to being able to generate solutions in real time. This may enable the shipping companies to take last-minute shipment order and react to changes in demands quickly.

The spread of influence under Independent Cascade model and Linear Threshold model has been studied extensively in the literature. The two models describe the process through which individuals adopt a new product. We study the rumour model, that describes the process through which a news is spread in a network. We consider the task of identifying a collection of seed nodes of minimal size to spread a news such that, within a certain time threshold, the news can be spread to a target number of nodes with certain probability. We show that the problem is NP-hard. Moreover, we show that the function that calculates the probability of achieving the coverage threshold is not submodular, and hence conventional optimization techniques based on the submodularity property cannot be applied directly. Nevertheless, we present an algorithm that can provably approximate the size of the optimal seed set. In addition, we present a Monte-Carlo algorithm for choosing the best node that generates the greatest marginal increment in expected coverage. We compare the size of seed set with other baseline algorithms by using both real and synthetic networks. Our algorithm consistently outperforms other methods. For certain cases, the sizes of seed sets returned by our algorithm are less than a hundredth of that returned by the baseline algorithms compared.

Identifying nodes that play important roles in network dynamics in large scale complex networks is crucial for both characterizing the network and resource management. Under the viral marketing setting, Diffusion Centrality (DC) estimates the influential power of an individual. For the transport and physics communities, a node is considered important in Markov centrality (MC) if it can be quickly reached from the other nodes. Because these networks could contain millions of nodes, any ranking algorithm must have low time requirements to be practically useful. In this paper, we show that both metrics are strongly correlated, and we present a new method to enable fast estimation of the two metrics for large scale networks. The new approach is further validated empirically by using both real and synthetic networks. Our results refined the intuition that the influential power of an individual is largely governed by the local topology, rather than the mere number of contacts (node degree) alone. This allows us to better characterize the properties of the nodes that affect the outcome of the two centrality metrics.

Previous studies suggest that human mobility is highly regular in two respects. Firstly, individual's travels are governed by occasional exploration of new locations and preferential return to most frequently visited locations. Secondly, human mobility sequences exhibit high predictability. The existing model [1] is able to mimic exploration and preferential return, and lit actual mobility data. However, the high predictability issue is not addressed in this model. In this paper, we derive an upper bound of the predictability manifested by this model. Motivated by the incorrigible gap between the bound and the empirical results shown in [2], we further propose a new Markovian model by modifying the rule of preferential return to be conditional on the individuals' current location. We show both theoretically and empirically that the new Markovian model presents high predictability while preserving the desirable scaling properties of the original model in [1], making it the most complete model to date in capturing the essence of human mobility.

Various Markov models have been proposed to model individuals' mobility, i.e., the transitions between locations. Although these studies are able to show high predicting accuracy of individuals' next move, two basic assumptions of these studies, namely the stationarity of individuals' mobility sequence and the dependency of visiting the locations, have never been validated. Moreover, a famous recent research suggests that individuals prefer to revisit the locations merely according to the visitation frequency. In this paper, we study these two presumed properties of individuals' mobility sequence. Specifically, stationarity is validated by analyzing the autocorrelation of the mobility sequences that are encoded under three popular schemes. With appropriate choice of spatial and temporal scale, two types of periodicity, e.g., daily and weekly, are observed. The visiting dependency between the locations is validated by comparing the entropy of the mobility sequence to the entropies generated from either i.i.d. or Markov sources. Based on these two statistical properties, we then construct two Markov models with three revisiting rules to model individuals' mobility. The average log-loss values show that the best revisiting rule for the Markov model is a combination of the visitation frequency and the distance of the next location to the current locations. This finding suggests that individuals' mobility is influenced by both temporal and spatial localities, rather than by either form of locality alone as suggested in the previous study.

The spread of influence in a network is a fundamental issue in many complex systems. For instance, the word of-mouth effect in a social network is crucial to the emerging viral market. The process was previously analyzed with a voter model where an individual weighs the opinions of his acquaintances equally. However, one would expect that an individual's opinion is often more swayed by her/his better connected peers. As such, the influence of a node x on another node should be proportional to x's degree. This paper studies the spread of influence under the latter model - called Preferential Voter Model (PVM) for easier reference. We first present the exact form of the random walk stationary distribution for PVM, based on which, we show that the First Passage Time (FPT) of PVM follows an exponential decay. Furthermore, compared against the conventional (nonpreferential) voter model, we show that nodes with larger degrees exhibit faster decay rate and lower mean First Passage Time in PVM. These new results have applications to network-based complex systems. For instance, in the context of viral marketing in a social network, picking nodes of larger degrees as the starting nodes of a sales campaign not only maximizes the expected number of influenced nodes in the network, but also reduces the expected time to spread the influence. Thus, our result confirms analytically that well-connected individuals indeed exert faster and more effective influences in social networks under the preferential model.

The ability to foresee the next moves of a user is crucial to ubiquitous computing. Disregarding major differences in individuals' routines, recent ground-breaking analysis on mobile phone data suggests high predictability in mobility. By nature, however, mobile phone data offer very low spatial and temporal resolutions. It remains largely unknown how the predictability changes with respect to different spatial/temporal scales. Using high-resolution GPS data, this paper investigates the scaling effects on predictability. Given specified spatial-temporal scales, recorded trajectories are encoded into long strings of distinct locations, and several information-theoretic measures of predictability are derived. Somewhat surprisingly, high predictability is still present at very high spatial/temporal resolutions. Moreover, the predictability is independent of the overall mobility area covered. This suggests highly regular mobility behaviors. Moreover, by varying the scales over a wide range, an invariance is observed which suggests that certain trade-offs between the predicting accuracy and spatial-temporal resolution are unavoidable. As many applications in ubiquitous computing concern mobility, these findings should have direct implications.

Both fairness and efficiency are crucial measures for the performance of parallel applications on multiprocessor systems. In this paper, we study online adaptive scheduling for multiple sets of such applications, where each set may contain one or more jobs with time-varying parallelism profile. This scenario arises naturally when dealing with several applications submitted simultaneously by different users in a large parallel system, where both user-level fairness and system-wide efficiency are important concerns. To achieve fairness, we use the equipartitioning algorithm, which evenly splits the available processors among the active job sets at any time. For efficiency, we apply a feedback-driven adaptive scheduler, which periodically adjusts the processor allocations within each set by consciously exploiting the jobs' execution history. We show that our algorithm is competitive for the objective of minimizing the set response time. For sufficiently large jobs, this theoretical result improves upon an existing algorithm that provides only fairness but lacks efficiency. Furthermore, we conduct simulations to empirically evaluate our algorithm, and the results confirm its improved performance using malleable workloads consisting of a wide range of parallelism variation structures.

MOTIVATION: Motifs in DNA sequences often appear in degenerate form, so there has been an increased interest in computational algorithms for weak motif discovery. Probabilistic algorithms are unable to detect weak motifs while exact methods have been able to detect only short weak motifs. This article proposes an exact tree-based motif detection (TreeMotif) algorithm capable of discovering longer and weaker motifs than by the existing methods. RESULTS: TreeMotif converts the graphical representation of motifs into a tree-structured representation in which a tree that branches with nodes from every sequence represents motif instances. The method of tree construction is novel to motif discovery based on graphical representation. TreeMotif is more efficient and scalable in handling longer and weaker motifs than the existing algorithms in terms of accuracy and execution time. The performances of TreeMotif were demonstrated on synthetic data as well as on real biological data. AVAILABILITY: https://sites.google.com/site/shqssw/treemotif CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

With proliferation of multicore computers and multiprocessor systems, an imminent challenge is to efficiently schedule parallel applications on these resources. In contrast to conventional static scheduling, adaptive schedulers that dynamically allocate processors to jobs possess good potential for improving processor utilization and speeding up job's execution. In this paper, we focus on adaptive scheduling of malleable jobs with periodic processor reallocations based on parallelism feedback of the jobs and allocation policy of the system. We present an efficient adaptive scheduler Acdeq that provides parallelism feedback using an adaptive controller A-Control and allocates processors based on the well-known Dynamic Equipartitioning algorithm (Deq). Compared to A-Greedy, an existing adaptive scheduler that experiences feedback instability thus incurs unnecessary scheduling overheads, we show that A-Control achieves much more stable feedback among other desirable control-theoretic properties. Furthermore, we analyze algorithmically the performances of Acdeq in terms of its response time and processor waste for an individual job as well as makespan and total response time for a set of jobs. To the best of our knowledge, Acdeq is the first multiprocessor scheduling algorithm that offers both control-theoretic and algorithmic guarantees. We further evaluate Acdeq via simulations by using Downey's parallel job model augmented with internal parallelism variations. The results confirm its improved performances over Agdeq, and they show that Acdeq excels especially when the scheduling overhead becomes high.

The emergence of multi-core computers has led to explosive development of parallel applications and hence the need of efficient schedulers for parallel jobs. Adaptive online schedulers have recently been proposed to exploit the multiple processor resource and shown good promise in theory. To verify the effectiveness of these parallel schedulers, it will be reassuring to test them extensively with various parallel workloads. Unfortunately it is still unknown how the job mixes will eventually evolve for multi-core computers; moreover, it is also non-obvious how the parallelism of a typical job will look like. To evaluate the dynamic behaviors of an adaptive scheduler under various scenarios, an ideal workload model for schedulers should thus allow the user to vary parallelism profiles of individual jobs as well as the job arrival patterns. In this paper, we present a tool called Malleable-Lab, which models malleable parallel jobs by extending the traditional moldable job models. Instead of generating a completely random parallelism, which does not allow clear account of the request-allocate responses, we identify several generic patterns of parallelism variations in parallel programs. Using Malleable-Lab we have evaluated two feedback-driven adaptive schedulers, namely, AG-DEQ (Adaptive-Greedy-DEQ) and ABG-DEQ (Adaptive B-Greedy-DEQ), and the well-known scheduler EQUI (Equi-partition). The results reveal that both feedback-driven schedulers outperform EQUI, but on the other hand suffer from high sensitivity to the scheduling overhead. We also found that ABG-DEQ exhibits better transient responses and stability than AG-DEQ. In conclusion, the tool has enabled us to analyze various aspects of the performance of online schedulers, and we have gained valuable insights for adaptive scheduling of parallel jobs on multiple processors.

BACKGROUND: Weak motif discovery in DNA sequences is an important but unresolved problem in computational biology. Previous algorithms that aimed to solve the problem usually require a large amount of memory or execution time. In this paper, we proposed a fast and memory efficient algorithm, RecMotif, which guarantees to discover all motifs with specific (l, d) settings (where l is the motif length and d is the maximum number of mutations between a motif instance and the true motif). RESULTS: Comparisons with several recently proposed algorithms have shown that RecMotif is more scalable for handling longer and weaker motifs. For instance, it can solve the open challenge cases such as (40, 14) within 5 hours while the other algorithms compared failed due to either longer execution times or shortage of memory space. For real biological sequences, such as E.coli CRP, RecMotif is able to accurately discover the motif instances with (l, d) as (18, 6) in less than 1 second, which is faster than the other algorithms compared. CONCLUSIONS: RecMotif is a novel algorithm that requires only a space complexity of O(m²n) (where m is the number of sequences in the data and n is the length of the sequences).

This work presents an empirical property-based model to describe web-based vulnerability. We define a web application using a new descriptive model with pre-condition, behavior, entity and communication property sets. The Vulnerable Property Relationship Graph (VPRG) defines a vulnerability as vulnerable properties in application with relations to other properties in cause- and consequence-relationships. The Vulnerable Property Relationship Matrix (VPRM) is used to quantify the existence vulnerability and to measure its impact according to the relations of vulnerable properties to other properties in execution of the web application. A severity score calculation is proposed based on VPRM: the vulnerability severity score is typically the sum of consequence as a result of state changes of every evolving property in the vulnerable property relationship model. The prototype model is applied to a case study involving specified web vulnerabilities.

This paper presents a cognitive approach for a reliable yet battery-friendly personal positioning. A user's position is learned from both historical log and possible measurements. Firstly, user's past activities recorded in the log are summarized into an activity map. Accordingly, a user-habit guided particle filtering algorithm is presented for position prediction. Specifically, our algorithm makes reference to the map to determine the most probable correct position, smoothed with occasional measurement. User's current position is modeled probabilistically by a collection of particles and her future moves are modeled with a tendency to follow a familiar path on the map; The estimate is then smoothed by Bayesian filtering. We also allow the number of particles to vary according to user's position in the map. Thus, along with better insights about user's movement experience, our approach can learn from the past and potentially improve the quality of estimates. Our experiments show that this adaptive filtering model using the activity map can deal with non-linear behaviors rather effectively. The new cognitive scheme can indeed track the user's position with a high degree of accuracy. Moreover, the algorithms exhibit low computational complexities, making them well suited for applications on wearable computers.

In order to improve processor utilizations on parallel systems, adaptive scheduling with parallelism feedback was recently proposed. A-Greedy, an existing adaptive scheduler, offers provably-good job execution time and processor utilization. Unfortunately, it suffers from unstable feedback and hence unnecessary processor reallocations even when the job has constant parallelism. This problem may cause difficulties in the management of system resources. We propose a new adaptive scheduler called ABG (for Adaptive B-Greedy), which ensures both performance and stability. In a direct comparison with A-Greedy using simulated dataparallel jobs, ABG shows an average 50% reduction in wasted processor cycles and an average 20% improvement in running time. For a set of jobs, ABG also outperforms A-Greedy by 10% to 15% on average in terms of both makespan and mean response time, provided the system is not heavily loaded. Our detailed analysis shows that ABG indeed offers improved transient and steady-state behaviors in terms of control-theoretic metrics. Using trim analysis, we show that ABG provides nearly linear speedup for individual jobs and good processor utilizations. Using competitive analysis, we also show that ABG offers good makespan and mean response time bounds.

Multiprocessor scheduling in a shared multiprogramming environment can be structured as two-level scheduling, where a kernel-level job scheduler allots processors to jobs and a user-level thread scheduler schedules the work of a job on its allotted processors. We present a randomized work-stealing thread scheduler for fork-join multithreaded jobs that provides continual parallelism feedback to the job scheduler in the form of requests for processors. Our A-STEAL algorithm is appropriate for large parallel servers where many jobs share a common multiprocessor resource and in which the number of processors available to a particular job may vary during the job's execution. Assuming that the job scheduler never allots a job more processors than requested by the job's thread scheduler, A-STEAL guarantees that the job completes in near-optimal time while utilizing at least a constant fraction of the allotted processors. We model the job scheduler as the thread scheduler's adversary, challenging the thread scheduler to be robust to the operating environment as well as to the job scheduler's administrative policies. For example, the job scheduler might make a large number of processors available exactly when the job has little use for them. To analyze the performance of our adaptive thread scheduler under this stringent adversarial assumption, we introduce a new technique called trim analysis, which allows us to prove that our thread scheduler performs poorly on no more than a small number of time steps, exhibiting near-optimal behavior on the vast majority. More precisely, suppose that a job has work T 1 and span T ∞ . On a machine with P processors, A-STEAL completes the job in an expected duration of O ( T 1 / P˜ + T ∞ + L lg P ) time steps, where L is the length of a scheduling quantum, and P˜ denotes the O ( T ∞ + L lg P )-trimmed availability. This quantity is the average of the processor availability over all time steps except the O ( T ∞ + L lg P ) time steps that have the highest processor availability. When the job's parallelism dominates the trimmed availability, that is, P˜ < T 1 / T ∞ , the job achieves nearly perfect linear speedup. Conversely, when the trimmed mean dominates the parallelism, the asymptotic running time of the job is nearly the length of its span, which is optimal. We measured the performance of A-STEAL on a simulated multiprocessor system using synthetic workloads. For jobs with sufficient parallelism, our experiments confirm that A-STEAL provides almost perfect linear speedup across a variety of processor availability profiles. We compared A-STEAL with the ABP algorithm, an adaptive work-stealing thread scheduler developed by Arora et al. [1998] which does not employ parallelism feedback. On moderately to heavily loaded machines with large numbers of processors, A-STEAL typically completed jobs more than twice as quickly as ABP, despite being allotted the same number or fewer processors on every step, while wasting only 10% of the processor cycles wasted by ABP.

Multiprocessor scheduling in a shared multiprogramming environment can be structured in two levels, where a kernel-level job scheduler allots processors to jobs and a user-level thread scheduler maps the ready threads of a job onto the allotted processors. We present two provably-efficient two-level scheduling schemes called G-RAD and S-RAD respectively. Both schemes use the same job scheduler RAD for the processor allotments that ensures fair allocation under all levels of workload. In G-RAD, RAD is combined with a greedy thread scheduler suitable for centralized scheduling; in S-RAD, RAD is combined with a work-stealing thread scheduler more suitable for distributed settings. Both G-RAD and S-RAD are non-clairvoyant. Moreover, they provide effective control over the scheduling overhead and ensure efficient utilization of processors. We also analyze the competitiveness of both G-RAD and S-RAD with respect to an optimal clairvoyant scheduler. In terms of makespan, both schemes can achieve O(1)-competitiveness for any set of jobs with arbitrary release time. In terms of mean response time, both schemes are O(1)-competitive for arbitrary batched jobs. To the best of our knowledge, G-RAD and S-RAD are the first non-clairvoyant scheduling algorithms that guarantee provable efficiency, fairness and minimal overhead.

A parallel program usually incurs operations on multiple processing resources, interleaving computations, I/Os, and communications, where each task can only be executed on a processor of a matching category. Many parallel systems also embed special-purpose processors like vector units, floating-point co-processors, and various I/O processors. Presently, there is no provably good scheduling algorithm that ensures efficient use of multiple resources with functional heterogeneity. This paper presents K-RAD, an algorithm that adoptively schedules parallel jobs on multiple processing resources without requiring prior information about the jobs, such as their release times and parallelism profiles. Let K denote the number of categories of heterogenous resources and Pmaxdenote the maximum number of processors among all categories. We show that, for any set of jobs with arbitrary release times, K-RAD is (K + 1 - 1/Pmax)- competitive with respect to the makespan. This competitive ratio is provably the best possible for any non-clairvoyant deterministic algorithms for K-resource scheduling. We also show that K-RAD is (4K + 1 - 4K/(|J| + 1))- competitive with respect to the mean response time for any batched job set J. For the special case of K = 1, i.e., scheduling on homogeneous resources, the best existing mean response time bound for online non-clairvoyant algorithm is 2 + radic(3) ap 3.73 proved by Edmonds et al. in STOC'97. We show that K-RAD is 3-competitive with respect to the mean response time when K = 1, which offers the best competitive ratio to date.

Multiprocessor scheduling in a shared multiprogramming environment can be structured as two-level scheduling, where a kernel-level job scheduler allots processors to jobs and a user-level thread scheduler schedules the work of a job on the allotted processors. In this context, the number of processors allotted to a particular job may vary during the job's execution, and the thread scheduler must adapt to these changes in processor resources. For overall system efficiency, the thread scheduler should also provide parallelism feedback to the job scheduler to avoid allotting a job more processors than it can use productively. This paper provides an overview of several adaptive thread schedulers we have developed that provide provably good history-based feedback about the job's parallelism without knowing the future of the job. These thread schedulers complete the job in near-optimal time while guaranteeing low waste. We have analyzed these thread schedulers under stringent adversarial conditions, showing that the thread schedulers are robust to various system environments and allocation policies. To analyze the thread schedulers under this adversarial model, we have developed a new technique, called trim analysis, which can be used to show that the thread scheduler provides good behavior on the vast majority of time steps, and performs poorly on only a few. When our thread schedulers are used with dynamic equipartitioning and other related job scheduling algorithms, they are O(1)-competitive against an optimal offline scheduling algorithm with respect to both mean response time and makespan for batched jobs and nonbatched jobs, respectively. Our algorithms are the first nonclairvoy-ant scheduling algorithms to offer such guarantees.

Scheduling competing jobs on multiprocessors has always been an important issue for parallel and distributed systems. The challenge is to ensure global, system-wide efficiency while offering a level of fairness to user jobs. Various degrees of successes have been achieved over years. However, few existing schemes address both efficiency and fairness over a wide range of work loads. Moreover, in order to obtain analytical results, most of them require prior information about jobs, which may be difficult to obtain in real applications. This paper presents a novel adaptive scheduling algorithm GRAD that ensures fair allocation under all levels of workload, and it offers provable efficiency without requiring prior information of job's parallelism. Moreover, it provides effective control over the scheduling overhead and ensures efficient utilization of processors. Specifically, we show that GRAD is O(1)-competitive against an optimal offline scheduling algorithm with respect to both mean response time and makespan for batched jobs and non-batched jobs respectively. To the best of our knowledge, GRAD is the first non-clairvoyant scheduling algorithm that offers such guarantees. We also believe that our new approach of resource request-allotment protocol deserves further exploration. The simulation results show that, for non-batched jobs, the makespan produced by GRAD is no more than 1.39 times of the optimal on average. For batched jobs, the mean response time produced by GRAD is no more than 2.37 times of the optimal on average.

Multiprocessor scheduling in a shared multiprogramming environment is often structured as two-level scheduling, where a kernel-level job scheduler allots processors to jobs and a user-level task scheduler schedules the work of a job on the allotted processors. In this context, the number of processors allotted to a particular job may vary during the job's execution, and the task scheduler must adapt to these changes in processor resources. For overall system efficiency, the task scheduler should also provide parallelism feedback to the job scheduler to avoid the situation where a job is allotted processors that it cannot use productively.We present an adaptive task scheduler for multitasked jobs with dependencies that provides continual parallelism feedback to the job scheduler in the form of requests for processors. Our scheduler guarantees that a job completes near optimally while utilizing at least a constant fraction of the allotted processor cycles. Our scheduler can be applied to schedule data-parallel programs, such as those written in High Performance Fortran (HPF), *Lisp, C*, NESL, and ZPL.Our analysis models the job scheduler as the task scheduler's adversary, challenging the task scheduler to be robust to the system environment and the job scheduler's administrative policies. For example, the job scheduler can make available a huge number of processors exactly when the job has little use for them. To analyze the performance of our adaptive task scheduler under this stringent adversarial assumption, we introduce a new technique called "trim analysis," which allows us to prove that our task scheduler performs poorly on at most a small number of time steps, exhibiting near-optimal behavior on the vast majority.To be precise, suppose that a job has work T1 and critical-path length T∞ and is running on a machine with P processors. Using trim analysis, we prove that our scheduler completes the job in O(T1/P + T∞ + Llg P) time steps, where L is the length of a scheduling quantum and P denotes the O(T∞ + L lg P)-trimmed availability. This quantity is the average of the processor availability over all time steps excluding the O(T∞ + L lg P) time steps with the highest processor availability. When T1/T∞ >> P (the job's parallelism dominates the O(T∞ + L lg P)-trimmed availability), the job achieves nearly perfect linear speedup. Conversely, when T1/T∞ << P, the asymptotic running time of the job is nearly the length of its critical path.

We propose a simple distributed hash table called ReCord, which is a generalized version of Randomized- Chord and offers improved tradeoffs in performance and topology maintenance over existing P2P systems. ReCord is scalable and can be easily implemented as an overlay network, and offers a good tradeoff between the node degree and query latency. For instance, an n-node ReCord with O(log n) node degree has an expected latency of \theta (\log n) hops. Alternatively, it can also offer \theta (\frac{{\log n}}{{\log \log n}}) hops latency at a higher cost of o(\frac{{\log ^2 n}}{{\log \log n}}) node degree. Meanwhile, simulations of the dynamic behaviors of ReCord are studied.

Recently a bulk of research [14, 5, 15, 9] has been done on the modelling of the small-world phenomenon, which has been shown to be pervasive in social and nature networks, and engineering systems [16, 1, 2, 11]. In order to examine the navigating aspects of small-world graphs, Kleinberg [9] proposes a network model based on a d-dimensional torus lattice with long-range links chosen at random according to the d-harmonic distribution. Kleinberg shows that the greedy routing algorithm, by using only local information, performs in O(lg^2 n) expected number of hops.We extend Kleinberg’s small-world model in that each node x has two more random links to nodes chosen uniformly and randomly within (lg n)\frac{2}{a} Manhattan distance from x, where d denotes the dimension of the model. Based on this extended model, we then propose an oblivious algorithm that can route messages between any two nodes in O(lg n) expected number of hops, which is an optimal expected bound for routing. Our routing algorithm keeps only O((\lg n)^{\beta + 1} ) bits of information on each node, where 1 \le \beta \le 2, thus being scalable with the network size. To our knowledge, our result is the first to achieve the optimal routing complexity while stillkeeping a poly-logarithmic number of bits of information stored on each node in the small-world networks. Our results may be applied to the design of the logical overlay structure of large-scale distributed systems, such as peer-to-peer networks, in the same spirit as Symphony [11].

This paper presents the exchanged hypercube, a new interconnection network obtained by systematically removing links from a binary hypercube. It maintains several desirable properties of the binary hypercube yet with reduced interconnection complexity. We also introduce the extended binomial tree, a spanning tree of the exchanged hypercube that preserves many desirable properties of the original binomial tree. A fault-tolerant routing strategy is also proposed for the exchanged hypercube.

We address the issue of shuffling loads in automated storage/retrieval system (AS/RS). To minimize the response time of retrievals, we pre-sort the loads into any specified locations. 1D, 2D and 3D AS/RS racks have been designed to achieve the shuffling efficiently. The corresponding shuffling algorithms are described in detail. The response time of retrieval, the lower and upper bounds of energy consumption are also derived. Results of the analysis and numerical experiments show that the shuffling algorithms are quite efficient indeed.

Summary form only given. One common problem with present P2P systems is the dynamic membership of the peer hosts. The arbitrary joining and leaving of the peers make it difficult to maintain the overlay structure of the system and cause large amount of nonproductive exchange of protocol overhead (e.g., updating finger entries to adjust the structure). We present a novel, decentralized and fault tolerant protocol called Alpha-Beta cluster-based protocol (ABC). With the new scheme, the function of a node is undertaken by a cluster of hosts; moreover, the size of a cluster can vary between an upper bound (Alpha) and a lower bound (Beta). This helps maintain the stability of the system even if nodes join or leave the system dynamically; it also retains the query response efficiency. With each node maintaining at most 2logn+2logn/loglogn logical links, ABC can achieve each query within at most 2logn/loglogn hops. In addition, we present a modified ABC which reduces the number of hops to at most logn/loglogn with the same number of logic links. The two protocols offer provably better performance than existing protocols while solving the stability problem.

In conventional Automated Storage and Retrieval Systems (AS/RS), stacker cranes are used to deliver loads to the AS/RS racks and to retrieve loads from the racks. Stacker cranes travel simultaneously in the vertical and horizontal directions. However, the stacker cranes are inadequate for extra heavy loads. In this paper a new kind of Storage/Retrieval (S/R) mechanism is presented to handle such loads. Unlike stacker cranes, the new S/R mechanism has one vertical platform and N horizontal platforms to serve N tiers of an AS/RS rack. The vertical platform provides the vertical link among the tiers of the AS/RS rack, whereas the horizontal platforms transfer loads to the individual storage cells on a given tier. The operations of the vertical platform and the horizontal platforms may be independent and concurrent. In this paper, the design, operation and advantages of the new mechanism are presented. We present a travel-time model under the dwell point policy that the platforms remain where they are after completing a storage/retrieval operation. The model is validated by computer simulations. The results show that our model is reliable for the design and analysis of the new kind of AS/RS. We also present guidelines for the optimal design of a rectangular-in-time AS/RS rack with the new S/R mechanism.

The ever-increasing demand on container port throughput has mounted the necessity of a more efficient container storage structure, the requirements of which apparently can be met by AS/RS because of its abilities of fully automating material handling and the potentials for delivering high performance. In this study, we present an AS/RS for container storage, develop the travel time models for the proposed system, and confirm its feasibility in terms of throughput performance. A pre-processing scheme for operation scheduling that significantly improves AS/RS throughput is proposed and evaluated. Additional constraints arising from the container size and weight on AS/RS design and scheduling are taken into considerations, which in effect leads to a platform-based AS/RS.

Automated guided vehicles (or AGVs) have become an important option in material handling. In many applications, such as container terminals, the service area is often arranged into rectangular blocks, which leads to a mesh-like path topology. Therefore, developing efficient algorithms for AGV routing on the mesh topology has become an important research topic. In this paper, we present a discrete time model, based on which a simple routing algorithm on the mesh topology is presented. The algorithm works by carefully choosing suitable parameters such that the vehicles using a same junction will arrive at different points in time, and hence no conflicts will occur during the routing; meanwhile, high routing performance can be achieved. Analyses of the task completion time and the requirements on timing control during the AGV routing are also presented.

We examine the application of Cilk, a C-based runtime system for multithreaded parallel programming in task scheduling. Given a task graph G, the output of the scheduling algorithm is an intermediate schedule $\mathcal{S}$ which, when interpreted by the Cilk runtime scheduler, guarantees that the tasks will be executed concurrently in a manner consistent with the precedence requirement of G. However, there are certain precedence relations that cannot be expressed exactly in the Cilk model—hence no algorithms can guarantee an optimal schedule for task graphs containing such relations. Nonetheless, this limitation does not prevent Cilk from becoming a useful tool for task scheduling. Let n and e denote the number of nodes and edges of a task graph. By using Tarjan's disjoint-set algorithm to handle tasks that can be scheduled concurrently, we demonstrate that an intermediate schedule can be derived in $O(n+e)$ time for any task graph of practical size. We further show that with P processors, the expected completion time for the scheduled tasks achieves a near-optimum of $\Gamma_{P} \approx \Gamma_{1} / P + 1.5\Gamma_{\infty}$, where $\Gamma_{1}$ denotes the work, i.e. the sequential execution time of all tasks, and $\Gamma_{\infty}$ denotes the critical path, i.e. the total execution time of all tasks lying on the longest dependency path. Besides confirming its expressive power in handling complicated types of concurrency, our results show that the performance guarantee of Cilk can lead to a new efficient approach for task scheduling.

We present a new class of interconnection topologies called the Linear Recursive Networks (LRNs) and examine their possible applications in distributed systems. Each LRN is characterized by a recursive pattern of interconnection which can be specified by simple parameters. Basic properties such as node degree, diameter, and the performance of routing algorithms for all LRNs are then collectively analyzed in terms of these parameters. By choosing appropriate values for the parameters, our results can assist a network designer in selecting a topology with required routing performance and cost of interconnection. A subclass of LRNs, called Congruent LRNs (CLRNs), is also identified here and shown to possess desirable properties for more tightly coupled systems. It is shown that the CLRNs include existing networks such as hypercube and generalized Fibonacci cubes. These results suggest that the linear recursive networks potentially have applications in interconnecting distributed systems.

The interconnection topology of a network plays a key role in determining the performance and cost of routing messages in the system. Presently, there are many known results about individual network topologies and their applications. However, relatively few results exist about the relations among these topologies; for instance, it is rather difficult to relate quantitatively the cost of interconnection with the routing efficiency. As such, the theory is incomplete for assisting a designer to choose a suitable topology for a required routing performance under a given cost of interconnection. Here, by extending the popular hypercube, a family of parameterized network topologies called Gaussian Cubes (GCs) is presented. By varying the parameter that controls the interconnection density, the routing performance of a GC can be scaled according to the traffic loads without changing the routing algorithm. It is demonstrated that these new networks can approximate the concurrent offered by hypercubes while lowering the cost of interconnection; common communication primitives such as Unicast, Multicast and Broadcast can all be supported efficiently on GCs. Therefore, the new network topologies can be applied to distributed systems with scalable messaging performance. Because GCs are also subgraphs of the conventional hypercubes, our results may also be useful to fault-tolerant computing based on hypercubes.

We present a new class of interconnection topologies called the Linear Recursive Networks. It is shown that each member of this fairly large class of network topologies possesses a recursively-decomposable structure. The path and connectivity properties of the entire class of networks are analyzed and found to have useful features. It is also demonstrated that Point-To-Point or Broadcasting/Gathering operations can be performed efficiently on all Linear Recursive Networks. The preliminary results suggest that the Linear Recursive Networks potentially have many applications.

A novel interconnection topology called the Fibonacci cube is shown to possess attractive recurrent structures in spite of its asymmetric and relatively sparse interconnections. Since it can be embedded as a subgraph in the Boolean cube (hypercube) and it is also a supergraph of other structures, the Fibonacci cube may find applications in fault-tolerant computing. For a graph with N nodes, the diameter, the edge connectivity, and the node connectivity of the Fibonacci cube are in the logarithmic order of N. It is also shown that common system communication primitives can be implemented efficiently.>