2011 Technical Reports

Department of Computing and Information Sciences
Kansas State University

Report 2011-2 Mutual Exclusion in Cyber-Physical Systems by Sumeet Gujrati and Gurdip Singh
Abstract: Cyber-physical system wherein both the cyber and the physical subsystems cooperate to accomplish tasks are becoming more prevalent. Distributed computing problems such as mutual exclusion have been studied extensively for traditional distributed systems. In traditional systems, a strict layered approach is taken wherein a set of users (application processes) U1,...,Un is layered on top of a mutual exclusion algorithm with processes P1,...,Pn. User Ui interacts with Pi to request access to resources, and users rely entirely on the cyber infrastructure to regulate access to the resources. In a cyber-physical system, the physical entities (users) may themselves possess capabilities such as sensing, observing and mobility using which they may also attempt to locate resources. Thus, a mutual exclusion algorithm in a cyber-physical system must be defined as a combination of a cyber algorithm and the behavior of physical entities. In this paper, we propose a graph-based model for cyber-physical systems which can be used to describe cyber algorithms as well as physical entity behavior. Based on this model, we present several solutions for the mutual exclusion problem. We have also developed a system on top of OMNeT++ to simulate cyber-physical algorithms. We present extensive study of our algorithms using this system.

Report 2011-1. Censorship resistant overlay publishing by Eugene Y. Vasserman, Victor Heorhiadi, Yongdae Kim, and Nicholas Hopper
Abstract: The fundamental requirement of censorship resistance is content availability and discoverability‚--- it should be easy for users to find and access documents. At the same time, participating storage providers should be unaware of what they are storing to preserve plausible deniability. Fulfilling these requirements simultaneously seems impossible‚--- how does a system maintain a searchable index of content for users and yet hide it from storage providers? These paradoxical requirements have been previously reconciled by requiring out-of-band communication to either find ways to connect to the system, locate files, or learn file decryption keys ‚--- an unacceptable situation when easy content discovery is critical. This paper describes a design for a peer-to-peer, permanent, and unblockable content store which is easily searchable and yet self-contained, i.e. does not require out-of-band communication. To achieve this, we separate file data, metadata, and encryption keys such that someone searching for information about a specific topic can retrieve all three components and reconstruct the file, but someone who only stores at most two components can neither determine the nature of the file content nor locate the missing component. We begin by identifying the core requirements for unblockable storage systems to resist state-level Internet censorship, construct a system that fulfills those requirements, and analyze how it avoids the problem of prior attempts at censorship resistance. Finally, we present measurements of a deployed proof-of-concept implementation, demonstrating the feasibility of our design.