OpenRaiser/Intern-Atlas huggingface dataset:
A Decidable Fragment of Strategy Logic
Venue: arXiv cs.LO 2012
Year: 2012

Strategy Logic (SL, for short) has been recently introduced by Mogavero, Murano, and Vardi as a useful formalism for reasoning explicitly about strategies, as first-order objects, in multi-agent concurrent games. This logic turns to be very powerful, subsuming all major previously studied modal logics for strategic reasoning, including ATL, ATL*, and the like. Unfortunately, due to its expressiveness, SL has a non-elementarily decidable model-checking problem and a highly undecidable satisfiability problem, specifically, $Σ_{1}^{1}$-Hard. In order to obtain a decidable sublogic, we introduce and study here One-Goal Strategy Logic (SL[1G], for short). This logic is a syntactic fragment of SL, strictly subsuming ATL*, which encompasses formulas in prenex normal form having a single temporal goal at a time, for every strategy quantification of agents. SL[1G] is known to have an elementarily decidable model-checking problem. Here we prove that, unlike SL, it has the bounded tree-model property and its satisfiability problem is decidable in 2ExpTime, thus not harder than the one for ATL*.
An Energy Efficient Semi-static Power Control and Link Adaptation Scheme in UMTS HSDPA
Venue: arXiv cs.IT 2012
Year: 2012

High speed downlink packet access (HSDPA) has been successfully applied in commercial systems and improves user experience significantly. However, it incurs substantial energy consumption. In this paper, we address this issue by proposing a novel energy efficient semi-static power control and link adaptation scheme in HSDPA. Through estimating the EE under different modulation and coding schemes (MCSs) and corresponding transmit power, the proposed scheme can determine the most energy efficient MCS level and transmit power at the Node B. And then the Node B configure the optimal MCS level and transmit power. In order to decrease the signaling overhead caused by the configuration, a dual trigger mechanism is employed. After that, we extend the proposed scheme to the multiple input multiple output (MIMO) scenarios. Simulation results confirm the significant EE improvement of our proposed scheme. Finally, we give a discussion on the potential EE gain and challenge of the energy efficient mode switching between single input multiple output (SIMO) and MIMO configuration in HSDPA.
MEGCOM: Min-Energy Group COMmunication in Multi-hop Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

Given the increasing demand from wireless applications, designing energy-efficient group communication protocols is of great importance to multi-hop wireless networks. A group communication session involves a set of member nodes, each of them needs to send a certain number of data packets to all other members. In this paper, we consider the problem of building a shared multicast tree spanning the member nodes such that the total energy consumption of a group communication session using the shared multicast tree is minimized. Since this problem was proven as NP-complete, we propose, under our Min-Energy Group COMmunication (MEGCOM) framework, three distributed approximation algorithms with provable approximation ratios. When the transmission power of each wireless node is fixed, our first two algorithms have the approximation ratios of O(ln(Δ+ 1)) and O(1), respectively, where Δis the maximum node degree in the network. When the transmission power of each wireless node is adjustable, our third algorithm again delivers a constant approximation ratio. We also use extensive simulations to verify the practical performance of our algorithms.
Automatic Clustering with Single Optimal Solution
Venue: arXiv cs.CV 2012
Year: 2012

Determining optimal number of clusters in a dataset is a challenging task. Though some methods are available, there is no algorithm that produces unique clustering solution. The paper proposes an Automatic Merging for Single Optimal Solution (AMSOS) which aims to generate unique and nearly optimal clusters for the given datasets automatically. The AMSOS is iteratively merges the closest clusters automatically by validating with cluster validity measure to find single and nearly optimal clusters for the given data set. Experiments on both synthetic and real data have proved that the proposed algorithm finds single and nearly optimal clustering structure in terms of number of clusters, compactness and separation.
Data Exchange Problem with Helpers
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we construct a deterministic polynomial time algorithm for the problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge of the file. We further assume the existence of another set of terminals in the system, called helpers, who are not interested in the common file, but who are willing to help the users. Given that the collective information of all the terminals is sufficient to allow recovery of the entire file, the goal is to minimize the (weighted) sum of bits that these terminals need to exchange over a noiseless public channel in order achieve this goal. Based on established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing the largest shared secret key in the presence of an eavesdropper. We consider the following side-information settings: (i) side-information in the form of uncoded packets of the file, where the terminals' side-information consists of subsets of the file; (ii) side-information in the form of linearly correlated packets, where the terminals have access to linear combinations of the file packets; and (iii) the general setting where the the terminals' side-information has an arbitrary (i.i.d.) correlation structure. We provide a polynomial-time algorithm (in the number of terminals) that finds the optimal rate allocations for these terminals, and then determines an explicit optimal transmission scheme for cases (i) and (ii).
Open Data: Reverse Engineering and Maintenance Perspective
Venue: arXiv cs.SE 2012
Year: 2012

Open data is an emerging paradigm to share large and diverse datasets -- primarily from governmental agencies, but also from other organizations -- with the goal to enable the exploitation of the data for societal, academic, and commercial gains. There are now already many datasets available with diverse characteristics in terms of size, encoding and structure. These datasets are often created and maintained in an ad-hoc manner. Thus, open data poses many challenges and there is a need for effective tools and techniques to manage and maintain it. In this paper we argue that software maintenance and reverse engineering have an opportunity to contribute to open data and to shape its future development. From the perspective of reverse engineering research, open data is a new artifact that serves as input for reverse engineering techniques and processes. Specific challenges of open data are document scraping, image processing, and structure/schema recognition. From the perspective of maintenance research, maintenance has to accommodate changes of open data sources by third-party providers, traceability of data transformation pipelines, and quality assurance of data and transformations. We believe that the increasing importance of open data and the research challenges that it brings with it may possibly lead to the emergence of new research streams for reverse engineering as well as for maintenance.
Efficient Decoding of Partial Unit Memory Codes of Arbitrary Rate
Venue: arXiv cs.IT 2012
Year: 2012

Partial Unit Memory (PUM) codes are a special class of convolutional codes, which are often constructed by means of block codes. Decoding of PUM codes may take advantage of existing decoders for the block code. The Dettmar--Sorger algorithm is an efficient decoding algorithm for PUM codes, but allows only low code rates. The same restriction holds for several known PUM code constructions. In this paper, an arbitrary-rate construction, the analysis of its distance parameters and a generalized decoding algorithm for PUM codes of arbitrary rate are provided. The correctness of the algorithm is proven and it is shown that its complexity is cubic in the length.
A transformation approach for collaboration based requirement models
Venue: arXiv cs.SE 2012
Year: 2012

Distributed software engineering is widely recognized as a complex task. Among the inherent complexities is the process of obtaining a system design from its global requirement specification. This paper deals with such transformation process and suggests an approach to derive the behavior of a given system components, in the form of distributed Finite State Machines, from the global system requirements, in the form of an augmented UML Activity Diagrams notation. The process of the suggested approach is summarized in three steps: the definition of the appropriate source Meta-Model (requirements Meta-Model), the definition of the target Design Meta-Model and the definition of the rules to govern the transformation during the derivation process. The derivation process transforms the global system requirements described as UML diagram activities (extended with collaborations) to system roles behaviors represented as UML finite state machines. The approach is implemented using Atlas Transformation Language (ATL).
Semantic Visualization and Navigation in Textual Corpus
Venue: arXiv cs.IR 2012
Year: 2012

This paper gives a survey of related work on the information visualization domain and study the real integration of the cartography paradigms in actual information search systems. Based on this study, we propose a semantic visualization and navigation approach which offer to users three search modes: precise search, connotative search and thematic search. The objective is to propose to the users of an information search system, new interaction paradigms which support the semantic aspect of the considered information space and guide users in their searches by assisting them to locate their interest center and to improve serendipity.
Encryption of Data using Elliptic Curve over Finite fields
Venue: arXiv cs.CR 2012
Year: 2012

Cryptography is the study of techniques for ensuring the secrecy and authentication of the information. Public-key encryption schemes are secure only if the authenticity of the public-key is assured. Elliptic curve arithmetic can be used to develop a variety of elliptic curve cryptography (ECC) schemes including key exchange, encryption and digital signature. The principal attraction of elliptic curve cryptography compared to RSA is that it offers equal security for a smaller key-size, thereby reducing the processing overhead. In the present paper we propose a new encryption algorithm using some Elliptic Curve over finite fields
FATAL+: A Self-Stabilizing Byzantine Fault-tolerant Clocking Scheme for SoCs
Venue: arXiv cs.DC 2012
Year: 2012

We present concept and implementation of a self-stabilizing Byzantine fault-tolerant distributed clock generation scheme for multi-synchronous GALS architectures in critical applications. It combines a variant of a recently introduced self-stabilizing algorithm for generating low-frequency, low-accuracy synchronized pulses with a simple non-stabilizing high-frequency, high-accuracy clock synchronization algorithm. We provide thorough correctness proofs and a performance analysis, which use methods from fault-tolerant distributed computing research but also addresses hardware-related issues like metastability. The algorithm, which consists of several concurrent communicating asynchronous state machines, has been implemented in VHDL using Petrify in conjunction with some extensions, and synthetisized for an Altera Cyclone FPGA. An experimental validation of this prototype has been carried out to confirm the skew and clock frequency bounds predicted by the theoretical analysis, as well as the very short stabilization times (required for recovering after excessively many transient failures) achievable in practice.
Traffic and Security using Randomized Dispersive Routes in Heterogeneous Sensor Network
Venue: arXiv cs.NI 2012
Year: 2012

Generally traffic and the sensor network security have many challenges in the transmission of data in the network. The existing schemes consider homogeneous sensor networks which have poor performance and scalability. Due to many-to-one traffic pattern, sensors may communicate with small portion of its neighbours. Key management is the critical process in sensor nodes to secure the data. Most existing schemes establish shared keys for all the sensors no matter whether they are communicating or not. Hence it leads to large storage overhead. Another problem in sensor network is compromised node attack and denial of service attack which occurs because of its wireless nature. Existing multi path routing algorithms are vulnerable to these attacks. So once an adversary acquires the routing algorithm, it can compute the same routes known to the source, and hence endanger all information sent over these routes. If an adversary performs node compromise attack, they can easily get the encryption/ decryption keys used by that node and hence they can intercept the information easily. In this paper we are proposing a key management scheme which only establishes shared keys with their communicating neighbour and a mechanism to generate randomized multipath routes for secure transmission of data to the sink. Here we are adopting heterogeneous sensor networks and we are utilizing elliptic curve cryptography for efficient key management which is more efficient, scalable, and highly secure and reduces communication overhead. The routes generated by our mechanism are highly dispersive, energy efficient and making them quite capable of bypassing the back holes at low energy cost.
Discovery through Gossip
Venue: arXiv cs.DC 2012
Year: 2012

We study randomized gossip-based processes in dynamic networks that are motivated by discovery processes in large-scale distributed networks like peer-to-peer or social networks. A well-studied problem in peer-to-peer networks is the resource discovery problem. There, the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network - new edges are added to the network - and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes with a continuously self-changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip-based discovery processes. In the push process, each node repeatedly chooses two random neighbors and puts them in contact (i.e., "pushes" their mutual information to each other). In the pull discovery process, each node repeatedly requests or "pulls" a random contact from a random neighbor. Both processes are lightweight, local, and naturally robust due to their randomization. Our main result is an almost-tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n-node graph both processes take O(n log^2 n) rounds to connect every node to all other nodes with high probability, whereas Omega(n log n) is a lower bound. In the directed case we give an O(n^2 log n) upper bound and an Omega(n^2) lower bound for strongly connected directed graphs. A key technical challenge that we overcome is the analysis of a randomized process that itself results in a constantly changing network which leads to complicated dependencies in every round.
Decentralized Delay Optimal Control for Interference Networks with Limited Renewable Energy Storage
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider delay minimization for interference networks with renewable energy source, where the transmission power of a node comes from both the conventional utility power (AC power) and the renewable energy source. We assume the transmission power of each node is a function of the local channel state, local data queue state and local energy queue state only. In turn, we consider two delay optimization formulations, namely the decentralized partially observable Markov decision process (DEC-POMDP) and Non-cooperative partially observable stochastic game (POSG). In DEC-POMDP formulation, we derive a decentralized online learning algorithm to determine the control actions and Lagrangian multipliers (LMs) simultaneously, based on the policy gradient approach. Under some mild technical conditions, the proposed decentralized policy gradient algorithm converges almost surely to a local optimal solution. On the other hand, in the non-cooperative POSG formulation, the transmitter nodes are non-cooperative. We extend the decentralized policy gradient solution and establish the technical proof for almost-sure convergence of the learning algorithms. In both cases, the solutions are very robust to model variations. Finally, the delay performance of the proposed solutions are compared with conventional baseline schemes for interference networks and it is illustrated that substantial delay performance gain and energy savings can be achieved.
Museum: Multidimensional web page segment evaluation model
Venue: arXiv cs.IR 2012
Year: 2012

The evaluation of a web page with respect to a query is a vital task in the web information retrieval domain. This paper proposes the evaluation of a web page as a bottom-up process from the segment level to the page level. A model for evaluating the relevancy is proposed incorporating six different dimensions. An algorithm for evaluating the segments of a web page, using the above mentioned six dimensions is proposed. The benefits of fine-granining the evaluation process to the segment level instead of the page level are explored. The proposed model can be incorporated for various tasks like web page personalization, result re-ranking, mobile device page rendering etc.
Wavelength Assignment in Design DWDM Transport Network Using Algorithm BCO-RWA
Venue: arXiv cs.NI 2012
Year: 2012

The main problem in designing DWDM transport networks is the wavelength assignment of light paths. One way of solving this problem is to use the algorithm BCO-RWA. However, BCO-RWA has the following disadvantages: algorithm not solved the problem of choosing the location of the optical convector in the network; base algorithm ignores placement optical convector during calculating route selecting probability; base algorithm do not take into account the nonlinear four-wave mixing phenomenon. In this paper we present an algorithm which takes into account a number of disadvantages due to modifications introduced in the algorithm.
Topic Diffusion and Emergence of Virality in Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

We propose a stochastic model for the diffusion of topics entering a social network modeled by a Watts-Strogatz graph. Our model sets into play an implicit competition between these topics as they vie for the attention of users in the network. The dynamics of our model are based on notions taken from real-world OSNs like Twitter where users either adopt an exogenous topic or copy topics from their neighbors leading to endogenous propagation. When instantiated correctly, the model achieves a viral regime where a few topics garner unusually good response from the network, closely mimicking the behavior of real-world OSNs. Our main contribution is our description of how clusters of proximate users that have spoken on the topic merge to form a large giant component making a topic go viral. This demonstrates that it is not weak ties but actually strong ties that play a major part in virality. We further validate our model and our hypotheses about its behavior by comparing our simulation results with the results of a measurement study conducted on real data taken from Twitter.
Efficient Web-based Facial Recognition System Employing 2DHOG
Venue: arXiv cs.CV 2012
Year: 2012

In this paper, a system for facial recognition to identify missing and found people in Hajj and Umrah is described as a web portal. Explicitly, we present a novel algorithm for recognition and classifications of facial images based on applying 2DPCA to a 2D representation of the Histogram of oriented gradients (2D-HOG) which maintains the spatial relation between pixels of the input images. This algorithm allows a compact representation of the images which reduces the computational complexity and the storage requirments, while maintaining the highest reported recognition accuracy. This promotes this method for usage with very large datasets. Large dataset was collected for people in Hajj. Experimental results employing ORL, UMIST, JAFFE, and HAJJ datasets confirm these excellent properties.
How the Scientific Community Reacts to Newly Submitted Preprints: Article Downloads, Twitter Mentions, and Citations
Venue: arXiv cs.SI 2012
Year: 2012

We analyze the online response to the preprint publication of a cohort of 4,606 scientific articles submitted to the preprint database arXiv.org between October 2010 and May 2011. We study three forms of responses to these preprints: downloads on the arXiv.org site, mentions on the social media site Twitter, and early citations in the scholarly record. We perform two analyses. First, we analyze the delay and time span of article downloads and Twitter mentions following submission, to understand the temporal configuration of these reactions and whether one precedes or follows the other. Second, we run regression and correlation tests to investigate the relationship between Twitter mentions, arXiv downloads and article citations. We find that Twitter mentions and arXiv downloads of scholarly articles follow two distinct temporal patterns of activity, with Twitter mentions having shorter delays and narrower time spans than arXiv downloads. We also find that the volume of Twitter mentions is statistically correlated with arXiv downloads and early citations just months after the publication of a preprint, with a possible bias that favors highly mentioned articles.
Survey-Based Analysis of the Proposed Component-Based Development Process
Venue: arXiv cs.SE 2012
Year: 2012

The concept of component-based development (CBD) is widely practiced in software (SW) development. CBD is based on reuse of the existing components with the new ones. The objective of this paper is to propose a novel process model for CBD. Importance of repository has also been discussed. A survey has been conducted to evaluate the proposed model. The results of the survey show that proposed process model can be efficiently implemented for CBD projects.
Experimental study of the impact of historical information in human coordination
Venue: arXiv cs.SI 2012
Year: 2012

We perform laboratory experiments to elucidate the role of historical information in games involving human coordination. Our approach follows prior work studying human network coordination using the task of graph coloring. We first motivate this research by showing empirical evidence that the resolution of coloring conflicts is dependent upon the recent local history of that conflict. We also conduct two tailored experiments to manipulate the game history that can be used by humans in order to determine (i) whether humans use historical information, and (ii) whether they use it effectively. In the first variant, during the course of each coloring task, the network positions of the subjects were periodically swapped while maintaining the global coloring state of the network. In the second variant, participants completed a series of 2-coloring tasks, some of which were restarts from checkpoints of previous tasks. Thus, the participants restarted the coloring task from a point in the middle of a previous task without knowledge of the history that led to that point. We report on the game dynamics and average completion times for the diverse graph topologies used in the swap and restart experiments.