The paper concerns sampling from a data stream {$S_{i}$}: at a moment t the sampler should hold a value $S_{t-j}$, where j$\in${0,$\ldots$,n-1} should be chosen according to an a priori specified probability distribution D on {0,$\ldots$,n-1}, where D as well as the window size n are fixed and do not depend on t. We assume that the sampler has a constant size memory, while n might be large, so the sampler cannot remember the last n values of the stream except for a few. The problem is that the window of the last n elements changes at each step and when we have to resample, then almost all values from which we have to choose are already forgotten. The case of uniform distribution D has been considered by Braverman, Ostrovsky, and Zaniolo in 2013. We present an alternative generic approach based on specific Markov chains called devil’s staircases. Unlike the previous solution, it is not limited to the uniform distribution: it generates a sample according to any admissible distribution in the window of size n and uses memory of size $\mathrm{O}(1)$. We provide sufficient conditions for the distribution D to be admissible. Although the class of such distributions is quite wide from the point of view of practical applications, we show some natural limitations for this class.

We propose a new algorithm for the classical averaging problem for distributed wireless sensors networks. This subject has been studied extensively and there are many clever algorithms in the literature. These algorithms are based on the idea of local exchange of information. They behave well in dense networks (e.g., in networks whose connections form a complete graph), but their convergence to the real average is very slow in linear or cyclic graphs. Our solution is different. In order to calculate the average, we first build an approximate histogram of observed data; then, from this histogram, we estimate the average. In our solution, we use the extreme propagation technique and probabilistic counters. It allows us to find the approximation of the average of a set of measurements done by sensor network with arbitrary precision, controlled by two parameters. Our method requires O(D) rounds, where D is the diameter of the network. We study the message complexity of this algorithm and show that it is of order O(log n) for each node, where n is the size of the network.

We consider the problem of reliable and minimal delay transmission in a wireless sensor network that uses time division in order to schedule its node-to-node communication in time-bounded manner. We propose an algorithm that uses the message acknowledgment method and solves this problem. We show bounds for its expected value of message delivery time. Moreover, our algorithm is based on simple state machine that do not require much computational power, thus could be executed on very weak devices.

In this paper we study the efficiency of information flooding protocols in various communication networks, and in the presence of random faults. We show big differences between the flooding performance of networks with a seemingly similar structure. Since real-life systems usually consist of a moderate number of devices, the analysis presented in this paper is not limited to the asymptotic behavior of the flooding protocol. Instead, exact formulas are provided whenever possible. The presented results can be useful building blocks for the analysis of other, more sophisticated protocols. In particular, they may be used for planning and analyzing sensors network deployed in an environment subject to communication failures.

Efficient cardinality estimation is a common requirement for many wireless sensor network (WSN) applications. The task must be accomplished at extremely low overhead due to severe sensor resource limitation. This poses an interesting challenge for large-scale WSNs. In this paper we present a two-phase probabilistic algorithm based on order statistics and Bernoulli scheme, which effectively estimates the cardinality of WSNs. We thoroughly examine properties of estimators used in each phase as well as the precision of the whole procedure. The algorithm discussed in this paper is a modification of a recently published idea - the modification enables us to obtain a provable precision.

Flash memory are very popular storage device. Due to its shock resistance and power economy it is adopted in sensor networks and embedded systems. Recently more attention is paid to the data storage in flash memory. Data in flash memory should be distributed evenly among data blocks. If the number of writes in a data block is too high, it may cause damage of the block. Requirements for highly reliable storage systems include efficient algorithms to maximize its lifetime and tools to predict it or monitor system status. One way to achieve this goal is to embed a system of counters which could control block usage (especially erasing operations). Some solutions of this kind including necessary algorithms are patented. In this paper we propose a solution involving the use of approximate counting of the number of block modifications. Our solution essentially reduces the number of bits needed to memorize counters and also essentially reduces the number of changes of counters. Our results are are based on new theoretical results about the behavior of a collection of probabilistic counters.

We consider an ad-hoc network consisting of devices that try to gain access for transmission through a shared radio communication channel. We consider two randomized leader election protocols the first one is due to Nakanoand Olariu (2000); the second one is due to Cai, Lu and Wang (2003) and propose combinations which give us an improvement of both of them. We show that with discrete starting points of transmission, between which a station may choose in a non-uniform way, leads to a simple algorithm that substantially outperforms the previous techniques of resolving channel access problems. We provide methods to optimize values of parameters used.

Abstract We make a more systematic study of the van Douwen diagram for cardinal coefficients related to combinatorial properties of partitions of natural numbers.

Abstract By ℬ2 we denote the σ-ideal of all subsets A of the Cantor set {0, 1}ω such that for every infinite subset T of ω the restriction A∣{0, 1}T is a proper subset of {0, 1}T. In this paper we investigate set theoretical properties of this and similar ideals.

Abstract We discuss in the paper the following problem: Given a function in a given Baire class, into “how many” (in terms of cardinal numbers) functions of lower classes can it be decomposed? The decomposition is understood here in the sense of the set-theoretical union.

Abstract Let be any proper ideal of subsets of the real line R which contains all finite subsets of R. We define an ideal * ∣ as follows: X ∈ * ∣ if there exists a Borel set B ⊂ R × R such that X ⊂ B and for any x ∈ R we have {y ∈ R: 〈x, y〉 ∈ B} ∈ . We show that there exists a family ⊂ * ∣ of power ω1 such that ⋃ ∉ * ∣ . In the last section we investigate properties of ideals of Lebesgue measure zero sets and meager sets in Cohen extensions of models of set theory.

We say that the Boolean algebra B is λ-compact, where λ is a cardinal number, if for every family Z ⊆ B∖{0} of power at most λ, if inf Z = 0 then for some finite subfamily Z0 ⊆ Z we have inf Z0 = 0. On the set of all finite subsets of a cardinal number κ, which is denoted [κ]<ω, the sets of the form for any p Є [κ]<ω generate the filter Tκ. This filter is a standard example of a κ-regular filter (see [2]). Because of the importance of κ-regular filters in studying the saturatedness of ultraproducts and reduced products by model-theoretic methods, the question of compactness of the algebra Bκ = P([κ]<ω/Tκ was natural. This question in the most optimistical way was formulated by M. Benda [1, Problem 5c]: is the algebra Bκω-compact for every uncountable κ? In this paper we show that for most of the cardinal numbers which are greater or equal to 2ω the algebra Bκ is not ω-compact. Hence, in view of obtained results, the following question appears: does there exist an uncountable κ such that the algebra Bκ is κ-compact? We use standard set-theoretical notations. CH denotes the Continuum Hypothesis, GCH denotes the General Continuum Hypothesis and MA denotes Martin's Axiom.