@inproceedings{Twigg:2011:SBV:2002218.2002228,
author = {Twigg, Andrew and Byde, Andrew and Mi{\l}os, Grzegorz and Moreton, Tim and Wilkes, John and Wilkie, Tom},
abstract = {External-memory versioned dictionaries are fundamen- tal to file systems, databases and many other algorithms. The ubiquitous data structure is the copy-on- write (CoW) B-tree. Unfortunately, it doesn’t inherit the B-tree’s optimality properties; it has poor space utilization, cannot offer fast updates, and relies on random IO to scale. We describe the ‘stratified B-tree’, which is the first versioned dictionary offering fast updates and an optimal tradeoff between space, query and update costs.},
title = {Stratified {B}-trees and versioned dictionaries},
booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in storage and file systems},
series = {HotStorage'11},
year = {2011},
location = {Portland, OR},
pages = {10--10},
numpages = {1},
url = {http://dl.acm.org/citation.cfm?id=2002218.2002228},
acmid = {2002228},
publisher = {USENIX Association},
address = {Berkeley, CA, USA},
pdf = {pubs/2011-hotstorage.pdf}
}
@article{DBLP:journals/mst/CourcelleT10,
author = {Bruno Courcelle and Andrew Twigg},
abstract = {Given a graph G we consider the problem of preprocessing it so that given two vertices x,y and a set X of vertices, we can efficiently report the shortest path (or just its length) between x,y that avoids X. We attach labels to vertices in such a way that this length can be determined from the labels of x,y and the vertices X. For a graph with n vertices of tree-width or clique-width k, we construct labels of size O(k^2 log^2 n). The constructions extend to directed graphs. The problem is motivated by routing in networks in case of failures or of routing policies which forbid certain paths.},
title = {Constrained-Path Labellings on Graphs of Bounded Clique-Width},
journal = {Theory Comput. Syst.},
volume = {47},
number = {2},
year = {2010},
pages = {531-567},
url = {http://springerlink.metapress.com/content/b3268gtk313180q0/},
bibsource = {DBLP, http://dblp.uni-trier.de},
pdf = {pubs/2010-tocs.pdf}
}
@techreport{IC-10-18,
author = {Andrew Twigg and Eduardo Xavier},
title = {{Locality-preserving allocation problems and coloured bin packing}},
year = 2010,
pdf = {pubs/TR-10-18.pdf},
institution = {UNICAMP, Brazil},
abstract = {We study a generalized version of a data locality problem in networks introduced by Chung and Graham et al. (2006). The problem is to distribute items of different sizes and colors among processors (or bins) so that we simultaneously minimize `bin stretch' (total number of bins used compared to optimal) and `color stretch' (for each color, the number of bins spanned by its items, compared to optimal considering just that color). We prove several inapproximability tradeoffs between these two quantities, and give the first offline and online approximation algorithms for the problem. In particular, we show that no online algorithm can achieve $O(1)$ approximation in both quantities, but that with a small restriction on the inputs, $O(1)$ approximations can be achieved.},
number = {IC-10-18}
}
@inproceedings{DBLP:conf/sigmetrics/BonaldMMPT08,
author = {Thomas Bonald and
Laurent Massouli{\'e} and
Fabien Mathieu and
Diego Perino and
Andrew Twigg},
title = {Epidemic live streaming: optimal performance trade-offs},
booktitle = {SIGMETRICS},
year = {2008},
pages = {325-336},
url = {http://doi.acm.org/10.1145/1375457.1375494},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{DBLP:journals/corr/abs-0810-5477,
author = {Andrew Twigg},
abstract = {We give a simple algorithm for decremental graph connectivity that handles edge deletions in worst-case time $O(k \log n)$ and connectivity queries in $O(\log k)$, where $k$ is the number of edges deleted so far, and uses worst-case space $O(m^2)$. We use this to give an algorithm for $k$-edge witness (``does the removal of a given set of $k$ edges disconnect two vertices $u,v$?'') with worst-case time $O(k^2 \log n)$ and space $O(k^2 n^2)$. For $k = o(\sqrt{n})$ these improve the worst-case $O(\sqrt{n})$ bound for deletion due to Eppstein et al. We also give a decremental connectivity algorithm using $O(n^2 \log n / \log \log n)$ space, whose time complexity depends on the toughness and independence number of the input graph. Finally, we show how to construct a distributed data structure for \kvw by giving a labeling scheme. This is the first data structure for \kvw that can efficiently distributed without just giving each vertex a copy of the whole structure. Its complexity depends on being able to construct a linear layout with good properties.},
title = {Worst-case time decremental connectivity and k-edge witness},
journal = {CoRR},
volume = {abs/0810.5477},
year = {2008},
url = {http://arxiv.org/abs/0810.5477},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{DBLP:journals/endm/CourcelleGKT08,
author = {Bruno Courcelle and
Cyril Gavoille and
Mamadou Moustapha Kant{\'e} and
Andrew Twigg},
abstract = {We consider the problem of determining in a planar graph G whether two vertices x and y are linked by a path that avoids a set X of vertices and a set F of edges. We attach labels to vertices in such a way that this fact can be determined from the labels of x and y, the vertices in X and the ends of the edges of F. For a planar graph with n vertices, we construct labels of size O(log n). The problem is motivated by the need to quickly compute alternative routes in networks under node or edge failures.},
title = {Connectivity check in 3-connected planar graphs with obstacles},
journal = {Electronic Notes in Discrete Mathematics},
volume = {31},
year = {2008},
pages = {151-155},
url = {http://dx.doi.org/10.1016/j.endm.2008.06.030},
bibsource = {DBLP, http://dblp.uni-trier.de},
pdf = {pubs/2008-planar.pdf}
}
@article{DBLP:journals/pe/MassoulieT08,
author = {Laurent Massouli{\'e} and
Andrew Twigg},
abstract = {In this paper we consider the problem of sending data in real time from information sources to sets of receivers, using peer-to-peer communications. We consider several models of communication resources, and for each model we identify schemes that achieve successful diffusion of information at optimal rates.
For edge-capacitated networks, we show optimality of the so-called “random-useful” packet forwarding algorithm. As a byproduct, we obtain a novel proof of a famous theorem of Edmonds, characterising the broadcast capacity of a capacitated graph.
For node-capacitated networks, assuming a complete communication graph, we show optimality of the so-called “most-deprived” neighbour selection scheme combined with random useful packet selection. We then show that optimality is preserved when each peer can exchange data with a limited number of neighbours, when neighbourhoods are dynamically adapted according to a particular scheme.
Finally, we consider the case of multiple information sources, each creating distinct information to be disseminated to a specific set of receivers. In this context, we prove optimality of the so-called “bundled most-deprived neighbour random useful packet” selection.},
title = {Rate-optimal schemes for Peer-to-Peer live streaming},
journal = {Perform. Eval.},
volume = {65},
number = {11-12},
year = {2008},
pages = {804-822},
url = {http://dx.doi.org/10.1016/j.peva.2008.03.003},
bibsource = {DBLP, http://dblp.uni-trier.de},
pdf = {pubs/2008-jperfeval.pdf}
}
@inproceedings{towsleytwigg08,
author = {Don Towsley and Andrew Twigg},
title = {Rate-optimal decentralised broadcasting the wireless case},
booktitle = {ACITA},
year = {2008},
url = {https://www.usukita.org/papers/3888/final-ITA.pdf},
abstract = {We consider the problem of broadcasting information from a source node to all nodes in a wireless network, using a local-control algorithm. For simplicity, we assume some oracle that provides the scheduling decisions required for interference. Under this assumption, we can show that a local control algorithm exists that achieves a stable system whenever the injection rate at the source is feasible for the network. We show results for the case of a single antenna and for multiple antennas operating independently.},
pdf = {pubs/2008-ita.pdf}
}
@article{DBLP:journals/corr/abs-0810-5263,
author = {Rahul Sami and
Andy Twigg},
title = {Lower bounds for distributed markov chain problems},
journal = {CoRR},
volume = {abs/0810.5263},
year = {2008},
url = {http://arxiv.org/abs/0810.5263},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = {We study the worst-case communication complexity of distributed algorithms computing a path problem based on stationary distributions of random walks in a network $G$ with the caveat that $G$ is also the communication network. The problem is a natural generalization of shortest path lengths to expected path lengths, and represents a model used in many practical applications such as pagerank and eigentrust as well as other problems involving Markov chains defined by networks.
For the problem of computing a single stationary probability, we prove an $\Omega(n^2 \log n)$ bits lower bound; the trivial centralized algorithm
costs $O(n^3)$ bits and no known algorithm beats this. We also prove lower bounds for the related problems of approximately computing the stationary probabilities, computing only the ranking of the nodes, and computing the node with maximal rank. As a corollary, we obtain lower bounds for labelling schemes for the hitting time between two nodes.}
}
@techreport{TR-2007-08-0001,
author = {Andrew Twigg and Laurent Massoulie},
title = {{Local routing algorithms for node-capacitated multicommodity broadcast}},
year = 2007,
pdf = {pubs/TR-2007-08-0001.pdf},
institution = {Thomson Research},
abstract = {Given a directed network with upload and download capacities at nodes, we consider the multicommodity relay-free multicast problem: there are $k$ multicast sessions, each with a source $s_i \in V$, receiver set $R_i \subseteq V$ and demand $\lambda_i > 0$, with the constraint that nodes only forward packets of commodities for which they are also a receiver. When each $R_i$ is a clique, we prove that whenever demands $\{\lambda_i + \varepsilon\}$ are feasible, a simple local-control routing algorithm is stable under demands $\{\lambda_i\}$. We also give a randomized procedure for resampling neighbours that allows the use of bounded-degree neighbourhoods.},
number = {TR-2007-08-0001}
}
@inproceedings{DBLP:conf/infocom/MassoulieTGR07,
author = {Laurent Massouli{\'e} and
Andrew Twigg and
Christos Gkantsidis and
Pablo Rodriguez},
abstract = {We consider the problem of broadcasting a live stream of data in an unstructured network. Broadcasting has been studied extensively for networks with capacity constraints at the edges. We give the first completely distributed algorithm that optimally solves the broadcast problem in edge-capacitated networks, providing a new proof of Edmonds’ theorem. Motivated by the access capacity limitations in todays Internet, we study the problem of efficient decentralized broadcasting in node capacitated networks. We present the first completetly decentralized algorithm for solving the node-capacitated broadcast problem, and show some of its optimality properties analytically and through simulation. We study the delay that users must wait in order to playback the stream with a small number of skipped packets, and discuss the suitability of our algorithms for live video streaming.},
title = {Randomized Decentralized Broadcasting Algorithms},
booktitle = {INFOCOM},
year = {2007},
pages = {1073-1081},
url = {http://dx.doi.org/10.1109/INFCOM.2007.129},
bibsource = {DBLP, http://dblp.uni-trier.de},
pdf = {pubs/2007-infocom.pdf}
}
@inproceedings{DBLP:conf/stacs/CourcelleT07,
author = {Bruno Courcelle and
Andrew Twigg},
abstract = {We study labelling schemes for X-constrained path problems. Given a graph (V,E) and X \subseteq V, a path is X-constrained if all intermediate vertices avoid X. We study the problem of assigning labels J(x) to vertices so that given {J(x) : x \in X} for any X \subseteq V , we can route on the shortest X-constrained path between x,y \in X. This problem is motivated by Internet routing, where the presence of routing policies means that shortest-path routing is not appropriate. For graphs of tree width k, we give a routing scheme using routing tables of size O(k^2 log^2 n). We introduce m-clique width, generalizing clique width, to show that graphs of m-clique width k also have a routing scheme using size O(k^2 log^2 n) tables.},
title = {Compact Forbidden-Set Routing},
booktitle = {STACS 2007, 24th Annual Symposium on Theoretical Aspects
of Computer Science, Aachen, Germany},
year = {2007},
pages = {37-48},
url = {http://dx.doi.org/10.1007/978-3-540-70918-3_4},
bibsource = {DBLP, http://dblp.uni-trier.de},
pdf = {pubs/2007-stacs.pdf}
}
@article{locality2007twigg,
author = {Bruno Courcelle and Cyril Gavoulle and Mustapha Kante and Andrew Twigg},
title = {Forbidden-set labelling on graphs},
abstract = {We describe recent work on a variant of a distance labeling problem in graphs, called the forbidden-set labeling problem. Given a graph G = (V, E), we wish to assign labels L(x) to vertices and edges of G so that given {L(x)|x \in X} for any X \subset V \union E and L(u), L(v) for u, v \in V , we can decide if a property holds in the graph G \ X, or compute a value like the distance between u, v in G \ X . The problem is motivated by routing in networks where some nodes or edges may fail, or where nodes may decide to route on paths avoiding some ‘forbidden’ set of nodes or edges.},
journal = {Second Workshop on Locality Preserving Distributed Computing Methods (LOCALITY), co-located with PODC},
year = {2007},
pdf = {pubs/2007-locality.pdf}
}
@article{DBLP:journals/tcs/KrukowT07,
author = {Karl Krukow and
Andrew Twigg},
abstract = {In this paper we consider the complexity of some problems arising in a fixed point model of trust in large-scale distributed systems, based on the notion of trust structures introduced by Carbone, Nielsen and Sassone; a set of trust levels with two distinct partial orderings. In the trust model, a global trust state exists as the least fixed point of a collection of local policy functions of nodes in the network.
We first show that it is possible to efficiently compute a single component of the global trust state using a simple, robust and totally asynchronous distributed algorithm. We complement this with a lower bound which shows that, if the policies are unrestricted then communication and time linear in the number of distinct trust levels is required in the worst case.
We then consider the notion of distributed proof carrying requests previously introduced as a means of safely approximating the global trust state without computing its exact value. We present a new result that enables us to give a continuum of proof carrying protocols, the previously known protocol being one extreme of this. The theorem allows us to generate protocols that can prove all possible trust values (previously, it was only possible to prove trust values representing ‘not too much bad behaviour’). However, we show that such a general protocol may not be efficient — it is NP-hard to construct an approximately minimal size proof in our model, and in the worst case the nodes must communicate almost as much data as if they were to compute the global trust state from scratch. The implications of our negative results are that it may be necessary to restrict the policy language in order to efficiently implement a fixed point model of trust in a distributed network.},
title = {The complexity of fixed point models of trust in distributed
networks},
journal = {Theor. Comput. Sci.},
volume = {389},
number = {3},
year = {2007},
pages = {528-549},
url = {http://dx.doi.org/10.1016/j.tcs.2007.09.007},
bibsource = {DBLP, http://dblp.uni-trier.de},
pdf = {pubs/2007-tcs-krukow.pdf}
}
@techreport{UCAM-CL-TR-678,
author = {Twigg, Andrew D.},
title = {{Compact forbidden-set routing}},
year = 2006,
month = dec,
url = {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-678.pdf},
institution = {University of Cambridge, Computer Laboratory},
issn = {1476-2986},
abstract = {We study the compact forbidden-set routing problem. We
describe the first compact forbidden-set routing schemes
that do not suffer from non-convergence problems often
associated with Bellman-Ford iterative schemes such as
the interdomain routing protocol, BGP. For degree-d
n-node graphs of treewidth t, our schemes use space
O(t$^2$ d polylog(n)) bits per node; a trivial scheme
uses O(n$^2$) and routing trees use $\Omega$(n) per node
(these results have since been improved and extended --
see [Courcelle, Twigg, Compact forbidden-set routing,
24th Symposium on Theoretical Aspects of Computer
Science, Aachen 2007]. We also show how to do
forbidden-set routing on planar graphs between nodes
whose distance is less than a parameter l. We prove a
lower bound on the space requirements of forbidden-set
routing for general graphs, and show that the problem is
related to constructing an efficient distributed
representation of all the separators of an undirected
graph. Finally, we consider routing while taking into
account path costs of intermediate nodes and show that
this requires large routing labels. We also study a novel
way of approximating forbidden-set routing using quotient
graphs of low treewidth.},
number = {UCAM-CL-TR-678},
pdf = {pubs/2006-thesis.pdf}
}
@techreport{massoulie-msr-tr,
author = {Laurent Massoulie and Andrew Twigg and Christos Gkantsidis and Pablo Rodriguez Rodriguez},
title = {Provably optimal decentralized broadcasting algorithms},
note = {Microsoft Research Technical Report MSR-TR-2006-105},
year = {2006},
abstract = {In this paper we consider the problem of broadcasting information from a source node to a set of receiver nodes. In the context of edge-capacitated networks, we consider the ``random useful'' packet forwarding algorithm. We prove that it yields a stable system, provided the data injection rate at the source node is less than the (min(min-cut)) of the graph. As a corollary we retrieve a famous theorem of Edmonds. We next consider node-capacitated networks. In this context we introduce the ``random useful to most deprived neighbour'' packet forwarding scheme. We show that it yields a stable system in the particular case where the network graph is the complete graph, whenever the node capacities are large enough for centralised schemes to achieve successful broadcast of the data injection rate.},
url = {http://research.microsoft.com/research/pubs/view.aspx?type=Technical%20Report&id=1151},
pdf = {pubs/2006-msr-tr.pdf}
}
@techreport{BRICS-RS-05-6,
author = {Karl Krukow and Andrew Twigg},
title = {Distributed Approximation of Fixed-Points in Trust Structures},
institution = {BRICS (Centre for Basic Research In Computer Science), Aarhus University, Denmark},
year = 2005,
type = {BRICS Research Series},
number = {RS-05-6},
abstract = {Carbone, Nielsen and Sassone introduced the trust-structure
framework; a semantic model for trust-management in global-scale
distributed systems. The framework is based on the notion of trust
structures; a set of ``trust-levels'' ordered by two distinct partial
orderings. In the model, a unique global trust-state is defined
as the least fixed-point of a collection of local policies assigning
trust-levels to the entities of the system. However, the framework is
a purely denotational model: it gives precise meaning to the global
trust-state of a system, but without specifying a way to
compute this abstract mathematical object.
This paper complements the denotational model of trust structures with
operational techniques. It is shown how the least fixed-point can be
computed using a simple, totally-asynchronous distributed
algorithm. Two efficient protocols for approximating the least
fixed-point are provided, enabling sound reasoning about the global
trust-state without computing the exact fixed-point. Finally, dynamic
algorithms are presented for safe reuse of information between
computations, in face of dynamic trust-policy updates.
},
pdf = {pubs/brics-rs-05-6.pdf}
}
@inproceedings{DBLP:conf/icdcs/KrukowT05,
author = {Karl Krukow and
Andrew Twigg},
title = {Distributed Approximation of Fixed-Points in Trust Structures},
booktitle = {25th International Conference on Distributed Computing Systems
(ICDCS 2005), 6-10 June 2005, Columbus, OH, USA},
year = {2005},
pages = {805-814},
url = {http://doi.ieeecomputersociety.org/10.1109/ICDCS.2005.23},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = { We consider distributed algorithms for solving problems in a framework for trust in large-scale distributed systems. The framework is based on the notion of trust structures; a set of `trust-levels' with two distinct partial orderings. In the trust model, a global trust-state exists as the least fixed-point of a collection of local policies of nodes in the network. We first show that it is possible to compute the global trust values using a simple, robust and totally asynchronous distributed algorithm. We also consider a notion of distributed proof-carrying requests as a means of \hbox{approximating} the least fixed-point, enabling sound reasoning about the global trust-state without computing the exact fixed-point. Our proof carrying request model is different to that of PolicyMaker; in particular, all proofs are efficiently verifiable or easily rejected, but may require as much communication as computing the actual trust value itself, in the worst-case.
},
pdf = {pubs/2005-ICDCS05.pdf}
}
@inbook{gridbook2004,
author = {Jon Crowcroft and Tim Moreton and Ian Pratt and Andrew Twigg},
title = {The Grid: Blueprint for a New Computing Infrastructure (Second Edition)},
chapter = {Peer-to-peer technologies},
publisher = {Morgan Kaufmann},
year = {2004},
url = {http://www.mkp.com/mk/default.asp?isbn=1558609334}
}
@unpublished{7,
author = {Andrew Twigg},
title = {Pairwise permutations and online algorithms},
note = {Unpublished},
year = {2003},
abstract = {Imagine a network $\mathcal{N}$ with delays, such that when a message
sequence $a,b,c, \ldots$ is sent over the network, elements of the
sequence may individually experience delays. This is a simplified
model of UDP transmission, which is often used for broadcasting
streams of data where low transmission overhead is important (for now,
let's assume that the stream is lossless, ie the maximum delay
experienced by any element is finite). We say that $\mathcal{N}$ has
delay of $d$ if the maximum amount of time any element can be delayed
for is $d$. Clearly, the set of $d$-delayed versions of a stream $\sigma$ is a
subset of the permutations of the elements of $\sigma$. For example, a 1-delayed version of $\sigma = \sigma_1, \sigma_2, \sigma_3, \ldots$
is $\sigma' = \sigma_1, \sigma_3, \sigma_2, \ldots$.
Now imagine an on-line algorithm $\textrm{ALG}$ that receives an input stream
$\sigma'$ over the network, as in Figure \ref{fig:network}. The
network can be considered a set of links and the network chooses (adversarially) which link to send each
element over. We investigate the effect of the network on the competitive ratio of $\textrm{ALG}$, by comparing
the worst-case performance of $\textrm{ALG}(\sigma')$ to
$\textrm{ALG}(\sigma)$. We look at on-line algorithms for three well-studied problems: minimum spanning tree, steiner tree and static list-accessing.
},
pdf = {pubs/2003-online.pdf}
}
@inproceedings{DBLP:conf/wetice/TwiggD03,
author = {Andrew Twigg and
Nathan Dimmock},
title = {Attack-Resistance of Computational Trust Models},
booktitle = {WETICE},
year = {2003},
pages = {275-280},
url = {http://doi.ieeecomputersociety.org/10.1109/ENABL.2003.1231420},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = {The World Wide Web encourages widely-distributed, open, decentralised systems
that span multiple administrative domains. Recent research has turned to
\emph{trust management} \cite{blaze96decentralized} as a framework for
decentralising security decisions in such systems. However, whilst traditional
security measures such as cryptography and encryption are well-understood
(theoretically and empirically), the same cannot be said for computational trust
models. This paper describes the attack-resistance of several well-referenced
trust models, in a move toward a possible framework and terminology for such
analyses. We present a number of open questions, and consider possible future
directions in the area.},
pdf = {pubs/2003-wetice.pdf}
}
@inproceedings{moreton03,
author = {Tim Moreton and Andrew Twigg},
title = {Trading in Trust, Tokens and Stamps},
optkey = {},
booktitle = {Proceedings of the 2nd Workshop on Economics of Peer-to-Peer
Systems, Berkeley CA},
optpages = {},
year = {2003},
opteditor = {},
optvolume = {},
optnumber = {},
optseries = {},
address = {Berkeley, CA},
optmonth = {},
optorganization = {},
optpublisher = {},
optnote = {},
optannote = {},
abstract = {Many peer-to-peer networks rely on cooperation between nodes. Reputation and payment protocols are two methods of introducing incentives to participate in systems such as Mojo Nation and Free Haven. We are interested in the relationship between reputation and payment protocols, in particular the types and properties of the economies and incentives they induce. Our work reveals some interesting parallels. It turns out that both types of protocol induce similar incentive schemes, in that there exists a more general protocol - stamp trading - which captures the essence of both. Our analysis and results have implications for many peer-to-peer systems including spam-resistant networks, filesharing and routing.
},
pdf = {pubs/2003-trading-trust.pdf}
}
@inproceedings{DBLP:conf/itrust/Twigg03,
author = {Andrew Twigg},
title = {A Subjective Approach to Routing in P2P and Ad Hoc Networks},
booktitle = {iTrust},
year = {2003},
pages = {225-238},
url = {http://dx.doi.org/10.1007/3-540-44875-6_16},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = {This paper presents a subjective approach to routing in peer-to-peer and ad hoc networks. The main difference between our approach and traditional routing models is the use of a trust model to mediate the risk inherent in routing decisions. Rather than blindly exchanging routing table entries, nodes `discount' recommendations from other nodes using a distributed trust computation which allows them to avoid malicious, faulty and unreliable nodes and links in routing decisions. Adding the risk model allows energy-efficient routing decisions to be made in a wireless network, and we show how our model can be optimized for different network behaviours, including wireless networks. The model is described in the context of the DSR \cite{johnson01dsr} routing algorithm, although it is equally-applicable to others, including peer-to-peer routing substrates.
},
pdf = {pubs/2003-trustrouting.pdf}
}
@inproceedings{DBLP:conf/itrust/MoretonT03,
author = {Tim D. Moreton and
Andrew Twigg},
title = {Enforcing Collaboration in Peer-to-Peer Routing Services},
booktitle = {iTrust},
year = {2003},
pages = {255-270},
url = {http://dx.doi.org/10.1007/3-540-44875-6_18},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = {Many peer-to-peer services rely on a cooperative model of interaction among nodes, yet actually provide little incentive for nodes to collaborate. In this paper, we develop a trust and security architecture for a routing and node location service based on Kademlia [1], a distributed hash table. Crucially, rather than `routing round' defective or malicious nodes, we discourage free-riding by requiring a node to contribute honestly in order to obtain routing service in return. We claim that our trust protocol enforces collaboration and show how our modified version of Kademlia resists a wide variety of attacks.},
pdf = {pubs/2003-kademlia-trust.pdf}
}
@inproceedings{DBLP:conf/itrust/DragovicHHKT03,
author = {Boris Dragovic and
Steven Hand and
Timothy L. Harris and
Evangelos Kotsovinos and
Andrew Twigg},
title = {Managing Trust and Reputation in the XenoServer Open Platform},
booktitle = {iTrust},
year = {2003},
pages = {59-74},
url = {http://dx.doi.org/10.1007/3-540-44875-6_5},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = {Participants in public distributed computing do not find it
easy to trust each other. The massive number of parties involved,
their heterogeneous backgrounds, disparate goals and independent
nature are not a good basis for the development of relationships
through purely social mechanisms.
This paper discusses the trust management issues that arise in the
context of the XenoServer Open Platform: a public infrastructure for
wide-area computing, capable of hosting tasks that span the full
spectrum of distributed paradigms. We examine the meaning and
necessity of trust in our platform, and present our trust management
architecture, named XenoTrust.
XenoTrust follows the same design principles that we are using
throughout the XenoServer project: it provides a flexible platform
over which many of the interesting distributed trust-management
algorithms presented in the literature can be evaluated in a
large-scale wide-area setting.
},
pdf = {pubs/2003-xenotrust.pdf}
}
@article{uncertainty:2003,
author = {Vinny Cahill and Brian Shand and Elizabeth Gray and
Ciaran Bryce and Nathan Dimmock and Andrew Twigg and
Jean Bacon and Colin English and Waleed Wagealla and
Sotirios Terzis and Paddy Nicon and Giovanna di
Marzo Serugendo and Jean-Marc Seigneur and Marco
Carbone and Karl Krukow and Christian Jensen and
Yong Chen and Mogens Nielsen},
title = {Using Trust for Secure Collaboration in Uncertain
Environments},
journal = {IEEE Pervasive Computing},
year = 2003,
volume = 2,
number = 3,
pages = {52--61},
month = {August},
url = {http://csdl.computer.org/comp/mags/pc/2003/03/b3052abs.htm},
pdf = {http://csdl.computer.org/dl/mags/pc/2003/03/b3052.pdf}
}
@techreport{2002-websearch,
author = {Hristo N.~Djidjev and Mike Joy and Andrew Twigg},
title = {Collecting and Classifying Web Documents},
institution = {University of Warwick},
year = {2002},
optkey = {},
opttype = {},
optnumber = {},
optaddress = {},
optmonth = {},
optnote = {},
optannote = {},
abstract = {The large size and explosive growth rate of the
World-Wide Web make general purpose search engines expensive and
difficult to use. Specialized search machines that collect
information on particular pre-defined topics have emerged as a
competitive alternative. This paper studies some issues related to
the design and implementation of such types of search engines. We
study in more detail a classification procedure that determines
the relevance of a query page to the topic of interest and a
crawling strategy that aims at visiting a large number of relevant
pages early in the search. We describe the results of a number of
experiments that test the effectiveness of the methods.}
}
This file was generated by bibtex2html 1.96.