OpenRaiser/Intern-Atlas huggingface dataset:
A Local Broadcast Layer for the SINR Network Model
Venue: arXiv cs.DC 2015
Year: 2015

We present the first algorithm that implements an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that efficient SINR implementations are not possible for the standard absMAC specification. We modify that specification to an "approximate" version that better suits the SINR model. We give an efficient algorithm to implement the modified specification, and use it to derive efficient algorithms for higher-level problems of global broadcast and consensus. In particular, we show that the absMAC progress property has no efficient implementation in terms of the SINR strong connectivity graph $G_{1-ε}$, which contains edges between nodes of distance at most $(1-ε)$ times the transmission range, where $ε>0$ is a small constant that can be chosen by the user. This progress property bounds the time until a node is guaranteed to receive some message when at least one of its neighbors is transmitting. To overcome this limitation, we introduce the slightly weaker notion of approximate progress into the absMAC specification. We provide a fast implementation of the modified specification, based on decomposing a known algorithm into local and global parts. We analyze our algorithm in terms of local parameters such as node degrees, rather than global parameters such as the overall number of nodes. A key contribution is our demonstration that such a local analysis is possible even in the presence of global interference. Our absMAC algorithm leads to several new, efficient algorithms for solving higher-level problems in the SINR model. Namely, by combining our algorithm with known high-level algorithms, we obtain an improved algorithm for global single-message broadcast in the SINR model, and the first efficient algorithm for multi-message broadcast in that model.
From Non-preemptive to Preemptive Scheduling using Synchronization Synthesis
Venue: arXiv cs.PL 2015
Year: 2015

We present a computer-aided programming approach to concurrency. The approach allows programmers to program assuming a friendly, non-preemptive scheduler, and our synthesis procedure inserts synchronization to ensure that the final program works even with a preemptive scheduler. The correctness specification is implicit, inferred from the non-preemptive behavior. Let us consider sequences of calls that the program makes to an external interface. The specification requires that any such sequence produced under a preemptive scheduler should be included in the set of such sequences produced under a non-preemptive scheduler. The solution is based on a finitary abstraction, an algorithm for bounded language inclusion modulo an independence relation, and rules for inserting synchronization. We apply the approach to device-driver programming, where the driver threads call the software interface of the device and the API provided by the operating system. Our experiments demonstrate that our synthesis method is precise and efficient, and, since it does not require explicit specifications, is more practical than the conventional approach based on user-provided assertions.
Place Recognition with Event-based Cameras and a Neural Implementation of SeqSLAM
Venue: arXiv cs.RO 2015
Year: 2015

Event-based cameras offer much potential to the fields of robotics and computer vision, in part due to their large dynamic range and extremely high "frame rates". These attributes make them, at least in theory, particularly suitable for enabling tasks like navigation and mapping on high speed robotic platforms under challenging lighting conditions, a task which has been particularly challenging for traditional algorithms and camera sensors. Before these tasks become feasible however, progress must be made towards adapting and innovating current RGB-camera-based algorithms to work with event-based cameras. In this paper we present ongoing research investigating two distinct approaches to incorporating event-based cameras for robotic navigation: the investigation of suitable place recognition / loop closure techniques, and the development of efficient neural implementations of place recognition techniques that enable the possibility of place recognition using event-based cameras at very high frame rates using neuromorphic computing hardware.
A critical cluster analysis of 44 indicators of author-level performance
Venue: arXiv cs.DL 2015
Year: 2015

This paper explores the relationship between author-level bibliometric indicators and the researchers the "measure", exemplified across five academic seniorities and four disciplines. Using cluster methodology, the disciplinary and seniority appropriateness of author-level indicators is examined. Publication and citation data for 741 researchers across Astronomy, Environmental Science, Philosophy and Public Health was collected in Web of Science (WoS). Forty-four indicators of individual performance were computed using the data. A two-step cluster analysis using IBM SPSS version 22 was performed, followed by a risk analysis and ordinal logistic regression to explore cluster membership. Indicator scores were contextualized using the individual researcher's curriculum vitae. Four different clusters based on indicator scores ranked researchers as low, middle, high and extremely high performers. The results show that different indicators were appropriate in demarcating ranked performance in different disciplines. In Astronomy the h2 indicator, sum pp top prop in Environmental Science, Q2 in Philosophy and e-index in Public Health. The regression and odds analysis showed individual level indicator scores were primarily dependent on the number of years since the researcher's first publication registered in WoS, number of publications and number of citations. Seniority classification was secondary therefore no seniority appropriate indicators were confidently identified. Cluster methodology proved useful in identifying disciplinary appropriate indicators providing the preliminary data preparation was thorough but needed to be supplemented by other analyses to validate the results. A general disconnection between the performance of the researcher on their curriculum vitae and the performance of the researcher based on bibliometric indicators was observed.
Synthesising Interprocedural Bit-Precise Termination Proofs (extended version)
Venue: arXiv cs.SE 2015
Year: 2015

Proving program termination is key to guaranteeing absence of undesirable behaviour, such as hanging programs and even security vulnerabilities such as denial-of-service attacks. To make termination checks scale to large systems, interprocedural termination analysis seems essential, which is a largely unexplored area of research in termination analysis, where most effort has focussed on difficult single-procedure problems. We present a modular termination analysis for C programs using template-based interprocedural summarisation. Our analysis combines a context-sensitive, over-approximating forward analysis with the inference of under-approximating preconditions for termination. Bit-precise termination arguments are synthesised over lexicographic linear ranking function templates. Our experimental results show that our tool 2LS outperforms state-of-the-art alternatives, and demonstrate the clear advantage of interprocedural reasoning over monolithic analysis in terms of efficiency, while retaining comparable precision.
Reflection-in-Action Markers for Reflection-on-Action in Computer-Supported Collaborative Learning Settings
Venue: arXiv cs.CY 2015
Year: 2015

We describe an exploratory study on the use of markers set during a synchronous collaborative interaction (reflection-in-action) for later construction of reflection reports upon the collaboration that occurred (reflection-on-action). During two sessions, pairs of students used the Visu videoconferencing tool for synchronous interaction and marker setting (positive, negative or free) and then individual report building on the interaction (using markers or not). A quantitative descriptive analysis was conducted on the markers put in action, on their use to reflect on action and on the reflection categories of the sentences in these reports. Results show that the students (1) used the markers equally as a note-taking and reflection means during the interaction, (2) used mainly positive markers both to reflect in and on action; (3) paid more attention in identifying what worked in their interaction (conservative direction) rather than in planning on how to improve their group work (progressive direction); (4) used mainly their own markers to reflect on action, with an increase in the use of their partners's markers in the second reflection reports; (5) reflected mainly on their partner in the first reflection reports and more on themselves in the second reports to justify themselves and to express their satisfaction.
Building a fault tolerant application using the GASPI communication layer
Venue: arXiv cs.DC 2015
Year: 2015

It is commonly agreed that highly parallel software on Exascale computers will suffer from many more runtime failures due to the decreasing trend in the mean time to failures (MTTF). Therefore, it is not surprising that a lot of research is going on in the area of fault tolerance and fault mitigation. Applications should survive a failure and/or be able to recover with minimal cost. MPI is not yet very mature in handling failures, the User-Level Failure Mitigation (ULFM) proposal being currently the most promising approach is still in its prototype phase. In our work we use GASPI, which is a relatively new communication library based on the PGAS model. It provides the missing features to allow the design of fault-tolerant applications. Instead of introducing algorithm-based fault tolerance in its true sense, we demonstrate how we can build on (existing) clever checkpointing and extend applications to allow integrate a low cost fault detection mechanism and, if necessary, recover the application on the fly. The aspects of process management, the restoration of groups and the recovery mechanism is presented in detail. We use a sparse matrix vector multiplication based application to perform the analysis of the overhead introduced by such modifications. Our fault detection mechanism causes no overhead in failure-free cases, whereas in case of failure(s), the failure detection and recovery cost is of reasonably acceptable order and shows good scalability.
Flexible, Scalable Mesh and Data Management using PETSc DMPlex
Venue: arXiv cs.MS 2015
Year: 2015

Designing a scientific software stack to meet the needs of the next-generation of mesh-based simulation demands, not only scalable and efficient mesh and data management on a wide range of platforms, but also an abstraction layer that makes it useful for a wide range of application codes. Common utility tasks, such as file I/O, mesh distribution, and work partitioning, should be delegated to external libraries in order to promote code re-use, extensibility and software interoperability. In this paper we demonstrate the use of PETSc's DMPlex data management API to perform mesh input and domain partitioning in Fluidity, a large scale CFD application. We demonstrate that raising the level of abstraction adds new functionality to the application code, such as support for additional mesh file formats and mesh re- ordering, while improving simulation startup cost through more efficient mesh distribution. Moreover, the separation of concerns accomplished through this interface shifts critical performance and interoperability issues, such as scalable I/O and file format support, to a widely used and supported open source community library, improving the sustainability, performance, and functionality of Fluidity.
A survey of recent results in (generalized) graph entropies
Venue: arXiv cs.IT 2015
Year: 2015

The entropy of a graph was first introduced by Rashevsky \cite{Rashevsky} and Trucco \cite{Trucco} to interpret as the structural information content of the graph and serve as a complexity measure. In this paper, we first state a number of definitions of graph entropy measures and generalized graph entropies. Then we survey the known results about them from the following three respects: inequalities and extremal properties on graph entropies, relationships between graph structures, graph energies, topological indices and generalized graph entropies, complexity for calculation of graph entropies. Various applications of graph entropies together with some open problems and conjectures are also presented for further research.
Kalman Filtering With Relays Over Wireless Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

This note studies the use of relays to improve the performance of Kalman filtering over packet dropping links. Packet reception probabilities are governed by time-varying fading channel gains, and the sensor and relay transmit powers. We consider situations with multiple sensors and relays, where each relay can either forward one of the sensors' measurements to the gateway/fusion center, or perform a simple linear network coding operation on some of the sensor measurements. Using an expected error covariance performance measure, we consider optimal and suboptimal methods for finding the best relay configuration, and power control problems for optimizing the Kalman filter performance. Our methods show that significant performance gains can be obtained through the use of relays, network coding and power control, with at least 30-40$\%$ less power consumption for a given expected error covariance specification.
Natural Data Storage: A Review on sending Information from now to then via Nature
Venue: arXiv cs.IT 2015
Year: 2015

Digital data explosion drives a demand for robust and reliable data storage medium. Development of better digital storage device to accumulate Zetta bytes (1 ZB = $10^{21}$ bytes ) of data that will be generated in near future is a big challenge. Looking at limitations of present day digital storage devices, it will soon be a big challenge for data scientists to provide reliable. affordable and dense storage medium. As an alternative, researcher used natural medium of storage like DNA, bacteria and protein as information storage systems. This article discuss DNA based information storage system in detail along with an overview about bacterial and protein data storage systems.
Character-level Chinese Writer Identification using Path Signature Feature, DropStroke and Deep CNN
Venue: arXiv cs.CV 2015
Year: 2015

Most existing online writer-identification systems require that the text content is supplied in advance and rely on separately designed features and classifiers. The identifications are based on lines of text, entire paragraphs, or entire documents; however, these materials are not always available. In this paper, we introduce a path-signature feature to an end-to-end text-independent writer-identification system with a deep convolutional neural network (DCNN). Because deep models require a considerable amount of data to achieve good performance, we propose a data-augmentation method named DropStroke to enrich personal handwriting. Experiments were conducted on online handwritten Chinese characters from the CASIA-OLHWDB1.0 dataset, which consists of 3,866 classes from 420 writers. For each writer, we only used 200 samples for training and the remaining 3,666. The results reveal that the path-signature feature is useful for writer identification, and the proposed DropStroke technique enhances the generalization and significantly improves performance.
Modular Action Language ALM
Venue: arXiv cs.LO 2015
Year: 2015

The paper introduces a new modular action language, ALM, and illustrates the methodology of its use. It is based on the approach of Gelfond and Lifschitz (1993; 1998) in which a high-level action language is used as a front end for a logic programming system description. The resulting logic programming representation is used to perform various computational tasks. The methodology based on existing action languages works well for small and even medium size systems, but is not meant to deal with larger systems that require structuring of knowledge. ALM is meant to remedy this problem. Structuring of knowledge in ALM is supported by the concepts of module (a formal description of a specific piece of knowledge packaged as a unit), module hierarchy, and library, and by the division of a system description of ALM into two parts: theory and structure. A theory consists of one or more modules with a common theme, possibly organized into a module hierarchy based on a dependency relation. It contains declarations of sorts, attributes, and properties of the domain together with axioms describing them. Structures are used to describe the domain's objects. These features, together with the means for defining classes of a domain as special cases of previously defined ones, facilitate the stepwise development, testing, and readability of a knowledge base, as well as the creation of knowledge representation libraries. To appear in Theory and Practice of Logic Programming (TPLP).
Brief Announcement : Average Complexity for the LOCAL Model
Venue: arXiv cs.DC 2015
Year: 2015

A standard model in network synchronised distributed computing is the LOCAL model. In this model, the processors work in rounds and, in the classic setting, they know the number of vertices of the network, $n$. Using $n$, they can compute the number of rounds after which they must all stop and output. It has been shown recently that for many problems, one can basically remove the assumption about the knowledge of $n$, without increasing the asymptotic running time. In this case, it is assumed that different vertices can choose their final output at different rounds, but continue to transmit messages. In both models, the measure of the running time is the number of rounds before the last node outputs. In this brief announcement, the vertices do not have the knowledge of $n$, and we consider an alternative measure: the average, over the nodes, of the number of rounds before they output. We prove that the complexity of a problem can be exponentially smaller with the new measure, but that Linial's lower bound for colouring still holds.
Koszul-Young Flattenings and Symmetric Border Rank of the Determinant
Venue: arXiv cs.CC 2015
Year: 2015

We present new lower bounds for the symmetric border rank of the n x n determinant for all n. Further lower bounds are given for the 3 x 3 permanent.
Reed-Muller Codes Achieve Capacity on Erasure Channels
Venue: arXiv cs.IT 2015
Year: 2015

This paper introduces a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, this method requires only that the codes are highly symmetric. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge to a number between 0 and 1, and the permutation group of each code is doubly transitive. This also provides a rare example in information theory where symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing blocklength achieves capacity if its code rate converges to a number between 0 and 1. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to affine-invariant codes and, thus, to all extended primitive narrow-sense BCH codes. The primary tools used in the proof are the sharp threshold property for monotone boolean functions and the area theorem for extrinsic information transfer functions.
Network Simulator - Visão Geral da Ferramenta de Simulação de Redes
Venue: arXiv cs.PF 2015
Year: 2015

This paper describes NS - Network Simulator, the computer networks simulation tool. We offer an overview NS, and also analyze its characteristics and functions. Finally, we present in detail all steps for preparing a simulation of a simple model in NS.
Homomorphic Data Isolation for Hardware Trojan Protection
Venue: arXiv cs.CR 2015
Year: 2015

The interest in homomorphic encryption/decryption is increasing due to its excellent security properties and operating facilities. It allows operating on data without revealing its content. In this work, we suggest using homomorphism for Hardware Trojan protection. We implement two partial homomorphic designs based on ElGamal encryption/decryption scheme. The first design is a multiplicative homomorphic, whereas the second one is an additive homomorphic. We implement the proposed designs on a low-cost Xilinx Spartan-6 FPGA. Area utilization, delay, and power consumption are reported for both designs. Furthermore, we introduce a dual-circuit design that combines the two earlier designs using resource sharing in order to have minimum area cost. Experimental results show that our dual-circuit design saves 35% of the logic resources compared to a regular design without resource sharing. The saving in power consumption is 20%, whereas the number of cycles needed remains almost the same
Regional Development Classification Model using Decision Tree Approach
Venue: arXiv cs.CY 2015
Year: 2015

Regional development classification is one way to look at differences in levels of development outcomes. Some frequently used methods are the shift share, Gain index, the Iindex Williamson and Klassen typology. The development of science in the field of data mining, offers a new way for regional development data classification. This study discusses how the decision tree is used to classify the level of development based on indicators of regional gross domestic product (GDP). GDP Data Central Java and Banten used in this study. Before the data is entered into the decision tree forming algorithm, both the provincial GDP data are classified using Klassen typology. Three decision tree algorithms, namely J48, NBTRee and REPTree tested in this study using cross-validation evaluation, then selected one of the best performing algorithms. The results show that the J48 has a better accuracy rate which is equal to 85.18% compared to the algorithm NBTRee and REPTree. Testing the model is done to the six districts / municipalities in the province of Banten, and shows that there are two districts / cities are still at the development of the status quadrant relatively underdeveloped regions, namely Kota Tangerang and Kabupaten Tangerang. As for the Central Java Province, Kendal, Magelang, Pemalang, Rembang, Semarang and Wonosobo are an area with a quadrant of development also on the status of the region is relatively underdeveloped. Classification model that has been developed is able to classify the level of development fast and easy to enter data directly into the decision tree is formed. This study can be used as an alternative decision support for policy makers in order to determine the future direction of development.
Managing Null Entries in Pairwise Comparisons
Venue: arXiv cs.OH 2015
Year: 2015

This paper shows how to manage null entries in pairwise comparisons matrices. Although assessments can be imprecise, since subjective criteria are involved, the classical pairwise comparisons theory expects all of them to be available. In practice, some experts may not be able (or available) to provide all assessments. Therefore managing null entries is a necessary extension of the pairwise comparisons method. It is shown that certain null entries can be recovered on the basis of the transitivity property which each pairwise comparisons matrix is expected to satisfy.