| CS-2012-01 | ||||
|---|---|---|---|---|
| Title | "Looks cool, I'll try this later!": Understanding the Faces and Uses of Online Tutorials | |||
| Authors | Ben Lafreniere, Andrea Bunt, Matthew Lount and Michael Terry | |||
| Abstract | Despite their prevalence, little is known about how users make use of web tutorials or feature-rich applications, and why authors take the time to create them. In this paper, we analyze comments posted to web tutorials to understand the purposes that tutorials serve for users, and examine the tutorials themselves to understand their structure and authors' motivations to create them. Our results indicate that users come to tutorials for help performing techniques with applications, and to achieve complex end results beyond their current expertise. As for tutorial authors, we found that most tutorials had clear extrinsic reasons for existing, including earning ad or referral revenue, promoting premium products or services, or acting as portfolios for their authors. Based on these results, we suggest a number of improvements to current tutorial interfaces. | |||
| Date | January 5, 2012 | |||
| Report | "Looks cool, I'll try this later!": Understanding the Faces and Uses of Online Tutorials (PDF) | |||
| CS-2012-02 | ||||
|---|---|---|---|---|
| Title | A Web-based Framework for Collaborative Innovation | |||
| Authors | Donald Cowan, Paulo Alencar, Fred McGarry and Carlos Lucena | |||
| Abstract |
Twenty-first century global change in most sectors is challenging us and our communities in the management and use of resources. The World Economic Forum has recognized the need for new approaches to enable collective action among both the leadership and concerned members of communities. We call this approach of working together to produce societal solutions collaborative innovation (CI). CI is part of web science as it brings together information networks of people and communities who use and augment the digital records related to common problems mediated by the web. This paper outlines an approach to CI based on dynamic asset-mapping and how it has been supported through a web-based framework that requires both communication and operations on a knowledge base or asset map. Based on the experience using the framework in designing and deploying over 70 systems that incorporate dynamic asset-mapping as a foundation for CI, it is clear that CI takes many forms. We illustrate some of these forms through specific examples in environment, socio-economic development and planning. We conclude that it is not possible to build a single set of tools to support CI and that the users need access to meta-tools and frameworks to implement tailored systems supporting CI directly rather than relying on people with in-depth knowledge of the technologies. We then outline some of the properties of a set of software meta-tools that have been be used to implement these systems. | |||
| Date | February 07, 2012 | |||
| Report | A Web-based Framework for Collaborative Innovation (PDF) | |||
| CS-2012-03 | ||||
|---|---|---|---|---|
| Title | A Study on Justifications for Choices: Explanation Patterns and Guidelines | |||
| Authors | Ingrid Oliveira de Nunes, Simon Miles, Michael Luck and Carlos José Pereira de Lucena | |||
| Abstract | Many different forms of explanation have been proposed for justifying decisions made by automated systems. However, there is no consensus on what constitutes a good explanation, or what information these explanations should include. In this paper, we present the results of a study into how people justify their decisions. Analysis of our results allowed us to extract the forms of explanation adopted by users to justify choices, and the situations in which these forms are used. The analysis led to the development of guidelines and patterns for explanations to be generated by automated decision systems. This paper presents the study, its results, and the guidelines and patterns we derived. | |||
| Date | February 16, 2012 | |||
| Report | A Study on Justifications for Choices: Explanation Patterns and Guidelines (PDF) | |||
| CS-2012-04 | ||||
|---|---|---|---|---|
| Title | Assertion Absorption in Object Queries over Knowledge Bases | |||
| Authors | Jiewen Wu, Alexander Hudek, David Toman and Grant Weddell | |||
| Abstract |
We present a novel optimization of evaluating object queries, especially instance queries, over description logic knowledge bases. The method is designed to perform well for large ABoxes and expressive TBoxes, e.g., where background knowledge requires the use of disjunction and negation. The method significantly improves the performance of answering object queries, and particularly so in cases where a large number of concrete feature values are included. We also report on the results of an experimental evaluation that validates the efficacy of the optimazation. | |||
| Date | August 21, 2012 | |||
| Report | Assertion Absorption in Object Queries over Knowledge Bases (PDF) | |||
| CS-2012-05 | ||||
|---|---|---|---|---|
| Title | A Feature-Oriented Requirements Modelling Language | |||
| Authors | Pourya Shaker and Joanne M. Atlee | |||
| Abstract | In this report, we present FORML, a language for modelling the requirements of features in a software product line. FORML aims to support feature modularity and precise requirements modelling, and to ease the task of adding new features to a set of existing requirements. In particular, FORML decomposes a product line’s requirements into feature modules, and provides language support for specifying tightly-coupled features as model fragments that extend and override existing feature modules. We discuss how decisions in the design of FORML affect the succinctness of feature modules, the evolvability of requirements models, and the specification of intended interactions among related features. We applied FORML to the specification of a set of telephony features, the models of which are included in the report. | |||
| Date | March 9, 2012 | |||
| Report | A Feature-Oriented Requirements Modelling Language (PDF) | |||
| CS-2012-06 | ||||
|---|---|---|---|---|
| Title | A Framework for Adaptive Workflow (Model Human Behaviour - Don’t Constrain It!) | |||
| Authors | H. Dominic Covvey, Donald D. Cowan, Paulo Alencar, William Malyk, Joel So, D. Henriques and Shirley L. Fenton | |||
| Abstract | Healthcare processes are complex and highly variable from day to day. Healthcare process execution can be affected by any participant in a process, including clinicians, the patient, and the patient’s family, as well as by environmental factors such as clinician, staff, facility and equipment availability, and patient clinical status. However, there are no solutions that enable computer support for a process to address the full complexity and variability of healthcare processes. We have re-conceptualized workflow and developed an innovative process representation and execution framework based on concepts from software engineering, machine learning, complexity, and database management. This new framework frees processes to track human behaviour, thereby releasing us from the constraints of past methods. | |||
| Date | March 28, 2012 | |||
| Report | A Framework for Adaptive Workflow (Model Human Behaviour - Don’t Constrain It!) (PDF) | |||
| CS-2012-07 | ||||
|---|---|---|---|---|
| Title | Pathwidth and small-height drawings of 2-connected outer-planar graphs | |||
| Authors | Therese Biedl | |||
| Abstract | In this paper, we study planar drawings of 2-connected outer-planar graphs. In an earlier paper we showed that every such graph has a visibility representation with height O(log n). In this paper, we show that with a different construction, the height is 4pw(G)-3, where pw(G) denotes the pathwidth of graph G. Since for any planar graph G, any planar drawing has height >= pw(G), this is a 4-approximation algorithm for the height. We also show that our visibility representations can be converted into straight-line drawings of the same height. | |||
| Date | April 17, 2012 | |||
| Report | Pathwidth and small-height drawings of 2-connected outer-planar graphs (PDF) | |||
| CS-2012-08 | ||||
|---|---|---|---|---|
| Title | On the Impact of Storage in Residential Power Distribution Systems | |||
| Authors | Omid Ardakanian, Catherine Rosenberg, and S. Keshav | |||
| Abstract | It is anticipated that energy storage will be incorporated into the distribution network component of the future smart grid to allow desirable features such as distributed generation integration and reduction in the peak demand. There is, therefore, an urgent need to understand the impact of storage on distribution system planning. In this paper, we focus on the effect of storage on the loading of neighbourhood pole-top transformers. We apply a probabilistic sizing technique originally developed for sizing buffers and communication links in telecommunications networks to jointly size storage and transformers in the distribution network. This allows us to compute the potential gains from transformer upgrade deferral due to the addition of storage. We validate our results through numerical simulation using measurements of home load in a testbed of 20 homes and demonstrate that our guidelines allow local distribution companies to defer transformer upgrades without reducing reliability. | |||
| Date | May 2, 2012 | |||
| Report | On the Impact of Storage in Residential Power Distribution Systems (PDF) | |||
| CS-2012-09 | ||||
|---|---|---|---|---|
| Title | In Silico Spectral Investigation of Methemoglobin and Sulfhemoglobin Effects on Human Skin Reflectance | |||
| Authors | Gladimir V. G. Baranoski, Tenn F. Chen, BradleyW. Kimmel, Erik Miranda, and Daniel Yim | |||
| Abstract | There are several pathologies whose study and diagnosis is impaired by a relatively small number of documented cases. A practical approach to overcome this obstacle and advance the research in this area consists in employing computer simulations to perform controlled in silico experiments. The results of these experiment, in turn, may be incorporated in the design of differential protocols for these pathologies. Accordingly, in this paper, we investigate the spectral responses of human skin affected by the presence of abnormal amounts of two dysfunctional hemoglobins, methemoglobin and sulfhemoglobin, which are associated with two life-threatening medical conditions, methemoglobinemia and sulfhemoglobinemia respectively. We analyse the results of our in silico experiments, and discuss their potential applications to the development of more effective noninvasive differentiation and monitoring procedures for these medical conditions. | |||
| Date | June 4, 2012 | |||
| Report | In Silico Spectral Investigation of Methemoglobin and Sulfhemoglobin Effects on Human Skin Reflectance (PDF) | |||
| CS-2012-10 | ||||
|---|---|---|---|---|
| Title | A Qualitative Study of Mozilla's Process Management Practices | |||
| Authors | Olga Baysal and Reid Holmes | |||
| Abstract | The Mozilla Anthropology project was started in late 2011 to examine how various Mozilla community stakeholders make use of Bugzilla in practice and to gain a sense of how Bugzilla could be improved in the future to better support the community. In this report, we present the results of a qualitative study on the interview data of the community members on their engagement and experience with the Bugzilla bug tracking system. We performed an open card sort to gain insight into high-level themes about Bugzilla to identify strengths, weaknesses, and ideas for future enhancement of the platform. | |||
| Date | July 5, 2012 | |||
| Report | A Qualitative Study of Mozilla's Process Management Practices (PDF) | |||
| CS-2012-11 | ||||
|---|---|---|---|---|
| Title | Sharing of Fire Fighting Resources | |||
| Authors | Alan Tsang, Kate Larson, Rob McAlpine | |||
| Abstract |
The
Canadian
Interagency
Forest
Fire
Center
(CIFFC)
was
created
in
1982
with
the
primary
mandate
to
facilitate
the
exchange
of
wildland
fire
fighting
resources
including
personnel,
equipment
and
aircraft
between
member
agencies.
Since
its
establishment,
resource
sharing
across
agencies
has
increased
dramatically.
However,
there
has
been
a
growing
recognition
by
the
CIFFC
Council
of
Directors
and
the
Wildland
Fire
Management
Working
Group
that
the
current
levels
of
resource
sharing
will
not
be
adequate
for
future
activity.
There
have
been
several
incidents
in
the
recent
past
where
there
were
insufficient
resources
to
meet
the
national
demand,
and
trends
in
changing
climates,
fire
occurence
and
the
expansion
of
the
wildland-urban
interface
coupled
with
government
fiscal
trends
of
cost
containment
and
reduction
all
point
to
increased
resource
shortages.
There
is,
thus,
interest
in
investigating
new
solutions
to
the
problem. Although in Canada we have been sharing resources between agencies for more than 25 years, to the best of our knowledge, little is known about the strategic process that goes into the borrow/lend decision. When does an agency request resources is, perhaps, an easy question, but the more difficult, and perhaps more interesting, is "When and how do we lend?". Understanding the parameters that guide this decision among the lending agencies could provide a profound understanding of the nature of lending in the country and provide some guidance to mitigating barriers to resource sharing. To this end, we have commenced a study of the factors which influence decision-making with respect to resource sharing across Canada. By conducting interviews with agencies across the country as well as CIFFC, and by building a game-theoretic model to capture strategic aspects of resource-sharing, we aim to provide insights into resource-sharing across the country. | |||
| Date | July 16, 2012 | |||
| Report | Sharing of Fire Fighting Resources (PDF) | |||
| CS-2012-12 | |||||
|---|---|---|---|---|---|
| Title | Translating the Feature-Oriented Requirements Modelling Language to Alloy | ||||
| Authors | David Dietrich, Pourya Shaker, Jan Gorzny, Joanne Atlee and Derek Rayside | ||||
| Abstract | The Feature-Oriented Requirements Modelling Language (FORML) provides explicit support for modelling Software Product Lines and systems that are composed of features. However, a problem that developers must be aware of when developing feature oriented software are interactions between features. The purpose of this project is to provide a method for analyzing FORML models to detect interactions that may occur. To this end a translator has been created that will translate FORML models into Alloy models so that they can be analyzed to show a lack of unwanted interactions. This report discusses the implementation of this translator, gives several examples of how various structures in the FORML are translated and discusses the methods of analysis that have been implemented. A small evaluation is also performed to demonstrate how the translator can be used in practice. | ||||
| Date | August 24, 2012 | ||||
| Report | Translating the Feature-Oriented Requirements Modelling Language to Alloy (PDF) | ||||
| CS-2012-13 | ||||
|---|---|---|---|---|
| Title | Delay Differentiation without Rate Tinkering | |||
| Authors | Martin Karsten, Jens Schmitt, and Michael Beck | |||
| Abstract | Link buffering is a key element in packet-switched networks to absorb temporary traffic bursts without excessive dropping. The resulting queuing delay is a critical performance factor. Research on buffer management typically studies differentiated buffer allocation to control forwarding rates or buffer size management to control the overall queuing delay. On the other hand, delay differentiation is typically accomplished by packet scheduling and thus implies rate differentiation. In this paper a radically simpler approach to delay differentiation through buffer management is studied. Instead of actively managing throughput, Delay Differentiated FIFO (DDF) uses a simple drop-based mechanism to offer multiple delay classes, but closely tracks the per-class throughput of the corresponding single-class FIFO queuing system. End systems choose which delay class best balances their loss and delay requirements. Architecturally, DDF does not interfere with management and policy decisions at end and edge systems and does not add another control loop to the existing mix of traffic management techniques. The forwarding characteristics of DDF are analyzed using stochastic models. Refinements to the basic algorithm are presented and it is shown how DDF can be implemented with very little execution overhead compared to FIFO. Packet-level simulation results are presented to complement the analytical findings. | |||
| Date | August 23, 2012 | |||
| Report | Delay Differentiation without Rate Tinkering (PDF) | |||
| CS-2012-14 | ||||
|---|---|---|---|---|
| Title | On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighbourhoods | |||
| Authors | Reza Dorrigiv, Robert Fraser, Meng He, Shahin Kamali, Akitoshi Kawamura, Alejandro Lopez-Ortiz and Diego Seco | |||
| Abstract | We study optimization problems for the Euclidean minimum spanning tree (MST) on imprecise data. To model imprecision, we accept a set of disjoint disks in the plane as input. From each member of the set, one point must be selected, and the MST is computed over the set of selected points. We consider both minimizing and maximizing the weight of the MST over the input. The minimum weight version of the problem is known as the minimum spanning tree with neighbourhoods (MSTN) problem, and the maximum weight version (max-MSTN) has not been studied previously to our knowledge. We provide deterministic and parameterized approximation algorithms for the max-MSTN problem, and a parameterized algorithm for the MSTN problem. Additionally, we present hardness of approximation proofs for both settings. | |||
| Date | August 27, 2012 | |||
| Report | On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighbourhoods (PDF) | |||
| CS-2012-15 | ||||
|---|---|---|---|---|
| Title | Minimizing Cache Usage in Paging | |||
| Authors | Alejandro L´opez-Ortiz and Alejandro Salinger | |||
| Abstract | Traditional paging models seek algorithms that maximize their performance while using the maximum amount of cache resources available. However, in many applications this resource is shared or its usage involves a cost. In this work we introduce the Minimum Cache Usage problem, which is an extension to the classic paging problem that accounts for the efficient use of cache resources by paging algorithms. In this problem, the cost of a paging algorithm is a combination of both its number of faults and the amount of cache it uses, where the relative cost of faults and cache usage can vary with the application. We present a simple family of online paging algorithms that adapt to the ratio between cache and fault costs, achieving competitive ratios that vary with , and that are between 2 and the cache size k. Furthermore, for sequences with high locality of reference, we show that the competitive ratio is at most 2, and provide evidence of the competitiveness of our algorithms on real world traces. Finally, we show that the offline problem admits a polynomial time algorithm. In doing so, we define a reduction of paging with cache usage to weighted interval scheduling on identical machines. | |||
| Date | August 30, 2012 | |||
| Report | Minimizing Cache Usage in Paging (PDF) | |||
| CS-2012-16 | ||||
|---|---|---|---|---|
| Title | αRoute: A Name Based Routing Scheme for Information Centric Networks | |||
| Authors | Reaz Ahmed, Md. Faizul Bari, Shihabur Rahman Chowdhury, Md. Golam Rabbani, Raouf Boutaba and Bertrand Mathieu | |||
| Abstract | One of the crucial building blocks for Information Centric Networking (ICN) is a name based routing scheme that can route directly on content names instead of IP addresses. However, moving the address space from IP addresses to content names brings scalability issues to a whole new level, due to two reasons. First, name aggregation is not as trivial a task as the IP address aggregation in BGP routing. Second, the number of addressable contents in the Internet is several orders of magnitude higher than the number of IP addresses. With the current size of the Internet, name based, anycast routing is very challenging specially when routing efficiency is of prime importance. We propose a novel name-based routing scheme (αRoute) for ICN that offers efficient bandwidth usage, guaranteed content lookup and scalable routing table size. αRoute consists of two components: an alphanumeric Distributed Hash Table (DHT) and an overlay to underlay (Internet topology) mapping algorithm. Simulation results show that αRoute performs significantly better than Content Centric Network (CCN) [1] in terms of network bandwidth usage, lookup latency and load balancing. | |||
| Date | September 4, 2012 | |||
| Report | αRoute: A Name Based Routing Scheme for Information Centric Networks (PDF) | |||
| CS-2012-17 | ||||
|---|---|---|---|---|
| Title | DEWS: A Decentralized Engine for Web Search | |||
| Authors | Reaz Ahmed, Rakibul Haque, Md. Faizul Bari, Raouf Boutaba and Bertrand Mathieu | |||
| Abstract | The way we explore the web is largely governed by centrally controlled, clustered search engines, which is not healthy for our freedom in the Internet. A better solution is to enable the web to index itself in a decentralized manner. In this work we propose a decentralized web search mechanism, named DEWS, which will enable the existing webservers to collaborate with each other to form a distributed index of the web. DEWS can rank the search results based on query keyword relevance and relative importance of websites. DEWS also supports approximate matching of query keywords and incremental retrieval of search results in a decentralized manner. We use the standard LETOR 3.0 dataset to validate the DEWS protocol. Simulation results show that the ranking accuracy of DEWS is very close to the centralized case, while network overhead for collaborative search and indexing is logarithmic on network size. Simulation results also show that DEWS is resilient to changes in the available pool of indexing webservers and works efficiently even in presence of heavy query load. | |||
| Date | September 4, 2012 | |||
| Report | DEWS: A Decentralized Engine for Web Search (PDF) | |||
| CS-2012-18 | ||||
|---|---|---|---|---|
| Title | Persistence Service for Non-Persistent P2P Systems | |||
| Authors | Reaz Ahmed, Nashid Shahriar, Mahfuza Sharmin, Raouf Boutaba and Bertrand Mathieu | |||
| Abstract | Ensuring content persistence with minimal replication overhead is a prerequisite for providing any consistent service over a peer-to-peer (P2P) overlay. This paper introduces S-DATA, a bandwidth efficient protocol for achieving highly available P2P systems with minimal replication overhead. When considering a global P2P system, the cyclic behaviour of peers situated at different time zones can be found complementary of one another. In S-DATA, peers with complementary diurnal availability patterns collaborate in small replication groups and host each other’s content in turn to ensure 24/7 availability. In this work we present a mathematical model for measuring time-based availability with (β - 1) redundancy as a function of replication group size and peer uptime behaviour. We also simulate the S-DATA protocol in the PeerSim simulator and compare its performance against a few other time-based replication protocols. | |||
| Date | September 4, 2012 | |||
| Report | Persistence Service for Non-Persistent P2P Systems (PDF) | |||
| CS-2012-19 | ||||
|---|---|---|---|---|
| Title | EdgeCloud: A New Hybrid Platform for On-Demand Gaming | |||
| Authors | Sharon Choy, Bernard Wong, Gwendal Simon and Catherine Rosenberg | |||
| Abstract | Cloud computing has been a revolutionary force in changing the way organizations deploy web applications and services. However, many of cloud computing's core design tenets, such as consolidating resources into a small number of datacenters and fine-grain partitioning of general purpose computing resources, conflict with an emerging class of multimedia applications that is highly latency sensitive and requires specialized hardware, such as graphic processing units (GPUs) and fast memory. In this paper, we look closely at one such application, namely, on-demand gaming (also known as cloud gaming), that has the potential to radically change the multi-billion dollar video game industry. We demonstrate through a large-scale measurement study that the current cloud computing infrastructure is unable to meet the strict latency requirements necessary for acceptable game play for many end-users. In response to these results, we propose augmenting the existing cloud infrastructure with an EdgeCloud, consisting of end-hosts that are more geographically diverse than datacenters and also more likely to have specialized resources. We detail the challenges introduced by such a hybrid design and our solutions to these challenges, and demonstrate through a large-scale simulation that the addition of even a small number of end-hosts significantly reduces latency and improves client coverage for on-demand gaming. | |||
| Date | September 20, 2012 | |||
| Report | EdgeCloud: A New Hybrid Platform for On-Demand Gaming (PDF) | |||
| CS-2012-20 | ||||
|---|---|---|---|---|
| Title | On the Sublinear Processor Gap for Multi-Core Architectures | |||
| Authors | Alejandro Lopez-Ortiz and Alejandro Salinger | |||
| Abstract |
In the past, parallel algorithms were developed, for the most part, under the assumption that the number of processors is $\Theta(n)$ and that if in practice the actual number was smaller, this could be resolved using Brent's Lemma to simulate the highly parallel solution on a lower-degree parallel architecture. In this paper, however, we argue that design and implementation issues of algorithms and architectures are significantly different — both in theory and in practice — between computational models with high and low degrees of parallelism. We report an observed gap in the behaviour of a CMP/parallel architecture depending on the number of processors. This gap appears repeatedly in both empirical cases, when studying practical aspects of architecture design and program implementation as well as in theoretical instances when studying the behaviour of various parallel algorithms. It separates the performance, design and analysis of systems with a sublinear number of processors and systems with linearly many processors. More specifically we observe that systems with either logarithmically many cores or with $O(n^\alpha)$ cores (with $\alpha<1$) exhibit a qualitatively different behaviour than a system with a linear number of cores on the size of the input, i.e. $\Theta(n)$. The evidence we present suggests the existence of a sharp theoretical gap between the classes of problems that can be efficiently parallelized with $o(n)$ processors and with $\Theta(n)$ processors unless $NC=P$. | |||
| Date |
October 30, 2012 | |||
| Report | On the Sublinear Processor Gap for Multi-Core Architectures (PDF) | |||
| CS-2012-21 | ||||
|---|---|---|---|---|
| Title | Algorithms in the Ultra-Wide Word Model | |||
| Authors | Arash Farzan, Alejandro Lopez-Ortiz, Patrick K. Nicholson and Alejandro Salinger | |||
| Abstract | The effective use of parallel computing resources to speed up algorithms in current multicore and other parallel architectures remains a difficult challenge, with ease of programming playing a key role in the eventual success of these architectures. In this paper we consider an alternative view of parallelism in the form of an ultra-wide word processor. We introduce the Ultra-Wide Word architecture and model, an extension of the word-RAM model, that allows for constant time operations on thousands of bits in parallel. Word parallelism as exploited by the word-RAM model does not suffer from the more difficult aspects of parallel programming, namely synchronization and concurrency. In practice, the speedups obtained by word-RAM algorithms are moderate, as they are limited by the word size. We argue that a large class of word-RAM algorithms can be implemented in the Ultra-Wide Word model, obtaining speedups comparable to multi-threaded computations while keeping the simplicity of programming of the sequential RAM model. We show that this is the case by describing implementations of Ultra-Wide Word algorithms for dynamic programming and string searching. In addition, we show that the Ultra-Wide Word model can be used to implement a non-standard memory architecture, which enables the sidestepping of lower bounds of important data structure problems such as priority queues and dynamic prefix sums. | |||
| Date | October 30, 2012 | |||
| Report | Algorithms in the Ultra-Wide Word Model (PDF) | |||
| CS-2012-22 | ||||
|---|---|---|---|---|
| Title | Broadcasting in Confict-Aware Multi-Channel Networks | |||
| Authors | Francisco Claude, Reza Dorrigiv, Shahin Kamali, Alejandro Lopez-Ortiz, Pawel Pralat, Jazmin Romero, Alejandro Salinger and Diego Seco | |||
| Abstract |
The
broadcasting
problem
asks
for
the
fastest
way
of
transmitting
a
message
to
all
nodes
of
a
communication
network.
We
consider
the
problem
in
conflict-aware
multi-channel
networks.
These
networks
can
be
modeled
as
undirected
graphs
in
which
each
edge
is
labeled
with
a
set
of
available
channels
to
transmit
data
between
its
endpoints.
Each
node
can
send
and
receive
data
through
any
channel
on
its
incident
edges,
with
the
restriction
that
it
cannot
successfully
receive
through
a
channel
when
multiple
neighbours
send
data
via
that
channel
simultaneously.
We
present
efficient
algorithms
as
well
as
hardness
results
for
the
broadcasting
problem
on
various
network
topologies.
We
propose
polynomial
time
algorithms
for
optimal
broadcasting
in
grids,
and
also
for
trees
when
there
is
only
one
channel
on
each
edge.
Nevertheless,
we
show
that
the
problem
is
NP-hard
for
trees
in
general,
as
well
as
for
complete
graphs.
In
addition,
we
consider
balanced
complete
graphs
and
propose
a
policy
for
assigning
channels
to
these
graphs.
This
policy,
together
with
its
embedded
broadcasting
schemes,
result
in
fault-tolerant
networks
which
have
optimal
broadcasting
time. | |||
| Date | November 20, 2012 | |||
| Report | Broadcasting in Confict-Aware Multi-Channel Networks (PDF) | |||
| CS-2012-23 | ||||
|---|---|---|---|---|
| Title | A Web-based Toolkit for Collaborative Innovation | |||
| Authors |
Donald Cowan, TerryWilkinson, Douglas Mulholland, Paulo Alencar and Fred McGarry | |||
| Abstract |
In
a
previous
report
we
outlined
the
need
for
a
web-based
framework
for
collaborative
innovation.
In
this
report
we
describe
the
toolkit,
meta-components
and
meta-processes that are needed to support such activity. | |||
| Date | November 28, 2012 | |||
| Report | A Web-based Toolkit for Collaborative Innovation (PDF) | |||
| CS-2012-24 | ||||
|---|---|---|---|---|
| Title | smv-morph: Working with Cadence SMV models in Moscow ML | |||
| Authors | Alma L. Juarez-Dominguez and Nancy A. Day | |||
| Abstract | We describe smv-morph: a toolkit of functions to manipulate and print SMV models (both Cadence and NuSMV) in Moscow ML. Our toolkit includes the ability to read Cadence SMV models and counterexamples produced by both SMV model checkers. In this report, we concentrate our explanations on functionality related to Cadence SMV. | |||
| Date | December 10, 2012 | |||
| Report | smv-morph: Working with Cadence SMV models in Moscow ML (PDF) | |||
| CS-2012-25 | ||||
|---|---|---|---|---|
| Title | An Automated Verication of Property TP2 for Concurrent Collaborative Text Buffers | |||
| Authors | Brad Lushman and Adam Roegiest | |||
| Abstract | Using the Coq proof assistant, we present a mechanically verified proof that the operation transforms defined on text buffer insertions and deletions, as outlined in Ressel et al's adOPTed algorithm do not satisfy Ressel's transformation property TP2. We then apply similar techniques to Cormack's Calculus for Concurrent Update (CCU) and show that the CCU ransformations also do not satisfy TP2. | |||
| Date | December 17, 2012 | |||
| Report | An Automated Verication of Property TP2 for Concurrent Collaborative Text Buffers (PDF) | |||
| CS-2012-26 | ||||
|---|---|---|---|---|
| Title | Materialized Views for Eventually Consistent Record Stores | |||
| Authors | Changjiu Jin, Rui Liu, Kenneth Salem | |||
| Abstract |
Distributed, replicated keyed-record stores are often used by applications that place a premium on high availability and scalability. Such systems provide fast access to stored records given a primary key value, but access without the primary key may be very slow and expensive. This problem can be addressed using materialized views. Materialized views redundantly store records, or parts of records, and the redundant copies can be organized and distributed differently than the originals, e.g, according to the value of a secondary key. In this paper, we consider the problem of supporting materialized views in multimaster, eventually consistent keyed-record stores. Incremental maintenance of materialized views is challenging in such systems because there no single master server responsible for serializing the updates to each record. We present a decentralized technique for incrementally maintaining materialized views in multi-master systems. We have implemented a prototype of our technique using Cassandra, a widely used system of this type. Using the prototype, we show that secondary-key-based access is much faster using materialized views than using Cassandra’s native secondary indexes, but maintaining the views in the face of updates may be more expensive than maintaining indexes. | |||
| Date | December 31, 2012 | |||
| Report |
Materialized Views for Eventually Consistent Record Stores (PDF) | |||