@inproceedings{Skowron2013p2pbackup,
author = {Skowron, Piotr and Rzadca, Krzysztof},
title = {Exploring heterogeneity of unreliable machines for p2p backup},
keywords = {p2p},
booktitle = {(accepted) HPCS 2013, International Conference on High Performance Computing \& Simulation},
pdf = {papers/p2pbackup_hpcs2013.pdf},
abstract = {P2P architecture is a viable option for enterprise backup. In contrast to dedicated backup servers, nowadays a standard solution, making backups directly on organization's workstations should be cheaper (as existing hardware is used), more efficient (as there is no single bottleneck server) and more reliable (as the machines are geographically dispersed).
We present the architecture of a p2p backup system that uses pairwise replication contracts between a data owner and a replicator. In contrast to standard p2p storage systems using directly a DHT, the contracts allow our system to optimize replicas' placement depending on a specific optimization strategy,
and so to take advantage of the heterogeneity of the machines and the network.
Possible goals include geographical dispersion of the replicas, minimization of backup or restore time or the usage of long-range links.
However, managing the contracts, keeping them consistent and adjusting them in response to dynamically changing environment is challenging.
We built a scientific prototype and ran the experiments on 150 workstations in the university's computer laboratories and, separately, on 50 PlanetLab nodes.
We found out that the main factor affecting the quality of the system is the availability of the machines.
Yet, our main conclusion is that it is possible to build an efficient and reliable backup system on highly unreliable machines (our computers had just 13\% average availability).},
optpages = {},
year = {2013},
opteditor = {},
optvolume = {},
optnumber = {},
optseries = {},
optaddress = {},
optmonth = {},
optorganization = {},
optpublisher = {},
optnote = {},
optannote = {}
}
@inproceedings{Skowron2013shapleyscheduling,
author = {Skowron, Piotr and Rzadca, Krzysztof},
title = {Non-monetary fair scheduling --- a cooperative game theory approach},
keywords = {scheduling,resource_management,fairness},
booktitle = {(accepted) SPAA 2013, 25th ACM Symposium on Parallelism in Algorithms and Architectures},
url = {http://arxiv.org/abs/1302.0948},
pdf = {papers/shapleyScheduling-spaa2013.pdf},
abstract = {We consider a multi-organizational system in which each organization contributes processors to the global pool but also jobs to be processed on the common resources. The fairness of the scheduling algorithm is essential for the stability and even for the existence of such systems (as organizations may refuse to join an unfair system).
We consider on-line, non-clairvoyant scheduling of sequential jobs.
The started jobs cannot be stopped, canceled, preempted, or moved to other processors.
We consider identical processors, but most of our results can be extended to related or unrelated processors.
We model the fair scheduling problem as a cooperative game and we use the Shapley value to determine the ideal fair schedule. In contrast to the current literature, we do not use money to assess the relative utilities of jobs. Instead, to calculate the contribution of an organization, we determine how the presence of this organization influences the performance of other organizations. Our approach can be used with arbitrary utility function (e.g., flow time, tardiness, resource utilization), but we argue that the utility function should be strategy resilient. The organizations should be discouraged from splitting, merging or delaying their jobs. We present the unique (to within a multiplicative and additive constants) strategy resilient utility function.
We show that the problem of fair scheduling is NP-hard and hard to approximate. However, for unit-size jobs, we present a fully polynomial-time randomized approximation scheme (FPRAS). We also show that the problem parametrized with the number of organizations is fixed parameter tractable (FPT).
In cooperative game theory, the Shapley value is considered in many contexts as ``the'' fair solution. Our results show that, although the problem for the large number of organizations is computationally hard, this solution concept can be used in scheduling (for instance, as a benchmark for measuring fairness of heuristic algorithms).},
optpages = {},
year = {2013},
opteditor = {},
optvolume = {},
optnumber = {},
optseries = {},
optaddress = {},
optmonth = {},
optorganization = {},
optpublisher = {},
optnote = {},
optannote = {}
}
@inproceedings{Skowron2013networkdelaylb,
author = {Skowron, Piotr and Rzadca, Krzysztof},
title = {Network delay-aware load balancing in selfish and cooperative distributed systems},
keywords = {resource_management},
booktitle = {(accepted) HCW 2013, 22st International Heterogeneity in Computing Workshop (in conjunction with IPDPS 2013)},
url = {http://arxiv.org/abs/1212.0421},
pdf = {papers/contentDelivery_hcw2013.pdf},
abstract = {We consider a geographically distributed request processing system composed of various organizations and their servers connected by the Internet.
The latency a user observes is a sum of communication delays and the time needed to handle the request on a server. The handling time depends on the server congestion, i.e. the total number of requests a server must handle. We analyze the problem of balancing the load in a network of servers in order to minimize the total observed latency. We consider both cooperative and selfish organizations (each organization aiming to minimize the latency of the locally-produced requests). The problem can be generalized to the task scheduling in a distributed cloud; or to content delivery in an organizationally-distributed CDNs.
In a cooperative network, we show that the problem is polynomially solvable. We also present a distributed algorithm iteratively balancing the load. We show how to estimate the distance between the current solution and the optimum based on the amount of load exchanged by the algorithm. During the experimental evaluation, we show that the distributed algorithm is efficient, therefore it can be used in networks with dynamically changing loads.
In a network of selfish organizations, we prove that the price of anarchy (the worst-case loss of performance due to selfishness) is low when the network is homogeneous and the servers are loaded (the request handling time is high compared to the communication delay). After relaxing these assumptions, we assess the loss of performance caused by the selfishness experimentally, showing that it remains low.
Our results indicate that a set of servers handling requests, connected in a heterogeneous network, can be efficiently managed by a distributed algorithm. Additionally, even if the network is organizationally distributed, with individual organizations optimizing performance of their requests, the network remains efficient.},
optpages = {},
year = {2013},
opteditor = {},
optvolume = {},
optnumber = {},
optseries = {},
optaddress = {},
optmonth = {},
optorganization = {},
optpublisher = {},
optnote = {},
optannote = {}
}
@article{LiuXin2012stereotypes,
author = {Xin, Liu and Datta, Anwitaman and Rzadca, Krzysztof},
title = {Trust beyond reputation: A computational trust model based on stereotypes},
journal = {Electronic Commerce Research and Applications},
year = {2013},
keywords = {trust},
doi = {10.1016/j.elerap.2012.07.001},
url = {http://arxiv.org/abs/1103.2215},
abstract = {Models of computational trust support users in taking decisions. They are commonly used to guide users' judgements in online auction sites; or to determine quality of contributions in Web 2.0 sites. However, most existing systems require historical information about the past behavior of the specific agent being judged. In contrast, in real life, to anticipate and to predict a stranger's actions in absence of the knowledge of such behavioral history, we often use our "instinct"- essentially stereotypes developed from our past interactions with other "similar" persons. In this paper, we propose StereoTrust, a computational trust model inspired by stereotypes as used in real-life. A stereotype contains certain features of agents and an expected outcome of the transaction. When facing a stranger, an agent derives its trust by aggregating stereotypes matching the stranger's profile. Since stereotypes are formed locally, recommendations stem from the trustor's own personal experiences and perspective. Historical behavioral information, when available, can be used to refine the analysis. According to our experiments using Epinions.com dataset, StereoTrust compares favorably with existing trust models that use different kinds of information and more complete historical information.},
optkey = {},
volume = {12},
issue = {1},
pages = {24-39},
month = {January-February},
optnote = {},
optannote = {}
}
@inproceedings{Pinheiro2012campaign,
author = {Vinicious Pinheiro and Krzysztof Rzadca and Denis Trystram},
title = {Campaign Scheduling},
booktitle = {IEEE International Conference on High Performance Computing (HiPC), Proceedings},
keywords = {scheduling, fairness},
year = 2012,
pdf = {papers/campaign_scheduling_hipc2012.pdf},
abstract = {We study the problem of scheduling in parallel systems with many users. We analyze scenarios with many submissions issued over time by several users. These submissions contain one or more jobs; the set of submissions are organized in successive campaigns. Jobs belonging to a single campaign are sequential and independent, but any job from a campaign cannot start until all the jobs from the previous campaign are completed. Each user's goal is to minimize the sum of flow times of his campaigns.
We define a theoretical model for Campaign Scheduling and show that, in the general case, it is NP-hard.
For the single-user case, we show that an rho-approximation scheduling algorithm for the (classic) parallel job scheduling problem is also an rho-approximation for the Campaign Scheduling problem. For the general case with k users, we establish a fairness criterion inspired by time sharing. We propose FAIRCAMP, a scheduling algorithm which uses campaign deadlines to achieve fairness among users between consecutive campaigns. We prove that FAIRCAMP increases the flow time of each user by a factor of at most k rho compared with a machine dedicated to the user. We also prove that FAIRCAMP is a rho-approximation algorithm for the maximum stretch.
By simulation, we compare FAIRCAMP to the First-Come-First-Served (FCFS). We show that, compared with FCFS, FAIRCAMP reduces the maximum stretch by up to 3.4 times. The difference is significant in systems used by many (k>5) users.
Our results show that, rather than just individual, independent jobs, campaigns of jobs can be handled by the scheduler efficiently and fairly.}
}
@incollection{Datta2011DOSN,
author = {Datta, Anwitaman and Buchegger, Sonja and Le-Hung Vu and Thornsten,
Strufe and Rzadca, Krzysztof},
title = {Decentralized Online Social Networks},
booktitle = {Handbook of Social Network Technologies and Applications},
publisher = {Springer},
year = {2011},
editor = {Furht, B.},
address = {New York Dordrecht Heidelberg London},
keywords = {p2p},
owner = {krz},
timestamp = {2010.08.29},
url = {http://www.springer.com/computer/swe/book/978-1-4419-7141-8}
}
@incollection{Datta2010ServerlessSocialSoftware,
author = {Datta, Anwitaman and Rzadca, Krzysztof and Ang, Sally and Goh Chee
Hong},
title = {Serverless Social Software for Nomadic Collaboration},
booktitle = {e-Research Collaboration: Theory, Techniques and Challenges},
publisher = {Springer},
year = {2010},
editor = {Murugan, A.},
pages = {85-103},
address = {New York Dordrecht Heidelberg London},
abstract = {Recent portable devices, from sophisticated mobile phones, to netbooks,
thanks to wireless networking and powerful batteries, give hardware
support for collaborative work on the go, even when the Internet
connection is not available. Yet, current collaboration software,
from Concurent Versions System (CVS) or Subversion (SVN) repositories
to Google Docs and collaborative versions of commercial applications
(CoWord, CoMaya), requires a dedicated server to synchronize clients,
and thus a stable network connection.
In this chapter, we present two tools that use peer-to-peer paradigm
to build serverless collaboration networks. PBDMS enables users to
share, search and review bibliographic databases. SharedMind provides
collaborative document editing to FreeMind, popular, open source
mind-mapping software. Both tools handle disconnections and network
divisions, enabling users to continue their work and to synchronize
with their reachable peers.
Both tools have been implemented and tested in small scale. PBDMS
is available for download at http://code.google.com/p/bibliographicsocialinfosys/;
SharedMind is available at http://code.google.com/p/sharedmind .
We believe that such seamless, flexible collaboration applications
provide the degree of freedom promised by the recent portable devices,
yet not fully used by the current applications.},
keywords = {p2p, collaborative applications},
owner = {krz},
timestamp = {2010.08.29},
url = {http://www.springer.com/economics/book/978-3-642-12256-9}
}
@article{Trystram2010ApproximationAlgorithms,
author = {Dutot, Pierre-Francois and Pascual, Fanny and Rzadca, Krzysztof and
Trystram, Denis},
title = {Approximation Algorithms for the Multi-Organization Scheduling Problem},
journal = {IEEE Transactions on Parallel and Distributed Systems},
year = {2011},
volume = {22},
issue = {11},
pages = {1888 - 1895 },
doi = {10.1109/TPDS.2011.47},
pdf = {papers/mocca-tpds.pdf},
keywords = {scheduling, resource_management},
owner = {krz},
abstract = {The distributed nature of new computing platforms results in the problem of
scheduling parallel jobs produced by several independent
organizations that have each their own rules. They have no direct control over the whole system,
thus it is necessary to revisit classical scheduling with locality constraints.
In this article, we consider distributed computing systems in which each organization has
its own resources.
Each organization aims at minimizing the execution times of its own jobs.
We introduce a global centralized mechanism for designing
a collaborative solution that improves the global performance
of the system while respecting organizations' selfish objectives.
The proposed algorithm is proved to have an approximation ratio equal to
3 over the global optimal makespan and this bound is shown to be asymptotically tight
(when the number of organizations is large).
Several variants of this problem are also studied.
Then, we derive another algorithm that improves in practice
these solutions by further balancing the schedules.
Finally, we provide some experiments based on simulations
that demonstrate a very good efficiency of this last algorithm on typical instances.},
timestamp = {2010.08.29}
}
@inproceedings{ang2010sharedmind,
title = {SharedMind: A tool for collaborative mind-mapping},
author = {Ang, S. and Rzadca, K. and Datta, A.},
booktitle = {Multimedia and Expo (ICME), 2010 IEEE International Conference on},
pages = {1154--1155},
year = {2010},
organization = {IEEE}
}
@incollection{Dutot2009MultiObjectiveScheduling,
author = {P.-F Dutot and K. Rzadca and E. Saule and D. Trystram},
title = {Multi-Objective Scheduling},
booktitle = {Introduction to Scheduling},
publisher = {Chapman \& Hall/CRC},
year = {2009},
editor = {Y. Robert and F. Vivien},
series = {Computational Science},
keywords = {resource_management, scheduling},
owner = {krz},
timestamp = {2009.08.18},
url = {http://www.crcpress.com/product/isbn/9781420072730}
}
@incollection{hupa2010interdisciplinary,
author = {Hupa, A. and Rzadca, K. and Wierzbicki, A. and Datta, A.},
title = {Interdisciplinary matchmaking: Choosing collaborators by skill, acquaintance
and trust},
booktitle = {Computational Social Network Analysis},
publisher = {Springer},
year = {2010},
editor = {Ajith Abraham and Aboul-Ella Hassanien and Vaclav Snasel},
series = {Computer Communication and Networks},
pages = {319--347},
doi = {10.1007/978-1-84882-229-0_12},
keywords = {trust},
url = {http://www.springerlink.com/content/m75j67354387gj06/}
}
@inproceedings{Kaszuba2008DiscoveringMostTrusted,
author = {T. Kaszuba and K. Rzadca and A. Wierzbicki},
title = {Discovering the Most Trusted Agents without Central Control},
booktitle = {Embedded and Ubiquitous Computing, IEEE/IFIP International Conference
on},
year = {2008},
volume = {2},
pages = {616-621},
publisher = {IEEE Computer Society},
doi = {10.1109/EUC.2008.126},
keywords = {trust}
}
@inproceedings{Krystek2008ComparisonofCentralized,
author = {M. Krystek and K. Kurowski and A. Oleksiak and K. Rzadca},
title = {Comparison of Centralized and Decentralized Scheduling Algorithms
using GSSIM Simulation Environment},
booktitle = {Grid Computing: Achievements and Prospects},
year = {2008},
editor = {Sergei Gorlatch, Paraskevi Fragopoulou and Thierry Priol},
pages = {185--196},
publisher = {Springer},
doi = {10.1007/978-0-387-09457-1_16},
editors = {S. Gorlatch and P. Fragopoulu and T. Priol},
pdf = {papers/comp_centr_decentr_gssim.pdf},
keywords = {resource_management, scheduling}
}
@article{Pascual2009CooperationinMultiOrganization,
author = {F. Pascual and K. Rzadca and D. Trystram},
title = {Cooperation in Multi-Organization Scheduling},
journal = {Concurrency\&Computation: Practice and Experience},
year = {2009},
volume = {21},
pages = { 905-921 },
publisher = {Wiley InterScience},
abstract = {The distributed nature of the grid results in the problem of scheduling
parallel jobs produced by several independent organizations that
have partial control over the system. We consider systems in which
each organization owns a cluster of processors. Each organization
wants its tasks to be completed as soon as possible. In this paper,
we model an off-line system consisting of N identical clusters of
m processors. We show that it is always possible to produce a collaborative
solution that respects participants' selfish goals, at the same time
improving the global performance of the system. We propose an algorithm
(called MOLBA) with a guaranteed worst-case performance ratio on
the global makespan, equal to 4. Next, we show that a better bound
(equal to 3) can be obtained in a specific case when the last completed
job requires at most m-2 processors. Then, we derive another algorithm
(called ILBA) that in practice improves the proposed, guaranteed
solution by further balancing the schedules. Finally, by an extensive
evaluation by simulation, we show that the algorithms are efficient
on typical instances.},
doi = {10.1002/cpe.v21:7},
pdf = {papers/cooperation_multiorg_scheduling-conccomp09.pdf},
issue = { 7 },
keywords = {resource_management, scheduling, approximation algorithms, fairness}
}
@inproceedings{Pascual2007CooperationinMultiOrganization,
author = {F. Pascual and K. Rzadca and D. Trystram},
title = {Cooperation in Multi-Organization Scheduling},
booktitle = {Euro-Par 2007 Proceedings},
year = {2007},
volume = {4641},
series = {LNCS},
pages = {224--233},
publisher = {Springer},
note = {Conference version of \cite{Pascual2009CooperationinMultiOrganization}},
doi = {10.1007/978-3-540-74466-5_25},
keywords = {resource_management, scheduling}
}
@inproceedings{Roeblitz2006PlacementofReservations,
author = {T. Roeblitz and K. Rzadca},
title = {On the Placement of Reservations into Job Schedules},
booktitle = {Euro-Par 2006 Proceedings},
year = {2006},
volume = {4128},
series = {LNCS},
pages = {198--210},
publisher = {Springer},
abstract = {We present a new method for determining placements of flexible reservation
requests into a schedule. For each considered placement the what-if
method inserts a placeholder into the schedule and simulates the
processing of batch jobs currently known to the system. Each placement
is evaluated wrt. well-known scheduling metrics. This information
may be used by a Grid reservation service to choose the most likely
successful placement of a reservation. According to the results of
extensive simulations, the what-if method grants more reservations
and improves the performance of local jobs compared to our previously
used load method.},
doi = {10.1007/11823285_21},
pdf = {papers/reservation_scheduling_europar2006.pdf},
keywords = {resource_management, scheduling, reservations}
}
@phdthesis{Rzadca2008ResourceManagementModels,
author = {Rzadca, K.},
title = {Resource Management Models and Algorithms for Multi-Organizational
Grids},
school = {INPG and PJIIT},
year = {2008},
pdf = {papers/phd.pdf},
keywords = {scheduling, resource_management},
owner = {krz},
timestamp = {2009.12.02}
}
@inproceedings{Rzadca2007SchedulinginMultiOrganization,
author = {K. Rzadca},
title = {Scheduling in Multi-Organization Grids: Measuring the Inefficiency
of Decentralization},
booktitle = {PPAM 2007 Proceedings},
year = {2007},
number = {4967},
series = {LNCS},
pages = {1048-1058},
publisher = {Springer},
abstract = {We present a novel, generic model of the grid that emphasises the
roles of individual organizations that form the system. The model
allows us to study the global behaviour of the system without introducing
external forms of recompense. Using game-theory and equitable multicriteria
optimization, we study three diverse types of computational grids:
an off-line system with dedicated uniprocessors, an on-line system
with divisible load and an off-line system
with parallel jobs. Results show that, unless strong assumptions are
made, the complete decentralization leads to a significant loss of
performance.},
doi = {10.1007/978-3-540-68111-3_111},
pdf = {papers/multi_org_scheduling-ppam2007.pdf},
keywords = {resource_management, scheduling, fairness, game theory, price of anarchy}
}
@inproceedings{Rzadca2006EvaluatingQualityof,
author = {K. Rzadca},
title = {Evaluating the Quality of Maximum Variance Cluster Algorithms},
booktitle = {ICCVG 2004 (International Conference on Computer Vision and Graphics)
Proceedings},
year = {2006},
volume = {32},
series = {Computational Imaging and Vision},
pages = {981--986},
publisher = {Springer},
keywords = {data_clustering}
}
@inproceedings{Rzadca2010ReplicaPlacementin,
author = {Rzadca, Krzysztof and Datta, Anwitaman and Buchegger, Sonja},
title = {Replica Placement in P2P Storage: Complexity and Game Theoretic Analyses},
booktitle = {ICDCS 2010, The 30th International Conference on Distributed Computing
Systems, Proceedings},
year = {2010},
pages = {599-609},
address = {Los Alamitos, Washington, Tokyo},
publisher = {IEEE Computer Society},
abstract = {In peer-to-peer storage systems, peers replicate each others' data
in order to increase availability. If the matching is done centrally, the
algorithm can optimize data availability in an equitable manner for
all participants. However, if matching is decentralized, the peers'
selfishness can greatly alter the results, leading to performance
inequities that can render the system unreliable and thus ultimately
unusable.
We analyze the problem using both theoretical approaches (complexity
analysis for the centralized system, game theory for the
decentralized one) and simulation. We prove that the problem of
optimizing availability in a centralized system is NP-hard. In
decentralized settings, we show that the rational behavior of
selfish peers will be to replicate only with similarly-available
peers. Compared to the socially-optimal solution, highly available
peers have their data availability increased at the expense of
decreased data availability for less available peers. The price of
anarchy is high: unbounded in one model, and linear with the number
of time slots in the second model.
We also propose centralized and decentralized heuristics that,
according to our experiments, converge fast in the average case.
The high price of anarchy means that a completely decentralized
system could be too hostile for peers with low availability,
who could never achieve satisfying replication parameters. Moreover,
we experimentally show that even explicit consideration and
exploitation of diurnal patterns of peer availability has a small
effect on the data availability---except when the system has truly
global scope. Yet a fully centralized system is infeasible, not only
because of problems in information gathering, but also the
complexity of optimizing availability. The solution to this dilemma
is to create system-wide cooperation rules that allow a
decentralized algorithm, but also limit the selfishness of the
participants.},
doi = {10.1109/ICDCS.2010.67},
pdf = {papers/serenity_icdcs.pdf},
keywords = {p2p, p2p_storage, game theory, price of anarchy},
owner = {krz},
timestamp = {2010.02.26}
}
@inproceedings{Rzadca2003IncrementallyAssessingCluster,
author = {K. Rzadca and F. Ferri},
title = {Incrementally Assessing Cluster Tendencies with a Maximum Variance
Cluster Algorithm},
booktitle = {IbPRIA (Iberian Conference on Pattern Recognition and Image Analysis)
Proceedings},
year = {2003},
volume = {2653},
series = {LNCS},
pages = {868--875},
publisher = {Springer},
pdf = {papers/imva.pdf},
keywords = {data_clustering}
}
@inproceedings{Rzadca2005HeterogeneousMultiprocessorScheduling,
author = {K. Rzadca and F. Seredynski},
title = {Heterogeneous Multiprocessor Scheduling with Differential Evolution},
booktitle = {IEEE CEC 2005 (Congress of Evolutionary Computation) Proceedings},
year = {2005},
pages = {2840--2847},
publisher = {IEEE Computer Society},
doi = {10.1109/CEC.2005.1555051},
pdf = {papers/scheduling-de.pdf},
keywords = {scheduling, resource_management}
}
@article{Rzadca2010MulticastOverlay,
author = {Rzadca, Krzysztof. and Tan Teck, Jackson and Datta, Anwitaman},
title = {Multi-Objective Optimization of Multicast Overlay for Collaborative
Applications},
journal = {Computer Networks},
year = {2010},
volume = {54},
pages = {1986-2005},
number = {12},
publisher = {Elsevier},
abstract = {Current implementations of real-time collaborative applications rely on a dedicated infrastructure to carry out all synchronizing and communication functions, and require all end nodes to communicate directly with and through the central server. In this paper, we investigate scenarios, in which the most resource intensive functionality of continuous communication among collaborators to disseminate changes is decentralized, utilizing the end users as relays. We observe that communication characteristics of real-time collaboration makes use of existing multicast mechanisms unsuitable. As collaborative editing sessions are typically long, we are able to gather and then use additional parameters of nodes (their instabilities and frequency of sending updates) and communication links (latencies and average costs). We identify several criteria to determine the quality of a multicast tree: cost, latency and instability. We analyze the complexity of these problems and propose algorithms to optimize the communication topology. We also consider the multiobjective problem in which we search for a tree that results in a good trade-off between these measures. Validation of algorithms on numerous graphs shows that it is important to consider the multiobjective problem, as optimal solutions for one performance measure can be far from optimal values of the others. Finally, we briefly present an implementation of a communication library that uses the proposed algorithms to periodically adjust the dissemination tree. },
doi = {10.1016/j.comnet.2010.05.018},
pdf = {papers/momocomm-comnet.pdf},
keywords = {p2p, communication topology, collaborative applications, multi-objective
optimization},
owner = {krz},
timestamp = {2010.08.29}
}
@article{Rzadca2009PromotingCooperationin,
author = {K. Rzadca and D. Trystram},
title = {Promoting Cooperation in Selfish Computational Grids},
journal = {European Journal of Operational Research},
year = {2009},
volume = {199},
pages = {647-657},
publisher = {Elsevier},
abstract = {In distributed computing the recent paradigm shift from centrally-owned
clusters to organizationally distributed computational grids introduces
a number of new challenges in resource management and scheduling.
In this work, we study the problem of Selfish Load Balancing which
extends the well-known Load Balancing (LB) problem to scenarios in
which each processor is concerned only with the performance of its
local jobs. We propose a simple mathematical model for such systems
and a novel function for computing the cost of the execution of foreign
jobs. Then, we use the game-theoretic framework to analyze the model
in order to compute the expected result of LB performed in a grid
formed by two clusters. We show that, firstly, LB is a socially-optimal
strategy, and secondly, for similarly loaded clusters, it is sufficient
to collaborate during longer time periods in order to make LB the
dominant strategy for each cluster. However, we show that if we allow
clusters to make decisions depending on their current queue length,
LB will never be performed. Then, we propose a LB algorithm which
balances the load more equitably, even in the presence of overloaded
clusters. Our algorithms do not use any external forms of compensation
(such as money). The load is balanced only by considering the parameters
of execution of jobs. This analysis is assessed experimentally by
simulation, involving scenarios with multiple clusters and heterogeneous
load.},
doi = {10.1016/j.ejor.2007.06.067},
pdf = {papers/promoting_cooperation-ejor.pdf},
issue = { 3 },
keywords = {resource_management, scheduling, game theory}
}
@inproceedings{Rzadca2006BriefAnnouncementPromoting,
author = {K. Rzadca and D. Trystram},
title = {Brief Announcement: Promoting Cooperation in Selfish Grids},
booktitle = {SPAA 2006 (Annual ACM Symposium on Parallelism in Algorithms \& Architectures)
Proceedings},
year = {2006},
pages = {332},
publisher = {ACM Press},
note = {Conference version of \cite{Rzadca2009PromotingCooperationin}},
keywords = {resource_management, scheduling}
}
@inproceedings{Rzadca2007FairGameTheoreticResource,
author = {K. Rzadca and D. Trystram and A. Wierzbicki},
title = {Fair Game-Theoretic Resource Management in Dedicated Grids},
booktitle = {IEEE International Symposium on Cluster Computing and the Grid (CCGRID
2007), Proceedings},
year = {2007},
publisher = {IEEE Computer Society},
abstract = {We study two problems directly resulting from organizational decentralization
of the Grid. Firstly, the problem of fair scheduling in systems in
which the grid scheduler has complete control of processors' schedules.
Secondly, the problem of fair and feasible scheduling in decentralized
case, in which the grid scheduler can only suggest a schedule, which
can be later modified by a processor's owner. Using game theory,
we show that scheduling in decentralized case is analogous to the
Prisoner's Dilemma game. Moreover, the Nash equilibrium results in
significant performance drop. Therefore, a strong community control
is required to achieve acceptable performance.},
doi = {10.1109/CCGRID.2007.52},
pdf = {papers/fair_game_theoretic_resource-ccgrid2007.pdf},
keywords = {resource_management, scheduling, fairness, game theory, price of anarchy}
}
@inproceedings{Rzadca2009MulticastTreesCollaborative,
author = {K. Rzadca and J. Tan Teck Yong and A. Datta},
title = {Multicast Trees for Collaborative Applications},
booktitle = {9th IEEE/ACM International Symposium on Cluster Computing and the
Grid, Proceedings},
year = {2009},
pages = {60-67},
publisher = {IEEE Computer Society},
abstract = {Current implementations of real-time collaborative applications rely
on a dedicated infrastructure to carry out all synchronizing and
communication
functions, and require all end nodes to communicate directly with
and through the central server. In this paper, we investigate an
architecture, in which the most resource intensive functionality
of continuous communication among collaborators to disseminate changes
is decentralized, utilizing the end users as relays. We observe that
communication characteristics of real-time collaboration makes use
of existing multicast mechanisms unsuitable. As collaborative editing
sessions are typically long, we are able to gather and then use additional
parameters of nodes (their instabilities and frequency of sending
updates) and communication links (latencies and average costs). We
identify several criteria to determine the quality of a multicast
tree: cost, latency and instability. We analyze the complexity of
these problems and propose algorithms to optimize the communication
topology. We also consider the multiobjective problem in which we
search for a tree that results in a good trade-off between these
measures. Validation of algorithms on numerous graphs shows that
it is important to consider the multiobjective problem, as optimal
solutions for one performance measure can be far from optimal values
of the others.},
doi = {10.1109/CCGRID.2009.38},
pdf = {papers/multicast_trees-ccgrid09.pdf},
keywords = {p2p, communication topology, collaborative applications, multi-objective
optimization},
owner = {krz},
timestamp = {2009.08.18}
}
@incollection{Wierzbicki2009SupportingCollaborationand,
author = {Wierzbicki, Adam and Datta, Anwaitaman. and Zaczek, Lukasz and Rzadca,
Krzysztof},
title = {Supporting Collaboration and Creativity Through Mobile P2P Computing},
booktitle = {Handbook of Peer-to-Peer Networking},
publisher = {Springer},
year = {2010},
editor = {Shen, X. and Yu, H. and Buford, J. and Akon, M.},
pages = {1367-1400},
address = {New York Dordrecht Heidelberg London},
doi = {10.1007/978-0-387-09751-0},
keywords = {p2p},
owner = {krz},
timestamp = {2009.08.18}
}
@inproceedings{Wojtyla2006ArtificialImmuneSystems,
author = {G. Wojtyla and K. Rzadca and F. Seredynski},
title = {Artificial Immune Systems Applied to Multiprocessor Scheduling},
booktitle = {PPAM 2005 Proceedings},
year = {2006},
volume = {3911},
series = {LNCS},
pages = {904--911},
publisher = {Springer},
keywords = {resource_management, scheduling}
}
@inproceedings{Xin2009StereoTrustgroupbased,
author = {Liu Xin and A. Datta and K. Rzadca and Lim Ee-Peng},
title = {StereoTrust: A Group Based Personalized Trust Model},
booktitle = {CIKM 2009, The 18th ACM Conference on Information and Knowledge Management,
Proceedings},
year = {2009},
pages = {7-16},
publisher = {ACM Press},
abstract = {Trust plays important roles in diverse decentralized environments,
including our society at large. Computational trust models help to,
for instance, guide users' judgements in online auction sites about
other users; or determine quality of contributions in web 2.0 sites.
Most of the existing trust models, however, require historical information
about past behavior of a specific agent being evaluated - information
that is not always available. In contrast, in real life interactions
among users, in order to make the first guess about the trustworthiness
of a stranger, we commonly use our "instinct" - essentially stereotypes
developed from our past interactions with "similar" people.
We propose StereoTrust, a computational trust model inspired by real
life stereotypes. A user forms stereotypes using her previous transactions
with other agents. A stereotype contains certain features of agents
and an expected outcome of the transaction. These features can be
taken from agents' profile information, or agents' observed behavior
in the system. When facing a stranger, the stereotypes matching stranger's
profile are aggregated to derive his expected trust. Additionally,
when some information about stranger's previous transactions is available,
StereoTrust uses it to refine the stereotype matching.
According to our experiments, StereoTrust compares favorably with
existing trust models that use different kind of information and
more complete historical information. Moreover, because evaluation
is done according to user's personal stereotypes, the system is completely
distributed and the result obtained is personalized.
StereoTrust can be used as a complimentary mechanism to provide the
initial trust value for a stranger, especially when there is no trusted,
common third parties.},
doi = {10.1145/1645953.1645958},
pdf = {papers/stereotrust_cikm09.pdf},
keywords = {trust}
}
This file was generated by bibtex2html 1.96.