Consider a resource sharing system in peer-to-peer(P2P)networks where peers act as both suppliers and customers of resources.Each participant obtains the utility by exchanging its resources with its neighbors accordin...Consider a resource sharing system in peer-to-peer(P2P)networks where peers act as both suppliers and customers of resources.Each participant obtains the utility by exchanging its resources with its neighbors according to the preset rules.A series of recent work considered a market equilibrium mechanism and studied the robustness of such a protocol against the Sybil attack strategy,which is a kind of grave threat in P2P system.The concept of incentive ratio is applied to measure how much a participant could gain from the Sybil attack by splitting its identity and reconstructing its communication connections with others.Although Chen et al.(Incentive ratios of a proportional sharing mechanism in resource sharing.In:23rd Annual International Computing and Combinatorics Conference,2017)proved the incentive ratio on cycle networks is bounded by 2 and 4,an open problem is left that is how to narrow the gap furthermore.In this paper,we improve the upper bound of incentive ratio on cycle networks to 3.This improvement comes from a better understanding of the market equilibrium mechanism and a novel analysis technique for the improvement in utility.展开更多
The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes f...The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.展开更多
基金the National Natural Science Foundation of China(Nos.11871366 and 61803279).
文摘Consider a resource sharing system in peer-to-peer(P2P)networks where peers act as both suppliers and customers of resources.Each participant obtains the utility by exchanging its resources with its neighbors according to the preset rules.A series of recent work considered a market equilibrium mechanism and studied the robustness of such a protocol against the Sybil attack strategy,which is a kind of grave threat in P2P system.The concept of incentive ratio is applied to measure how much a participant could gain from the Sybil attack by splitting its identity and reconstructing its communication connections with others.Although Chen et al.(Incentive ratios of a proportional sharing mechanism in resource sharing.In:23rd Annual International Computing and Combinatorics Conference,2017)proved the incentive ratio on cycle networks is bounded by 2 and 4,an open problem is left that is how to narrow the gap furthermore.In this paper,we improve the upper bound of incentive ratio on cycle networks to 3.This improvement comes from a better understanding of the market equilibrium mechanism and a novel analysis technique for the improvement in utility.
基金Supported by the National Natural Science Foundation of China(No.11301475,11126202,11171207)the Nature Science Foundation of Zhejiang Province(No.LQ12A01011)partially supported by The Hong Kong CERG Research Fund PolyU 5515/10H
文摘The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.
