this article presents additional necessary measures that enable us to use Pict as an object-capability programing language. It is desirable to be able to assess the worst possible threat that we-users-risk if we run a...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
this article presents additional necessary measures that enable us to use Pict as an object-capability programing language. It is desirable to be able to assess the worst possible threat that we-users-risk if we run a given program. If we know the threat, we are able to decide whether or not we are willing to risk running the program. the cost of a security audit that reveals such an assessment will be non-zero but it need not to be directly dependent on the size of the whole original program. It is possible to write programs in such a way that this analysis can be reliably performed on a fraction of the original program-on the trusted computing base. this technique does not always give the most accurate assessment but it gives sound and interesting assessment relatively cheaply. It does not prevent usage of other techniques that can further refine the initial assessment.
In various Internet applications, reputation systems are typical means to collect experiences users make with each other. We present a reputation system that balances the security and privacy requirements of all users...
详细信息
ISBN:
(纸本)9783642183805
In various Internet applications, reputation systems are typical means to collect experiences users make with each other. We present a reputation system that balances the security and privacy requirements of all users involed. Our system provides privacy in the form of information theoretic relationship anonymity w.r.t. users and the reputation provider. Furthermore, it preserves liveliness, i.e., all past ratings can influence the current reputation profile of a user. In addition, mutual ratings are forced to be simultaneous and self rating is prevented, which enforces fairness. What is more, without performing mock interactions-even if all users are colluding-users cannot forge ratings. As far as we know, this is the first protocol proposed that fulfills all these properties simultaneously.
We design a formal model of an amorphous computer suitable for theoretical investigation of its computational properties. the model consists of a finite set of nodes created by RAMs with restricted memory, which are d...
详细信息
ISBN:
(纸本)9783540695066
We design a formal model of an amorphous computer suitable for theoretical investigation of its computational properties. the model consists of a finite set of nodes created by RAMs with restricted memory, which are dispersed uniformly in a given area. Within a limited radius the nodes can communicate withtheir neighbors via a single-channel radio. the assumptions on low-level communication abilities are among the weakest possible: the nodes work asynchronously, there is no broadcasting collision detection mechanism and no network addresses. For the underlying network we design a randomized communication protocol and analyze its efficiency. the subsequent experiments and combinatorial analysis of random networks show that the expectations under which our protocol was designed are met by the vast majority of the instances of our amorphous computer model.
this paper expands upon existing and introduces new formulations of Bennett's logical depth. A new notion based on pushdown compressors is developed. A pushdown deep sequence is constructed. the separation of (pre...
详细信息
ISBN:
(纸本)9783030389192;9783030389185
this paper expands upon existing and introduces new formulations of Bennett's logical depth. A new notion based on pushdown compressors is developed. A pushdown deep sequence is constructed. the separation of (previously published) finite-state based and pushdown based depth is shown. the previously published finite state depth notion is extended to an almost everywhere (a.e.) version. An a.e. finite-state deep sequence is shown to exist along with a sequence that is infinitely often (i.o.) but not a.e. finite-state deep. For both finite-state and pushdown, easy and random sequences with respect to each notion are shown to be non-deep, and that a slow growth law holds for pushdown depth.
From 2007 to 2010, researchers from Microsoft and the Verisoft XT project verified code from Hyper-V, a multi-core x-64 hypervisor, using VCC, a verifier for concurrent C code. However, there is a significant gap betw...
详细信息
ISBN:
(纸本)9783642358432
From 2007 to 2010, researchers from Microsoft and the Verisoft XT project verified code from Hyper-V, a multi-core x-64 hypervisor, using VCC, a verifier for concurrent C code. However, there is a significant gap between code verification of a kernel (such as a hypervisor) and a proof of correctness of a real system running the code. When the project ended in 2010, crucial and tricky portions of the hypervisor product were formally verified, but one was far from having an overall theory of multi core hypervisor correctness even on paper. For example, the kernel code itself has to set up low-level facilities such as its call stack and virtual memory map, and must continue to use memory in a way that justifies the memory model assumed by the compiler and verifier, even though these assumptions are not directly guaranteed by the hardware. Over the last two years, much of the needed theory justifying the approach has been worked out. We survey progress on this theory and identify the work that is left to be done.
An important role of a workflow system is to schedule and reschedule the workflow process and to allow the user to monitor and guide the overall progress of the workflow and its activities. this paper presents extensi...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
An important role of a workflow system is to schedule and reschedule the workflow process and to allow the user to monitor and guide the overall progress of the workflow and its activities. this paper presents extensions of a rescheduling algorithm based on minimal graph cut. the initial approach allowed to find an optimal rescheduling, which changed the initial schedule by shortening and moving of activities. the new schedule had the lowest overall price, counted as the sum of prices of shortening activities. the extension presented in this paper allows several extensions, while keeping the optimality: handling several delayed activities, handling the price of moving an activity and handling the price of deadline violation. the rescheduling algorithm is used within an ontology-based workflow management system for the process of military exercise preparation in Centre of simulation technologies National Academy of Defence.
Real-scale Semantic Web applications, such as Knowledge Portals and E-Marketplaces, require the management of voluminous repositories of resource metadata. At the same time, personalized access and content syndication...
详细信息
ISBN:
(纸本)3540207791
Real-scale Semantic Web applications, such as Knowledge Portals and E-Marketplaces, require the management of voluminous repositories of resource metadata. At the same time, personalized access and content syndication involving diverse conceptual representations of information resources are key challenges for such applications. the Resource Description Framework (RDF) enables the creation and exchange of metadata as any other Web data and constitutes nowadays the core language for creating and exchanging resource descriptions worldwide. Although large volumes of RDF descriptions are already appearing, sufficiently expressive declarative query languages for RDF and full-fledged view definition languages are still missing.
We consider the problem of matching reconfiguration, where we are given two matchings M-s and M-t in a graph G and the goal is to determine if there exists a sequence of matchings M-0, M-1,..., M-l, such that M-0 = M-...
详细信息
ISBN:
(数字)9783030108014
ISBN:
(纸本)9783030108014;9783030108007
We consider the problem of matching reconfiguration, where we are given two matchings M-s and M-t in a graph G and the goal is to determine if there exists a sequence of matchings M-0, M-1,..., M-l, such that M-0 = M-s, all consecutive matchings differ by exactly two edges (specifically, any matching is obtained from the previous one by the addition and deletion of one edge), and M-l = M-t. It is known that the existence of such a sequence can be determined in polynomial time [5]. We extend the study of reconfiguring matchings to account for the length of the reconfiguration sequence. We show that checking if we can reconfigure M-s to M-t in at most l steps is NP-hard, even when the graph is unweighted, bipartite, and the maximum degree is four, and the matchings M-s and M-t are maximum matchings. We propose two simple algorithmic approaches, one of which improves on the brute-force running time while the other is a SAT formulation that we expect will be useful in practice.
the value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
the value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational strategies that achieve the reachability objective with probability arbitrarily close to 1? this problem was shown undecidable recently. Our contribution is to introduce a class of partially observable Markov decision processes, namely #-acyclic partially observable Markov decision processes, for which the value 1 problem is decidable. Our algorithm is based on the construction of a two-player perfect information game, called the knowledge game, abstracting the behaviour of a #-acyclic partially observable Markov decision process M such that the first player has a winning strategy in the knowledge game if and only if the value of M is 1.
Incidents like the crash of Lion Air Flight 610 in 2018 challenge the design of reliable and secure cyber-physical systems that operate in the real-world and have to cope with unpredictable external phenomena and erro...
详细信息
ISBN:
(纸本)9783030677305;9783030677312
Incidents like the crash of Lion Air Flight 610 in 2018 challenge the design of reliable and secure cyber-physical systems that operate in the real-world and have to cope with unpredictable external phenomena and error-prone technology. We argue that their design needs to guarantee minimal machine consciousness, which expresses that these systems must operate with full awareness of (the state of) their components and the environment. the concept emerged from our recent effort to develop a computational model for conscious behavior in robots, based on the theory of automata. Making systems `minimal machine conscious' leads to more trustworthy systems, as it strengthens their behavioral flexibility in varying environments and their resilience to operation and cooperation failures of their components and as a whole. the notion of minimal machine consciousness has the potential to become one of the defining attributes of Industry 4.0.
暂无评论