1,721,008 research outputs found
Conflict vs Causality in Event Structures
No full textEvent structures are one of the best known models for concurrency. Many variants of the basic model and many possible notions of equivalence for them have been devised in the literature. In this paper, we study how the spectrum of equivalences for Labelled Prime Event Structures built by Van Glabbeek and Goltz changes if we consider two simplified notions of event structures: the first one is obtained by removing the causality relation (Coherence Spaces) and the second one by removing the conflict relation (Elementary Event Structures). As expected, in both cases the spectrum turns out to be simplified, since some notions of equivalence coincide in the simplified settings; actually, we prove that removing causality simplifies the spectrum considerably more than removing conflict. Furthermore, we also prove that the labeling of events and a property that we call finitariness strongly influence the spectrum of equivalences in the conflict-free setting, whereas they have no impact on the causality-free spectrum
Inefficiencies in network models: a graph-theoretic perspective
No full textWe consider three network models where information items flow from a source to a sink node: flow networks, depletable channels, and traffic networks. We start with the standard model of flow networks; we characterise graph topologies that admit non-maximum saturating flows, under some capacity-to-edge assignment. We then consider a model where routing is constrained by energy available on nodes in finite supply (like in Smartdust) and efficiency is related to energy consumption and again to maximality of saturating flows. Finally, we consider a traffic model for selfish routing, where efficiency is related to latency at a Wardrop equilibrium. We show that all these forms of inefficiency yield different classes of graphs (apart from in the acyclic case, where the first and the last forms generate the same class). Interestingly, in all cases inefficient graphs can be made efficient by removing edges; this resembles a well-known phenomenon, called Braess's paradox
Enhanced models for privacy and utility in continuous-time diffusion networks
No full textControlling the propagation of information in social networks is a problem of growing importance. On one hand, users wish to freely communicate and interact with their peers. On the other hand, the information they spread can bring to harmful consequences if it falls in the wrong hands. There is therefore a trade-off between utility, i.e. reaching as many intended nodes as possible, and privacy, i.e. avoiding the unintended ones. The problem has attracted the interest of the research community: some models have already been proposed to study how information propagates and to devise policies satisfying the intended privacy and utility requirements. In this paper, we adapt the basic framework of Backes et al. to include more realistic features, that in practice influence the way in which information is passed around. More specifically, we consider: (a) the topic of the shared information, (b) the time spent by users to forward information among them and (c) the user social behaviour. For all features, we show a way to reduce our model to the basic one, thus allowing the methods provided in the original paper to cope with our enhanced scenarios. Furthermore, we propose an enhanced formulation of the utility/privacy policies, to maximize the expected number of reached users among the intended ones, while minimizing this number among the unintended ones, and we show how to adapt the basic techniques to these enhanced policies. We conclude by giving a new approach to the maximization/minimization problem by finding a trade-off between the risk and the gain function through biobjective optimization
Approximate model counting, sparse XOR constraints and minimum distance
Full text linkThe problem of counting the number of models of a given Boolean formula has numerous applications, including computing the leakage of deterministic programs in Quantitative Information Flow. Model counting is a hard, #P-complete problem. For this reason, many approximate counters have been developed in the last decade, offering formal guarantees of confidence and accuracy. A popular approach is based on the idea of using random XOR constraints to, roughly, successively halving the solution set until no model is left: this is checked by invocations to a SAT solver. The effectiveness of this procedure hinges on the ability of the SAT solver to deal with XOR constraints, which in turn crucially depends on the length of such constraints. We study to what extent one can employ sparse, hence short, constraints, keeping guarantees of correctness. We show that the resulting bounds are closely related to the geometry of the set of models, in particular to the minimum Hamming distance between models. We evaluate our theoretical results on a few concrete formulae. Based on our findings, we finally discuss possible directions for improvements of the current state of the art in approximate model counting
- …
