A multiple case study of design pattern decay, grime, and rot in evolving software systems

Software designs decay as systems, uses, and operational environments evolve. Decay can involve the design patterns used to structure a system. Classes that participate in design pattern realizations accumulate grime—non-pattern-related code. Design pattern realizations can also rot, when changes break the structural or functional integrity of a design pattern. Design pattern rot can prevent a pattern realization from fulfilling its responsibilities, and thus represents a fault. Grime buildup does not break the structural integrity of a pattern but can reduce system testability and adaptability. This research examined the extent to which software designs actually decay, rot, and accumulate grime by studying the aging of design patterns in three successful object-oriented systems. We generated UML models from the three implementations and employed a multiple case study methodology to analyze the evolution of the designs. We found no evidence of design pattern rot in these systems. However, we found considerable evidence of pattern decay due to grime. Dependencies between design pattern components increased without regard for pattern intent, reducing pattern modularity, and decreasing testability and adaptability. The study of decay and grime showed that the grime that builds up around design patterns is mostly due to increases in coupling.     

A lower bound for sorting networks based on the shuffle permutation

We prove an (lg² n/lg lgn) lower bound for the depth ofn-input sorting networks based on the shuffle permutation. The best previously known lower bound was the trivial (lgn) bound, while the best upper bound is given by Batcher's (lg² n)-depth bitonic sorting network. The proof technique employed in the lower bound argument may be of independent interest.C. G. Plaxton was supported by NSF Research Initiation Award CCR-9111591, and the Texas Advanced Research Program under Grant No. 003658-480. T. Suel was supported by the Texas Advanced Research Program under Grant No. 003658-480, and by an MCD Fellowship of the University of Texas at Austin.     

A shuffle to achieve high efficiency through pre-computation and batch verification

Shuffle is an important anonymous routing protocol, in which a shuffling node (router) re-encrypts and reorders some encrypted messages. It is usually used to build anonymous communication networks. A new shuffle scheme is proposed in this paper. A shuffling node’s costly operations can be carried out offline in advance so that its online efficiency is very high. Moreover, any verifier can employ batch verification to efficiently verify validity of the shuffle. As in practical applications of shuffles like e-voting, there are many verifiers including some entities with weak computation capability, and offline pre-computation is a feasible solution for a shuffling node; our proposal is an effective efficiency optimisation mechanism. So our new shuffle design has an advantage in practical efficiency over the existing shuffle schemes. Moreover, its achievement of desired security properties is formally proved only on the base of the most basic computational assumption inevitable in any shuffle. Application of our new shuffle to e-voting is described in the end of this paper to show its importance and applicability in practice.     

Topological comparison of perfect shuffle and hypercube

Novel topological measures for static multiprocessor interconnection networks,disconnectivity, looseness, andcost-effectiveness, are developed. These and other measures are employed for a comparative analysis of such networks. The goal of this analysis is to predict network effectiveness, without resorting to execution benchmark techniques. In particular, we compare thehypercube andperfectshuffle-nearest-neighbor networks, and show that they are the best candidates for multiprocessor interconnections. We specifically find that the hypercube is capable of somewhat better performance than perfect-shuffle-nearest-neighbor, but the latter is significantly more cost-effective.     

A study of design characteristics in evolving software using stability as a criterion

There are many ideas in software design that are considered good practice. However, research is still needed to validate their contributions to software maintenance. This paper presents a method for examining software systems that have been actively maintained and used over the long term and are potential candidates for yielding lessons about design. The method relies on a criterion of stability and a definition of distance to flag design characteristics that have potentially contributed to long-term maintainability. It is demonstrated by application to an example of long-lived scientific software. The results from this demonstration show that the method can provide insight into the relative importance of individual elements of a set of design characteristics for the long-term evolution of software.     

Unison,canon, and sluggish clocks in networks controlled by a synchronizer

The effect of using a simple synchronizer on the performance of a directed, strongly connected, distributed network, is analysed. In this paper we assume that the time of message transmission is positive but negligible. It is shown that the synchronizer is sufficient to assure that a full rate of computation is achieved in networks with a global clock, in spite of the absence of a global start-up signal. In fact,unison is reached within linear time. A similar phenomenon occurs if there is no global clock, but all local clocks have the same rate. In case the local clocks do not have the same rate, it is shown that the computational rate is not slower than anysluggish clock; i.e., a clock such that between any two of its ticks, every local clock ticks at least once.The first author was supported by the Fund for the Promotion of Research at the Technion. The work of the second author was done while he was in the Computer Science Department of the Technion; he is presently visiting the Laboratory for Computer Science, MIT.     

A generative model for time evolving networks

Time evolving networks have some properties in common with complex networks, while some characteristics are specific to their time evolving nature. A number of interesting properties have been observed in time-varying complex networks such as densification power-law, shrinking diameter, scale-free degree distribution, big clustering coefficient and the emergence of community structure. Existing generative models either fail to simulate all the properties or undermine the social interactions between the existing nodes over time. In this paper, we propose a generative model called socializing graph model (SGM) for those networks that evolve over time. It is an iterative procedure consisting of two steps. In the first step, we add one new node to the network at every timestamp and connect it to an existing node using a preferential attachment rule. In the second step, we add a number of edges between the existing nodes in order to reflect the emergence of social interactions between nodes over time and mimic the evolution of real networks. We present empirical results to show that SGM generates realistic prototypes of evolving networks.

     

Ridges, crests and sub-parabolic lines of evolving surfaces

The ridge lines on a surface can be defined either via contact of the surface with spheres, or via extrema of principal curvatures along lines of curvature. Certain subsets of ridge lines called crest lines have been singled out by some authors for medical imaging applications. There is a related concept of sub-parabolic line on a surface, also defined via extrema of principal curvatures.In this paper we study in detail the structure of the ridge lines, crest lines and sub-parabolic lines on a generic surface, and on a surface which is evolving in a generic (one-parameter) family. The mathematical details of this study are in Bruce et al. (1994c).Supported by the Esprit grant VIVA.     

A computational evolutionary approach to evolving game strategy and cooperation

This paper describes an approach to the co-evolution of competing virtual creatures. Pairs of individuals enter one-on-one contests in which they contend to establish contact with a common resource. The individuals are subjected to competitive fitness functions. In each tournament one type of organism implements a game rule based on a set of basic cognitive capabilities. The second type of contestant genetically determines its game strategy. Interesting strategy patterns are identified when this evolutionary process is simulated on populations of competing individuals. These experiments show how cooperation emerges in order to improve both individual and collective game performances.     

Comments on "A computational evolutionary approach to evolving game strategies and cooperation"

Azuaje offers an approach to the co-evolution of competing virtual creatures and a model for the evolution of game strategies and their emerging behaviors (F. Azuaje, see ibid., vol. 33, p.498-502, 2003). This model can be greatly simplified and optimal solutions can be obtained more quickly and easily by using an analytical approach. We emphasize the importance of performing a model analysis before choosing an evolutionary or analytical approach to a problem. Furthermore, Azuaje's model is derived from the Prisoner's Dilemma, a classical model in game theory; some results have already been discussed in the literature. We discuss his model from the perspective of game theorists.     

Passive-space and time view: vector clocks for achieving higherperformance, program correction, and distributed computing

We have noticed two problems with viewing a process as a sequence of events. The first problem is the complete loss of information about potential intra-process concurrency for both sequential and distributed computations, and partial loss of information about potential inter-process concurrency for distributed computations. The second problem is that the resulting reasoning framework does not lend itself to refinement (from sequential computing or a given set of distributed processes) to a preferable set of distributed processes. We argue that it is more natural to view a computation, either distributed or sequential, as a partially ordered set of events. Doing so leads to a view, called passive-space and time view, which we propose. To aid users of the relation “Affects” in developing algorithms, we define vector clocks, that are global logical clocks, so that the relation “Affects”, and hence all potential concurrency, between events can be identified from their timestamps assigned     

基于向量时钟模型的NoSQL最终一致性的研究

最终一致性作为衡量NoSQL数据库性能的重要指标,对NoSQL的应用与发展起着重要作用。针对最终一致性解决方案存在的问题,提出基于向量时钟的最终一致性模型。模型为数据加入了版本的概念,通过版本向量和时间戳的引入,为数据标识了版本信息,同时给出了冲突检测和处理方案。对比分析表明,方案很好地解决了问题,提高了最终一致性的性能,在NOSQL数据库的设计过程中具有较好的应用价值。     

A single pass algorithm for clustering evolving data streams based on swarm intelligence

Existing density-based data stream clustering algorithms use a two-phase scheme approach consisting of an online phase, in which raw data is processed to gather summary statistics, and an offline phase that generates the clusters by using the summary data. In this article we propose a data stream clustering method based on a multi-agent system that uses a decentralized bottom-up self-organizing strategy to group similar data points. Data points are associated with agents and deployed onto a 2D space, to work simultaneously by applying a heuristic strategy based on a bio-inspired model, known as flocking model. Agents move onto the space for a fixed time and, when they encounter other agents into a predefined visibility range, they can decide to form a flock if they are similar. Flocks can join to form swarms of similar groups. This strategy allows to merge the two phases of density-based approaches and thus to avoid the computing demanding offline cluster computation, since a swarm represents a cluster. Experimental results show that the bio-inspired approach can obtain very good results on real and synthetic data sets.     

Design and reliability analysis of fault-tolerant shuffle exchange gamma logical neighborhood interconnection network

The Journal of Supercomputing - Multistage interconnection networks are used as a medium for interconnecting processors and memories in multiprocessor systems. Multistage interconnection networks...     

Controlling the spreading in small-world evolving networks: stability, oscillation, and topology

The spreading of viruses, diseases, and even disasters (such as power blackouts and financial crises) in many large-scale and small-world networks is one of the mostly concerned issues today. In this note, we study general spreading dynamical behaviors in small-world evolving networks when control strategies are applied to suppress the propagation of diseases, viruses, and disasters. After proposing a novel Watts-Strogatz (W-S) spreading model to capture the general spreading mechanism in small-world networks, we investigate the stability and Hopf bifurcations of delay-controlled spreading models with linear and nonlinear feedback controllers, where parameters of small-world rewiring probability, feedback control gain, and time delay are analyzed for the oscillating behaviors. We conclude that the oscillatory spreading phenomena in delay-controlled small-world networks are topologically inherent.     

A study on video semantics; overview,challenges, and applications

Multimedia Tools and Applications - Due to the increase in surveillance systems, there is a massive increase in surveillance data. As of now, the key challenge for video surveillance systems is...     

An Eulerian approach to transport and diffusion on evolving implicit surfaces

In this article we define a level set method for a scalar conservation law with a diffusive flux on an evolving hypersurface Γ(t) contained in a domain W ì \mathbb Rⁿ⁺¹{\Omega \subset \mathbb R^{n+1}} . The partial differential equation is solved on all level set surfaces of a prescribed time dependent function Φ whose zero level set is Γ(t). The key idea lies in formulating an appropriate weak form of the conservation law with respect to time and space. A major advantage of this approach is that it avoids the numerical evaluation of curvature. The resulting equation is then solved in one dimension higher but can be solved on a fixed grid. In particular we formulate an Eulerian transport and diffusion equation on evolving implicit surfaces. Using Eulerian surface gradients to define weak forms of elliptic operators naturally generates weak formulations of elliptic and parabolic equations. The finite element method is applied to the weak form of the conservation equation yielding an Eulerian Evolving Surface Finite Element Method. The computation of the mass and element stiffness matrices, depending only on the gradient of the level set function, are simple and straightforward. Numerical experiments are described which indicate the power of the method. We describe how this framework may be employed in applications.