[GNUnet-SVN] r26044 - gnunet-java

[gnunet]

Author: dold
Date: 2013-02-07 11:48:22 +0100 (Thu, 07 Feb 2013)
New Revision: 26044

Modified:
   gnunet-java/ISSUES
Log:
issues


Modified: gnunet-java/ISSUES
===================================================================
--- gnunet-java/ISSUES  2013-02-06 18:23:34 UTC (rev 26043)
+++ gnunet-java/ISSUES  2013-02-07 10:48:22 UTC (rev 26044)
@@ -1,71 +1,73 @@
 
-* what currently (somewhat) works:
- * connecting with the right topology
- * exchanging strata, ibfs, values
+* Writing down the details: How / How formal should I do it?
 
-BUT currently sometimes crashes mesh (=>segfault), very hard to reproduce
+* IBF implemente with 8-bit count, 64-bit key, 32-bit checksum
+ * improved decoding algorithm by checking locations generated by hash in 
(supposedly) pure bucket
+ * 1mio elements take ~25sec on my machine, scales linearly
+  * performance in the last version was better, because now there's one more 
call to CRYPTO_hash to generate
+    the ~4 32-bit indices from the 64-bit key
 
-* what's next
- * consensus groups
- * retries, when IBFs don't decode
-  * do we double the size, or change the salt?
+(
+* one problems with IBFs that is solvable (solution by original authors in 
another paper):
+ * inserting the same element twice poisons the associated buckets
+ * .. but that is not really a problem, as we just won't insert an element 
twice
+ * problem with hash-collisions though
+ * author's solution: don't XOR, add, check for divisibility of id-sum by count
+)
 
+* the order of the IBF should is its salt
+ * partially solves the above collision problem
 
-* what if another peer wants to join a session that the *client* has not 
joined yet?
- * appers often with large number of peers and gnunet-consensus
+* mapping between keys<->hashcodes
+ * i don't think there is the need for any *additional* mapping,
+   just map uint64_t to GNUNET_CONSENSUS_Element
+ * there's now ibf_key_to_hashcode and ibf_hashcode_to_key
+  * endianess wrt hashcode: how do i get the first 64bit in a 
platform-independent way?
+   * ok, found GNUNET_ntohll
 
-* memory errors in c are too much fun to debug!
- * then valgrind saved a lot of time
-  * but the stack traces are strange, how do I disable optimization?
+* why doesn't multihashmap_contains return an integer (=how many elements does 
the key have)?
+ * would be nice, so I can pre-allocate an array
 
-==19221== Conditional jump or move depends on uninitialised value(s)
-==19221==    at 0x5D054E0: inflateReset2 (in 
/lib/x86_64-linux-gnu/libz.so.1.2.3.4)
-==19221==    by 0x5D055D8: inflateInit2_ (in 
/lib/x86_64-linux-gnu/libz.so.1.2.3.4)
-==19221==    by 0x5D004F5: uncompress (in 
/lib/x86_64-linux-gnu/libz.so.1.2.3.4)
-==19221==    by 0x529F7A3: helper_mst (testbed_api.c:1313)
-==19221==    by 0x4E78C10: GNUNET_SERVER_mst_receive (server_mst.c:265)
-==19221==    by 0x4E66C65: helper_read.part.0 (helper.c:302)
-==19221==    by 0x4E74F80: GNUNET_SCHEDULER_run (scheduler.c:597)
-==19221==    by 0x4E6E87F: GNUNET_PROGRAM_run2 (program.c:273)
-==19221==    by 0x4E6EA69: GNUNET_PROGRAM_run (program.c:308)
-==19221==    by 0x52ADD6A: GNUNET_TESTBED_test_run (testbed_api_test.c:153)
-==19221==    by 0x400E9E: run (gnunet-consensus.c:296)
-==19221==    by 0x4E6E946: GNUNET_PROGRAM_run2 (program.c:278)
+* assume we multiple CONSENSUS_Elements in one message
+ * how do we handle alignment?
 
+* handling 64-bit collisions
+ * just send/request all values associated with the key
 
----------------------------------------------------
+* stream api
+ * write is not very useful, as we have to either allocate a buffer or point 
it to an existing one
+ * but, in the second case, we can't splice together information from multiple 
places
+   as we have to wait for the continuation.
+ * stuff like sending all values for a key in a multihashmap gets messy
 
-==20385== Invalid read of size 4
-==20385==    at 0x651E100: send_connect (mesh_api.c:803)
-==20385==    by 0x65232E7: reconnect_cbk (mesh_api.c:876)
-==20385==    by 0x4E74F80: GNUNET_SCHEDULER_run (scheduler.c:597)
-==20385==    by 0x4E7F6C5: GNUNET_SERVICE_run (service.c:1815)
-==20385==    by 0x401475: main (gnunet-service-consensus.c:1827)
-==20385==  Address 0x7fefef830 is not stack'd, malloc'd or (recently) free'd
-==20385== 
+* what are min-wise hashes, and does it make sense to use them for higher 
(=less elements) strata, as in the paper?
+ * I know what they are by know
+ * i think implementing them is very low priority
 
---------------------------------------------
+* how do I expose the key in the IBF api? currently it's pass-by-value 
uint64_t,
+  which I like, as I don't see a need to hide the type.
 
+* how well would a group-selection based on repeatedly adding the peer with
+  the greatest similarity to all others work?
+ * => greedy algorithm
+ * what are pathological cases where it works badly?
+  * ... and can those be exploited?
+ * could it be good enough for most cases?
+ * easy to implement, no combinatorial explosion
+ * it's easy to compute pairwise similarity with strata estimators of a2a round
 
-* something i use printf's stuff, how do i find out what?
- * looks like output from mesh, seen while running mesh test cases
- * numbers, like 1228
+* do we agree that the client should only get one consensus group on conclude?
 
+conclude process:
+ * (implement later) exponential exchange
+ * a2a exchange
+ * a2a inventory
+ * (implement later) inventory agreement / fraud detection
+ * group finding
 
-* currently, the consensus protocol implementation is a bit chaotic, any ideas 
on what to improve?
- * except for the usual, comments etc.
+anything to add?
 
-* are client acks necessary now?
 
 
 
-Enumerating Groups:
-* would it make sense only to _not include_ a peer into a group if we'd
-  lose >x elements? this makes the search space smaller, but we may lose some 
votes.
 
-For voting:
-* does first generating all groups, and then agreeing on one of them even make 
sense?
-* 
http://csis.bits-pilani.ac.in/faculty/murali/aos-09/papers/Byzantine%20Agreement%20in%20the%20Full-Information%20Model%20in%20O-log-n%20Rounds%20-%20Ben-Or%20Vaikuntanathan%20Pavlov.pdf
- * describes the graded broadcast with n^2 communication complexity
- * can we somehow use these ideas?
-