ALBERT

Description: Merged processes (MPs) are a recently proposed condensed representation of a Petri net's behaviour similar to branching processes (unfoldings), which copes well not only with concurrency but also with other sources of state space explosion like sequences of choices. They are by orders of magnitude more compact than traditional unfoldings, and yet can be used for efficient model checking. However, constructing complete MPs is difficult, and the only known algorithm is based on building a (potentially much larger) complete unfolding prefix of a Petri net, whose nodes are then merged. Obviously, this significantly reduces their appeal as a representation that can be used for practical model checking. In this paper, we develop an algorithm that avoids constructing the intermediate unfolding prefix and builds a complete merged process directly from a safe Petri net. In particular, a challenging problem of truncating a merged process is solved.

Description: We present an algorithm for the correction of an XML document with respect to schema constraints expressed as a document type definition. Given a well-formed XML document t seen as a tree, a schema S and a non-negative threshold th , the algorithm finds every tree t ' valid with respect to S such that the edit distance between t and t ' is no higher than th . The algorithm is based on a recursive exploration of the finite-state automata representing structural constraints imposed by the schema, as well as on the construction of an edit distance matrix storing edit sequences leading to correction trees. We prove the termination, correctness and completeness of the algorithm, as well as its exponential time complexity. We also perform experimental tests on real-life XML data showing the influence of various input parameters on the execution time and on the number of solutions found. The algorithm's implementation demonstrates polynomial rather than exponential behavior. It has been made public under the GNU LGPL v3 license. As we show in our in-depth discussion of the related work, this is the first full-fledged study of the document-to-schema correction problem.

Description: Software architecture slicing extracts the right software architecture to provide reference or design guiding for developing software architecture. It will reduce the complexity of the requirement specifications based on a selected slicing criterion of either the component or the connector, but little effort has been made regarding the relationship between forward slicing and backward slicing analysis at the architectural level. This paper combines architecture description language -architecture description language semantics to build behavior graph ( BG) to represent the software architecture, and proposes methods for the coarse-grained software architecture slicing, which can reduce the number of components, connectors and constraints of BG. This method is based on the relationships between the port of the component and the role of the connector, which makes use of both forward and backward coarse-grained architecture slicing of BG. In order to understand the similarities and differences between the forward and backward architecture slicing techniques, some experiments are done. Two results are obtained: The first point is that the average percentage reduction of the backward coarse-grained architecture slice is equal to the average percentage reduction of the forward coarse-grained architecture slice. The second point is that the percentage reduction of the forward coarse-grained architecture slice cluster changes on average, while the percentage reduction of the backward coarse-grained architecture slice cluster change the quickly, and the more extreme cases.

Description: There is an increasing demand to efficiently process emerging types of queries, such as progressive queries (PQs), from contemporary database applications including telematics, e-commerce and social media. Unlike conventional queries, a PQ consists of a set of step-queries (SQ). A user formulates a new SQ on the fly based on the result(s) from the previous SQ(s). Existing database management systems were not designed to efficiently process such queries. In this paper, we present a novel technique to efficiently process a special type of PQ, called monotonic linear PQs, based on dynamically materialized views. The key idea is to create a superior relationship graph for SQs from historical PQs that can be used to estimate the benefit of keeping the current SQ result as a materialized view. The materialized views are used to improve the performance of future SQs. A new storage structure for the materialized views set is designed to facilitate efficient search for a usable view to answer a given SQ. Algorithms/strategies to efficiently construct a superior relationship graph, dynamically select materialized views, effectively manage the materialized views set and efficiently search for usable views are discussed. Experiment results demonstrate that our proposed technique is quite promising.

Description: This article presents AccessedBefore (AccB), an algorithm and its associated minimal hardware support to detect data races, and compares it with two widely known and used commercial tools: Helgrind, the data race detection tool included in the general purpose memory checking suite Valgrind, and Intel Thread Checker, now shipped as part of Intel Thread Inspector. It provides a performance overhead evaluation using current workloads, along with an analysis of AccB's scalability with the number of threads and workload input set size. It demonstrates that AccB is in the range of 2 x to 11 x faster than these two tools. Finally, it shows the complete proof that AccB is complete in that, for every static data race present in a program, there exists an instruction interleaving that would expose this data race such that AccB can detect it.

Description: The problems of query containment, equivalence and minimization are fundamental problems in the context of query processing and optimization. In their classic work published in 1977 [Chandra, A. and Merlin, P. (1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90, ACM, USA], Chandra and Merlin solved the three problems for the language of conjunctive queries (CQ queries) on relational data, under the ‘set-semantics’ assumption for query evaluation. While the results of Chandra and Merlin ((1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90, ACM, USA] have been very influential in database research, it was recognized long ago that the set semantics does not correspond to the semantics of the standard commercial query language structured query language (SQL). Alternative semantics, called bag and bag-set semantics , have been studied since 1993; Chaudhuri and Vardi [(1993) Optimization of Real Conjunctive Queries (Extended Abstract). Proc. PODS , Washington, DC, USA, May 25–28, pp. 59–70. ACM Press, USA] outlined necessary and sufficient conditions for the equivalence of CQ queries under these semantics. (The problems of containment of CQ bag and bag-set queries remain open to this day.) More recently, Cohen [(2006) Equivalence of Queries Combining Set and Bag-Set Semantics. Proc. PODS , Chicago, IL, USA, 26–28 June, pp. 70–79. ACM, USA; (2009) Equivalence of queries that are sensitive to multiplicities. VLDB J. , 18, 765–785] introduced a formalism for treating (generalizations of) CQ queries evaluated under each of set, bag and bag-set semantics uniformly as special cases of the more general combined semantics . This formalism provides tools for studying broader classes of practical SQL queries, specifically important types of queries that arise in on-line analytical processing. Cohen [(2009) Equivalence of queries that are sensitive to multiplicities. VLDB J. , 18, 765–785] provides a sufficient condition for the equivalence of (generalizations of) combined-semantics CQ queries, as well as sufficient and necessary equivalence conditions for several proper sublanguages of the query language of Cohen ((2009) Equivalence of queries that are sensitive to multiplicities. VLDB J. , 18, 765–785]. To the best of our knowledge, no results on minimization of CQ queries beyond set-semantics queries have been reported in the literature. Our goal in this paper is to continue the study of equivalence and minimization of CQ queries. We focus on the practically important problem of finding minimized versions of combined-semantics CQ queries. The main contribution of this paper is the extension of the minimization result of Chandra and Merlin ((1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90, ACM, USA] to all combined-semantics CQ queries; we develop this result using our sufficient condition for containment of combined-semantics CQ queries [Chirkova, R. (2012) Combined-semantics equivalence is decidable for a practical class of conjunctive queries. Submitted for publication]. We also present an extension to all combined-semantics CQ queries of the well-known equivalence condition of Chandra and Merlin ((1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90. ACM, USA] of CQ set-semantics queries. Similarly to the condition of Chandra and Merlin ((1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90. ACM, USA], our extension is given in terms of the relationship between the minimized versions of the queries.

Description: Most previous studies need to learn a complex object model for parsing a specific object instance. This paper directly learns the general parsing patterns from the set of parsed objects and formalizes the parsing patterns as a series of parsing templates instead of learning the complex object model. Moreover, a novel hierarchical structure is presented to represent an object by using the parsing templates, which implicitly contains the multi-scale object parts and their relationships. For a single object, the parsing process is equivalent to establishing its hierarchical representation and determining the parsing template for each node. We combine the top-down decomposing scheme and the bottom-up composing scheme to infer the parsing process and formalize the inference as an energy minimization problem. The effect of our method is demonstrated by parsing the human body with aggressive pose variations. Compared with the state-of-the-art methods, the parsing results are more satisfying.

Description: We propose a transductive Gaussian process (TGP) regression method with regularized Laplacian kernels. Transductive learning exploits not only the labeled data but also the unlabeled test instances for learning. GPs are Bayesian probabilistic regressors which use only labeled data. To use unlabeled data in GPs, regularized Laplacian kernels are used. Similar to the case of a supervised GP regression, the proposed method provides not only the predicted target values but also their error bars. It also provides a hyperparameter selection method based on a Bayesian model selection scheme. We applied the proposed TGP method to the object pose estimation data sets as well as artificial data sets and compared the existing methods. Experimental results show that the proposed method has some advantages over the existing methods.

Description: Owing to the sheer volume of text generated by a microblog site like Twitter, it is often difficult to fully understand what is being said about various topics. This paper presents algorithms for summarizing microblog documents. Initially, we present algorithms that produce single-document summaries but later extend them to produce summaries containing multiple documents. We evaluate the generated summaries by comparing them to both manually produced summaries and, for the multiple-post summaries, to the summarization results of some of the leading traditional summarization systems.

Description: This paper addresses the development of a new framework to control traffic signal lights for a road network with a recently introduced bus rapid transit (BRT) system. By applying automated goal-directed learning and decision-making called reinforcement learning, the best possible traffic signal actions can be sought upon changes of network states as modelled by the signalized cell transmission model (CTM). An extension to a network of cascading interactions with a BRT system has been proposed with simple uni-directional flows without turning movements. Motivated by the BRT system in Thailand, the conventional signalized CTM has been generalized to cope with the preplanned space-usage priority of a BRT over other non-priority vehicles. A BRT physical lane separator as well as the location of BRT stations have been explicitly modelled. The delay function of both carried passengers on BRT and on other non-priority vehicles as well as waiting passengers at stations has been introduced. The deployment of BRT system with one lane deducted by the lane separator cannot reduce the total passenger delay in comparison with the same road and traffic condition before the installation of the BRT system. Moreover, our proposed method outperforms preemptive and differential priority control methods because of the improved awareness of the signal switching cost.

Description: A square matrix of distinct numbers in which every row, column and both diagonals have the same total is referred to as a magic square. Constructing a magic square of a given order is considered a difficult computational problem, particularly when additional constraints are imposed. Hyper-heuristics are emerging high-level search methodologies that explore the space of heuristics for solving a given problem. In this study, we present a range of effective selection hyper-heuristics mixing perturbative low-level heuristics for constructing the constrained version of magic squares. The results show that selection hyper-heuristics, even the non-learning ones deliver an outstanding performance, beating the best-known heuristic solution on average.

Description: Probabilistic Logic Programming (PLP) allows one to represent domains containing many entities connected by uncertain relations and has many applications in particular in Machine Learning. PITA is a PLP algorithm for computing the probability of queries, which exploits tabling, answer subsumption and Binary Decision Diagrams (BDDs). PITA does not impose any restriction on the programs. Other algorithms, such as PRISM, reduce computation time by imposing restrictions on the program, namely that subgoals are independent and that clause bodies are mutually exclusive. Another assumption that simplifies inference is that clause bodies are independent. In this paper, we present the algorithms PITA(IND,IND) and PITA(OPT). PITA(IND,IND) assumes that subgoals and clause bodies are independent. PITA(OPT) instead first checks whether these assumptions hold for subprograms and subgoals: if they do, PITA(OPT) uses a simplified calculation, otherwise it resorts to BDDs. Experiments on a number of benchmark datasets show that PITA(IND,IND) is the fastest on datasets respecting the assumptions, while PITA(OPT) is a good option when nothing is known about a dataset.

Description: This paper discusses a system that extracts and displays temporal and geospatial entities in text. The first task involves identification of all events in a document followed by identification of important events using a classifier. The second task involves identifying named entities associated with the document. In particular, we extract geospatial named entities. We disambiguate the set of geospatial named entities and geocode them to determine the correct coordinates for each place name, often called grounding. We resolve ambiguity based on sentence and article context. Finally, we present a user with the key events and their associated people, places and organizations within a document in terms of a timeline and a map. For purposes of testing, we use Wikipedia articles about historical events, such as those describing wars, battles and invasions. We focus on extracting major events from the articles, although our ideas and tools can be easily used with articles from other sources such as news articles. We use several existing tools such as Evita, Google Maps, publicly available implementations of Support Vector Machines, Hidden Markov Model and Conditional Random Field, and the MIT SIMILE Timeline.

Description: Server-aided verification (SAV) has potential applicability in lightweight devices for improving signature verification, where the verifier possesses a computationally weak hardware. We observe that lightweight devices run all algorithms through hardware implementation with logic circuits. Existing SAV protocols indeed improve computational efficiency for lightweight devices, however, few of them take the hardware cost into consideration. The hardware implementation of SAV protocols could be still costly and expensive for lightweight devices. Currently, the most secure SAV protocols in the literature for pairing-based (G 1 x G 2 -〉 G T ) signatures can securely delegate pairing computations to the server; however, verifiers are still required to perform group operations over two completely different groups G 1 and G T , which heavily contribute to the cost of hardware implementation. In this work, we propose several collusion-resistant SAV protocols for pairing-based signatures to improve their applicability for lightweight devices. In our SAV protocols, verifiers are only required to perform group operations in G 1 . In comparison with existing SAV protocols, our protocols save the unnecessary hardware cost for implementing group operations in G T and therefore are more applicable to lightweight applications.

Description: Secrecy of decryption keys is an important pre-requisite for security of any encryption scheme and compromised private keys must be immediately replaced. Forward Security (FS), introduced to Public Key Encryption (PKE) by Canetti et al. (Eurocrypt 2003), reduces damage from compromised keys by guaranteeing confidentiality of messages that were encrypted prior to the compromise event. The FS property was also shown to be achievable in (Hierarchical) Identity-Based Encryption (HIBE) by Yao et al. (ACM CCS 2004). Yet, for emerging encryption techniques, offering flexible access control to encrypted data, by means of functional relationships between ciphertexts and decryption keys, FS protection was not known to exist. In this paper, we introduce FS to the powerful setting of Hierarchical Predicate Encryption (HPE), proposed by Okamoto and Takashima (Asiacrypt 2009). Anticipated applications of FS-HPE schemes can be found in searchable encryption and in fully private communication. Considering the dependencies among the concepts, our FS-HPE scheme implies forward-secure flavors of Predicate Encryption and (Hierarchical) Attribute-Based Encryption. Our FS-HPE scheme guarantees FS for plaintexts and for attributes that are hidden in HPE ciphertexts. It further allows delegation of decrypting abilities at any point in time, independent of FS time evolution. It realizes zero-inner-product predicates and is proved adaptively secure under standard assumptions. As the ‘cross-product’ approach taken in FS-HIBE is not directly applicable to the HPE setting, our construction resorts to techniques that are specific to existing HPE schemes and extends them with what can be seen as a reminiscent of binary tree encryption from FS-PKE.

Description: Distributed denial of service (DDoS) attack is a coordinated attack, generally performed on a massive scale on the availability of services of a target system or network resources. Owing to the continuous evolution of new attacks and ever-increasing number of vulnerable hosts on the Internet, many DDoS attack detection or prevention mechanisms have been proposed. In this paper, we present a comprehensive survey of DDoS attacks, detection methods and tools used in wired networks. The paper also highlights open issues, research challenges and possible solutions in this area.

Description: A novel adaptive steganographic scheme for spatial image is proposed. A noisy function is used to measure texture complexity of 2 x 2 pixel blocks, which keeps monotonic increasing after ±1 modifications. Therefore, the message is embedded into the noisiest areas and the recipient can identify the embedding region. The ‘double-layered embedding’ is exploited to reduce the number of ±1 modifications, in which the fast matrix embedding and wet paper codes are applied to the least significant bit (LSB) plane and the second LSB plane, respectively. The experiments on resisting three steganalyzers show that the proposed method performs better than four typical steganographic schemes. Moreover, comparing with the extended highly undetectable steGO having parameter T = 255, the novel method achieves the competitive ability of resisting detection and faster embedding speed.

Description: In this study, we propose an efficient aggregate signcryption scheme to maximize the security of data in a kind of wireless medical network named the disconnected or unattended wireless sensor network (applied in medical systems). These networks address patients who need to be monitored for a long time. The main challenge of these networks that are usually implanted on the patient's clothing and established in sensitive conditions is that the server (station) visits sensors continuously. Moreover, the sensors must retain data for long enough time to off-load to the station as they have limited capacity and batteries. This disconnected nature gives adversaries the power to read and modify target data without being detected or disclose private medical data related to a patient. In this paper, we address these security problems and improve the first study of identity-based aggregate signcryption in UWSNs to achieve both key privacy and invisibility. Our improved approach is at the same time efficient in terms of space and communication overload. Moreover, the proposed scheme allows servers to efficiently verify and unsigncrypt all the related data accumulated by sensors. We further show that the proposed scheme has resistance against reading and modifying attacks. We compare our scheme with the best alternative works in the literature.

Description: We introduce ZIDS, a client-server solution for private detection of intrusions that is suitable for private detection of zero-day attacks in input data. The system includes an intrusion detection system (IDS) server that has a set of sensitive signatures for zero-day attacks and IDS clients that possess some sensitive data (e.g. files, logs). Using ZIDS, each IDS client learns whether its input data matche any of the zero-day signatures, but neither party learns about any additional information. In other words, the IDS client learns nothing about the zero-day signatures and the IDS server learns nothing about the input data and the analysis results. To solve this problem, we reduce privacy-preserving intrusion detection to an instance of secure two-party oblivious deterministic finite automata (ODFA) evaluation. Then, motivated by the fact that the DFAs associated with attack signature are often sparse , we propose a new and efficient ODFA protocol that takes advantage of this sparsity. Our new construction is considerably more efficient than the existing solutions and, at the same time, does not leak any sensitive information about the nature of the sparsity in the private DFA. We provide a full implementation of our privacy-preserving system that includes optimizations that lead to better memory usage and evaluate its performance on rule sets from the Snort IDS.

Description: Anonymous multi-receiver identity-based encryption can protect the receiver identity privacy and message confidentiality. Thus, it can be used in many fields, such as Voice over Internet Protocol and pay-TV systems. In 2012, Chien improved an anonymous multi-receiver identity-based encryption scheme. This paper points out that Chien's scheme does not satisfy the indistinguishability of encryptions under selective multi-identity, chosen ciphertext attacks. The analysis is important for understanding the security risks.

Description: Conditionally anonymous ring signatures are a variant of ring signatures such that the anonymity is conditional: if a user is the true signer, then he can claim this through a confirmation protocol; if he is not the signer, he can prove this through a disavowal protocol. Hence, this can preserve the anonymity of a signer while reserving the right to trace it when necessary. The security of such a signature also requires that an innocent non-signer will not be framed as a signer. In this paper, we propose a new framework for this type of signature without random oracles. Our construction can be realized under general complexity assumptions and has a simple structure. In contrast, previous works are based on non-standard assumptions or proved secure in the random oracle model.

Description: With the growth of networked computers and associated applications, intrusion detection has become essential to keeping networks secure. A number of intrusion detection methods have been developed for protecting computers and networks using conventional statistical methods as well as data mining methods. Data mining methods for misuse and anomaly-based intrusion detection, usually encompass supervised, unsupervised and outlier methods. It is necessary that the capabilities of intrusion detection methods be updated with the creation of new attacks. This paper proposes a multi-level hybrid intrusion detection method that uses a combination of supervised, unsupervised and outlier-based methods for improving the efficiency of detection of new and old attacks. The method is evaluated with a captured real-time flow and packet dataset called the Tezpur University intrusion detection system (TUIDS) dataset, a distributed denial of service dataset, and the benchmark intrusion dataset called the knowledge discovery and data mining Cup 1999 dataset and the new version of KDD (NSL-KDD) dataset. Experimental results are compared with existing multi-level intrusion detection methods and other classifiers. The performance of our method is very good.

Description: Data transfer is a transmission of data over a point-to-point or point-to-multipoint communication channel. To protect the confidentiality of the transferred data, public-key cryptography has been introduced in data transfer schemes (DTSs). Unfortunately, there exist some drawbacks in the current DTSs. First, the sender must know who the real receivers are. This is undesirable in a system where the number of the users is very large, such as cloud computing. In practice, the sender only knows some descriptive attributes of the receivers. Secondly, the receiver cannot be guaranteed to only receive messages from the legal senders. Therefore, it remains an elusive and challenging research problem on how to design a DTS scheme where the sender can send messages to the unknown receivers and the receiver can filter out false messages according to the described attributes. In this paper, we propose an attribute-based data transfer with filtering (ABDTF) scheme to address these problems. In our proposed scheme, the receiver can publish an access structure so that only the users whose attributes satisfy this access structure can send messages to him. Furthermore, the sender can encrypt a message under a set of attributes such that only the users who hold these attributes can obtain the message. In particular, we provide an efficient filtering algorithm for the receiver to resist the denial-of-service attacks. Notably, we propose the formal definition and security models for ABDTF schemes. To the best of our knowledge, it is the first time that a provable ABDTF scheme is proposed. Hence, this work provides a new research approach to ABDTF schemes.

Description: Certificateless encryption (CLE) effectively solves the inherent key escrow problem in identity-based encryption while retaining its keeping certificate-free property. Although a number of CLE schemes have been available in the literature, little attention has been paid to the problem of user revocation in the certificateless setting. In this work, we study CLE systems with user revocation capabilities. At first, we establish reasonable security models for revocable CLE (RCLE) schemes. Then we put forward the first efficient and CCA2-secure RCLE scheme in the standard model. A rigorous security proof of our RCLE scheme is presented based on the decisional truncated q -ABDHE assumption and decisional bilinear Diffie–Hellman (DBDH) assumption.

Description: A new algorithm is given to find product-form solutions for the joint equilibrium probabilities in a class of synchronized Markov processes. This is based on, and proved by, multiple applications of the Reversed Compound Agent Theorem (RCAT) and can describe multi-way synchronizations (seen as chains of pairwise synchronizations) that occur in a prescribed order. The length of the sequence is unbounded but finite with probability 1. Several applications are given to illustrate the methodology, which include various modes of resets in queueing networks with negative customers. In particular, it is shown that there is a type of reset that can propagate further transitions in a chain actively. Furthermore, a number of completely new product-form models, for example, where the transitions in a chain are non-homogeneous, are given.

Description: The error-recovery efficiency of packet-level forward-error-correction (PFEC) coding is sensitive to the loss-burst nature of mobile channels. Interleaving, which rearranges the packet transmission orders to scatter loss bursts, is commonly employed to help PFEC overcome this problem. Unfortunately, we still lack an efficient adaptation mechanism based on a tractable performance formulation that characterizes the tradeoffs between the interleaving and PFEC subject to network loss conditions (packet loss rate and loss correlation) and user requirements (buffer delay constraint and target packet loss rate). This paper addresses this issue by proposing an interleaving-first (IF) algorithm, in which we first pursue near-perfect interleaving based on a threshold mechanism, followed by optimizing PFEC throughput. Such an approach enables us to: (1) obtain a simplified performance model and (2) practice a simple systematic adaptation. The simulation confirms that the proposed scheme is capable of providing good quality sub-optimal solutions under typical mobile link conditions (i.e. the packet loss rate is ≤ 0.2, the mean burst length is ≤10 packets and the buffering delay is ≤256 packet times).

Description: We present fast strongly universal string hashing families: they can process data at a rate of 0.2 CPU cycle per byte. Maybe surprisingly, we find that these families—though they require a large buffer of random numbers—are often faster than popular hash functions with weaker theoretical guarantees. Moreover, conventional wisdom is that hash functions with fewer multiplications are faster. Yet we find that they may fail to be faster due to operation pipelining. We present experimental results on several processors including low-power processors. Our tests include hash functions designed for processors with the carry-less multiplication instruction set. We also prove, using accessible proofs, the strong universality of our families.

Description: A graph G =( V , E ) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers d min and d max such that each leaf l u of T corresponds to a vertex u V and there is an edge ( u , v ) E if and only if d min ≤ d T , w ( l u , l v ) ≤ d max , where d T , w ( l u , l v ) is the sum of the weights of the edges on the unique path from l u to l v in T . In this paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices W n , n =7, ..., 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any PCG admits a full binary tree as witness tree T .

Description: This study provides a comparative assessment on the different techniques of classifying human activities performed while wearing inertial and magnetic sensor units on the chest, arms and legs. The gyroscope, accelerometer and the magnetometer in each unit are tri-axial. Naive Bayesian classifier, artificial neural networks (ANNs), dissimilarity-based classifier, three types of decision trees, Gaussian mixture models (GMMs) and support vector machines (SVMs) are considered. A feature set extracted from the raw sensor data using principal component analysis is used for classification. Three different cross-validation techniques are employed to validate the classifiers. A performance comparison of the classifiers is provided in terms of their correct differentiation rates, confusion matrices and computational cost. The highest correct differentiation rates are achieved with ANNs (99.2%), SVMs (99.2%) and a GMM (99.1%). GMMs may be preferable because of their lower computational requirements. Regarding the position of sensor units on the body, those worn on the legs are the most informative. Comparing the different sensor modalities indicates that if only a single sensor type is used, the highest classification rates are achieved with magnetometers, followed by accelerometers and gyroscopes. The study also provides a comparison between two commonly used open source machine learning environments (WEKA and PRTools) in terms of their functionality, manageability, classifier performance and execution times.

Description: In this paper, we propose a self-stabilizing distance-2 edge coloring algorithm for arbitrary graphs. The algorithm operates correctly under the distributed model and guarantees that two edges within distance 2 of each other receive distinct colors when the system stabilizes. It uses 2 ( – 1) + 1 colors and stabilizes in 4 n + (2 ( – 1) + 2) m rounds, where n , m , respectively, denote the number of nodes and edges and is the maximum degree of nodes in the graph.

Description: An orchestration is a multi-threaded computation that invokes a number of remote services. In practice, the responsiveness of a web-service fluctuates with demand; during surges in activity service responsiveness may be degraded, perhaps even to the point of failure. An uncertainty profile formalizes a user's perception of the effects of stress on an orchestration of web-services; it describes a strategic situation, modelled by a zero-sum angel–daemon game. Stressed web-service scenarios are analysed, using game theory, in a realistic way, lying between over-optimism (services are entirely reliable) and over-pessimism (all services are broken). The ‘resilience’ of an uncertainty profile can be assessed using the valuation of its associated zero-sum game. In order to demonstrate the validity of the approach, we consider two measures of resilience and a number of different stress models. It is shown how (i) uncertainty profiles can be ordered by risk (as measured by game valuations) and (ii) the structural properties of risk partial orders can be analysed.

Description: Geography Markup Language (GML) has become a de facto standard for encoding and exchanging geographic data. Usually, GML documents are of huge size due to its verbose structures and textual data, hence it is very costly to store and transit them. In this paper, we propose an effective pattern-based approach to compressing GML documents. First, a tree-structured pattern from the GML document under compression is extracted. Then, a tree automaton for matching the document against the extracted pattern is constructed. While doing compression, the GML document is matched against the pattern to generate a bits-stream that represents the difference between the document's structure and the extracted pattern. Meanwhile, we separate document structure from document content and group document content into different streams according to the tags. Spatial coordinate data are compressed by delta encoding. Finally, the extracted pattern, all streams and encodings are forwarded to a text compressor gzip. Extensive experiments on real GML documents show that the proposed approach outperforms the existing XML and GML compression approaches in compression ratio, while keeping an acceptable compression efficiency.

Description: Message-passing interface (MPI) has proved to be very successful in the high performance computing domain. However, suitability of MPI for embedded real-time system design is still under investigation. In this work, we have provided our methods and experiences of implementing MPI parallel environment for a real-time embedded multi-core system. Our main contributions were to: (1) enable hyper transport bus communication mechanism to establish MPI parallel environment; (2) support VxWorks operating system for establishing MPI parallel environment and (3) enhance the real-time property of MPI mechanism. The digital signal processor (DSP)-MPI presented in this work can also be used on other platforms supporting VxWorks operating system. The results indicate that the real-time property of DSP-MPI has been improved significantly compared with MPICH2. The test on realistic applications also shows that DSP-MPI can fulfill the requirement of our target multi-core platform.

Description: Consider an orthogonal art gallery partitioned into n rectangular rooms. If two rooms are adjacent, there is a door connecting them and a guard positioned at this door will see both rooms. In Czyzowicz et al. [(1994) Guarding rectangular art galleries. Discrete Appl. Math. , 50 , 149–157], it is shown that any rectangular gallery can be guarded with n /2 guards. We prove that the same bound holds for L-shape polygons. We extend it to staircases and prove that an orthogonal staircase with n rooms and r reflex vertices can be guarded with ( n + r /2)/2 guards. Then we prove an upper bound on the number of guards for arbitrary orthogonal polygon with orthogonal holes. This result improves the previous bound by Czyzowicz et al. [(1994) Guarding rectangular art galleries. Discrete Appl. Math. , 50 , 149–157] (even in the case of polygon without holes).

Description: This work targets the problem of search efficiency vs. answer quality of approximate metric-based similarity search. We especially focus on techniques based on recursive Voronoi-like partitioning or, from another perspective, on pivot permutations. These techniques use sets of reference objects (anchors/pivots) to partition the metric space into cells of close data items. Instead of refining the search space by enlarging the anchor set of a single index, we propose to divide a large pivot set into several subsets and build multiple indexes with independent space partitioning; at query time, the overall search costs are also divided among the separate indexes. Our thorough experimental study on three different real datasets uncovers drawbacks of excessive increase of a single pivot set size—such partitioning refinement can be counterproductive beyond a certain number of pivots. Our approach overcomes the root causes of this limitation and increases the answer quality while preserving the search costs. Further, we address the question of robustness of the answer quality, which can be significantly improved by utilization of independent anchor spaces.

Description: We review the problem of finding contained rewritings (CRs) for XPath queries using XPath views. CR is proposed to cater for data integration scenarios, where views are unlikely to be complete due to the limited coverage of data sources, and hence equivalent rewritings are impossible to be found. As a result, we are usually required to find a maximal contained rewriting (MCR) for a query to provide the best possible answers. An MCR is a set of CRs, and may contain redundant CRs. Obviously, evaluating redundant CRs on materialized views is unnecessary. In this paper, we first address how to find the irredundant maximal contained rewriting (IMCR), i.e. all the irredundant CRs. We show that the existing approach ignores a type of situation, and turns out to be not sufficient. As a result, the only safe solution is a brute-force pairwise containment check for all the CRs. We then propose some heuristics to speed up the brute-force comparisons. When a materialized view is given, we propose how to evaluate the IMCR on the materialized view, which, to our knowledge, is the first work on optimizing the evaluation of a set of produced CRs on the materialized view by considering the inherent structural characteristics of the CRs. Our experiments show the effectiveness and efficiency of our algorithms.

Description: Rapid proliferation of information technologies has generated a great volume of information that makes scientific information searching more challenging. Personalized recommendation is a widely used technique to help researchers find relevant information. Researchers involved in a social computing context generate abundant content and form heterogeneous connections. Existing article recommendation techniques fail to perform a deep analysis of this information. This research proposes a novel approach to recommend scientific articles to researchers by leveraging content and connections. In this approach, we first analyze the semantic content of the article by keyword similarity calculation and then extract online users’ connections to support article voting and finally employ a two-stage recommendation process to suggest relevant articles. The proposed method has been implemented in ScholarMate ( www.scholarmate.com ), an online research social network platform. Two experiments are conducted and the evaluation results indicate that the proposed method is more effective than the baseline methods.

Description: Most of the classic theoretical systems and tools in statistics, data mining and machine learning are built on the fundamental assumption of IIDness, which assumes the independence and identical distribution of underlying objects, attributes and/or values. However, complex behavioral and social problems often exhibit strong couplings and heterogeneity between values, attributes and objects (i.e., non-IIDness). This fundamentally challenges the IIDness-based learning methodologies and techniques. This paper presents a high-level overview of the needs, challenges and opportunities of non-IIDness learning for handling complex behavioral and social problems. By reviewing the nature and issues of classic IIDness-based algorithms in frequent pattern mining, clustering and classification to complex behavioral and social applications, concepts, structures, frameworks and exemplar techniques are discussed for non-IIDness learning. Case studies, related work and prospects of non-IIDness learning are presented. Non-IIDness learning is also a fundamental issue in big data analytics.

Description: Centrality indices are essential in network analysis and betweenness centrality , which is based on shortest paths, is one of the most important measures. It has been widely used in different areas like social network analysis, World Wide Web and route planning. However, even for mid-size networks, it is computationally expensive to compute exact betweenness scores. In this paper, we propose a generic randomized framework for unbiased estimation of betweenness scores. The proposed framework can be adapted with various sampling techniques and give algorithms with different characteristics. We discuss the conditions a promising sampling technique should satisfy to minimize the approximation error, and propose a sampling method that partially satisfies the conditions. We perform extensive experiments on synthetic networks as well as networks from the real world, and show that, compared with existing exact and inexact algorithms, our method works with higher accuracy or gives significant speedups.

Description: A Laguerre tessellation is a generalization of a Voronoi tessellation where the proximity between points is measured via a power distance rather than the Euclidean distance. Laguerre tessellations have found significant applications in materials science, providing improved modeling of (poly)crystalline microstructures and grain growth. There exist efficient algorithms to construct Laguerre tessellations from given sets of weighted generator points, similar to methods used for Voronoi tessellations. The purpose of this paper is to provide theory and methodology for the inverse construction; that is, to recover the weighted generator points from a given Laguerre tessellation. We show that, unlike the Voronoi case, the inverse problem is in general non-unique: different weighted generator points can create the same tessellation. To recover pertinent generator points, we formulate the inversion problem as a multimodal optimization problem and apply the cross-entropy method to solve it.

Description: As the microblogging systems such as Twitter and Sina Weibo become more and more popular in recent years, the requirement for real-time and personalized search over microblogging systems also becomes more important. In general, a user may expect a quick response that also satisfies her personalized requirements. Unfortunately, since there exist a huge number of users and massive updating microblogs in a microblogging system, personalized search on the system becomes a challenging task. In this paper, we design a new search engine containing four modules to infer the topics of microblogs and update the interests of users, build indexes efficiently, return microblogs for a keyword search, and personalize the order of microblogs, respectively. We also conduct a series of experiments on a real dataset to illustrate the effectiveness and efficiency of the proposed methods.

Description: Retrieval of similar anatomical structures of brain MR images across patients would help the expert in diagnosis of diseases. In this paper, modified local binary pattern with ternary encoding called modified local ternary pattern (MOD-LTP) is introduced, which is more discriminant and less sensitive to noise in near-uniform regions, to locate slices belonging to the same level from the brain MR image database. The ternary encoding depends on a threshold, which is a user-specified one or calculated locally, based on the variance of the pixel intensities in each window. The variance-based local threshold makes the MOD-LTP more robust to noise and global illumination changes. The retrieval performance is shown to improve by taking region-based moment features of MOD-LTP and iteratively reweighting the moment features of MOD-LTP based on the user's feedback. The average rank obtained using iterated and weighted moment features of MOD-LTP with a local variance-based threshold, is one to two times better than rotational invariant LBP (Unay, D., Ekin, A. and Jasinschi, R.S. (2010) Local structure-based region-of-interest retrieval in brain MR images. IEEE Trans. Inf. Technol. Biomed. , 14, 897–903.) in retrieving the first 10 relevant images.

Description: Community detection is a long-standing yet very difficult task in social network analysis. It becomes more challenging as many online social networking sites are evolving into super-large scales. Numerous methods have been proposed for community detection from massive networks, but how to reconcile the partitioning efficiency and the community quality remains an open problem. In this paper, we attempt to address this challenge by introducing a COSine-pattern-based COMmunity extraction framework: COSCOM. The COSCOM adopts an extracting view of community detection. It first extracts the so-called asymptotically equivalent structures (AESs) from networks, from which the nodes are further partitioned into crisp communities using any of the existing methods. Specifically, we prove that an AES is a very tight group of nodes, and is actually a cosine pattern defined by the extended cosine similarity. A novel cosine-pattern mining algorithm based on the ordered anti-monotone of cosine similarity is thus proposed for the efficient extraction of AESs. Experiments on various real-world social networks demonstrate the advantage of the extracting view of community detection. In particular, COSCOM shows merits in detecting genuine communities by either internal or external validity.

Description: In recent years, there has been a proliferation of collaborative tagging systems in Web 2.0 communities. With the increasingly large amount of social data, how to manage and organize them becomes an important and crucial problem for folksonomy applications. To better understand and meet users’ needs, multimedia resources can be organized or indexed from these user perspectives; it is thus important to find latent user communities for social media applications. In this paper, we propose the mechanism of augmented folksonomy graph (AFG) to incorporate multi-faceted relations in social media, along with a novel density-based clustering method to discover latent user community from AFG by combining contents and tags of multimedia resources. To evaluate the proposed method, we conduct experiments on a public dataset, the empirical results of which show that our approach outperforms baseline ones in terms of tag-based and content-based personalized search.

Description: The increasing need for traffic prediction systems has become an important issue in advanced traffic management and information systems. The forecast of traffic density reduces traffic congestion and improves transportation mobility. This study describes a novel methodology for traffic prediction by extracting important time-related association rules using an evolutionary algorithm named genetic network programming (GNP). The extracted rules provide a useful means for forecasting the future traffic density level of traffic networks. The proposed methodology is implemented and experimentally evaluated using a large-scale real-time traffic simulator named SOUND/4U. The routing algorithm combined with the traffic prediction was also studied using different environments.

Description: In modern societies the process of communication is greatly influenced by information technology and computer systems. Social interactions in both real-life and cyber communities are frequently being shaped by two main features of social computing tools: (1) sharing great deal of information with whole groups of consumers and (2) deriving collective intelligence by collaborative information evaluation, discussion, annotation, etc. The latter is further supported by reasoning mechanisms implemented in software to derive more pertinent and synthesized information for its consumers, e.g. recommendations. In consequence, communities are empowered to make more than ever informed conclusions and decisions. In our work, we consider situations that people find themselves in as pieces of information frequently driving decision making in classical human relations. We argue that augmenting social intelligence can be achieved by both (1) facilitating sharing context among community members and (2) encouraging their collaborative effort to learn about the importance of certain situations. We present Kind of Reasoning that Abstracts Meta-situations for Empowering Recommendations, a recommender system that enriches social computing principle with that notion of situation awareness. In this paper, we discuss our system with an emphasis on its social computing mechanisms. We present also its evaluation in the form of a special user test game.

Description: Automated essay-scoring (AES) systems utilize computer techniques and algorithms to automatically rate essays written in an educational setting, by which the workload of human raters is greatly reduced. AES is usually addressed as a classification or regression problem, where classical machine learning algorithms such as K-nearest neighbor and support vector machines are applied. In this paper, we argue that essay rating is based on the comparison of writing quality between essays and treat AES rather as a ranking problem by capturing the difference in writing quality between essays. We propose a rank-based approach that trains an essay-rating model by learning to rank algorithms, which have been widely used in many information retrieval and social Web mining tasks. Various linguistic and statistical features are utilized to facilitate the learning algorithms. Extensive experiments on two public English essay datasets, Automated Student Assessment Prize and Chinese Learners English Corpus, show that our proposed approach based on pairwise learning outperforms previous classification or regression-based methods on all 15 topics. Finally, analysis on the importance of the features extracted reveals that content, organization and structure are the main factors that affect the ratings of essays written by native English speakers, while non-native speakers are prone to losing ratings on improper term usage, syntactic complexity and grammar errors.

Description: Advances in lightweight, small-sized and low-power sensors led to the development of wearable biosensors, and thus, to the accurate monitoring of human periphery. On top of this, pervasive computing has been improved and technologies have been matured enough to build plug-and-play body area networks (BANs). In a BAN, the main functionality of a node is to effectively and efficiently collect data from vital body parts, share it with the neighbors and make decisions accordingly. Because of the fact that the captured phenomenon is highly sensitive to privacy breaches in addition to being transmitted using the wireless communication medium, BANs require a security infrastructure. However, due to the extreme energy scarcity, bandwidth and storage constraints of the nodes, conventional solutions are inapplicable. In this survey, we present an overview of BANs and provide a detailed investigation into the developed security infrastructures. We examined the literature and combined the corresponding proposals under two major classes: (i) pure-cryptographic security mechanisms and (ii) bio-cryptographic security mechanisms. Pure-cryptographic methods include constructions based on the well-known symmetric or asymmetric cryptography primitives and they are suitable for securing the communication between any two network entities. On the other hand, bio-cryptographic methods benefit from the network's context-awareness and to the best of our knowledge, they have been utilized only for the communication among the biosensors.

Description: We present a tool for automatic analysis of computational indistinguishability between two strings of information. This is designed as a generic tool for proving cryptographic security based on a formalism that provides computational soundness preservation. The tool has been implemented and tested successfully with several cryptographic schemes.

Description: In this paper, we introduce a general paradigm called identity-based extractable hash proof system (IB-EHPS), which is an extension of extractable hash proof system (EHPS) proposed by Wee (CRYPTO'10). We show how to construct identity-based key encapsulation mechanism (IB-KEM) from IB-EHPS in a simple and modular fashion. Our construction provides a generic method of building and interpreting CCA-secure IB-KEMs based on computational assumptions. As instantiations, we realize IB-EHPS from the bilinear Diffie–Hellman assumption and the modified bilinear Diffie–Hellman assumption, respectively. Besides, we carefully investigate the relation between EHPS and IB-EHPS, and indicate possible refinement and generalization of EHPS.

Description: Nowadays, electoral processes can be automated, using electronic devices and communication networks. The electronic voting systems allow easy voter casting and fast vote counting for electoral entities. In this paper, an electronic voting scheme is proposed, it performs the communication among voters and electoral entities with a minimal number of phases and cryptographic operations. The scheme uses a combination of the blind signature scheme proposed by Boldyreva in 2003 and the short signature proposed by Boneh–Lynn–Shacham in 2001. Both signatures use pairing-based cryptography and a special hash function known as map-to-point. The scheme generates small ballots which consist of just two messages, one blind signature and one short signature. We present experimental data showing that our pairing-based scheme is considerably more efficient than other blind signature e-voting schemes recently proposed whose security is based on the integer factorization problem or on the discrete logarithm problem over prime fields.

Description: This paper proposes an efficient, secure and anonymous routing protocol based on Weil pairing for wireless mesh networks (WMNs). The proposed protocol considers symmetric and asymmetric links during wireless communication in WMNs. A WMN integrates several types of wireless devices, and induces the asymmetric links that result from different transmission ranges of wireless devices. Enhancing the security and privacy of WMNs has been an important research focus in recent years. Most research on this topic has focused on providing security and anonymity for routing and data in symmetric links. However, the asymmetric links in these protocols have not been addressed. This paper proposes a novel distributed routing protocol suitable for WMNs that include symmetric and asymmetric links. The proposed protocol guarantees security, anonymity and high reliability in WMNs. The proposed protocol generates routes that are shorter than those of previous studies. The proposed scheme protects the real identities of the source and intermediate users, which remain unknown even to the mesh router, while still providing node authentication. Using the proposed protocol, mesh clients anonymously discover a secure route to the mesh router. This protocol also ensures data transmission anonymity and enhances WMN coverage, in addition to assuring security and anonymity.

Description: Motivated by perfect guessing security for private key encryption by Alimomeni and Safavi-Naini (ICITS 2012), we study the relations between various unconditional -security notions, including $\epsilon$-guess security, -min entropic security and -Shannon security. We characterize the relations between these security notions. Our results stem from the essential mathematical properties of the underlying measures (i.e. guessing probability, min entropy and Shannon mutual information). We also prove the lower bound on either key entropy or key size or key min entropy for these models. Our results show that the -security under these models has a large key size or (min) entropy and hence impossible to be efficient.

Description: The notion of Affiliation-Hiding Authenticated Group Key Agreement (AH-AGKA) protocols was first introduced by Jarecki et al. in CT-RSA 2007, where they presented two concrete AH-AGKA protocols. In this paper, we show that Jarecki et al. 's second protocol has some drawbacks. We propose a new affiliation-hiding protocol. Differing from Jarecki et al. 's protocol, our protocol is asymmetric. Compared with existing AH-AGKA protocols, our scheme not only exhibits the affiliation-hiding property, but also holds the properties of detectability and perfect forward secrecy.

Description: There are so many IP-based mobility management schemes proposed and standardized but mobility management is still a bigger challenge today. The notion of Mobile IPv4 (MIPv4) has been standardized as a macro-mobility management protocol. Hierarchical Mobility Management scheme for MIPv4 networks (HMIPv4), Dynamic Hierarchical Mobile IP (DHMIP) have been suggested as micro-mobility management protocols. A network-assisted protocol called Proxy MIPv4 (PMIPv4) has been proposed to reduce the wireless overhead of mobile users (MUs) induced by location registration. But none of these schemes consider the fixed mobility pattern of MUs. In urban cities, many MUs have a fixed mobility pattern on a daily basis and there is scope of further reduction in registration cost and packet delivery cost. In this paper, we propose a hierarchical mobility anchoring point (HMAP) for IPv4 networks. The proposed scheme has reduced the location update cost and the packet delivery cost when compared with the existing MIPv4, DHMIP, HMIPv4 and PMIPv4 schemes.

Description: Maintaining connectivity is a very important objective of wireless sensor networks (WSNs) in successfully achieving data collection for applications. A cut vertex (node) is defined as a critical vertex whose removal disconnects a network component and partially disables data delivery. Hence, it is crucial that cut vertices be detected and treated with caution. In this paper, we propose an energy-efficient cut vertex detection (CVD) algorithm for WSNs. Our algorithm uses a depth-first search approach and is completely distributed. It benefits from the radio multicast capabilities of sensor nodes and is the first algorithm with a time complexity of O ( N ) and a sent message complexity of O ( N ), in which each message is O (log 2 ( N )) bits. We show the operation of the algorithm, analyze it in detail, provide testbed experiments and extensive simulations. We compare our proposed algorithm with the other CVD algorithms and show that our algorithm saves up to 6.8 times more energy in less time.

Description: One important component of network reprogramming is code dissemination (CD), when the updated program code is distributed to the relevant nodes. Very few CD protocols tolerate transient faults that corrupt the state and these faults can cause the old code to disseminate in the network. We propose two protocols called BestEffort-Repair and Consistent-Repair that transform fault-intolerant CD protocols into non-masking fault-tolerant protocols where, eventually, all nodes obtain the new code. We conduct experiments with both protocols on TelosB-like motes and over TOSSIM simulations to show their correctness and also their performance. We conduct a case study whereby both protocols are added to a state-of-the-art CD protocol, namely Varuna to evaluate their impact on Varuna. Our results show that (i) Varuna, which is fault-intolerant, is transformed into a stabilizing CD protocol; (ii) they induce low overhead on Varuna, and cause all nodes to eventually receive the new code. BestEffort-Repair is biased towards fast recovery, whereas Consistent-Repair attempts to reduce the number of erroneous downloads in the network. Our main contribution is the first corrector protocols that correct CD in the presence of transient faults.

Description: The iceberg query finds data whose aggregate values exceed a pre-specified threshold. To process an iceberg query in sensor networks, all sensor data have to be aggregated and then sensor data whose aggregate values are smaller than the threshold are eliminated. Whether a certain sensor datum is in the query result depends on the other sensor data values. Since sensor nodes are distributed, communications between sensor nodes are required to know the sensor data from the other sensor nodes. However, sensor nodes have limited energy resources and communication is a primary source of the energy consumption. Thus, reducing the communication overhead is the most critical issue in sensor networks. In this paper, we propose an energy-efficient iceberg query processing technique in sensor networks. To compactly represent the data transmitted, a lossless sensor data compression method based on the Fundamental Theorem of Arithmetic is devised. To reduce the energy consumption caused by the number of data transmitted, a filtering-based query processing method is devised. Using the temporal correlation of sensor data and the semantics of an iceberg query, a prediction model is proposed. Based on the predicted future query result, sensor nodes effectively filter out unnecessary transmissions. The experimental results confirm the effectiveness of our approach.

Description: In this paper, we propose a fast scalable video coding (SVC)-based channel-recommendation system for IPTV on a Cloud and peer-to-peer (P2P) hybrid platform. When a user switches channels, the system redirects the client to the cloud network and delivers the base layer of SVC streams to the client. The system provides a multichannel preview window with a small resolution and a fast channel-switching mechanism without additional traffic. After a user has selected a channel, the system redirects the client to the P2P network and sends the necessary enhancement layer streams, so that the client can receive high-quality video. Because of the fact that the recommendation system is known as an effective approach for enhancing the efficiency of channel previews, we propose a novel recommendation system based on the feedback loser tree (FLT) algorithm. The FLT algorithm can be trained by the user's historical log, and attempt to find the user's preferred channels quickly. Our experimental results indicate that the proposed platform can obtain a higher peak signal to noise ratio quality than the original P2P networks, and the proposed system can help users find their favorite channels in only 2 to 5 switching pages. The performance of the proposed system is ~75% better than that of the high-performance multichannel preview system.

Description: IEEE 802.22 wireless regional area network (WRAN) is a cognitive radio-based network. WRANs are intended to be deployed by different service providers and designed to opportunistically utilize the unused TV bands. WRANs have to self-coexist with other overlapped WRANs in a distributed manner. Therefore, every service provider tries to acquire a band free of interference from others to satisfy a required quality of service. This self-coexistence problem is one of the major challenges in WRAN. In this paper, we propose a Markov-based distributed approach for mitigating this problem. We model the problem as an absorbing discrete-time Markov chain. In this model, if two or more overlapped WRANs select the same band, then each one should either stay or switch to another band according to a certain switching probability. This process continues until each one of the WRANs finds an interference-free band. In this case, the Markov chain reaches the absorbing state. This model is employed to find the optimal switching probability, which in turn minimizes the time required to reach the absorbing state. The switching probability is numerically found as a function of the number of overlapped WRANs and available bands. Extensive simulation has been conducted to validate our numerical results.

Description: In this paper, we deal with vulnerabilities in IEEE 802.11 DCF protocol itself and its interaction with transmission control protocol (TCP) protocol. Selfish configurations at medium access control or TCP layer give an increased bandwidth share for selfish stations, and malicious operations disturb overall network operations. We first analyzed the bandwidth allocation for each station under the assumption that all the stations behave well by obeying the protocol. We then expressed the bandwidth allocation with the traffic constraints in network calculus theory in order to guarantee the fair access for well-behaving stations in the presence of misbehaving stations. Based on the network calculus model, we constructed the framework of protecting well-behaving stations from malicious or selfish behaviors, called NetPro . We then built up the proposed NetPro framework in a simulation environment and an empirical test-bed, and we carried out a performance evaluation study. The results indicate that the proposed network calculus -based protection framework successfully secures well-behaving stations from selfish or malicious misbehaviors.

Description: In this paper, the Non-deterministic Repairable Fault Tree (NdRFT) formalism is proposed: it allows the modeling of failures of complex systems in addition to their repair processes. Its originality with respect to other Fault Tree extensions allows us to address repair strategy optimization problems: in an NdRFT model, the decision as to whether to start or not a given repair action is non-deterministic, so that all the possibilities are left open. The formalism is rather powerful, it allows: the specification of self-revealing events, the representation of components degradation, the choice among local repair, global repair, preventive maintenance, and the specification of the resources needed to start a repair action. The optimal repair strategy with respect to some relevant system state function, e.g. system unavailability, can then be computed by solving an optimization problem on a Markov Decision Process derived from the NdRFT. Such derivation is obtained by converting the NdRFT model into an intermediate formalism called Markov Decision Petri Net (MDPN). In the paper, the NdRFT syntax and semantics are formally described, together with the conversion rules to derive from the NdRFT the corresponding MDPN model. The application of NdRFT is illustrated through examples.

Description: Handling large concurrent queries in an energy-efficient way always has been a critical problem in wireless sensor networks (WSNs) due to its resource-constrained nature. Many sensor applications use non-spatial queries for accessing precise sensor data at specific locations rather than spatial queries that retrieve data over a region. Though performing pre-optimization of queries externally is a common technique followed for sensor query optimization before it is optimized in-network; a detailed cost-based model for optimizing non-spatial queries has not yet been carried out effectively. This paper focuses on optimizing non-spatial queries through a bi-level multi-query optimization scheme that uses an elaborate cost model to compute the execution cost of different query plans. Further, in-network optimization is implemented to reduce the energy consumption due to query result transmissions. Experimental analysis shows that the proposed optimization reduces the overall energy consumption and increases the scalability of non-spatial concurrent queries.

Description: High-performance computing (HPC) systems, including Clusters, Grids and the most recent Clouds, have emerged as attractive platforms to tackle various applications. One significant type of applications in the HPC systems is workflow computation, which has been applied in various scientific and engineering domains. The workflow computation frequently produces intermediate result files, which become garbage after being used and are usually cleaned up without making any contribution to future computation. In this paper, we argue that such garbage data could be useful in the future computation and should not be immediately cleaned up. This is because workflow computation usually contains multiple instances that may share some common data products produced in the past. This sharing scheme provides opportunities to reuse the historical data to speed-up subsequent computation and simplify re-computation due to faulty or crashed runs. To this end, we propose a novel approach, referred to as garbage data manager (GDM), for the workflow computation in HPC systems. The GDM organizes and manages the garbage data for batch schedulers to enhance the performance of subsequent computation. The essence of the GDM is to record the history of computation by constructing a dataflow graph on per instance (run) basis and set up inheritance relationships between the different instances of the same workflow, called run-tree , to achieve the data reuse. Our simulation results demonstrate that exploiting the garbage data is an effective way of improving the workflow computation.

Description: The analysis of a queue that serves batches of customers with a novel service policy is presented in this paper, showing that a closed steady-state distribution of the number of customers in the queue can be derived for a very general setting of its parameters. Two output processes are flowing out of this queue depending on the fact that single customers are removed from the queue upon completion of a service, or bulks of customers of a fixed size are departing from the queue at the completion of the service's. Based on the expression of the steady-state distribution which assumes a Poisson arrival process, specific parameter configurations are identified that make the queue quasi-reversible, depending on the output process of interest. Since quasi-reversible queues are very important in the context of product form queueing networks, these results have relevant impacts on their own as well as when considered as the basis for possible computationally efficient approximations. Comparisons among the results obtained for different parameter settings are provided using both stochastic order arguments and numerical experiments. Future research directions are proposed considering also the many practical applications of this model ranging from flexible manufacturing, to logistics, to transportation systems.

Description: Without any doubt XML is currently a de facto standard for data representation. Its popularity is given by the fact that it is well-defined, easy-to-use, and, at the same time, sufficiently expressive. However, most of XML documents are still created without the respective description of their structure, i.e. an XML schema. Since the knowledge of XML schema is crucial for various data processing approaches as well as a standard optimization tool, approaches to (semi-)automatic inference of XML schema become an interesting research problem. Recently, there have been introduced several approaches that improve particular steps of the inference process. The problem is how to compare such approaches, how to find the optimal ones and how to join them to get the best possible result. In this paper, we introduce jInfer , a general framework for XML schema inference. It represents an easily extensible tool that enables one to implement, test and compare new modules of the inference process. Since the compulsory parts of the process, such as parsing of XML data, visualization of automata, transformation of automata to XML schema languages, etc. are implemented, the user can focus purely on the research and the improved aspect of the inference process. We describe not only the framework, but the area of schema inference in general, including related work and open problems.

Description: The popular Nelder and Mead (NM) algorithm has four parameters associated to the operations known as reflection, expansion, contraction and shrinkage. The authors set their values to 1, 2, 0.5 and 0.5, respectively, which have been universally used. Here, we propose to use NM to calibrate itself. A computational experiment is carried out and results show that the parameter values originally proposed by NM are better than those obtained with more sophisticated ways.

Description: A related-key attack (RKA) occurs when an adversary tampers the private key stored in a cryptographic hardware device, and observes the result of the cryptographic primitive under this modified private key. In this paper, we consider the security of signcryption schemes under linear RKAs, where an adversary is allowed to tamper the private keys of the receiver and the sender, and subsequently observe the outcome of a signcryption system under these modified private keys of both parties. We define two security notions for RKA-secure signcryption schemes: chosen ciphertext RKA and chosen message RKA. We require that a signcryption scheme remains secure even when an adversary is allowed to access the designcryption oracle and the signcryption oracle on linear shifts of the private keys of the receiver and the sender, respectively. After reviewing some basic definitions related to our construction, we give a specific signcryption scheme from bilinear Diffie–Hellman which is secure against RKAs. Furthermore, we extend the security model of signcryption with anonymity, where the ciphertext is anonymous to others except the real receiver given the honest sender and the honest receiver. Fortunately, with a trivial modification to the original signcryption scheme, our proposed signcryption scheme can protect the privacy of both the sender and the receiver.

Description: This paper tackles the problem of parallelizing heterogeneous computational tasks across a number of computational nodes (aka agents) where each agent may not be able to perform all the tasks and may have different computational speeds. An equivalent problem can be found in operations research, and it is known as scheduling tasks on unrelated parallel machines (also known as R || C max ). Given this equivalence observation, we present the spanning tree decentralized task distribution algorithm (ST-DTDA), the first decentralized solution to R || C max . ST-DTDA achieves decomposition by means of the min–max algorithm, a member of the generalized distributive law family, that performs inference by message-passing along the edges of a graphical model (known as a junction tree). Specifically, ST-DTDA uses min–max to optimally solve an approximation of the original R || C max problem that results from eliminating possible agent-task allocations until it is mapped into an acyclic structure. To eliminate those allocations that are least likely to have an impact on the solution quality, ST-DTDA uses a heuristic approach. Moreover, ST-DTDA provides a per-instance approximation ratio that guarantees that the makespan of its solution (optimal in the approximated R || C max problem) is not more than a factor times the makespan of the optimal of the original problem. In our empirical evaluation of ST-DTDA, we show that ST-DTDA, with a min-regret heuristic, converges to solutions that are between 78 and 95% optimal whilst providing approximation ratios lower than 3.

Description: This special issue focuses on optimization in multi-agent systems (OptMASs), a sub-field of MASs research that poses novel research challenges. OptMASs is concerned with solving MAS problems using optimization techniques that cannot ignore the active participation of the actors in the system. Therefore, OptMASs must cope with the distributed nature of MASs, where agents reside on different computational units that may be prone to failures and have different computation/communication capabilities. Furthermore, it must consider that agents may be acting on behalf of different stakeholders, each with its own aims and objectives. Taking into account such assumptions leads to very hard optimization problems that are substantially different from problems traditionally dealt with in other areas. The objective of this special issue is to provide a detailed sample of recent advances in algorithms, theories and applications in the field of OptMASs. The seven papers included in this special issue are intended to outline the current state of the art in the field.

Description: This paper demonstrates a decentralized method for optimization using game-theoretic multi-agent techniques, applied to a sensor network management problem. Our first major contribution is to show how the marginal contribution utility design is used to construct an unknown-reward potential game formulation of the problem. This formulation exploits the sparse structure of sensor network problems, and allows us to apply a bound to the price of anarchy of the Nash equilibria of the induced game. Furthermore, since the game is a potential game, solutions can be found using multi-agent learning techniques. The techniques we derive use Q -learning to estimate an agent's rewards, while an action adaptation process responds to an agent's opponents’ behaviour. However, there are many different algorithmic configurations that could be used to solve these games. Thus, our second major contribution is an extensive evaluation of several action adaptation processes. Specifically, we compare six algorithms across a variety of parameter settings to ascertain the quality of the solutions they produce, their speed of convergence and their robustness to pre-specified parameter choices. Our results show that they each perform similarly across a wide range of parameters. There is, however, a significant effect from moving to a learning policy with sampling probabilities that go to zero too quickly for rewards to be accurately estimated.

Description: Increasingly, large-scale computing systems are consuming more power each passing year. As power consumption is on the rise, concern has been raised over the growing implications on power bills, carbon emissions and power supply limitations for data centers. Computing systems use hardware components that are not power proportional and machines comprising large systems tend to be underutilized, resulting in great wastage of energy. Motivated by this fact, researchers aim to improve the energy efficiency of these systems by increasing resource utilization and exploiting system characteristics in order to achieve power proportionality. However, many challenges burden the task of producing a power-aware, energy-efficient large-scale system that provides the same performance as today's systems. Particularly, storage systems are of great concern since storage consumes a large amount of power in the data center. This paper outlines the main problems and challenges of delivering power-efficient storage solutions, and proposes a taxonomy of power-aware techniques. This work aims to provide a detailed exposition of current trends in power-aware storage systems in a comprehensive and organized manner, outlining and comparing current solutions and challenges.

Description: In this paper, we deal with the exact circular string matching problem (abbreviated as ECSM). Given a string P = p 1 p 2 ··· p m , a string P ( i ) = p i p i +1 ··· p m p 1 ··· p i –1 , for 1 ≤ i ≤ m , is a circular string of P . Given a text string T = t 1 t 2 ··· t n and a pattern P , the ECSM problem is to find all occurrences of P ( i ) in text T for 1 ≤ i ≤ m . This paper proposes two algorithms that perform searching of a circular string on text using the bit-parallel technique. Our algorithms use only the composition of bitwise-logical operations and basic arithmetic operations, and apply this technique to solve the problem. These algorithms are given names CSBNDM and CSBNDN q , respectively. We give several experiments to verify that they have good performance for random strings and DNA sequences.

Description: Timing is often seen as the most important property of systems after function, and safety-critical systems are no exception. In this paper, we consider how timing is typically treated in safety assurance and, in particular, the safety arguments being proposed by industry and academia. A critique of these arguments is performed based on how systems are generally developed and how evidence is gathered. Significant weaknesses are exposed resulting in a more appropriate safety argument being proposed. As part of this work techniques for identifying relationships, in the form of contracts, between parts of the argument and the strength of evidence are used. The work is demonstrated using a Computer-Assisted Braking example, specifically an Anti-Lock Braking System for a car, as it is a classic example of a component that may be used ‘Out of Context’, as discussed in a number of safety standards, and may also be reused across a number of systems as well as part of a product line.

Description: Consider a distributed system with n processors, which receive triggers from the outside world. The distributed trigger counting (DTC) problem is to raise an alarm if the total number of triggers over the system reaches w , which is an user-specified input. DTC is used as a primitive operation in many applications, such as distributed monitoring, global snapshots, etc. Many of the earlier studies on DTC was done using non-deterministic algorithms. In this paper, we propose a deterministic algorithm for the DTC problem with a message complexity of O ( n log w log n ) and each node in the system receives O ( n log w ) number of messages, which is an improvement over earlier result for certain values of w . The distribution of triggers among the n nodes may be arbitrary. This paper gives insight into the deterministic algorithm for the DTC problem. Also to the best of our knowledge the overall message complexity and per node message complexity are better than earlier deterministic algorithms.

Description: Message sequence charts (MSCs) form a popular language in which scenario-based specifications and models can be written. There has been significant interest in automating aspects of testing from MSCs. This paper concerns the Oracle Problem, in which we have an observation made in testing and wish to know whether this is consistent with the specification. We assume that there is an MSC specification and consider the case where we have entirely independent local testers (local observability) and where the observations of the local testers are logged and brought together (tester observability). It transpires that, under local observability, the Oracle Problem can be solved in low-order polynomial time if we use sequencing, loops and choices, but becomes NP-complete if we also allow parallel components; if we place a bound on the number of parallel components, then it again can be solved in polynomial time. For tester observability, the problem is NP-complete when we have either loops or choices. However, it can be solved in low-order polynomial time if we have only one loop, no choices and no parallel components. If we allow parallel components, then the Oracle Problem is NP-complete for tester observability even if we restrict to the case where there are at most two processes.

Description: Sparse matrix matrix (SpMM) multiplication is involved in a wide range of scientific and technical applications. The computational requirements for this kind of operation are enormous, especially for large matrices. This paper analyzes and evaluates a method to efficiently compute the SpMM product in a computing environment that includes graphics processing units (GPUs). Some libraries to compute this matricial operation can be found in the literature. However, our strategy (FastSpMM) outperforms the existing approaches because it combines the use of the ELLPACK-R storage format with the exploitation of the high ratio computation/memory access of the SpMM operation and the overlapping of CPU–GPU communications/computations by Compute Unified Device Architecture streaming computation. In this work, FastSpMM is described and its performance evaluated with regard to the CUSPARSE library (supplied by NVIDIA), which also includes routines to compute SpMM on GPUs. Experimental evaluations based on a representative set of test matrices show that, in terms of performance, FastSpMM outperforms the CUSPARSE routine as well as the implementation of the SpMM as a set of sparse matrix vector products.

Description: The node-to-set disjoint paths problem in a k -connected network is defined as follows: given a node s and a set of k other nodes t 1 , t 2 , ... , t k in , find k node-disjoint paths connecting s and t i , with 1 ≤ i ≤ k . It is known that such disjoint paths must exist since is k -connected. However, building them, and ensuring that they are as short as possible are non-trivial problems. An efficient solution to the node-to-set disjoint paths problem in a network, with short paths, can be used as a building block in synthesizing collective communication operations that achieve high performance or are highly resilient to node or link failures. Recently proposed Biswapped networks, improved versions of well-known Optical Transpose Interconnection System networks or swapped networks, are a family of interconnection architectures applicable to constructing massive parallel computers. It has been known that any Biswapped network built of a connected factor network is maximally fault-tolerant, implying that such a Biswapped network has maximal connectivity. In this paper, we propose a general algorithm for the node-to-set disjoint paths problem in an arbitrary Biswapped network with a connected factor network that yields paths of length at most 1.5 D + 3 in time, where D , and N represent, respectively, the diameter, maximum degree and order of the Biswapped network, and O ( f ( n )) is the time complexity of a shortest-path routing algorithm for the n -node factor network. The algorithm is time-optimal for certain Biswapped networks of practical interest, including those built of meshes and hypercubes.

Description: A barrier certificate is an inductive invariant of functions which can be used to prove the safety property of a hybrid system. Utilizing a barrier certificate has the benefit of avoiding explicit computation of the exact reachable set which is usually not tractable for non-linear hybrid systems. In this paper, we propose a new barrier certificate condition, called Exponential Condition , for the safety verification of semialgebraic hybrid systems. The main important benefit of Exponential Condition is that it has a lower conservativeness than the existing convex conditions and meanwhile it possesses the convexity. On the one hand, a less conservative barrier certificate forms a tighter over-approximation for the reachable set and hence is able to verify critical safety properties. On the other hand, the convexity guarantees its solvability by a semidefinite programming method. Some examples are presented to illustrate the effectiveness and practicality of our method.

Description: Safety-critical Java (SCJ) is a restriction of the real-time specification for Java to support the development and certification of safety-critical applications. The SCJ technology specification is the result of an international effort from industry and academia. In this paper, we present a formalization of the SCJ Level 1 execution model, formalize a translation strategy from SCJ into a refinement notation and describe a tool that largely automates the generation of the formal models. Our modelling language is part of the Circus family; at the core, we have Z, communicating sequential processes and Morgan's calculus, but we also use object-oriented and timed constructs from the OhCircus and Circus Time variants. Our work is an essential ingredient for the development of refinement-based reasoning techniques for SCJ.

Description: Analyzing the underlying social network is very important for the development of online applications. Owing to the increasingly growing size of these networks, parallel techniques play important roles in many network analysis tasks. In this paper, we explore the link sign prediction problem in large-scale online social networks, and propose a parallel approach, called PLSP, to solve the problem. Specifically, we first extract a set of features that serve as a base for prediction. Experiments on several real datasets show that these features outperform those proposed by existing methods in predictive accuracy. Next, we present two speedup strategies, i.e. dataset division and feature selection, to shorten the training time. Experimental evaluations show that our parallel approach is much faster than the traditional non-parallel method and achieves higher predictive accuracy than other methods at the same time.

Description: DARPA's AACE project aimed to develop Architecture Aware Compiler Environments. Such a compiler automatically characterizes the targeted hardware and optimizes the application codes accordingly. We present the BlackjackBench suite, a collection of portable micro-benchmarks that automate system characterization, plus statistical analysis techniques for interpreting the results. The BlackjackBench benchmarks discover the effective sizes and speeds of the hardware environment rather than the often unattainable peak values. We aim at hardware characteristics that can be observed by running executables generated by existing compilers from standard C codes. We characterize the memory hierarchy, including cache sharing and non-uniform memory access characteristics of the system, properties of the processing cores affecting the instruction execution speed and the length of the operating system scheduler time slot. We show how these features of modern multicores can be discovered programmatically. We also show how the features could potentially interfere with each other resulting in incorrect interpretation of the results, and how established classification and statistical analysis techniques can reduce experimental noise and aid automatic interpretation of results. We show how effective hardware metrics from our probes allow guided tuning of computational kernels that outperform an autotuning library further tuned by the hardware vendor.

Description: Parrow and Victor introduced the fusion calculus (FC) (IEEE Symposium on Logic in Computer Science 1998) as a canonically reduced calculus of concurrency. In this paper, we consider an extension to the FC to deal with possible effects of non-Byzantine errors in name fusions. Extended syntax is defined in terms of meta-names and probabilistic variant of matching conditions with corresponding semantics in terms of labeled transition systems utilizing probabilistic matching graph. A variant of bisimulation (strictly stronger than hyperbisimulation of the original FC) is defined and shown to be a congruence. We further enrich the existing axiomatic system of FC to provide algebraic laws to decide the equivalence between processes in the presence of errors in the occurrence of fusion actions. The enriched axiomatization is proved to be both sound and complete for finite processes.

Description: A significant number of Cloud applications follow the 3-tier architectural pattern. Many of them serve customers worldwide and must meet non-functional requirements such as reliability, responsiveness and Quality of Experience (QoE). Thus the flexibility and scalability offered by clouds make them a suitable deployment environment. Latest developments show that using multiple clouds can further increase an application's reliability and user experience to a level that has not been achievable before. However, the research in scheduling and provisioning 3-tier applications in clouds and across clouds is still in its infancy. To foster the research efforts in the area, we propose an analytical performance model of 3-tier applications in Cloud and Multi-Cloud environments. It takes into account the performance of the persistent storage and the heterogeneity of cloud data centres in terms of Virtual Machine (VM) performance. Furthermore, it allows for modelling of heterogeneous workloads directed to different data centres. Based on our model, we have extended the CloudSim simulator, through which we validate the plausibility of our approach. The conducted experiments with the RUBiS workload show that the predicted performance characteristics by the simulation approximate well those of the modelled system.

Description: A method is given for calculating the strict minimum message length (SMML) estimator for 1-dimensional exponential families with continuous sufficient statistics. A set of n equations are found that the n cut-points of the SMML estimator must satisfy. These equations can be solved using Newton's method and this approach is used to produce new results and to replicate results that C.S. Wallace obtained. A rigorous proof is also given that the length of the 2-part code corresponding to the SMML estimator is a continuous function of the data, even though this length is composed of step functions.

Description: Stochastic Symmetric Nets (SSNs) are a High-Level Stochastic Petri Net formalism which provides a parametric system description and an efficient analysis technique that exploit system symmetries to automatically aggregate its states. Even if significant reductions can be achieved in highly symmetric models, the reduced state space can still be too large to derive and/or solve the underlying stochastic process, so that Monte Carlo simulation and fluid approximation remain the only viable ways that need to be explored. In this paper, we contribute to this line of research by proposing a new approach based on fluid approximation to automatically derive from an SSN model a set of ordinary differential equations (ODEs) which mimic the system behavior, and by showing how the SSN formalism allows us to define an efficient translation method which reduces the size of the corresponding ODE system with an automatic exploitation of system symmetries. Additionally, some case studies are presented to show the effectiveness of the method and the relevance of its application in practical cases.

Description: This work is primarily inspired by the observation that supervisory control and regulated rewriting have the same nature. Indeed, both of them model a system using some formalism and use a certain formalized control structure to restrict the behavior of the system via some designated control mechanisms . In this paper, we propose the theory of Control Systems (C Systems), which provides a more generic framework to integrate the automaton and grammar representations of control in supervisory control and regulated rewriting. The C system contains two components: the controlled component and the controlling component . The two components are expressed using the same formalism, e.g. automata or grammars. More specifically, we define three types of control systems based on the automaton or grammar representation, namely Automaton Control Systems (AC Systems), Grammar Control Systems (GC Systems) and Leftmost-derivation-based Grammar Control Systems (LGC Systems). We formally study their key theoretical characterizations, such as generative power, equivalence and translation techniques, as well as their connections with supervisory control and regulated rewriting, including the relationships between AC systems and supervisory control, and between GC/LGC systems and regulated rewriting. We also discuss some applications of C systems and finally propose some open questions.

Description: This paper presents an analysis of the energy consumption of an extensive number of the optimizations a modern compiler can perform. Using GCC as a test case, we evaluate a set of 10 carefully selected benchmarks for 5 different embedded platforms. A fractional factorial design is used to systematically explore the large optimization space (2 82 possible combinations), while still accurately determining the effects of optimizations and optimization combinations. Hardware power measurements on each platform are taken to ensure all architectural effects on the energy consumption are captured. We show that fractional factorial design can find more optimal combinations than relying on built-in compiler settings. We explore the relationship between run-time and energy consumption, and identify scenarios where they are and are not correlated. A further conclusion of this study is the structure of the benchmark has a larger effect than the hardware architecture on whether the optimization will be effective, and that no single optimization is universally beneficial for execution time or energy consumption.

Description: This paper focuses on a variation of the Art Gallery problem that considers open-edge guards and open mobile-guards. A mobile guard can be placed on edges and diagonals of a polygon, and the ‘open’ prefix means that the endpoints of such an edge or diagonal are not taken into account for visibility purposes. This paper studies the number of guards that are sufficient and sometimes necessary to guard some classes of simple polygons for both open-edge and open mobile-guards. A wide range of polygons is studied, which include orthogonal polygons with or without holes, spirals, orthogonal spirals and monotone polygons. Moreover, this problem is also considered for planar triangulation graphs using open-edge guards.

Description: With the rapid development of cloud computing technologies, more and more service providers place their services in clouds for users. In the cloud environment, users can access the resources and services without knowing the location of data, computing devices and platforms. With the popularity of cloud computing applications, authentication and security issues of cloud computing have become important research topics. Considering the benefits of implementing a service system in the cloud environment and the convenience of the integration of different ticket-sale systems, we propose a novel and secure diverse ticket-sale system (DTS) in hybrid cloud using smart cards. The accuracy of involved participant authentication is demonstrated according to the BAN logic. The DTS contains a ticket integration platform that the service providers can delegate the sale of their service tickets to the integrated server, and the customers can freely browse and purchase electronic service tickets from the system in any networked place. We also show that the DTS system possesses many good features and can effectively resist a number of potential attacks.

Description: Global constraints are an essential component in the efficiency of centralized constraint programming. We propose to include global constraints in distributed constraint satisfaction problem (DisCSP) and distributed constraint optimization problem (DCOP). We detail how this inclusion can be done, considering different representations for global constraints (direct, nested, binary). We explore the relation of global constraints with local consistency (both in the hard and soft cases), in particular, for generalized arc consistency (GAC). We provide experimental evidence of the benefits of global constraints on several benchmarks, both for distributed constraint satisfaction and for distributed constraint optimization.

Description: Research on optimization in multi-agent systems (MASs) has contributed with a wealth of techniques to solve many of the challenges arising in a wide range of multi-agent application domains. Multi-agent optimization focuses on casting MAS problems into optimization problems. The solving of those problems could possibly involve the active participation of the agents in a MAS. Research on multi-agent optimization has rapidly become a very technical, specialized field. Moreover, the contributions to the field in the literature are largely scattered. These two factors dramatically hinder access to a basic, general view of the foundations of the field. This tutorial is intended to ease such access by providing a gentle introduction to fundamental concepts and techniques on multi-agent optimization.

Description: Many strategic actions carry a ‘contagious’ component beyond the immediate locale of the effort itself. Viral marketing and peacekeeping operations have both been observed to have a spreading effect. In this work, we use counterinsurgency as our illustrative domain. Defined as the effort to block the spread of support for an insurgency, such operations lack the manpower to defend the entire population and must focus on the opinions of a subset of local leaders. As past researchers of security resource allocation have done, we propose using game theory to develop such policies and model the interconnected network of leaders as a graph. Unlike this past work in security games, actions in these domains possess a probabilistic, non-local impact. To address this new class of security games, we combine recent research in influence-blocking maximization with a double oracle approach and create novel heuristic oracles to generate mixed strategies for a real-world leadership network from Afghanistan, synthetic leadership networks and scale-free graphs. We find that leadership networks that exhibit highly interconnected clusters can be solved equally well by our heuristic methods, but our more sophisticated heuristics outperform simpler ones in less interconnected scale-free graphs.

Description: This paper proposes a method for multi-agent path planning on a road network in the presence of congestion. We suggest a distributed method to find paths for multiple agents by introducing a probabilistic path choice achieving global goals such as the user equilibrium or the social optimum. This approach, which shows that the global goals can be achieved by local processing using only local information, can be parallelized and sped-up using massive parallel processing. The probabilistic assignment reliably copes with the case of random choices of unidentified agents or random route changes of agents who ignore our path guidance. We provide the analytical result on convergence and running time. We demonstrate and evaluate our algorithm by an implementation using asynchronous computation on multi-core computers.

Description: Information assurance (IA) is a growing concern, since almost every aspect of our lives depends on distributed information systems and the frequency and sophistication of cyber attacks targeting these systems is on the rise. However, IA cannot be considered in isolation, as it also affects the Quality of Service (QoS); with limited resources, the security mechanisms employed for IA (e.g. firewalls, antivirus, encryption) usually adversely affect QoS levels delivered by a system. The system therefore needs to make tradeoffs between IA and QoS. These tradeoffs are complicated by the facts that users’ relative preferences over QoS–IA change based on the situation, the preferences of different users conflict and tradeoff decisions made at one node in the distributed system typically affect other nodes as well. We address the problem of distributed computation of tradeoffs among various aspects of QoS and IA in a way that maximizes the satisfaction of all stakeholders. Specifically, we want the nodes in the system to make coordinated decisions as to what local actions to take to optimize QoS/IA levels delivered by the system. Our first contribution is formulating this problem as a distributed constraint optimization problem (DCOP). This entails quantifying various notions involved in tradeoffs to be able to compare options in the course of optimization, as well as encoding the effects of various decisions on the quantities we want to optimize. The DCOPs we obtain have cost functions where multiple local configurations result in the same cost. In addition, the corresponding factor graphs contain many cycles. To deal with these issues, our second contribution is a value propagation (VP) algorithm that helps nodes reach a consistent set of decisions even in cyclic factor graphs with non-unique local optima. We present experimental results comparing the performance of the max-sum algorithm with and without VP against other algorithms when applied to domain-inspired and random instances. On the domain-inspired instances, max-sum with VP achieves near optimal solutions at a fraction of time taken by Distributed Pseudotree Optimization Procedure, with the reduction in solution cost due to VP most pronounced in scenarios with resource contention. On random instances, VP obtains solutions with cost 1.7 x of optimal, even when performed without a utility propagation algorithm first.

Description: In this paper, we revisit the modeling assumptions of some of the most widely accepted models in existing literature on the IEEE 802.11 distributed coordination function (DCF) with respect to their accuracy. Ultimately, our objective is to verify the precision of the analytical models with simulation results. First, we outline a number of issues and criticalities in underlying assumptions of existing approaches to backoff process modeling for unsaturated and saturated scenarios. Then, by revisiting the assumptions in existing backoff process models, we reassess them for the more complicated unsaturated case under more realistic assumptions. We argue that under unsaturated load conditions the backoff process exhibits a -persistent behavior. Our claims are supported by observing the simulated behavior of a wireless local area network (WLAN) under varying load conditions. Also, the principle of ‘measures of uncertainty’ provides theoretical basis for our arguments. Comparison with known models in different simulation environments confirms the increased accuracy of the proposed model over a wide range of settings.

Description: In this paper, a positioning system with a single base station, named Direction and Distance Positioning System (D 2 PS), is proposed for wireless infrastructure networks. The proposed method can be applied to those base stations (BSs) that are equipped with an omni-directional antenna. The general products of access points can use it without installing the special antenna hardware such as the directional antenna array. This positioning system is launched when a mobile host (MH) is moving. A BS locates an MH according to the moving direction and distance. The received signal strength is also used to refine the moving direction of the MH. The distance from the BS to the MH is computed according to the signal propagation time. Locating the position of the MH is transformed to a geometric model which finds the cross points between a line and a circle on the plane. The simulation discusses the positioning errors caused by the current location of the MH and the precision of the electronic compass. The localization accuracy of the proposed method is close to that of the positioning technique which uses the directional antenna array. The simulation results also conclude that the MH can be located within five measurements if its probability of changing the moving direction is higher than 20%.

Description: Nowadays, video data transfers account for much of the Internet bandwidth and a huge number of users use it daily. However, despite its apparent interest, video streaming is still done in a suboptimal manner. Indeed, more and more high-definition and high-quality videos are nowadays stored on Internet but they are not accessible for everybody because a high and stable bandwidth is needed to stream them; also, during videoconferencing, the highest possible quality often exceeds the available bandwidth. Hence, a lower bitrate encoding is usually chosen but it leads to lower quality and network under-utilization too. This paper presents Video Adaptation at Application Layer (VAAL), a simple and efficient method designed to use optimally network resources and to ameliorate user video experience. It involves only the application layer on the server. The main idea of VAAL is that it checks Transmission Control Protocol-friendly transport protocol buffer overflows and adapts the video bitrate accordingly; as a result, the bitrate constantly matches the network bandwidth. It can be used together with Zigzag Avoidance Algorithm (ZAAL), a novel algorithm aiming to avoid quality oscillations. Experimental results show that the video adaptation using VAAL+ZAAL performs much better compared with the currently widely used static encoding, making it a strong candidate for hard real-time video streaming.

Description: In a peer-to-peer (P2P) video-on-demand (VoD) system, each peer contributes a limited disc storage and stores some watched movies to offload the servers when these movies are requested. When the contributed disc storage of a peer is full, to minimize the server load, which movie should be replaced is a key design problem for P2P VoD systems. This problem is a P2P replication problem. Previous studies on this problem mainly consider content availability, but fail to consider bandwidth availability of peers on the system level. In this paper, assuming that movie popularity is known, we first analyze bandwidth availability of peers on the system level, and then formulate the replication problem as a minimization problem. Based on the minimization problem, we derive two design guidelines. According to the two design guidelines, we propose a bandwidth-availability-based replication algorithm aiming at minimizing the server load, called BAB algorithm. BAB algorithm can make the replicas’ distribution towards the optimal distribution in a distributed way. Furthermore, we consider some practical implementation issues of BAB algorithm. Through extensive simulations, we demonstrate that BAB algorithm outperforms the previously proposed algorithms in terms of reducing the server load and improving the streaming quality, in stable environment and dynamic environment, respectively.