From c3f354c6fc99424c0b405e65266ee0a8c82dd07d Mon Sep 17 00:00:00 2001
From: Mosharaf Chowdhury <mosharaf@mosharaf-ubuntu.(none)>
Date: Sat, 13 Nov 2010 20:18:48 -0800
Subject: Guide now select random peers to select sources instead of rolling
 statically. Random is good. Deterministic is bad. Well, mostly.

---
 src/scala/spark/Broadcast.scala | 42 +++++++++++++++++++++++++++++------------
 1 file changed, 30 insertions(+), 12 deletions(-)

diff --git a/src/scala/spark/Broadcast.scala b/src/scala/spark/Broadcast.scala
index 2ffc37b4bb..1b3c4e9c48 100644
--- a/src/scala/spark/Broadcast.scala
+++ b/src/scala/spark/Broadcast.scala
@@ -832,9 +832,6 @@ extends BroadcastRecipe  with Logging {
       private var sourceInfo: SourceInfo = null
       private var selectedSources: ListBuffer[SourceInfo] = null
       
-      // Used to select a rolling window of peers from listOfSources
-      private var rollOverIndex = 0
-      
       override def run: Unit = {
         try {
           logInfo ("new GuideSingleRequest is running")
@@ -878,18 +875,39 @@ extends BroadcastRecipe  with Logging {
           return selectedSources
         }
         
-        var curIndex = rollOverIndex
-
         listOfSources.synchronized {
-          do {
-            if (listOfSources(curIndex) != skipSourceInfo) { 
-              selectedSources = selectedSources + listOfSources(curIndex)
+          if (listOfSources.size <= BroadcastBT.MaxPeersInGuideResponse) {
+            selectedSources = listOfSources.clone
+          } else {
+            var picksLeft = BroadcastBT.MaxPeersInGuideResponse
+            var alreadyPicked = new BitSet (listOfSources.size)
+            
+            while (picksLeft > 0) {
+              var i = -1
+              
+              do {
+                i = BroadcastBT.ranGen.nextInt (listOfSources.size)
+              } while (alreadyPicked.get(i))
+              
+              var peerIter = listOfSources.iterator        
+              var curPeer = peerIter.next
+              
+              while (i > 0) {
+                curPeer = peerIter.next
+                i = i - 1
+              }
+              
+              selectedSources = selectedSources + curPeer
+              alreadyPicked.set (i)
+              
+              picksLeft = picksLeft - 1
             }
-            curIndex = (curIndex + 1) % listOfSources.size
-          } while (curIndex != rollOverIndex && 
-            selectedSources.size != BroadcastBT.MaxPeersInGuideResponse)
+          }
         }
-        rollOverIndex = curIndex
+        
+        // Remove the receiving source (if present)
+        selectedSources = selectedSources - skipSourceInfo
+        
         return selectedSources
       }
     }    
-- 
cgit v1.2.3