OpenRaiser/Intern-Atlas huggingface dataset:
An architecture-based dependability modeling framework using AADL
Venue: arXiv cs.PF 2007
Year: 2007

For efficiency reasons, the software system designers' will is to use an integrated set of methods and tools to describe specifications and designs, and also to perform analyses such as dependability, schedulability and performance. AADL (Architecture Analysis and Design Language) has proved to be efficient for software architecture modeling. In addition, AADL was designed to accommodate several types of analyses. This paper presents an iterative dependency-driven approach for dependability modeling using AADL. It is illustrated on a small example. This approach is part of a complete framework that allows the generation of dependability analysis and evaluation models from AADL models to support the analysis of software and system architectures, in critical application domains.
Sensor Networks with Random Links: Topology Design for Distributed Consensus
Venue: arXiv cs.IT 2007
Year: 2007

In a sensor network, in practice, the communication among sensors is subject to:(1) errors or failures at random times; (3) costs; and(2) constraints since sensors and networks operate under scarce resources, such as power, data rate, or communication. The signal-to-noise ratio (SNR) is usually a main factor in determining the probability of error (or of communication failure) in a link. These probabilities are then a proxy for the SNR under which the links operate. The paper studies the problem of designing the topology, i.e., assigning the probabilities of reliable communication among sensors (or of link failures) to maximize the rate of convergence of average consensus, when the link communication costs are taken into account, and there is an overall communication budget constraint. To consider this problem, we address a number of preliminary issues: (1) model the network as a random topology; (2) establish necessary and sufficient conditions for mean square sense (mss) and almost sure (a.s.) convergence of average consensus when network links fail; and, in particular, (3) show that a necessary and sufficient condition for both mss and a.s. convergence is for the algebraic connectivity of the mean graph describing the network topology to be strictly positive. With these results, we formulate topology design, subject to random link failures and to a communication cost constraint, as a constrained convex optimization problem to which we apply semidefinite programming techniques. We show by an extensive numerical study that the optimal design improves significantly the convergence speed of the consensus algorithm and can achieve the asymptotic performance of a non-random network at a fraction of the communication cost.
Architecture for Pseudo Acausal Evolvable Embedded Systems
Venue: arXiv cs.NE 2007
Year: 2007

Advances in semiconductor technology are contributing to the increasing complexity in the design of embedded systems. Architectures with novel techniques such as evolvable nature and autonomous behavior have engrossed lot of attention. This paper demonstrates conceptually evolvable embedded systems can be characterized basing on acausal nature. It is noted that in acausal systems, future input needs to be known, here we make a mechanism such that the system predicts the future inputs and exhibits pseudo acausal nature. An embedded system that uses theoretical framework of acausality is proposed. Our method aims at a novel architecture that features the hardware evolability and autonomous behavior alongside pseudo acausality. Various aspects of this architecture are discussed in detail along with the limitations.
Novelty and Collective Attention
Venue: arXiv cs.CY 2007
Year: 2007

The subject of collective attention is central to an information age where millions of people are inundated with daily messages. It is thus of interest to understand how attention to novel items propagates and eventually fades among large populations. We have analyzed the dynamics of collective attention among one million users of an interactive website -- \texttt{digg.com} -- devoted to thousands of novel news stories. The observations can be described by a dynamical model characterized by a single novelty factor. Our measurements indicate that novelty within groups decays with a stretched-exponential law, suggesting the existence of a natural time scale over which attention fades.
Antenna Combining for the MIMO Downlink Channel
Venue: arXiv cs.IT 2007
Year: 2007

A multiple antenna downlink channel where limited channel feedback is available to the transmitter is considered. In a vector downlink channel (single antenna at each receiver), the transmit antenna array can be used to transmit separate data streams to multiple receivers only if the transmitter has very accurate channel knowledge, i.e., if there is high-rate channel feedback from each receiver. In this work it is shown that channel feedback requirements can be significantly reduced if each receiver has a small number of antennas and appropriately combines its antenna outputs. A combining method that minimizes channel quantization error at each receiver, and thereby minimizes multi-user interference, is proposed and analyzed. This technique is shown to outperform traditional techniques such as maximum-ratio combining because minimization of interference power is more critical than maximization of signal power in the multiple antenna downlink. Analysis is provided to quantify the feedback savings, and the technique is seen to work well with user selection and is also robust to receiver estimation error.
Low Density Lattice Codes
Venue: arXiv cs.IT 2007
Year: 2007

Low density lattice codes (LDLC) are novel lattice codes that can be decoded efficiently and approach the capacity of the additive white Gaussian noise (AWGN) channel. In LDLC a codeword x is generated directly at the n-dimensional Euclidean space as a linear transformation of a corresponding integer message vector b, i.e., x = Gb, where H, the inverse of G, is restricted to be sparse. The fact that H is sparse is utilized to develop a linear-time iterative decoding scheme which attains, as demonstrated by simulations, good error performance within ~0.5dB from capacity at block length of n = 100,000 symbols. The paper also discusses convergence results and implementation considerations.
A Language-Based Approach for Improving the Robustness of Network Application Protocol Implementations
Venue: arXiv cs.PL 2007
Year: 2007

The secure and robust functioning of a network relies on the defect-free implementation of network applications. As network protocols have become increasingly complex, however, hand-writing network message processing code has become increasingly error-prone. In this paper, we present a domain-specific language, Zebu, for describing protocol message formats and related processing constraints. From a Zebu specification, a compiler automatically generates stubs to be used by an application to parse network messages. Zebu is easy to use, as it builds on notations used in RFCs to describe protocol grammars. Zebu is also efficient, as the memory usage is tailored to application needs and message fragments can be specified to be processed on demand. Finally, Zebu-based applications are robust, as the Zebu compiler automatically checks specification consistency and generates parsing stubs that include validation of the message structure. Using a mutation analysis in the context of SIP and RTSP, we show that Zebu significantly improves application robustness.
Personalizing Image Search Results on Flickr
Venue: arXiv cs.IR 2007
Year: 2007

The social media site Flickr allows users to upload their photos, annotate them with tags, submit them to groups, and also to form social networks by adding other users as contacts. Flickr offers multiple ways of browsing or searching it. One option is tag search, which returns all images tagged with a specific keyword. If the keyword is ambiguous, e.g., ``beetle'' could mean an insect or a car, tag search results will include many images that are not relevant to the sense the user had in mind when executing the query. We claim that users express their photography interests through the metadata they add in the form of contacts and image annotations. We show how to exploit this metadata to personalize search results for the user, thereby improving search performance. First, we show that we can significantly improve search precision by filtering tag search results by user's contacts or a larger social network that includes those contact's contacts. Secondly, we describe a probabilistic model that takes advantage of tag information to discover latent topics contained in the search results. The users' interests can similarly be described by the tags they used for annotating their images. The latent topics found by the model are then used to personalize search results by finding images on topics that are of interest to the user.
Fairness Provision in the IEEE 802.11e Infrastructure Basic Service Set
Venue: arXiv cs.OH 2007
Year: 2007

Most of the deployed IEEE 802.11e Wireless Local Area Networks (WLANs) use infrastructure Basic Service Set (BSS) in which an Access Point (AP) serves as a gateway between wired and wireless domains. We present the unfairness problem between the uplink and the downlink flows of any Access Category (AC) in the 802.11e Enhanced Distributed Channel Access (EDCA) when the default settings of the EDCA parameters are used. We propose a simple analytical model to calculate the EDCA parameter settings that achieve weighted fair resource allocation for all uplink and downlink flows. We also propose a simple model-assisted measurement-based dynamic EDCA parameter adaptation algorithm. Moreover, our dynamic solution addresses the differences in the transport layer and the Medium Access Control (MAC) layer interactions of User Datagram Protocol (UDP) and Transmission Control Protocol (TCP). We show that proposed Contention Window (CW) and Transmit Opportunity (TXOP) limit adaptation at the AP provides fair UDP and TCP access between uplink and downlink flows of the same AC while preserving prioritization among ACs.
The Wiretap Channel with Feedback: Encryption over the Channel
Venue: arXiv cs.IT 2007
Year: 2007

In this work, the critical role of noisy feedback in enhancing the secrecy capacity of the wiretap channel is established. Unlike previous works, where a noiseless public discussion channel is used for feedback, the feed-forward and feedback signals share the same noisy channel in the present model. Quite interestingly, this noisy feedback model is shown to be more advantageous in the current setting. More specifically, the discrete memoryless modulo-additive channel with a full-duplex destination node is considered first, and it is shown that the judicious use of feedback increases the perfect secrecy capacity to the capacity of the source-destination channel in the absence of the wiretapper. In the achievability scheme, the feedback signal corresponds to a private key, known only to the destination. In the half-duplex scheme, a novel feedback technique that always achieves a positive perfect secrecy rate (even when the source-wiretapper channel is less noisy than the source-destination channel) is proposed. These results hinge on the modulo-additive property of the channel, which is exploited by the destination to perform encryption over the channel without revealing its key to the source. Finally, this scheme is extended to the continuous real valued modulo-$Λ$ channel where it is shown that the perfect secrecy capacity with feedback is also equal to the capacity in the absence of the wiretapper.
Using Image Attributes for Human Identification Protocols
Venue: arXiv cs.CR 2007
Year: 2007

A secure human identification protocol aims at authenticating human users to a remote server when even the users' inputs are not hidden from an adversary. Recently, the authors proposed a human identification protocol in the RSA Conference 2007, which is loosely based on the ability of humans to efficiently process an image. The advantage being that an automated adversary is not effective in attacking the protocol without human assistance. This paper extends that work by trying to solve some of the open problems. First, we analyze the complexity of defeating the proposed protocols by quantifying the workload of a human adversary. Secondly, we propose a new construction based on textual CAPTCHAs (Reverse Turing Tests) in order to make the generation of automated challenges easier. We also present a brief experiment involving real human users to find out the number of possible attributes in a given image and give some guidelines for the selection of challenge questions based on the results. Finally, we analyze the previously proposed protocol in detail for the relationship between the secrets. Our results show that we can construct human identification protocols based on image evaluation with reasonably ``quantified'' security guarantees based on our model.
Bounded Pushdown dimension vs Lempel Ziv information density
Venue: arXiv cs.CC 2007
Year: 2007

In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a BPD automata, i.e. a finite state machine equipped with an extra infinite memory stack, with the additional requirement that every input symbol only allows a bounded number of stack movements. BPD automata are a natural real-time restriction of pushdown automata. We show that BPD dimension is a robust notion by giving an equivalent characterization of BPD dimension in terms of BPD compressors. We then study the relationships between BPD compression, and the standard Lempel-Ziv (LZ) compression algorithm, and show that in contrast to the finite-state compressor case, LZ is not universal for bounded pushdown compressors in a strong sense: we construct a sequence that LZ fails to compress signicantly, but that is compressed by at least a factor 2 by a BPD compressor. As a corollary we obtain a strong separation between finite-state and BPD dimension.
Algebraic Distributed Space-Time Codes with Low ML Decoding Complexity
Venue: arXiv cs.IT 2007
Year: 2007

"Extended Clifford algebras" are introduced as a means to obtain low ML decoding complexity space-time block codes. Using left regular matrix representations of two specific classes of extended Clifford algebras, two systematic algebraic constructions of full diversity Distributed Space-Time Codes (DSTCs) are provided for any power of two number of relays. The left regular matrix representation has been shown to naturally result in space-time codes meeting the additional constraints required for DSTCs. The DSTCs so constructed have the salient feature of reduced Maximum Likelihood (ML) decoding complexity. In particular, the ML decoding of these codes can be performed by applying the lattice decoder algorithm on a lattice of four times lesser dimension than what is required in general. Moreover these codes have a uniform distribution of power among the relays and in time, thus leading to a low Peak to Average Power Ratio at the relays.
Existence Proofs of Some EXIT Like Functions
Venue: arXiv cs.IT 2007
Year: 2007

The Extended BP (EBP) Generalized EXIT (GEXIT) function introduced in \cite{MMRU05} plays a fundamental role in the asymptotic analysis of sparse graph codes. For transmission over the binary erasure channel (BEC) the analytic properties of the EBP GEXIT function are relatively simple and well understood. The general case is much harder and even the existence of the curve is not known in general. We introduce some tools from non-linear analysis which can be useful to prove the existence of EXIT like curves in some cases. The main tool is the Krasnoselskii-Rabinowitz (KR) bifurcation theorem.
Random Access Broadcast: Stability and Throughput Analysis
Venue: arXiv cs.IT 2007
Year: 2007

A wireless network in which packets are broadcast to a group of receivers through use of a random access protocol is considered in this work. The relation to previous work on networks of interacting queues is discussed and subsequently, the stability and throughput regions of the system are analyzed and presented. A simple network of two source nodes and two destination nodes is considered first. The broadcast service process is analyzed assuming a channel that allows for packet capture and multipacket reception. In this small network, the stability and throughput regions are observed to coincide. The same problem for a network with N sources and M destinations is considered next. The channel model is simplified in that multipacket reception is no longer permitted. Bounds on the stability region are developed using the concept of stability rank and the throughput region of the system is compared to the bounds. Our results show that as the number of destination nodes increases, the stability and throughput regions diminish. Additionally, a previous conjecture that the stability and throughput regions coincide for a network of arbitrarily many sources is supported for a broadcast scenario by the results presented in this work.
Nature-Inspired Interconnects for Self-Assembled Large-Scale Network-on-Chip Designs
Venue: arXiv cs.AR 2007
Year: 2007

Future nano-scale electronics built up from an Avogadro number of components needs efficient, highly scalable, and robust means of communication in order to be competitive with traditional silicon approaches. In recent years, the Networks-on-Chip (NoC) paradigm emerged as a promising solution to interconnect challenges in silicon-based electronics. Current NoC architectures are either highly regular or fully customized, both of which represent implausible assumptions for emerging bottom-up self-assembled molecular electronics that are generally assumed to have a high degree of irregularity and imperfection. Here, we pragmatically and experimentally investigate important design trade-offs and properties of an irregular, abstract, yet physically plausible 3D small-world interconnect fabric that is inspired by modern network-on-chip paradigms. We vary the framework's key parameters, such as the connectivity, the number of switch nodes, the distribution of long- versus short-range connections, and measure the network's relevant communication characteristics. We further explore the robustness against link failures and the ability and efficiency to solve a simple toy problem, the synchronization task. The results confirm that (1) computation in irregular assemblies is a promising and disruptive computing paradigm for self-assembled nano-scale electronics and (2) that 3D small-world interconnect fabrics with a power-law decaying distribution of shortcut lengths are physically plausible and have major advantages over local 2D and 3D regular topologies.
Characterization of P2P IPTV Traffic: Scaling Analysis
Venue: arXiv cs.NI 2007
Year: 2007

P2P IPTV applications arise on the Internet and will be massively used in the future. It is expected that P2P IPTV will contribute to increase the overall Internet traffic. In this context, it is important to measure the impact of P2P IPTV on the networks and to characterize this traffic. Dur- ing the 2006 FIFA World Cup, we performed an extensive measurement campaign. We measured network traffic generated by broadcasting soc- cer games by the most popular P2P IPTV applications, namely PPLive, PPStream, SOPCast and TVAnts. From the collected data, we charac- terized the P2P IPTV traffic structure at different time scales by using wavelet based transform method. To the best of our knowledge, this is the first work, which presents a complete multiscale analysis of the P2P IPTV traffic. Our results show that the scaling properties of the TCP traffic present periodic behavior whereas the UDP traffic is stationary and lead to long- range depedency characteristics. For all the applications, the download traffic has different characteristics than the upload traffic. The signaling traffic has a significant impact on the download traffic but it has negligible impact on the upload. Both sides of the traffic and its granularity has to be taken into account to design accurate P2P IPTV traffic models.
2D Path Solutions from a Single Layer Excitable CNN Model
Venue: arXiv cs.RO 2007
Year: 2007

An easily implementable path solution algorithm for 2D spatial problems, based on excitable/programmable characteristics of a specific cellular nonlinear network (CNN) model is presented and numerically investigated. The network is a single layer bioinspired model which was also implemented in CMOS technology. It exhibits excitable characteristics with regionally bistable cells. The related response realizes propagations of trigger autowaves, where the excitable mode can be globally preset and reset. It is shown that, obstacle distributions in 2D space can also be directly mapped onto the coupled cell array in the network. Combining these two features, the network model can serve as the main block in a 2D path computing processor. The related algorithm and configurations are numerically experimented with circuit level parameters and performance estimations are also presented. The simplicity of the model also allows alternative technology and device level implementation, which may become critical in autonomous processor design of related micro or nanoscale robotic applications.
Vocabulary growth in collaborative tagging systems
Venue: arXiv cs.IR 2007
Year: 2007

We analyze a large-scale snapshot of del.icio.us and investigate how the number of different tags in the system grows as a function of a suitably defined notion of time. We study the temporal evolution of the global vocabulary size, i.e. the number of distinct tags in the entire system, as well as the evolution of local vocabularies, that is the growth of the number of distinct tags used in the context of a given resource or user. In both cases, we find power-law behaviors with exponents smaller than one. Surprisingly, the observed growth behaviors are remarkably regular throughout the entire history of the system and across very different resources being bookmarked. Similar sub-linear laws of growth have been observed in written text, and this qualitative universality calls for an explanation and points in the direction of non-trivial cognitive processes in the complex interaction patterns characterizing collaborative tagging.