IEEE IPDPS 2011
TechTalks from event: IEEE IPDPS 2011
Note 1: Only plenary sessions (keynotes, panels, and best papers) are accessible without requiring login. For other talks, you will need to login using the email you registered for IPDPS 2011. Note 2: Many of the talks (those without a thumbnail next to the their description below) are yet to be uploaded. Some of them were not recorded because of technical problems. We are working with the corresponding authors to upload the selfrecorded versions here. We sincerely thank all authors for their efforts in making their videos available.
SESSION 13: Distributed Algorithms and Models

Adding a referee to an interconnection network: What can(not) be computed in one round.In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model de?ned by Babai, Kimmel and Lokam. More precisely, each of these n nodes which only knows its own ID and the IDs of its neighbors is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, â€œdoes G contain a square?â€, â€œdoes G contain a triangle?â€ or â€œIs the diameter of G at most 3?â€ cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs.

Improved Algorithms for the Distributed Trigger Counting ProblemConsider a distributed system with n processors, in which each processor receives some triggers from an external source. The distributed trigger counting (DTC) problem is to raise an alert and report to a user when the number of triggers received by the system reaches w, where w is a userspeci?ed input. The problem has applications in monitoring, global snapshots, synchronizers and other distributed settings. In this paper, we present two decentralized and randomized algorithms for the DTC problem. The ?rst algorithm has message complexity O(n log w) and no processor receives more than O(log w) messages with high probability. It does not provide any bound on the messages sent per processor. This algorithm assumes complete connectivity between the processors. The second algorithm has message complexity O(n log n log w) and no processor exchanges more than O(log n log w) messages with high probability. However, there is a negligible failure probability in raising the alert on receiving w triggers. This algorithm only requires that a constant degree tree be embeddable in the underlying communication graph.

The Weighted Byzantine Agreement ProblemThis paper presents a weighted version of the Byzantine Agreement Problem and its solution under various conditions. In this version, each machine is assigned a weight depending on the application. Instead of assuming that at most f out of N machines fail, the algorithm assumes that the total weight of the machines that fail is at most f/N. When each machine has weight 1/N, this problem reduces to the standard Byzantine Generals Agreement Problem. By choosing weights appropriately, the weighted Byzantine Agreement Problem can be applied to situations where a subset of processes are more trusted. By using weights, the system can reach consensus in the presence of Byzantine failures, even when more than N/3 processes fail, so long as the total weight of the failed processes is less than 1/3. Also, a method to update the weights of the processes after execution of the weighted Byzantine Agreement is given. The update method guarantees that the weight of any correct process is never reduced and the weight of any faulty process, suspected by correct processes whose total weight is at least 1/4, is reduced to 0 for future instances. A short discussion of some weight assignment strategies is also given.

Leveraging Social Networks to Combat Collusion in Reputation Systems for PeertoPeer NetworksIn peertopeer networks (P2Ps), many autonomous peers without preexisting trust relationships share resources with each other. Due to their open environment, the P2Ps usually employ reputation systems to provide guidance in selecting trustworthy resource providers for high reliability and security. However, node collusion impairs the effectiveness of reputation systems in trustworthy node selection. Although some reputation systems have certain mechanisms to counter collusion, the effectiveness of the mechanisms is not suf?ciently high. In this paper, we leverage social networks to enhance the capability of reputation systems in combating collusion. We ?rst analyzed real trace of the reputation system in the Overstock online auction platform which incorporates a social network. The analysis reveals the important impact of the social network on user purchasing and reputation rating patterns. We thus identi?ed suspicious collusion behavior patterns and propose a social network based mechanism, namely SocialTrust, to counter collusion. SocialTrust adaptively adjusts the weight of ratings based on the social distance and interest relationship between peers. Experimental results show that SocialTrust can signi?cantly strengthen the capability of current reputation systems in combating collusion.
 All Sessions
 IPDPS 2011 Keynotes and Panels
 SESSION: Best Papers
 Special NSFSEES Presentation
 Intel Platinum Patron Night
 25th Year IPDPS Celebration
 SESSION 8: Reliability and Security
 SESSION 9: Wireless and Sensor Networks
 SESSION 10: GPU Acceleration
 SESSION 11: Multiprocessing and Concurrency
 SESSION 12: Compilers
 SESSION 13: Distributed Algorithms and Models
 SESSION 14: Parallel Graph and Particle Algorithms
 SESSION 15: Distributed Systems and Networks
 SESSION 16: Programming Environments and Tools
 SESSION 1: Resource Management
 SESSION 17: Parallel Algorithms
 SESSION 2: Communication & I/O Optimization
 SESSION 18: Distributed Systems
 SESSION 3: HardwareSoftware Interaction
 SESSION 19: Storage Systems and Memory
 SESSION 4: Runtime Systems
 SESSION 20: Operating Systems and Resource Management
 SESSION 5: Routing and Communication
 SESSION 6: Self Stabilization and Security
 SESSION 7: Numerical Algorithms
 SESSION 21: Numerical Algorithms
 SESSION 22: Fault Tolerance
 SESSION 23: Resource Utilization
 SESSION 24: Parallel Programming Models and Languages
 SESSION 25: Algorithms for Distributed Computing
 SESSION 26: Scheduling
 SESSION 27: Computational Biology and Simulations
 SESSION 28: Cloud Computing