[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r24832 - in gnunet-java: . consensus
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r24832 - in gnunet-java: . consensus |
|
Date: |
Thu, 8 Nov 2012 10:50:08 +0100 |
Author: dold
Date: 2012-11-08 10:50:08 +0100 (Thu, 08 Nov 2012)
New Revision: 24832
Added:
gnunet-java/consensus/
gnunet-java/consensus/GPL.txt
gnunet-java/consensus/Makefile
gnunet-java/consensus/README
gnunet-java/consensus/constants.cpp
gnunet-java/consensus/constants.h
gnunet-java/consensus/example_setA.txt
gnunet-java/consensus/example_setB.txt
gnunet-java/consensus/mainfile.cpp
gnunet-java/consensus/node.cpp
gnunet-java/consensus/node.h
gnunet-java/consensus/prob_recon_support.cpp
gnunet-java/consensus/prob_recon_support.h
gnunet-java/consensus/prob_reconcile.cpp
gnunet-java/consensus/prob_reconcile.h
gnunet-java/consensus/reconciled_set.cpp
gnunet-java/consensus/reconciled_set.h
gnunet-java/consensus/socket.cpp
gnunet-java/consensus/socket.h
gnunet-java/consensus/usage.txt
Modified:
gnunet-java/ISSUES
Log:
Modified: gnunet-java/ISSUES
===================================================================
--- gnunet-java/ISSUES 2012-11-08 01:59:00 UTC (rev 24831)
+++ gnunet-java/ISSUES 2012-11-08 09:50:08 UTC (rev 24832)
@@ -81,22 +81,31 @@
--------------------------------------------------------------
-* discuss PKIs
- * I don't really know where to start there
- * ePA would be quite interesing, but again, where to start?
- * WoT:
- * GPG itself has no API, but there's
http://www.gnupg.org/related_software/gpgme/
- * whole PKI in java http://www.ejbca.org/download.html
+some relevant reconciliation/consensus papers:
+https://gnunet.org/node/2014
+https://gnunet.org/node/2015
-* problem with statistics_watch unit case
- * service does not respond to restart! it should be killed afer a timeout ...
- * otherwise we can't simulate failure
+* discuss consent API
+ * how is a consent group formed?
+* how much of C++ should we use?
+ * only to interface NTL or also for the implementation?
+* existing recon implementation
+ * compiles now, with make, not yet autotools (I'm not very familiar with
autotools, yet!, yet!))
+ * prob_reconcile and prob_recon_support seem very useful (implementing the
basic set reconciliation)
+ * reconciled_set implements partitioning (useful => expected linear time),
+ interleaved with socket operations
+
+
* organizing test cases
* no support for JUnit mostly
-
-
-
+* not really relevant right now:
+ * discuss PKIs
+ * I don't really know where to start there
+ * ePA would be quite interesing, but again, where to start?
+ * WoT:
+ * GPG itself has no API, but there's
http://www.gnupg.org/related_software/gpgme/
+ * whole PKI in java http://www.ejbca.org/download.html
Added: gnunet-java/consensus/GPL.txt
===================================================================
--- gnunet-java/consensus/GPL.txt (rev 0)
+++ gnunet-java/consensus/GPL.txt 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,340 @@
+ GNU GENERAL PUBLIC LICENSE
+ Version 2, June 1991
+
+ Copyright (C) 1989, 1991 Free Software Foundation, Inc.
+ 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+ Preamble
+
+ The licenses for most software are designed to take away your
+freedom to share and change it. By contrast, the GNU General Public
+License is intended to guarantee your freedom to share and change free
+software--to make sure the software is free for all its users. This
+General Public License applies to most of the Free Software
+Foundation's software and to any other program whose authors commit to
+using it. (Some other Free Software Foundation software is covered by
+the GNU Library General Public License instead.) You can apply it to
+your programs, too.
+
+ When we speak of free software, we are referring to freedom, not
+price. Our General Public Licenses are designed to make sure that you
+have the freedom to distribute copies of free software (and charge for
+this service if you wish), that you receive source code or can get it
+if you want it, that you can change the software or use pieces of it
+in new free programs; and that you know you can do these things.
+
+ To protect your rights, we need to make restrictions that forbid
+anyone to deny you these rights or to ask you to surrender the rights.
+These restrictions translate to certain responsibilities for you if you
+distribute copies of the software, or if you modify it.
+
+ For example, if you distribute copies of such a program, whether
+gratis or for a fee, you must give the recipients all the rights that
+you have. You must make sure that they, too, receive or can get the
+source code. And you must show them these terms so they know their
+rights.
+
+ We protect your rights with two steps: (1) copyright the software, and
+(2) offer you this license which gives you legal permission to copy,
+distribute and/or modify the software.
+
+ Also, for each author's protection and ours, we want to make certain
+that everyone understands that there is no warranty for this free
+software. If the software is modified by someone else and passed on, we
+want its recipients to know that what they have is not the original, so
+that any problems introduced by others will not reflect on the original
+authors' reputations.
+
+ Finally, any free program is threatened constantly by software
+patents. We wish to avoid the danger that redistributors of a free
+program will individually obtain patent licenses, in effect making the
+program proprietary. To prevent this, we have made it clear that any
+patent must be licensed for everyone's free use or not licensed at all.
+
+ The precise terms and conditions for copying, distribution and
+modification follow.
+
+ GNU GENERAL PUBLIC LICENSE
+ TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+ 0. This License applies to any program or other work which contains
+a notice placed by the copyright holder saying it may be distributed
+under the terms of this General Public License. The "Program", below,
+refers to any such program or work, and a "work based on the Program"
+means either the Program or any derivative work under copyright law:
+that is to say, a work containing the Program or a portion of it,
+either verbatim or with modifications and/or translated into another
+language. (Hereinafter, translation is included without limitation in
+the term "modification".) Each licensee is addressed as "you".
+
+Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope. The act of
+running the Program is not restricted, and the output from the Program
+is covered only if its contents constitute a work based on the
+Program (independent of having been made by running the Program).
+Whether that is true depends on what the Program does.
+
+ 1. You may copy and distribute verbatim copies of the Program's
+source code as you receive it, in any medium, provided that you
+conspicuously and appropriately publish on each copy an appropriate
+copyright notice and disclaimer of warranty; keep intact all the
+notices that refer to this License and to the absence of any warranty;
+and give any other recipients of the Program a copy of this License
+along with the Program.
+
+You may charge a fee for the physical act of transferring a copy, and
+you may at your option offer warranty protection in exchange for a fee.
+
+ 2. You may modify your copy or copies of the Program or any portion
+of it, thus forming a work based on the Program, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+
+ a) You must cause the modified files to carry prominent notices
+ stating that you changed the files and the date of any change.
+
+ b) You must cause any work that you distribute or publish, that in
+ whole or in part contains or is derived from the Program or any
+ part thereof, to be licensed as a whole at no charge to all third
+ parties under the terms of this License.
+
+ c) If the modified program normally reads commands interactively
+ when run, you must cause it, when started running for such
+ interactive use in the most ordinary way, to print or display an
+ announcement including an appropriate copyright notice and a
+ notice that there is no warranty (or else, saying that you provide
+ a warranty) and that users may redistribute the program under
+ these conditions, and telling the user how to view a copy of this
+ License. (Exception: if the Program itself is interactive but
+ does not normally print such an announcement, your work based on
+ the Program is not required to print an announcement.)
+
+These requirements apply to the modified work as a whole. If
+identifiable sections of that work are not derived from the Program,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works. But when you
+distribute the same sections as part of a whole which is a work based
+on the Program, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Program.
+
+In addition, mere aggregation of another work not based on the Program
+with the Program (or with a work based on the Program) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+
+ 3. You may copy and distribute the Program (or a work based on it,
+under Section 2) in object code or executable form under the terms of
+Sections 1 and 2 above provided that you also do one of the following:
+
+ a) Accompany it with the complete corresponding machine-readable
+ source code, which must be distributed under the terms of Sections
+ 1 and 2 above on a medium customarily used for software interchange; or,
+
+ b) Accompany it with a written offer, valid for at least three
+ years, to give any third party, for a charge no more than your
+ cost of physically performing source distribution, a complete
+ machine-readable copy of the corresponding source code, to be
+ distributed under the terms of Sections 1 and 2 above on a medium
+ customarily used for software interchange; or,
+
+ c) Accompany it with the information you received as to the offer
+ to distribute corresponding source code. (This alternative is
+ allowed only for noncommercial distribution and only if you
+ received the program in object code or executable form with such
+ an offer, in accord with Subsection b above.)
+
+The source code for a work means the preferred form of the work for
+making modifications to it. For an executable work, complete source
+code means all the source code for all modules it contains, plus any
+associated interface definition files, plus the scripts used to
+control compilation and installation of the executable. However, as a
+special exception, the source code distributed need not include
+anything that is normally distributed (in either source or binary
+form) with the major components (compiler, kernel, and so on) of the
+operating system on which the executable runs, unless that component
+itself accompanies the executable.
+
+If distribution of executable or object code is made by offering
+access to copy from a designated place, then offering equivalent
+access to copy the source code from the same place counts as
+distribution of the source code, even though third parties are not
+compelled to copy the source along with the object code.
+
+ 4. You may not copy, modify, sublicense, or distribute the Program
+except as expressly provided under this License. Any attempt
+otherwise to copy, modify, sublicense or distribute the Program is
+void, and will automatically terminate your rights under this License.
+However, parties who have received copies, or rights, from you under
+this License will not have their licenses terminated so long as such
+parties remain in full compliance.
+
+ 5. You are not required to accept this License, since you have not
+signed it. However, nothing else grants you permission to modify or
+distribute the Program or its derivative works. These actions are
+prohibited by law if you do not accept this License. Therefore, by
+modifying or distributing the Program (or any work based on the
+Program), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Program or works based on it.
+
+ 6. Each time you redistribute the Program (or any work based on the
+Program), the recipient automatically receives a license from the
+original licensor to copy, distribute or modify the Program subject to
+these terms and conditions. You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties to
+this License.
+
+ 7. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License. If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Program at all. For example, if a patent
+license would not permit royalty-free redistribution of the Program by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Program.
+
+If any portion of this section is held invalid or unenforceable under
+any particular circumstance, the balance of the section is intended to
+apply and the section as a whole is intended to apply in other
+circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system, which is
+implemented by public license practices. Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+
+ 8. If the distribution and/or use of the Program is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Program under this License
+may add an explicit geographical distribution limitation excluding
+those countries, so that distribution is permitted only in or among
+countries not thus excluded. In such case, this License incorporates
+the limitation as if written in the body of this License.
+
+ 9. The Free Software Foundation may publish revised and/or new versions
+of the General Public License from time to time. Such new versions will
+be similar in spirit to the present version, but may differ in detail to
+address new problems or concerns.
+
+Each version is given a distinguishing version number. If the Program
+specifies a version number of this License which applies to it and "any
+later version", you have the option of following the terms and conditions
+either of that version or of any later version published by the Free
+Software Foundation. If the Program does not specify a version number of
+this License, you may choose any version ever published by the Free Software
+Foundation.
+
+ 10. If you wish to incorporate parts of the Program into other free
+programs whose distribution conditions are different, write to the author
+to ask for permission. For software which is copyrighted by the Free
+Software Foundation, write to the Free Software Foundation; we sometimes
+make exceptions for this. Our decision will be guided by the two goals
+of preserving the free status of all derivatives of our free software and
+of promoting the sharing and reuse of software generally.
+
+ NO WARRANTY
+
+ 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
+FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
+OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
+PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
+OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
+TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
+PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
+REPAIR OR CORRECTION.
+
+ 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
+WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
+REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
+INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
+OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
+TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
+YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
+PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGES.
+
+ END OF TERMS AND CONDITIONS
+
+ How to Apply These Terms to Your New Programs
+
+ If you develop a new program, and you want it to be of the greatest
+possible use to the public, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these terms.
+
+ To do so, attach the following notices to the program. It is safest
+to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least
+the "copyright" line and a pointer to where the full notice is found.
+
+ <one line to give the program's name and a brief idea of what it does.>
+ Copyright (C) <year> <name of author>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+
+Also add information on how to contact you by electronic and paper mail.
+
+If the program is interactive, make it output a short notice like this
+when it starts in an interactive mode:
+
+ Gnomovision version 69, Copyright (C) year name of author
+ Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
+ This is free software, and you are welcome to redistribute it
+ under certain conditions; type `show c' for details.
+
+The hypothetical commands `show w' and `show c' should show the appropriate
+parts of the General Public License. Of course, the commands you use may
+be called something other than `show w' and `show c'; they could even be
+mouse-clicks or menu items--whatever suits your program.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the program, if
+necessary. Here is a sample; alter the names:
+
+ Yoyodyne, Inc., hereby disclaims all copyright interest in the program
+ `Gnomovision' (which makes passes at compilers) written by James Hacker.
+
+ <signature of Ty Coon>, 1 April 1989
+ Ty Coon, President of Vice
+
+This General Public License does not permit incorporating your program into
+proprietary programs. If your program is a subroutine library, you may
+consider it more useful to permit linking proprietary applications with the
+library. If this is what you want to do, use the GNU Library General
+Public License instead of this License.
Added: gnunet-java/consensus/Makefile
===================================================================
--- gnunet-java/consensus/Makefile (rev 0)
+++ gnunet-java/consensus/Makefile 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,45 @@
+# makefile for the reconciliation program
+
+CPP = g++ # use g++ if icc is not available or doesn't work
+CCFLAGS = -Wno-deprecated $(P6)
+INCLUDES = -Igmp-4.1.2 -Intl-5.3.1/include
+LIBRARIES = -Lgmp-4.1.2/lib -Lntl-5.3.1/bin/lib
+LIBFLAGS = $(LIBRARIES) -lntl -lgmp -lm
+
+SOURCES = prob_recon_support.cpp prob_reconcile.cpp node.cpp mainfile.cpp
reconciled_set.cpp constants.cpp socket.cpp
+OBJECTS = prob_recon_support.o prob_reconcile.o node.o reconciled_set.o
constants.o mainfile.o socket.o
+### derived variables
+LOADFLAGS = $(INCLUDES)
+
+### constant variables
+# compiler optimizations - various optimizations for specific architectures
... take your pick.
+SUPERSPARC = -O3 -fstrength-reduce -fthread-jumps -fcse-follow-jumps
-fcse-skip-blocks -felide-constructors -fdelayed-branch -fschedule-insns
-fschedule-insns2 -msupersparc -funroll-loops -fexpensive-optimizations
+P6 = -O4 -fstrength-reduce -fthread-jumps -fcse-follow-jumps -fcse-skip-blocks
-felide-constructors -fschedule-insns -fschedule-insns2 -funroll-loops
-fexpensive-optimizations
+
+### rules
+.SUFFIXES: .C.cpp
+.C.o:
+ -$(CPP) $(CCFLAGS) $(LOADFLAGS) -c $<
+.cpp.o:
+ -$(CPP) $(CCFLAGS) $(LOADFLAGS) -c $<
+
+# main rules
+
+reconcile.exe: Makefile $(OBJECTS) $(SOURCES)
+ -$(CPP) $(CCFLAGS) $(OBJECTS) -o $@ $(LIBFLAGS)
+
+test: reconcile.exe
+ reconcile.exe -steps 10 -confirm on
+
+# auxiliary rules
+mainfile.o: reconciled_set.h prob_reconcile.h prob_recon_support.h socket.h
+reconciled_set.o: reconciled_set.h constants.h node.h prob_reconcile.h
prob_recon_support.h socket.h
+constants.o: constants.h
+node.o: node.h
+prob_reconcile.o: prob_reconcile.h prob_recon_support.h socket.h
+prob_recon_support.o: prob_recon_support.h socket.h
+socket.o: socket.h
+
+# cleanup
+clean:
+ rm -f $(OBJECTS) reconcile.exe
Added: gnunet-java/consensus/README
===================================================================
--- gnunet-java/consensus/README (rev 0)
+++ gnunet-java/consensus/README 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,54 @@
+Practical Set Reconciliation Implementation
+Version: Beta 0.998
+06/22/2004
+Initial implementation by Sachin Agarwal, Boston University (address@hidden)
+ Modifications by Ari Trachtenberg, Boston Unviersity (address@hidden)
+
+Theoretical references: (available at http://people.bu.edu/trachten)
+
+ Original set reconciliation algorithm:
+ Y. Minsky, A. Trachtenberg, and R. Zippel,
+ Set Reconciliation with Nearly Optimal Communication Complexity,
+ IEEE Transactions on Information Theory 49:9, pp. 2213-2218
+ -and-
+ IEEE International Syposium on Information Theory 2001.
+
+ Scalable set reconciliation algorithm:
+ Y. Minsky and A. Trachtenberg, Practical Set Reconciliation,
+ 40th Annual Allerton Conference on Communication, Control, and
Computing,
+ October 2002.
+
+ Implementation on Personal Digital Assistant devices:
+ D. Starobinski, A. Trachtenberg, and S. Agarwal,
+ Efficient PDA synchronization,
+ IEEE Transactions on Mobile Computing 2:1
+
+ A. Trachtenberg, D. Starobinski, and S. Agarwal,
+ Fast PDA Synchronization Using Characteristic Polynomial
Interpolation,
+ IEEE INFOCOM 2002
+
+Installation:
+ Type the following at the unix prompt:
+ ./configure
+ make
+ Additionally, you can test the system with:
+ make test
+
+The configure script will try to install the GMP and NTL libraries
+into subdirectories. Alternatively, the following websites provide more
+details on these standard math libraries:
+
+http://www.swox.com/gmp/#DOC
+http://shoup.net/ntl
+
+Usage:
+ Usage instructions are available in the file usage.txt.
+
+
+------------------------------------------------------------------------
+Note: This release has been tested partially , but not yet methodically.
+Contact the authors with any bugs and / or comments. Please acknowledge
+the authors and/or the theoretical references if you make use of this code.
+
+
+
Added: gnunet-java/consensus/constants.cpp
===================================================================
--- gnunet-java/consensus/constants.cpp (rev 0)
+++ gnunet-java/consensus/constants.cpp 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,7 @@
+// The various constants used throughout the program
+
+#include "constants.h"
+
+const ZZ ZZ_zero=to_ZZ(0);
+const ZZ ZZ_one=to_ZZ(1);
+const ZZ ZZ_two=to_ZZ(2);
Added: gnunet-java/consensus/constants.h
===================================================================
--- gnunet-java/consensus/constants.h (rev 0)
+++ gnunet-java/consensus/constants.h 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,20 @@
+#ifndef CONSTANTS
+#define CONSTANTS
+// Various constants used throughout the program
+#include <NTL/matrix.h>
+#include <NTL/mat_ZZ_p.h>
+#include <NTL/vec_ZZ.h>
+#include <NTL/ZZ.h>
+#include <NTL/ZZ_p.h>
+#include <NTL/vec_ZZ_p.h>
+#include <cmath>
+#include <NTL/vec_vec_ZZ_p.h>
+#include <NTL/ZZ_pX.h>
+#include <NTL/ZZ_pXFactoring.h>
+
+using namespace NTL;
+
+extern const ZZ ZZ_zero; // 0 in ZZ
+extern const ZZ ZZ_one; // 1 in ZZ
+extern const ZZ ZZ_two; // 2 in ZZ
+#endif
Added: gnunet-java/consensus/example_setA.txt
===================================================================
--- gnunet-java/consensus/example_setA.txt (rev 0)
+++ gnunet-java/consensus/example_setA.txt 2012-11-08 09:50:08 UTC (rev
24832)
@@ -0,0 +1 @@
+[100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700
1800 1900 2000 1150 1250 1350 1450]
Added: gnunet-java/consensus/example_setB.txt
===================================================================
--- gnunet-java/consensus/example_setB.txt (rev 0)
+++ gnunet-java/consensus/example_setB.txt 2012-11-08 09:50:08 UTC (rev
24832)
@@ -0,0 +1 @@
+[150 250 350 450 550 650 750 850 950 1500 1150 1250 1350 1450 1550 1650 1750
1850 1950 2500 2100 2200 2300]
Added: gnunet-java/consensus/mainfile.cpp
===================================================================
--- gnunet-java/consensus/mainfile.cpp (rev 0)
+++ gnunet-java/consensus/mainfile.cpp 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,270 @@
+
+/***********************************************************************************
+ * Practical RECONCILIATION
+ * Theoretical references: (available at http://people.bu.edu/trachten)
+ *
+ * Original set reconciliation algorithm:
+ * Y. Minsky, A. Trachtenberg, and R. Zippel,
+ * Set Reconciliation with Nearly Optimal Communication Complexity,
+ * IEEE Transactions on Information Theory 49:9, pp. 2213-2218
+ * -and-
+ * IEEE International Syposium on Information Theory 2001.
+ *
+ * Scalable set reconciliation algorithm:
+ * Y. Minsky and A. Trachtenberg, Practical Set Reconciliation,
+ * 40th Annual Allerton Conference on Communication, Control, and
Computing,
+ * October 2002.
+ *
+ * Implementation on Personal Digital Assistant devices:
+ * D. Starobinski, A. Trachtenberg, and S. Agarwal,
+ * Efficient PDA synchronization,
+ * IEEE Transactions on Mobile Computing 2:1
+ *
+ * A. Trachtenberg, D. Starobinski, and S. Agarwal,
+ * Fast PDA Synchronization Using Characteristic Polynomial
Interpolation,
+ * IEEE INFOCOM 2002
+ *
+ *
+ * Initial implementation by: Sachin Agarwal, address@hidden
+ * modified by: Ari Trachtenberg, address@hidden
+ * Version: 0.998 Beta
+ * Date: 06/23/2004
+
***********************************************************************************/
+
+#include <time.h>
+#include <stdlib.h>
+#include <fstream>
+#include <iostream>
+#include <iomanip>
+#include <NTL/matrix.h>
+#include <NTL/mat_ZZ_p.h>
+#include <NTL/vec_ZZ.h>
+#include <NTL/ZZ.h>
+#include <NTL/ZZ_p.h>
+#include <NTL/vec_ZZ_p.h>
+#include <math.h>
+#include <NTL/vec_vec_ZZ_p.h>
+#include <NTL/ZZ_pX.h>
+#include <NTL/ZZ_pXFactoring.h>
+#include "prob_recon_support.h"
+#include "prob_reconcile.h"
+#include "reconciled_set.h"
+
+// constants
+#define MIN_B 16 // bitsize
+#define MAX_B 16//128 // bitsize
+#define MAX_COMMON 1000 // common elements
+#define MAX_DIFF 300 // differing elements
+#define MIN_PP 2 // partition factor
+#define MAX_PP 10 // partition factor
+#define MIN_MBAR 1 // mbar
+#define MAX_MBAR 10 // mbar
+#define MIN_K 1 // redundancy factor
+#define MAX_K 10 // redundancy factor
+
+// global variables
+clock_t startTime;
+
+vec_ZZ_p ReadSet(char* filename)
+ /*
+ R: Filename of the file containing the set to input
+ E: Reads the set from the file
+ M:
+ Create: 03/17/2003
+ */
+{
+ ifstream fin(filename);
+ vec_ZZ_p rtn_set;
+ fin >> rtn_set;
+ return(rtn_set);
+}
+
+void displayMeas() {
+ // display measurement data
+ long totalComm = reconciled_set::bytes_sent+reconciled_set::bytes_received;
+
+ cout << "-------------------" << endl
+ << "Measurement data:" << endl
+ << " Running time: " << setw(6) << ((float)
((float)(clock()-startTime)/CLOCKS_PER_SEC)) << " seconds." << endl
+ << " setup: " << setw(6) << ((float)
((float)reconciled_set::time_setup/CLOCKS_PER_SEC)) << " seconds." << endl
+ << " communication: " << setw(6) << ((float)
((float)reconciled_set::time_comm/CLOCKS_PER_SEC)) << " seconds." << endl
+ << " reconciliation: " << setw(6) << ((float)
((float)reconciled_set::time_comput/CLOCKS_PER_SEC)) << " seconds." << endl <<
endl
+ << " Communication: " << setw(10) <<(totalComm) << " bytes (" <<
(totalComm/1024) << "K)." << endl
+ << " transmitted: " << setw(10) <<reconciled_set::bytes_sent << "
bytes (" << (reconciled_set::bytes_sent/1024) << "K)." << endl
+ << " received: " << setw(10) <<reconciled_set::bytes_received
<< " bytes (" << (reconciled_set::bytes_received/1024) << "K)." << endl;
+}
+
+inline bool eq(char *s1, char *s2)
+{
+ return(strcmp(s1,s2)==0);
+}
+
+int main(int argc, char** argv)
+{
+ // initialize defaults
+ startTime = clock();
+ int bitsize=16,
+ setCommon=100,
+ setDiff=100,
+ pp=2,
+ mbar=5,
+ numvals=2,
+ steps = 1;
+ bool confirm=false;
+ float pr_addA = 0.5,
+ pr_addB = 0.5,
+ pr_rec = 0.5;
+ SetSeed(to_ZZ(clock())); // random number seed
+
+ // types of commands to execute
+ bool fileSync=false,
+ staticTest=true, // the default operation
+ dynamicTest=false;
+ char *fileA=NULL, *fileB=NULL;
+
+ for (int loop=1; loop<argc; loop++) {
+ // the following commands require an argument
+ bool handled = true; // whether the command has handled
+
+ if (loop+1<argc) {
+ if (eq(argv[loop],"-b")) // number of bits per vector
+ bitsize=(int) atol(argv[++loop]);
+ else if (eq(argv[loop],"-common")) // # of elements common to both sets
+ setCommon=(int) atol(argv[++loop]);
+ else if (eq(argv[loop],"-diff")) // # of elements differing between
both sets
+ setDiff=(int) atol(argv[++loop]);
+ else if (eq(argv[loop],"-p")) // partition factor
+ pp=(int) atol(argv[++loop]);
+ else if (eq(argv[loop],"-mbar")) // maximmum number of differences
on which to run CPISync
+ mbar=(int) atol(argv[++loop]);
+ else if (eq(argv[loop],"-k")) // redundancy factor
+ numvals=(int) atol(argv[++loop]);
+ else if (eq(argv[loop],"-steps")) // # of iterations to run
+ steps=(int) atol(argv[++loop]);
+ else if (eq(argv[loop],"-confirm")) // whether to check tests for
correctness
+ if (strcmp(argv[++loop],"on")==0)
+ confirm=true;
+ else
+ confirm=false;
+ else if (eq(argv[loop],"-pA")) // probability of adding an entry
to A in an iteration
+ pr_addA=(float) atof(argv[++loop]);
+ else if (eq(argv[loop],"-pB")) // probability of adding an entry
to R in an iteration
+ pr_addB=(float) atof(argv[++loop]);
+ else if (eq(argv[loop],"-pR")) // probability of reconciling in
an iteration
+ pr_rec=(float) atof(argv[++loop]);
+ else if (eq(argv[loop],"-fileA")) // first file to synchronize
+ fileA=argv[++loop];
+ else if (eq(argv[loop],"-fileB")) // second file to synchronize
+ fileB=argv[++loop];
+ else handled=false;
+ }
+
+ // the following commands require no arguments
+ if (!handled)
+ if (eq(argv[loop],"-files"))
+ { staticTest=false; dynamicTest=false; fileSync=true;}
+ else if (eq(argv[loop],"-static"))
+ { staticTest=true; dynamicTest=false; fileSync=false;}
+ else if (eq(argv[loop],"-dynamic"))
+ { staticTest=false; dynamicTest=true; fileSync=false;}
+ else {
+ cout << "ERROR: Could not parse '" << argv[loop] << "'." << endl <<
endl;
+ ifstream usage("usage.txt");
+ while (usage.good()) cout << (char) usage.get();
+ usage.close(); cout << endl;
+ return(-1);
+ }
+ }
+
+ // reset measurements
+ reconciled_set::time_comput=0; reconciled_set::time_comm=0;
reconciled_set::time_setup=0;
+ reconciled_set::bytes_sent=0; reconciled_set::bytes_received=0;
+
+ if (fileSync) {
+ if (!fileA || !fileB) {
+ cout << "ERROR: Need to specify two files, -fileA and -fileB for
fileSync." << endl;
+ return(-1);
+ }
+
+ cout << "FILESYNC: synchronizing '" << fileA << "' and '" << fileB << "'"
<< endl;
+ cout << " b = " << bitsize << ", p =" << pp << ", mbar = " <<
mbar << ", k = " << numvals << endl;
+
+ reconciled_set::setField(bitsize,mbar);
+
+ int whoami=fork();
+ reconciled_set hostA( bitsize, (whoami==0?ReadSet(fileA):ReadSet(fileB)) ,
pp, mbar, numvals, whoami );
+ //reconciled_set hostB( bitsize, ReadSet(fileB), pp, mbar, numvals );
+
+ vec_ZZ_p diff_vector = hostA.fullReconcile();
+ if (whoami==0) exit(0); // don't need this process hereafter
+
+ cout << "Differences are: " << diff_vector << endl;
+ diff_vector.kill();
+ }
+ else if (staticTest) {
+ cout << "STATIC TEST:" << endl;
+ if(steps==1)
+ cout << "testing with b = " << bitsize << " p =" << pp << ", mbar = " <<
mbar << ", k = " << numvals << ", common = " << setCommon << ", diff = " <<
setDiff;
+ else
+ cout << "testing with steps = " << steps;
+ cout << ", confirm ";
+ if (confirm) cout << "on. "; else cout << "off. ";
+ cout << endl << endl;
+
+ if (steps==1) { // i.e. just one simple test
+ cout << "Test ";
+ if
(reconciled_set::test(bitsize,setCommon,setDiff,pp,mbar,numvals,confirm))
+ cout << "passed." << endl;
+ else
+ cout << "failed." << endl; }
+ else { // i.e. a wide-spectrum test of the system
+ cout << "Testing " << steps << " random reconciliations" << endl;
+ cout << "( bitsize, # common, # different, partition factor, mbar,
redundancy factor)... status" << endl;
+ long acc_time_set=0,acc_time_comput=0, acc_time_comm=0,
+ acc_bytes_sent=0,acc_bytes_received=0;
+ for (int ii=0; ii<steps; ii++) {
+ // pick random parameter values
+ int bitsize,setCommon,setDiff,
+ pp=RandomBnd(MAX_PP)+MIN_PP,
+ mbar=RandomBnd(MAX_MBAR)+MIN_MBAR,
+ numvals;
+ do {bitsize=RandomBnd(MAX_B)+MIN_B;
+ setCommon=RandomBnd(MAX_COMMON);
+ setDiff=RandomBnd(MAX_DIFF);
+ if (setCommon+setDiff==0) setCommon++; }
+ while (setCommon+setDiff > power(ZZ_two,bitsize));
+ do {numvals=RandomBnd(MAX_K)+MIN_K;}
+ while (numvals > power(ZZ_two,bitsize-1) - 2);
+ cout << "#" << ii << " (" << bitsize << "," << setCommon << "," <<
setDiff << "," << pp << "," << mbar << "," << numvals << ")..." << flush;
+ if
(reconciled_set::test(bitsize,setCommon,setDiff,pp,mbar,numvals,true))
+ cout << "ok" << endl;
+ else
+ cout << "FAILURE ... try increasing k!" << endl;
+ sleep(1); // allow all sockets to close, etc.
+ // accumulate statistics
+ acc_time_set+=reconciled_set::time_setup;
acc_time_comput+=reconciled_set::time_comput;
acc_time_comm+=reconciled_set::time_comm;
+ acc_bytes_sent+=reconciled_set::bytes_sent;
acc_bytes_received+=reconciled_set::bytes_received;
+ }
+ // copy accumulated values to reconciled_set for display
+ reconciled_set::time_setup = acc_time_set; reconciled_set::time_comput =
acc_time_comput; reconciled_set::time_comm = acc_time_comm;
+ reconciled_set::bytes_sent = acc_bytes_sent;
reconciled_set::bytes_received = acc_bytes_received;
+ }
+ }
+ else if (dynamicTest) {
+ cout << "DYNAMIC TEST:" << endl
+ << "testing with b = " << bitsize << ", p = " << pp << ", mbar = " <<
mbar << ", k = " << numvals << " confirm ";
+ if (confirm) cout << "on, "; else cout << "off, ";
+ cout << endl << " prA = " << pr_addA << ", pB = " << pr_addB
<< ", pR = " << pr_rec << ", steps = " << steps << endl;
+
+ cout << "Test result was: " <<
(reconciled_set::test(bitsize,pp,mbar,numvals,confirm,pr_addA, pr_addB, pr_rec,
steps)) << endl;
+
+ }
+ else {
+ cout << "ERROR: Command not recognized." << endl;
+ return(-1);
+ }
+
+ // display measurement statistics
+ displayMeas();
+ return 0;
+}
Added: gnunet-java/consensus/node.cpp
===================================================================
--- gnunet-java/consensus/node.cpp (rev 0)
+++ gnunet-java/consensus/node.cpp 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,37 @@
+#include "node.h"
+#include "prob_recon_support.h"
+
+// IMPLEMENTATION of node class functions
+node::node(vec_ZZ_p& subset_pp, vec_ZZ_p& samples, int p, int mbar, int
the_kk, int bitsize, ZZ strt, ZZ stp)
+ /* Constructor for node
+ R: Subset in vector space whose hashes have to be stored, samples,
number of subpartitions
+ E: Creates node
+ M: valids - makes it contain the validation points for this node
+ */
+ {
+ start = strt;
+ stop = stp;
+ setsize=subset_pp.length();
+ child = new node*[p];
+ for(long ii=0;ii<p;ii++)
+ child[ii]=NULL;
+
+ if(setsize <= samples.length())
+ {
+ node_type = 1; // Terminal Node
+ hash_vector=subset_pp;
+ }
+ else
+ {
+ node_type = 0; //Non Terminal Node
+ hash_vector=calc_poly(subset_pp,samples);
+ valids = compute_validationpoints(mbar,
+ the_kk,
+ power(ZZ_two,bitsize)+mbar/2 + 2,
+ ZZ_p::modulus() - (mbar/2) + 1,
+ start); // start item serves as a seed for the random numbers
+ extra_hashes = calc_poly(subset_pp,valids); //Extra
sample points evaluation for probabilistic
+ }
+ // cout << "\nNode type:" <<node_type;
+ // cout << ", Node setsize:"<<setsize;
+ }
Added: gnunet-java/consensus/node.h
===================================================================
--- gnunet-java/consensus/node.h (rev 0)
+++ gnunet-java/consensus/node.h 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,46 @@
+#ifndef NODE
+#define NODE
+
+// A node in the partition tree
+#include "NTL/matrix.h"
+#include "NTL/mat_ZZ_p.h"
+#include "NTL/vec_ZZ.h"
+#include "NTL/ZZ.h"
+#include "NTL/ZZ_p.h"
+#include "NTL/vec_ZZ_p.h"
+#include <math.h>
+#include "NTL/vec_vec_ZZ_p.h"
+#include "NTL/ZZ_pX.h"
+#include "NTL/ZZ_pXFactoring.h"
+
+using namespace NTL;
+
+class node
+/* This class defines nodes in the partition-tree data structure used to
amortize
+** the computational cost of characteristic polynomial evaluations over
insertions
+** and deletions into the database.
+*/
+
+{
+ public:
+
+ vec_ZZ_p hash_vector;
+ vec_ZZ_p extra_hashes; //For verifying interpolation
+ vec_ZZ_p valids; // validation points for the rational function -
deviation from theory, as these should be randomly chosen for each
synchronization (?)
+ ZZ start,stop;
+ short int node_type;
+ long setsize;
+ node** child;
+
+ node(){} //Default Constructor
+
+ node(vec_ZZ_p& subset_pp, vec_ZZ_p& samples, int p, int mbar, int
the_kk, int bitsize, ZZ strt, ZZ stp);
+ /* Constructor for node
+ R: Subset in vector space whose hashes have to be stored, samplepoints,
number of subpartitions
+ E: Creates node
+ M:
+ */
+
+ ~node(){ valids.kill(); hash_vector.kill(); extra_hashes.kill();}
+};
+#endif
Added: gnunet-java/consensus/prob_recon_support.cpp
===================================================================
--- gnunet-java/consensus/prob_recon_support.cpp
(rev 0)
+++ gnunet-java/consensus/prob_recon_support.cpp 2012-11-08 09:50:08 UTC
(rev 24832)
@@ -0,0 +1,277 @@
+// This is the probabilistic reconciliation emulation program.
+
+// WORKS WITH PALM FEB 27th 2001
+
+/* Set Reconciliation Implementation*/
+// Include Files
+#include <NTL/matrix.h>
+#include <NTL/mat_ZZ_p.h>
+#include <NTL/vec_ZZ.h>
+#include <NTL/ZZ.h>
+#include <NTL/ZZ_p.h>
+#include <NTL/vec_ZZ_p.h>
+#include <cmath>
+#include <NTL/vec_vec_ZZ_p.h>
+#include <NTL/ZZ_pX.h>
+#include <NTL/ZZ_pXFactoring.h>
+#include <cstdlib>
+#include <ctime>
+#include "prob_recon_support.h"
+
+using namespace std;
+using namespace NTL;
+
+
+vec_ZZ_p compute_samplepoints(const long numberof,const ZZ_p fieldminus1)
+// This function calculates Sample points and stores the result in a vector
which is returned by the function.
+// number_of - Number of desired sample points.
+//fieldminus1 - for a field chosen to be over prime p, fieldminus1 = p-1.
+{
+ vec_ZZ_p temp;
+ temp.SetLength(numberof);
+ for(long ii=0;ii<numberof;ii++) //Setting samplepoints to 0,-1,1,-2,2 .....
+ {
+ if ((ii % 2)==0) temp[ii]=ii/2;
+ else temp[ii]=fieldminus1-ii/2;
+ if (ii == 0) temp[ii]=0;
+ }
+ // cout << (rep(fieldminus1)+1) << ": " << temp << endl << endl;
+ return temp;
+}
+
+
+vec_ZZ_p compute_validationpoints(const int mbar, const int numpoints, const
ZZ start, const ZZ stop, ZZ seed)
+/*
+ R: the value of mbar and the number of validation points
+ validation points are chosen uniformly at random in the range start
... stop inclusive
+ 0 <= start <= stop <= ZZ_p::modulus - 1
+ E: Validation points so they dont clash with the sample points
+ M:
+*/
+{
+ vec_ZZ_p returnvector;
+ returnvector.SetLength(numpoints);
+ SetSeed(seed); // reset the random number seed to its default state (so
that valids is consistent among clients) --- nodes on different machines must
have consistent random numbers
+ for(long ii=0;ii<numpoints;ii++)
+ returnvector[ii]= to_ZZ_p(RandomBnd(stop-start)+start);
+ return returnvector;
+}
+
+vec_ZZ_p calc_poly(vec_ZZ_p& set, vec_ZZ_p& samplepoints)
+// This function calculates the polynomial formed by the elements of "set" at
the "sample points" and returns the vector containing the
+// evaluated set polynomials at each sample point. Characteristic Polynomial
evaluations.
+
+{
+ long samplepointvectorsize=samplepoints.length();
+ ZZ_p temp;
+ vec_ZZ_p polyval;
+ polyval.SetLength(samplepointvectorsize);
+ for(long ii=0;ii<samplepointvectorsize;ii++)
+ {
+ conv(temp,to_ZZ("1"));
+ for(long jj=0;jj<set.length();jj++)
+ {
+ temp*=(samplepoints[ii]-set[jj]);
+ }
+ polyval[ii]=temp;
+ }
+
+ return polyval;
+}
+
+
+
+
+long calc_diff_ma_mb(vec_ZZ_p& A, vec_ZZ_p& B)
+//This function calculates "d" = |Sa|-|Sb|
+{
+ long temp = A.length()-B.length();
+ return temp;
+}
+
+long calc_mabar(long mbar,long d)
+// This Function calculates ma_bar based on mbar and d
+//It returns the floor value
+
+{
+ long rtnvalue;
+ if((mbar+d)%2!=0)
+ rtnvalue=(mbar+d-1)/2;
+
+ else
+ rtnvalue=(mbar+d)/2;
+ if (rtnvalue<=0) rtnvalue=1; //Added this in the part2 program to take care
of parasitic case mbar=1.
+ return rtnvalue;
+
+}
+
+
+
+long calc_mbbar(long mbar,long d)
+// This Function calculates mb_bar based on mbar and d. Similar to the
calc_mabar function.
+{
+ long rtnvalue;
+ if((mbar-d)%2!=0)
+ rtnvalue=(mbar-d-1)/2;
+ else
+ rtnvalue=(mbar-d)/2;
+ if (rtnvalue<0) rtnvalue=0; //Added this in the part2 program to prevent
negative problems
+return rtnvalue;
+}
+
+mat_ZZ_p makeA(mat_ZZ_p vmat,long rank,long mbar)
+//Reducing the A matrix into rank*rank size. (This is done after Gauss
elimination
+{
+ long ii,jj;
+
+ vec_vec_ZZ_p tempmat;
+ mat_ZZ_p tmat;
+ tempmat.SetLength(rank);
+ for(ii=0;ii<rank;ii++)
+ {
+ tempmat[ii].SetLength(rank);
+ for(jj=0;jj<rank;jj++)
+ {
+ tempmat[ii][jj]=vmat[ii][jj];
+ }
+ }
+
+ tmat.SetDims(rank,rank);
+
+ MakeMatrix(tmat,tempmat);
+ return tmat;
+}
+
+
+
+
+vec_ZZ_p makeB(mat_ZZ_p& vmatrix,long& rank,long& mbar,long& d)
+//Reducing the B matrix into rank*1 size
+{
+ long ii;
+
+ long mabar=calc_mabar(mbar,d);
+ long mbbar=calc_mbbar(mbar,d);
+ //cout <<"\n MBAR = "<<mbar;
+ vec_ZZ_p temp;
+ temp.SetLength(rank);
+ for (ii=0;ii<rank;ii++)
+ temp[ii]=vmatrix[ii][mabar+mbbar];
+ return temp;
+}
+
+
+
+vec_ZZ_p backsubstitutesolve(mat_ZZ_p& mat, vec_ZZ_p& bvec, long rank,long
totalcoeffs)
+//Solve by back substitution - mat is the LHS rank*rank matrix. bvec is the
RHS rank size matrix
+{
+ vec_ZZ_p rtntemp;
+
+ long ii,jj;
+
+ rtntemp.SetLength(totalcoeffs);
+ //rtntemp.SetLength(rank);
+ for(ii=rank-1;ii>=0;ii--)
+ {
+ rtntemp[ii]=bvec[ii]/mat[ii][ii];
+ for(jj=0;jj<rank;jj++)
+ {
+ bvec[jj]=bvec[jj]-rtntemp[ii]*mat[jj][ii];
+ }
+ }
+ for(ii=rank;ii<totalcoeffs;ii++) //Setting the other coeffs - from index
mbar-rank upto mbar to 0
+ rtntemp[ii]=0;
+ return rtntemp;
+}
+
+
+
+int match_value(ZZ_pX& PX,ZZ_pX& QX,vec_ZZ_p& PCEVALS,vec_ZZ_p&
EXTRASPS,vec_ZZ_p& EXTRAEVALS)
+/* This function returns 0 if more Sample Points are needed, else returns a 1
if no more sample points are needed */
+
+{
+ long ii;
+
+ long num_of_points = EXTRASPS.length();
+ int returnvalue=1;
+ ZZ_p p,q;
+ for(ii=0;ii<num_of_points;ii++)
+ {
+ p = eval(PX, EXTRASPS[ii]);
+ q = eval(QX, EXTRASPS[ii]);
+ //cout <<q;
+ if (q !=0)
+ {
+ if(EXTRAEVALS[ii]==0)
+ {
+ returnvalue=0;
+ break;
+ }
+ if (p/q != PCEVALS[ii]/EXTRAEVALS[ii])
+ {
+ returnvalue=0;
+ // cout << "\nBreak1";
+ break;
+ }
+ // cout << "\nNo break";
+ }
+ else
+ {
+ if (EXTRAEVALS[ii]!=0)
+ {
+ returnvalue=0;
+ break;
+ }
+ }
+ }
+ return returnvalue;
+}
+
+void reconstruct(vec_ZZ_p& B,long& mm,long& old_mm)
+{
+ long ii;
+
+ vec_ZZ_p newvector;
+ cout <<"\nNeed new_mbar-old_mbar more char. polynomial evaluations of
Host B (PDA): (Enter "<< mm-old_mm << " more at the appropriate sample
points:\n";
+
+ cin >> newvector;
+
+ for(ii=old_mm;ii<mm;ii++)
+ B[ii]=newvector[ii-old_mm];
+}
+
+ZZ prime_to_use()
+ /* R: User Input of the bitsize of data being reconciled
+ E: Returns a suitable prime number to construct the finite field and init
ZZ_p
+ M:
+ */
+{
+ //The primes
+ ZZ prime[7];
+ GenPrime(prime[0],10); //Generating prime numbers 10bits,18
bits...514 bits
+ GenPrime(prime[1],18);
+ GenPrime(prime[2],34);
+ GenPrime(prime[3],66);
+ GenPrime(prime[4],130);
+ GenPrime(prime[5],258);
+ GenPrime(prime[6],514);
+ long sizearray[7]={8,16,32,64,128,256,512};
+ // User data
+ long bitsize;
+ cout <<"\nEnter the bitsize of the data being reconciled. Choose
between 8/16/32/64/128/256/512: ";
+ cin >>bitsize;
+ long location=0;
+ long temp=8;
+ while((location<7)&&(temp<bitsize)) //To determine which prime field
to use.
+ {
+ temp*=2;
+ location++;
+ }
+ ZZ tempZZ=prime[location];
+ ZZ_p::init(tempZZ);
+ cout << "\nAlright, I am using "<< prime[location] << " as the Finite
field over which to do the math here.";
+ return(tempZZ);
+}
+
+
+
Added: gnunet-java/consensus/prob_recon_support.h
===================================================================
--- gnunet-java/consensus/prob_recon_support.h (rev 0)
+++ gnunet-java/consensus/prob_recon_support.h 2012-11-08 09:50:08 UTC (rev
24832)
@@ -0,0 +1,73 @@
+#ifndef PROB_RECON_SUPPORT
+#define PROB_RECON_SUPPORT
+
+// Include Files
+#include <cstdlib>
+#include <ctime>
+#include <NTL/matrix.h>
+#include <NTL/mat_ZZ_p.h>
+#include <NTL/vec_ZZ.h>
+#include <NTL/ZZ.h>
+#include <NTL/ZZ_p.h>
+#include <NTL/vec_ZZ_p.h>
+#include <math.h>
+#include <NTL/vec_vec_ZZ_p.h>
+#include <NTL/ZZ_pX.h>
+#include <NTL/ZZ_pXFactoring.h>
+#include "constants.h"
+
+using namespace NTL;
+
+vec_ZZ_p compute_samplepoints(const long numberof, const ZZ_p fieldminus1);
+// This function calculates Sample points and stores the result in a vector
which is returned by the function.
+// number_of - Number of desired sample points.
+// fieldminus1 - for a field chosen to be over prime p, fieldminus1 = p-1.
+
+vec_ZZ_p compute_validationpoints(const int mbar, const int numpoints, const
ZZ start, const ZZ stop, ZZ seed = ZZ_zero);
+/*
+ R: the value of mbar and the number of validation points
+ E: Validation points so they dont clash with the sample points
+ M:
+ Date: 28th November 2002
+*/
+
+vec_ZZ_p calc_poly(vec_ZZ_p& set, vec_ZZ_p& samplepoints);
+// This function calculates the polynomial formed by the elements of "set" at
the "sample points" and returns the vector containing the
+// evaluated set polynomials at each sample point. Characteristic Polynomial
evaluations.
+
+// AUXILIARY PROCEDURES
+long calc_diff_ma_mb(vec_ZZ_p& A, vec_ZZ_p& B);
+//This function calculates "d" = |Sa|-|Sb|
+
+long calc_diff_ma_mb_1(long& A,long& B);
+
+long calc_mabar(long mbar,long d);
+// This Function calculates ma_bar based on mbar and d
+//It returns the floor value
+
+long calc_mbbar(long mbar,long d);
+// This Function calculates mb_bar based on mbar and d. Similar to the
calc_mabar function.
+
+mat_ZZ_p construct_vandermonde_matrix(const vec_ZZ_p& samplepoints,const
vec_ZZ_p& RF, const vec_ZZ_p& bmatrix, const long mbar, const long d);
+// This function constructs the Vandemonde Matrix.
+//RF is the Rational function vector (all the fi s) bmatrix is the RHS Matrix
of size m bar.
+
+vec_ZZ_p construct_RHS_constant_vector(vec_ZZ_p& RF,vec_ZZ_p&
samplepoints,long& rank,long& mbar, long& d);
+//Constructs the rhs for the vandrmonde matrix - the bmatrix . RF is the
Rational Function Matrix. Rank is the rank of the LHS Matrix
+
+mat_ZZ_p makeA(mat_ZZ_p vmat,long rank,long mbar);
+//Reducing the A matrix into rank*rank size. (This is done after Gauss
elimination
+
+vec_ZZ_p makeB(mat_ZZ_p& vmatrix,long& rank,long& mbar,long& d);
+//Reducing the B matrix into rank*1 size
+
+vec_ZZ_p backsubstitutesolve(mat_ZZ_p& mat, vec_ZZ_p& bvec, long rank,long
totalcoeffs);
+//Solve by back substitution - mat is the LHS rank*rank matrix. bvec is the
RHS rank size matrix
+
+int match_value(ZZ_pX& PX,ZZ_pX& QX,vec_ZZ_p& PCEVALS,vec_ZZ_p&
EXTRASPS,vec_ZZ_p& EXTRAEVALS);
+/* This function returns 0 if more Sample Points are needed, else returns a 1
if no more sample points are needed */
+
+void reconstruct(vec_ZZ_p& B,long& mm,long& old_mm);
+ZZ prime_to_use();
+
+#endif
Added: gnunet-java/consensus/prob_reconcile.cpp
===================================================================
--- gnunet-java/consensus/prob_reconcile.cpp (rev 0)
+++ gnunet-java/consensus/prob_reconcile.cpp 2012-11-08 09:50:08 UTC (rev
24832)
@@ -0,0 +1,155 @@
+#include "prob_recon_support.h"
+#include "prob_reconcile.h"
+#include "node.h"
+#include "reconciled_set.h"
+
+/*This is the native basic set reconciliation procedure */
+
+int reconcile_aux(reconciled_set* base, node* rootA, node* rootB, vec_ZZ_p&
returnvalue)
+/*
+ Function to run the basic reconciliation algorithm.
+ R: base contains the base class which contains, among other things,
sample points and evaluations of powers of these sample points
+ M: returnvalue - returns 0 if reconciliation is unsuccessful
+ E:
+*/
+
+{
+ long ii,jj;
+
+ // initialize local variables
+ vec_ZZ_p& HASamplevalues=rootA->hash_vector;
+ vec_ZZ_p& A_EVALS=rootA->extra_hashes;
+ vec_ZZ_p& HBSamplevalues=rootB->hash_vector;
+ vec_ZZ_p& B_EVALS=rootB->extra_hashes;
+ vec_ZZ_p& validationpoints=rootA->valids;
+ long asize=rootA->setsize;
+ long bsize=rootB->setsize;
+
+ vec_ZZ_p RF; //Rational function at sample points fits
+
+ vec_ZZ_p bvector; //RHS of Vandemonde equation
+ vec_ZZ_p bredvector; //The reduced RHS of the Vandermonde matrix size =
rank
+ ZZ_p fieldminus1; // holds p-1 for GF(p)
+
+ long mbar = HASamplevalues.length();
+
+
+ long d = asize-bsize; //Calculate d =|A|-|B|
+ if (d>mbar || d < -mbar) // then too many differences ... hopeless
+ return 0;
+
+ ZZ tempzz = ZZ_p::modulus();
+ conv(fieldminus1, tempzz-1); //Setting up the value of fieldminus1
+
+ //Calculate the Rational RF function at the sample points. m bar Rational
functions for m bar Sample points
+ RF.SetLength(mbar);
+ for(ii=0;ii<mbar;ii++)
+ {
+ RF[ii]=HASamplevalues[ii]/HBSamplevalues[ii];
+ }
+
+ //timevar3=clock();
+ vec_ZZ_p HBData;
+ HBData.SetLength(bsize); //This is a redundant albatross. Just to minimise
perturbation in palm program
+
+ bvector.SetLength(mbar); //This vector holds the RHS of the
Vandermonde Equations (As in MATRIX FORM)
+
+ bvector=base->construct_RHS_constant_vector(RF,mbar,d); //Computing
bvector. Note mbar,mbar argument since rank=mbar so far
+
+ mat_ZZ_p vmatrix;//This will hold the Vandermonde matrix
+ vmatrix = base->construct_vandermonde_matrix(RF,bvector,d);//Constructing
the Vandemonde Matrix
+
+ long mabar=calc_mabar(mbar,d);
+ long mbbar=calc_mbbar(mbar,d);;
+ long rank=gauss(vmatrix,mbar); //GAUSSIAN ELIMINATION
+ if (rank > mabar+mbbar) rank = mabar+mbbar; //TRY
+
+ bvector.SetLength(rank); //Take only the rank number of bvector constituents
+
+
+ mat_ZZ_p vredmatrix;// Vandermonde Reduced Matrix using only rank*rank
dimensions
+ vredmatrix.SetDims(rank,rank);
+ vredmatrix = makeA(vmatrix,rank,mbar); //Make the VanderMonde Matrix with
size Rank*Rank
+
+ bredvector.SetLength(rank);
+ bredvector = makeB(vmatrix,rank,mbar,d);
+ vmatrix.kill();
+
+
+ //Now Solving the Vandemonde Matrix by Back Substitution
+ vec_ZZ_p coeff_vector; //Holds the solution
+
+ //long mbbar=calc_mbbar(mbar,d);
+ coeff_vector.SetLength(mabar+mbbar);
+
+ coeff_vector=backsubstitutesolve(vredmatrix,bredvector,rank,mabar+mbbar);
+ vredmatrix.kill(); //Get rid of the huge chunk
+ bredvector.kill();
+ vec_ZZ_p coeffP;
+ vec_ZZ_p coeffQ;
+
+ if(rank >mabar)
+ {
+ coeffP.SetLength(mabar+1); //+1 is added beacuse the polynomial is
monic and we need to add this fact as the highest degree term p0
+ coeffQ.SetLength(1+mabar+mbbar-mabar); //Adding 1 for q0
+ }
+ else
+ {
+ coeffP.SetLength(mabar+1);
+ coeffQ.SetLength(1+mbbar);
+ }
+
+ long Plength=coeffP.length(); //Sizes of P & Q
+ long Qlength=coeffQ.length();
+
+ coeffP[Plength-1]=1; //Setting the coeff corresponding to the highest power
= 1 (Monic)
+ coeffQ[Qlength-1]=1;
+
+ for(ii=0;ii<Plength-1;ii++) //Getting the other coefficients from the
Solution to the VanderMonde Equations. p1 = index 0, p2 = index 1 etc.
+ coeffP[ii]=coeff_vector[Plength-2-ii]; //Plengh was added a +1 becasue of
p0 not being included.
+ for(jj=0;jj<Qlength-1;jj++)
+ coeffQ[jj]=coeff_vector[mabar+mbbar-jj-1];
+
+
+ ZZ_pX P; //These are the ZZ_pX avatars of coeffP & CoeffQ ( which in turn
are of type vec_ZZ_p )
+ ZZ_pX Q;
+ conv(P,coeffP);//Convert coefficients to polynomials
+ conv(Q,coeffQ);
+ coeffP.kill();
+ coeffQ.kill();
+
+ ZZ_pX gcdvalue;
+ gcdvalue= GCD(P,Q); //GCD calculation
+
+ P=P/gcdvalue; //Reducing by getting rid of common factors
+ Q=Q/gcdvalue;
+
+ vec_ZZ_p numerator;
+ vec_ZZ_p denominator;
+
+ returnvalue=numerator; //This is simply to define returnvalue = [] initially
+// vec_ZZ_p returnvalue;
+ int rtnbool=0;
+ if (match_value(P,Q,A_EVALS,validationpoints,B_EVALS)==0) ;
+ else
+ {
+ rtnbool=1;
+ // cout <"\n B I N G O !!! Match!!! \n";
+ numerator.SetLength(Plength-deg(gcdvalue));
+ denominator.SetLength(Qlength-deg(gcdvalue));
+
+ FindRoots(numerator,P); //Factorize P - Numerator
+
+ FindRoots(denominator,Q); //Factorize Q - Denominator
+
+ //cout<<"A Data not in B: "<<numerator;
+ //cout<<"\n\nB data not in A: "<<denominator;
+ // cout <<"\n";
+ returnvalue=denominator;
+ }
+ //cout <<"\nreconcile() Returning: "<<returnvalue;
+ numerator.kill();
+ denominator.kill();
+ return rtnbool;
+}
+
Added: gnunet-java/consensus/prob_reconcile.h
===================================================================
--- gnunet-java/consensus/prob_reconcile.h (rev 0)
+++ gnunet-java/consensus/prob_reconcile.h 2012-11-08 09:50:08 UTC (rev
24832)
@@ -0,0 +1,30 @@
+#ifndef PROB_RECON
+#define PROB_RECON
+
+// Include Files
+#include "NTL/matrix.h"
+#include "NTL/mat_ZZ_p.h"
+#include "NTL/vec_ZZ.h"
+#include "NTL/ZZ.h"
+#include "NTL/ZZ_p.h"
+#include "NTL/vec_ZZ_p.h"
+#include <math.h>
+#include "NTL/vec_vec_ZZ_p.h"
+#include "NTL/ZZ_pX.h"
+#include "NTL/ZZ_pXFactoring.h"
+#include <stdlib.h>
+#include <time.h>
+
+int reconcile(vec_ZZ_p& HASamplevalues,vec_ZZ_p& A_EVALS,vec_ZZ_p&
HBSamplevalues, vec_ZZ_p& B_EVALS,vec_ZZ_p& samplepoints, vec_ZZ_p&
validationpoints, long asize,long bsize,vec_ZZ_p& returnvalue);
+/*
+ Function to run the basic reconciliation algorithm.
+ R: Requires the sample point evelations of the characteristic
polynomials (H*Samplevalues),
+ Extra evaluation points for testing the interpolated rational
function (*_EVALS),
+ Sample points
+ Validation points
+ Set sizes of set A and set B
+ E:
+ M: returnvalue - returns 0 if reconciliation is unsuccessful
+*/
+
+#endif
Added: gnunet-java/consensus/reconciled_set.cpp
===================================================================
--- gnunet-java/consensus/reconciled_set.cpp (rev 0)
+++ gnunet-java/consensus/reconciled_set.cpp 2012-11-08 09:50:08 UTC (rev
24832)
@@ -0,0 +1,754 @@
+#include <time.h>
+#include <math.h>
+#include <strstream>
+#include "prob_recon_support.h"
+#include "prob_reconcile.h"
+#include "node.h"
+#include "constants.h"
+#include "reconciled_set.h"
+
+// external variables
+extern long reconciled_set::time_comput;
+extern long reconciled_set::time_comm;
+extern long reconciled_set::time_setup;
+extern long reconciled_set::bytes_sent;
+extern long reconciled_set::bytes_received;
+extern char genericBuf[MAXBUF]; // all purpose character buffer
+
+ZZ reconciled_set::getField(int bit_s, int m_bar) {
+ return NextPrime( 3*power(ZZ_two,bit_s-1) + m_bar);
+}
+
+void reconciled_set::setField(int bit_s, int m_bar) {
+ ZZ_p::init(getField(bit_s,m_bar));
+
+}
+
+reconciled_set::reconciled_set(int the_bitsize, vec_ZZ_p initialSet, int
the_pp, int the_mbar, int the_kk, short client)
+{
+ int ii;
+ clock_t start = clock();
+
+ bitsize=the_bitsize; pp=the_pp; mbar=the_mbar; kk=the_kk;
+ if (!(mbar%2)) mbar++; // Make this odd to optimize matrix back
substitution
+
+ // set dependent variables
+ fieldsize = getField(bitsize,mbar);
+ fieldbits = (int) ceil(log(fieldsize)/log(2));
+ dataStart = to_ZZ_p(mbar/2 + 1);
+ max = fieldsize-1;
+ ZZ_p::init( fieldsize);
+ samples = compute_samplepoints(mbar,to_ZZ_p(max));
+ // compute and store powers of the sample points
+ powSamples = new vec_ZZ_p[samples.length()];
+ for (ii=0; ii<samples.length(); ii++) // for various samples
+ for (int pow=0; pow<=mbar; pow++) // and various powers
+ append(powSamples[ii],power(samples[ii],pow)); //
compute the corresponding power
+ sock = new mySocket(DEFAULT_PORT,client); // open a socket
connection
+ // determine who is the master and who the slave
+ char myNum[2],otherNum[2];
+ do {
+ SetSeed(to_ZZ(clock()));
+ myNum[0] = (char) RandomBnd(10)+'0'; myNum[1]='\0';
+ (*sock) << myNum;
+ (*sock) >> otherNum;
+ } while (myNum[0]==otherNum[0]);
+ master = (myNum[0]>otherNum[0]); // this way one and only one reconcile
is the master (resp. slave)
+
+ // adjust the initialSet elements
+ for (ii=0; ii<initialSet.length(); ii++)
+ initialSet[ii]+=dataStart;
+ pTree = recurse_make(initialSet, pp, ZZ_zero, max);
+
+ time_setup += clock() - start;
+}
+
+reconciled_set::~reconciled_set() {
+ for (int ii=0; ii<samples.length(); ii++)
+ powSamples[ii].kill();
+ delete[] powSamples;
+ deletetree(pTree,pp);
+ samples.kill();
+ delete sock;
+}
+
+vec_ZZ_p reconciled_set::halfReconcile() { //const reconciled_set &other) {
+
+ vec_ZZ_p temp=the_reconing(pTree); //,other.pTree);
+ // fix up the data
+ for (int ii=0; ii<temp.length(); ii++)
+ temp[ii]-=dataStart;
+
+ return temp;
+}
+
+vec_ZZ_p reconciled_set::fullReconcile() {
+ clock_t start = clock();
+ ostrstream ostream(genericBuf,MAXBUF); // for socket stuff
+ istrstream istream(genericBuf,MAXBUF);
+
+ // normal master-slave
+ vec_ZZ_p diff = halfReconcile();
+
+ // invert master and slave and try again (getting the result from the
other host)
+ master=!master;
+ vec_ZZ_p other_diff, temp = halfReconcile();
+ master=!master; // restore to original
+
+ if (!master) {
+ ostream << temp << ends;
+ (*sock) << genericBuf;
+ (*sock) >> genericBuf;
+ istream >> diff;
+ }
+ else {
+ (*sock) >> genericBuf;
+ istream >> other_diff;
+ append(diff,other_diff); // put together the results
+ ostream << diff << ends; // send results to other party
+ (*sock) << genericBuf;
+ }
+
+ // clean up and finish
+ other_diff.kill(); temp.kill();
+ time_comput += clock() - start;
+ return(diff);
+}
+
+// AUXILIARY PROCEDURES
+vec_ZZ_p reconciled_set::return_terminal_data(node*& root,long p)
+{
+ vec_ZZ_p tempreturn;
+ if(root!=NULL)
+ {
+ if(root->node_type == 1) //Terminal node
+ {
+ append(tempreturn,root->hash_vector);
+ }
+ else
+ {
+ for(long ii=0;ii<p;ii++)
+ {
+
append(tempreturn,return_terminal_data(root->child[ii],p));
+ }
+ }
+ }
+ return tempreturn;
+}
+
+vec_ZZ_p difference_set(vec_ZZ_p set1, vec_ZZ_p set2)
+ /*
+ R: 2 sets whose differences has to be found
+ E: Returns set2\set1
+ M:
+ Date: 28th Nov 2002
+ */
+{
+ long ii,jj;
+
+ int flag=1;
+ vec_ZZ_p returnset;
+ returnset.SetLength(0);
+ for(ii=0;ii<set2.length();ii++)
+ {
+ flag = 1;
+ for (jj=0;jj<set1.length();jj++)
+ if(set2[ii]==set1[jj])
+ {
+ flag = 0;
+ break;
+ }
+ if (flag) append(returnset, set2[ii]);
+ }
+ return returnset;
+}
+
+void reconciled_set::transmitNode(node *nd) {
+ // transmits a node through the existing socket
+ ostrstream oo(genericBuf,MAXBUF);
+ if (nd==NULL)
+ oo << (short) 0 << ends; // transmit the fact that the node
is null
+ else
+ oo << (short) 1 << nd->hash_vector << nd->extra_hashes <<
nd->valids << nd->node_type << ',' << nd->setsize << ends; // put out the
important information; use commas as separators
+ (*sock) << genericBuf;
+}
+
+node *reconciled_set::receiveNode() {
+ // receives a node through the existing socket
+ (*sock) >> genericBuf;
+ istrstream ii(genericBuf,MAXBUF);
+ short code;
+ char SEP; // the separator
+ ii >> code;
+ if (code==0) return NULL; // i.e. the node is empty
+ node *temp = new node[1];
+ ii >> temp->hash_vector >> temp->extra_hashes >> temp->valids
>> temp->node_type
+ >> SEP >> temp->setsize;
+ return temp;
+}
+
+int iters=0;
+
+vec_ZZ_p reconciled_set::the_reconing(node* rootA) //,node* rootB)
+{
+ vec_ZZ_p return_vector;
+ node* rootB;
+
+ int myIter = iters++;
+
+ // set up rootA and rootB
+ transmitNode(rootA); // always transmit first
+ rootB=receiveNode();
+
+ if (rootB==NULL) { // SET B IS EMPTY - return an empty return_vector
+ if (rootA!=NULL && rootA->node_type!=1) { // i.e.
only send if rootA is a non-terminal; otherwise superfluous
+ vec_ZZ_p temp2 = return_terminal_data(rootA,pp);
+ sock->pushVec(temp2);
+ temp2.kill();
+ }
+ }
+ else if(rootB->node_type==1) // ROOT B IS TERMINAL, so hash_vector
simply contains Set B
+ {
+
+ if (rootA==NULL || rootA->node_type==1) // rootA is
also a terminal
+ if (master)
+ return_vector =
difference_set(return_terminal_data(rootA,pp),rootB->hash_vector);
+ else
+ return_vector =
difference_set(rootB->hash_vector,return_terminal_data(rootA,pp));
+ else { // rootA is a non-terminal ... send its info to
the other host
+ vec_ZZ_p temp2 = return_terminal_data(rootA,pp);
+ sock->pushVec(temp2);
+ if (master)
+ return_vector =
difference_set(temp2,rootB->hash_vector);
+ else
+ return_vector =
difference_set(rootB->hash_vector,temp2);
+ temp2.kill();
+ }
+ }
+ else // ROOT B IS NON-TERMINAL
+ if (rootA==NULL) //Set A is empty - this means all of rootB is
needed to complete A
+ {
+ return_vector = sock->getVec(); // i.e. get
return_terminal_data(rootB,pp);
+ }
+ else if(rootA->node_type==1) // rootA is a terminal node
+ {
+ vec_ZZ_p temp2 = sock->getVec();//i.e. get
return_terminal_data(rootB,pp);
+ if (master)
+ return_vector =
difference_set(rootA->hash_vector,temp2);
+ else
+ return_vector =
difference_set(temp2,rootA->hash_vector);
+ temp2.kill();
+ }
+ else //Try reconcile()
+ {
+ vec_ZZ_p temp;
+ int reconsuccess;
+ if (master) // master indicates the direction
of reconciliation
+ reconsuccess = reconcile_aux(this,
rootA,rootB,temp);
+ else
+ reconsuccess = reconcile_aux(this,
rootB,rootA,temp);
+
+ //reconcile returns S_B-S_A
+ if(!reconsuccess) //Reconcile failed condition
+ {
+ for(int ii=0;ii<pp;ii++)
+ {
+
append(return_vector,the_reconing(rootA->child[ii])); //,rootB->child[ii]));
+ }
+ }
+ else
+ {
+ return_vector=temp;
+ temp.kill();
+ }
+ }
+
+ if (rootB)
+ delete[] rootB; // free up node memory
+
+ return return_vector;
+}
+
+void reconciled_set::deletetree(node*& root,long p)
+ // Delete the tree from memory
+{
+ if(root!=NULL)
+ {
+ long ii;
+ //root->hash_vector.kill();
+ //root->extra_hashes.kill();
+ for(ii=0;ii<p;ii++)
+ {
+ deletetree(root->child[ii],p);
+ }
+ delete [] root->child;
+ delete root;
+ }
+}
+
+
+inline long reconciled_set::position_of_child(ZZ_p element_to_add,ZZ start, ZZ
stop, long p, ZZ d)
+ // computes the proper subdivision in which to put element_to_add
within start ... stop
+{
+ long position = to_long(((rep(element_to_add)-start)/d));
+ if (position >= p)
+ position = p-1;
+ return position;
+}
+
+inline long reconciled_set::position_of_child(ZZ_p element_to_add,ZZ start, ZZ
stop, long p)
+ // computes the proper subdivision in which to put element_to_add
within start ... stop
+{
+ ZZ d = (stop-start)/to_ZZ(p);
+ if (d<1) d = ZZ_one;
+ return position_of_child(element_to_add,start,stop,p,d);
+}
+
+node* reconciled_set::recurse_make(vec_ZZ_p set, long p, ZZ start,ZZ stop)
+ /* R: set - whose characteristic polynomial has to be computed and stored in
the node
+ p - Number of children the node will have in case there is a
need to further partition
+ start - the lower end (inclusive) of the sub-field's region
+ stop - the upper end (inclusive) of the sub-field's region
+ E: Nodes of partition tree
+ M: Node --> partition tree
+ */
+{
+ long jj;
+
+ node* temppointer;
+ temppointer = new node(set,samples,p,mbar,kk,bitsize,start,stop);
+ if (temppointer->node_type==0) //Non terminal node check
+ {
+ long index;
+ ZZ n,d;
+
+ vec_ZZ_p* subsets;
+ subsets = new vec_ZZ_p[p];
+
+ d = (stop-start)/to_ZZ(p);
+ if (d<1) d = ZZ_one;//to_ZZ("1");
+
+ for(jj=0;jj<set.length();jj++)
+ {
+
+ index =
position_of_child(set[jj],start,stop,p,d);
+ append(subsets[index],set[jj]);
+ clear(set[jj]); // save memory
+ }
+ set.kill();
+
+ ZZ temp = start;
+ ZZ newstart;
+ ZZ newstop;
+
+ for(jj=0;jj<p;jj++)
+ {
+ newstart = temp;
+ temp = temp+d;
+ newstop = temp-1;
+
+ if(jj==(p-1)) newstop = stop;
+ if ((subsets[jj].length()!=0))
+ {
+
temppointer->child[jj]=recurse_make(subsets[jj],p,newstart,newstop);
+ subsets[jj].kill();
+ }
+ else
+ temppointer->child[jj]=NULL;
+ }
+
+ delete [] subsets;
+ }
+
+ return(temppointer);
+}
+
+
+void reconciled_set::add_to_tree(node*& root,long p, ZZ_p& element_to_add)
+ // adds element_to_add to the tree rooted at "root"
+{
+ long ii;
+ long mbar = samples.length();
+ if(root->node_type==1) //Terminal Node
+ {
+
+ if(root->setsize<mbar) //Space in the terminal node -
don't need to convert to internal node
+ {
+
append(root->hash_vector,element_to_add);
+ root->setsize+=1;
+ }
+ else //Need to make this an internal node...
+ {
+ vec_ZZ_p set_vector =
root->hash_vector; //Save the set.
+ append(set_vector,element_to_add);
+ ZZ start = root->start;
+ ZZ stop = root->stop;
+ deletetree(root,p); //Destroy the root
node
+ root =
recurse_make(set_vector,p,start,stop);
+ }
+ }
+ else // Non terminal node
+ {
+ root->setsize +=1;
+
+ for(ii=0;ii<mbar;ii++)
+ root->hash_vector[ii] *=
(samples[ii]-element_to_add); //Updating sample point evaluations
+
+ for(ii=0;ii<root->valids.length();ii++)
+ root->extra_hashes[ii] *=
(root->valids[ii]-element_to_add); //Updating validation point evaluations
+
+
+ long position =
position_of_child(element_to_add,root->start,root->stop,p);
+
+ if (root->child[position] == NULL) //Need to compute
its range to create the node
+ {
+ ZZ d = (root->stop -
root->start)/to_ZZ(p);
+ if (d<1)
+ d = ZZ_one; //to_ZZ("1");
+
+ ZZ st = root->start + position*d;
+ ZZ stp = st+d-1;
+ if(position==(p-1))
+ stp = root->stop;
+
+ vec_ZZ_p subset_pp;
+ subset_pp.SetLength(1);
+ subset_pp[0]=element_to_add;
+ root->child[position] = new
node(subset_pp,samples,p,mbar,kk,bitsize,st,stp);
+ }
+ else
+
add_to_tree(root->child[position],p,element_to_add);
+ }
+}
+
+void reconciled_set::delete_from_tree(node*& root,long p,ZZ_p
element_to_delete)
+ /*
+ R:
+ E: Deletes the element_to_delete from the tree root
+ M: root
+ Data: 12th Dec 2002
+ Note: Suggest incorprating element _to_delete not in tree error
condition gracefully.
+ */
+{
+ long ii;
+ long mbar = samples.length();
+ root->setsize-=1;
+ if (root->node_type == 0) //Non Terminal node
+ {
+ if(root->setsize>mbar+1) //Dont need to convert to a
terminal node
+ {
+ for(ii=0;ii<mbar;ii++) //Samples
+ {
+ root->hash_vector[ii]
/= (samples[ii]-element_to_delete);
+ }
+ for(ii=0;ii<root->valids.length();ii++)
//Validation points
+ {
+ root->extra_hashes[ii]
/= (root->valids[ii]-element_to_delete);
+ }
+ long position =
position_of_child(element_to_delete,root->start,root->stop,p);
+
delete_from_tree(root->child[position],p,element_to_delete);
+ }
+ else //Need to convert to a terminal node
+ {
+ vec_ZZ_p allelements =
return_terminal_data(root,p);
+ vec_ZZ_p newset;
+ long alllength = allelements.length();
+ newset.SetLength(alllength-1);
+ long ctr=0;
+ for(ii = 0 ;ii<alllength;ii++)
//Weeding out the element to be deleted
+ {
+ if
(allelements[ii]!=element_to_delete)
+ newset[ctr++] =
allelements[ii];
+ }
+
+ ZZ start = root->start;
+ ZZ stop = root->stop;
+ deletetree(root,p);
+ root =
recurse_make(newset,p,start,stop);
+ }
+ }
+ else //Terminal Node
+ {
+ if(root->setsize==1) // Means the node needs to be
deleted since this one element is the element to be deleted
+ {
+ deletetree(root,p);
+ root = NULL;
+ }
+ else
+ {
+ vec_ZZ_p tempset;
+ tempset.SetLength(root->setsize-1);
+ long ctr=0;
+ for(ii = 0 ;ii<root->setsize;ii++)
//Weeding out the element to be deleted
+ {
+ if
(root->hash_vector[ii]!=element_to_delete)
+ tempset[ctr++]
= root->hash_vector[ii];
+ }
+ root->hash_vector = tempset;
+ }
+ }
+}
+
+inline bool elementOf(const ZZ_p item, const vec_ZZ_p vect) {
+ for (int ii=0; ii < vect.length(); ii++)
+ if (item == vect[ii])
+ return true;
+ return false;
+}
+
+bool reconciled_set::test(int the_bitsize, int setCommon, int setDiff, int
the_pp,int the_mbar,int the_kk, bool confirm) {
+ int ii,jj;
+ ostrstream ostream(genericBuf,MAXBUF); // for socket stuff
+ istrstream istream(genericBuf,MAXBUF);
+ clock_t start = clock(); // keep track of time
+
+ // initialize
+ reconciled_set::setField(the_bitsize,the_mbar);
+ time_comput = 0; time_setup=0; time_comm=0; bytes_sent=0;
bytes_received=0; // i.e. reset measurements
+ SetSeed(to_ZZ(time(NULL)));
+ ZZ_p randBits;
+
+ // generate the common elements
+ vec_ZZ_p commonV;
+ for (ii=0; ii<setCommon; ii++) { // only add unique elements
+ do {
+ randBits = to_ZZ_p(RandomBits_ZZ(the_bitsize));
+ } while(elementOf(randBits,commonV));
+ append(commonV,randBits);
+ }
+
+ // generate sets for A and B
+ // randomly allocate differences between A and B
+ int Adiff, Bdiff;
+ Adiff = to_int(RandomBnd(to_ZZ(setDiff)));
+ Bdiff = setDiff - Adiff;
+
+ int whoami = fork(); // fork into two processes
+ if (whoami==0) // set the random number seeds differently for each
subprocess
+ { setDiff = Bdiff; // i.e. I'm B
+ SetSeed(to_ZZ(1+time(NULL))); }
+ else
+ setDiff = Adiff;
+
+ vec_ZZ_p setA(commonV),setB(commonV);
+ for (ii=0; ii<setDiff; ii++) {
+ ZZ_p randBits = to_ZZ_p(RandomBits_ZZ(the_bitsize));
+ // if (RandomBits_ulong(1)==0) {// add to A if 0,
otherwise nothing
+ do {
+ randBits = to_ZZ_p(RandomBits_ZZ(the_bitsize));
+ } while(elementOf(randBits,setA) ||
elementOf(randBits,commonV));
+ append(setA,randBits);
+ //}
+ }
+
+ time_setup += clock() - start;
+ // reconcile the sets
+ //cout << whoami << " commonV: " << commonV << endl;
+ //cout << whoami << " setA: " << setA << endl << endl;
+ reconciled_set hostA( the_bitsize, setA, the_pp, the_mbar,
the_kk,whoami );
+ vec_ZZ_p diff_vector = hostA.fullReconcile();
+
+ if (confirm) {
+ ostrstream ostream(genericBuf,MAXBUF); // for socket stuff
+ istrstream istream(genericBuf,MAXBUF);
+
+ // transmit and receive setB
+ ostream << setA << ends;
+ (*hostA.sock) << genericBuf;
+ (*hostA.sock) >> genericBuf;
+ istream >> setB;
+ }
+
+ if (whoami==0) { delete hostA.sock; exit(0);} // i.e. close socket and
kill process
+
+ if (confirm) {
+ vec_ZZ_p real_diff = difference_set(setA,setB);
+ append(real_diff,difference_set(setB,setA));
+
+ // real_diff = diff_vector iff real_diff - diff_vector =
diff_vector - real_diff = 0
+ vec_ZZ_p check = difference_set(real_diff,diff_vector);
+ if (check.length()!=0) {
+ cout << "Set A: " << setA << endl
+ << "Set B: " << setB << endl
+ << "Differences: " << diff_vector <<
endl
+ << "Real diff: " << real_diff << endl
+ << "Error: " << check << endl;
+ return(false);
+ }
+ check = difference_set(diff_vector,real_diff);
+ if (check.length()!=0) {
+ cout << "Set A: " << setA << endl
+ << "Set B: " << setB << endl
+ << "Differences: " << diff_vector <<
endl
+ << "Real diff: " << real_diff << endl
+ << "Error: " << check << endl;
+ return(false);
+ }
+ }
+ else {
+ // just print out the results
+ cout << "Set A: " << setA << endl
+ << "Set B: " << setB << endl
+ << "Differences: " << diff_vector << endl;
+ }
+ return(true); // all confirmations passed
+}
+
+bool reconciled_set::test(int the_bitsize, int the_pp,int the_mbar,int the_kk,
bool confirm, float pr_addA, float pr_addB, float pr_rec, long steps) {
+ reconciled_set::setField(the_bitsize,the_mbar);
+ ZZ startSeed = to_ZZ(time(NULL)); // random number seed
+ ZZ_p randBits;
+ vec_ZZ_p diff_vector;
+
+ // initialize
+ time_comput = 0; time_comm=0; time_setup=0; bytes_sent=0;
bytes_received=0; // i.e. reset measurements
+ vec_ZZ_p setA, setB;
+
+ int numRecons=0;
+
+ ZZ randA, randB, randRec;
+ int whoami = fork();
+ reconciled_set hostA( the_bitsize, vec_ZZ_p(), the_pp, the_mbar,
the_kk, whoami);
+ // reconciled_set hostB( the_bitsize, vec_ZZ_p(), the_pp,
the_mbar, the_kk );
+
+ for (long ii=0; ii<steps; ii++) {
+ // make 3 random numbers of appropriate size
+ {
+ SetSeed(startSeed+ii); // synchronize random number
generations
+ if (pr_rec != 0) randRec = RandomBnd(to_ZZ(1/pr_rec));
// this must occur right after synchronizing reandom number seeds
+ }
+
+ if (whoami==0 && pr_addA != 0) randA =
RandomBnd(to_ZZ(1/pr_addA));
+ if (whoami!=0 && pr_addB != 0) randB =
RandomBnd(to_ZZ(1/pr_addB));
+
+ if (whoami==0 && randA == 0) {
+ do { randBits = to_ZZ_p(RandomBits_ZZ(the_bitsize)); }
+ while (elementOf(randBits,setA));
+ append(setA,randBits); // for the record
+ hostA.add_element(randBits); // add to the host
+ }
+ if (whoami!=0 && randB == 0) {
+ do { randBits = to_ZZ_p(RandomBits_ZZ(the_bitsize)); }
+ while (elementOf(randBits,setA));
+ append(setA,randBits); // for the record
+ hostA.add_element(randBits); // add to the host
(actually host B)
+ }
+ if (randRec == 0) {
+ diff_vector = hostA.fullReconcile();
+
+ if (confirm) {
+ // transmit and receive setB
+ hostA.sock->pushVec(setA);
+ setB = hostA.sock->getVec();
+
+ // CHECK THE ANSWER
+ vec_ZZ_p real_diff = difference_set(setA,setB);
+ append(real_diff,difference_set(setB,setA));
+
+ // real_diff = diff_vector iff real_diff -
diff_vector = diff_vector - real_diff = 0
+ vec_ZZ_p check =
difference_set(real_diff,diff_vector);
+
+ if (check.length()!=0) {
+ cout << "Set A: " << setA << endl
+ << "Set B: " <<
setB << endl
+ << "Differences: " <<
diff_vector << endl
+ << "Real diff: " <<
real_diff << endl
+ << "Error: " <<
check << endl;
+ return(false);
+ }
+ check = difference_set(diff_vector,real_diff);
+ if (check.length()!=0) {
+ cout << "Set A: " << setA << endl
+ << "Set B: " <<
setB << endl
+ << "Differences: " <<
diff_vector << endl
+ << "Real diff: " <<
real_diff << endl
+ << "Error: " <<
check << endl;
+ return(false);
+ }
+ }
+ }
+ }
+
+ if (whoami==0) {delete hostA.sock; exit(0);} // i.e. close socket and
kill process
+
+ return(true);
+}
+
+void reconciled_set::add_element(ZZ_p el) {
+ clock_t start = clock();
+ el+=dataStart; // element has to be adjusted as in
reconciled_set::reconciled_set
+ add_to_tree(pTree, pp, el);
+ time_setup += clock() - start;
+}
+
+// void reconciled_set::del_element(ZZ_p el) {
+// delete_from_tree(pTree,pp,el+dataStart);
+// }
+
+vec_ZZ_p reconciled_set::construct_RHS_constant_vector(vec_ZZ_p& RF,long&
rank, long& d)
+ //Constructs the rhs for the Vandermonde matrix - the bmatrix . RF is
the Rational Function Matrix. Rank is the rank of the LHS Matrix
+
+{
+ vec_ZZ_p rtnvalue;
+ long ii;
+ long mabar=calc_mabar(mbar,d);
+ long mbbar=calc_mbbar(mbar,d);
+
+ //long mbbar=mbar-mabar;
+ rtnvalue.SetLength(rank);
+ for(ii=0;ii<rank;ii++)
+ rtnvalue[ii]=RF[ii]*powSamples[ii][mbbar]-powSamples[ii][mabar];
+ // i.e.
RF[ii]*power(samplepoints[ii],mbbar)-power(samplepoints[ii],mabar);
+
+ return rtnvalue;
+}
+
+mat_ZZ_p reconciled_set::construct_vandermonde_matrix(const vec_ZZ_p& RF,
const vec_ZZ_p& bmatrix, const long d)
+ // This function constructs the Vandemonde Matrix.
+ //RF is the Rational function vector (all the fi s) bmatrix is the RHS
Matrix of size m bar.
+
+{
+ //cout <<"\nmbar = "<<mbar<<"\nd = "<<d;
+ long ii,jj,pp; //Counters
+
+ long mabar = calc_mabar(mbar,d);
+ long mbbar = calc_mbbar(mbar,d);
+ //long mbbar=mbar-mabar;
+ // cout <<"\nmabar = "<<mabar;
+ // cout <<"\nmbbar = "<<mbbar;
+
+ vec_vec_ZZ_p returnmatrix;
+ returnmatrix.SetLength(mbar);
+
+ for(ii=0;ii<mbar;ii++)
+ {
+ returnmatrix[ii].SetLength(mabar+mbbar+1); //+1 is for the B matrix
+
+ for(jj=0;jj<mabar;jj++)
+ returnmatrix[ii][jj]=powSamples[ii][mabar-jj-1];
+ for( jj=0;jj<mbbar;jj++)
+ returnmatrix[ii][jj+mabar]=
-RF[ii]*powSamples[ii][mbbar-jj-1];
+ returnmatrix[ii][mabar+mbbar]=bmatrix[ii]; //Augumented matrix
+ }
+
+ // //Adding alternate rows (starting from row 1 to mbar-1; leaving out
row 0)
+ // for(ii=1;ii<mbar-1;ii=ii+2)
+ // for(long jj=0;jj<=mabar+mbbar;jj++)
+ // returnmatrix[ii][jj]+=returnmatrix[ii+1][jj];
+
+ // //Dividing each alternate row by 2
+ // for(ii=1;ii<mbar;ii=ii+2)
+ // for(jj=0;jj<=mabar+mbbar;jj++)
+ // returnmatrix[ii][jj]/=2;
+
+ // //Subtracting alternate rows (Leaving Row 0 alone) row 2 = row 2 -
row 1 etc
+ // for(ii=2;ii<mbar;ii=ii+2)
+ // for(jj=0;jj<=mabar+mbbar;jj++)
+ // returnmatrix[ii][jj]-=returnmatrix[ii-1][jj];
+
+ mat_ZZ_p mat_rtn;
+ mat_rtn.SetDims(mbar,mabar+mbbar+1);//+1 is for the B matrix
+ MakeMatrix(mat_rtn,returnmatrix);
+
+ return mat_rtn;
+}
Added: gnunet-java/consensus/reconciled_set.h
===================================================================
--- gnunet-java/consensus/reconciled_set.h (rev 0)
+++ gnunet-java/consensus/reconciled_set.h 2012-11-08 09:50:08 UTC (rev
24832)
@@ -0,0 +1,175 @@
+#ifndef RECONCILED_SET
+#define RECONCILED_SET
+/* RECONCILED_SET
+** A data structure for holding set elements that can be
+** quickly reconciled with other reconciled_set's.
+**
+** %M: sets and resets NTL's random number seed often
+*/
+
+#include <sys/types.h>
+#include <unistd.h>
+#include <math.h>
+#include <time.h>
+#include "NTL/matrix.h"
+#include "NTL/mat_ZZ_p.h"
+#include "NTL/vec_ZZ.h"
+#include "NTL/ZZ.h"
+#include "NTL/ZZ_p.h"
+#include "NTL/vec_ZZ_p.h"
+#include "NTL/vec_vec_ZZ_p.h"
+#include "NTL/ZZ_pX.h"
+#include "NTL/ZZ_pXFactoring.h"
+#include "node.h"
+#include "socket.h"
+
+// RECONCILED_SET
+class reconciled_set {
+
+public:
+ // CONSTRUCTION
+ reconciled_set(int the_bitsize, vec_ZZ_p initialSet, int the_pp,int
the_mbar,int the_kk, short client);
+ /* %R: 1 <= the_kk < 2^(the_bitsize-1) - 2
+ 2 <= the_pp
+ %M: most data structure elements, and the ZZ_p modulus
+ %E: basic constructor
+ if client = 0, sets up as a server, otherwise sets up as a
client
+ */
+ ~reconciled_set(); // destructor
+
+ // MANIPULATION
+ void add_element(ZZ_p el); // adds an element to the set
+ // void del_element(ZZ_p el); // deletes an element
from the set - not really useful
+ vec_ZZ_p halfReconcile(); // returns the contents
of this set - other host's set
+
//const reconciled_set &other); // returns the contents of this set - other
+ vec_ZZ_p fullReconcile(); // returns mutual difference
of set and other host's set (i.e. a halfReconcile in each direction)
+
+ // AUXILIARY
+ static void setField(int bitsize, int mbar); // sets the size of
ZZ_p being used
+ static bool test(int the_bitsize, int setCommon, int setDiff, int
the_pp, int the_mbar, int the_kk, bool confirm);
+ /*
+ %R: setCommon+setDiff < 2^(the_bitsize), the_kk <
2^(the_bitsize-1) - 2
+ sleep for one second after calling before running another
test (to allow sockets to close properly)
+ %E: reconcile two random sets with setCommon common elements
and setDiff differences.
+ If confirm is true, then the result of the reconciliation
is checked for accuracy.
+ The reamining parameters as in the constructor.
+
+ note that mutual difference is not computed in
the most efficient way possible, so
+ data gleanded from this procedure is suboptimal
+ */
+ static bool test(int the_bitsize, int the_pp,int the_mbar,int the_kk,
bool confirm, float pr_addA, float pr_addB, float pr_rec, long steps);
+ /*
+ %R: same as other test procedure, but 0<=pr_addA,pr_addB<=1
+ sleep for one second after calling before running another
test (to allow sockets to close properly)
+ %E: tests reconciliation in a dynamic setting where data is
added to host A
+ with probability pr_addA each step (starting from an empty
set) and to
+ host B with probability pr_addB each step for
a total of "steps" iterations.
+ Reconciliation occurs at the end of each
iteration with probability pr_rec.
+
+ note that mutual difference is not computed in
the most efficient way possible, so
+ data gleanded from this procedure is suboptimal
+ */
+
+ static long time_setup; // the amount of time spent on the last
timed operation (in seconds)
+ static long time_comput; // a secondary timer for time spent in
the last operation
+ static long time_comm; // a secondary timer for time spent
during communication
+ static long bytes_sent; // the amount of bits communicated in the
last measured opearation
+ static long bytes_received; // the amount of bits communicated in the
last measured opearation
+private:
+ int bitsize; // number of bits per vector
+ int pp; // number of partitions per node
+ int mbar; // maximum number of differences to reconcile
(i.e. recovery bound)
+ int kk; // redundancy factor (determines probability of
error)
+ ZZ fieldsize; // size of the underlying filed; a prime number
in this case
+ int fieldbits; // the number of bits needed to represent
fieldsize
+ /* The field is divided as follows:
+ ** -(mbar-1)/2 .. mbar/2 : sample evaluations for even
mbar (-mbar/2 .. (mbar-1)/2 for odd mbar)
+ ** mbar/2+1 .. 2^bit_size + mbar/2+1 : data values
+ ** 2^bit_size + mbar/2+2 .. -mbar/2 : random evaluations
+ */
+ ZZ_p dataStart; // i gets mapped to dataStart+i to avoid
colisions with the sample evaluations
+
+ ZZ max; // the maximum element in the field, = fieldsize
- 1
+ vec_ZZ_p samples; // sample points on which char poly is evaluated
+ vec_ZZ_p *powSamples; // powers of the sample points in the chosen
finite field
+ node* pTree; // the partition tree containing char poly
evaluations
+ mySocket *sock; // the socket for communicating with the
reconciling host
+ bool master; // if true, this class is the master, otherwise it
is the slave
+
+ // auxuliary procedures
+ static ZZ getField(int bitsize, int mbar);
+ // %E: returns the appropriate field size (of ZZ_p) to use for the
given parameter
+
+ vec_ZZ_p return_terminal_data(node*& root,long p);
+ /*R: The root of the tree, p is the partition factor
+ E: Returns the terminal elements of the tree in form of a
vec_ZZ_p
+ */
+
+ vec_ZZ_p the_reconing(node* rootA); //, node* rootB -- on the other
host);
+ /*
+ R: Pointer to roots of A tree; all nodes in on rootA must have
valids field equal to corresponding nodes on rootB on any reconciling host
+ E: returns {elements in root B} - {elements in root A} as a
vector
+ M:
+ */
+
+ void deletetree(node*& root,long p);
+ // Delete the tree from memory
+
+ node* recurse_make(vec_ZZ_p set, long p, ZZ start,ZZ stop);
+ /* R:
+ ** * set - whose characteristic polynomial has to be computed and
stored in the node
+ ** * samplepoints - in order to calculate the evaluations
+ ** * p - Number of children the node will have incase there is a need
to further partition
+ ** * start - the lower end (inclusive) of the sub-field's region
+ ** * stop - the upper end (inclusive) of the sub-field's region
+ ** E: Nodes of partition tree
+ ** M: Node --> partition tree
+ */
+
+ vec_ZZ_p construct_RHS_constant_vector(vec_ZZ_p& RF,long& rank,long& d);
+ /* %R: RF is a vector of values of the rational function
evaluations at the sample points
+ (i.e. RF[i] = f_i = rational function at i'th
sample point
+ rank is the rank of the LHS matrix in the system to be solved
+ d is difference in set size
|S_A| - |S_B|
+ %E: Constructs the rhs for the vandrmonde matrix -
i.e. the bmatrix
+ */
+
+ mat_ZZ_p construct_vandermonde_matrix(const vec_ZZ_p& RF, const
vec_ZZ_p& bmatrix, const long d);
+ /* %R: RF is a vector of values of the rational function
evaluations at the sample points
+ (i.e. RF[i] = f_i = rational function at i'th
sample point
+ bmatrix if the right-hand-side of the linear system to be solved
(size = mbar x 1)
+ d is difference in set size
|S_A| - |S_B|
+ %E: Constructs and returns a Vandermonde matrix
needed to interpolate the rational
+ function; performs some row operations to
optimize performance
+ */
+
+ // ... tree procuedures
+ long position_of_child(ZZ_p element_to_add,ZZ start, ZZ stop, long p,
ZZ d);
+ // computes the proper subdivision in which to put element_to_add
within start ... stop
+ long position_of_child(ZZ_p element_to_add,ZZ start, ZZ stop, long p);
+ // computes the proper subdivision in which to put element_to_add
within start ... stop, if d is not known
+ void add_to_tree(node*& root,long p, ZZ_p& element_to_add);
+ void delete_from_tree(node*& root,long p,ZZ_p element_to_delete);
+
+
+ void transmitNode(node *nd);
+ // transmits the important information in *nd
+
+ node *receiveNode();
+ // receives important information from a remote transmitNode operation,
and returns a node containing that information
+
+ // FRIENDS
+ friend int reconcile_aux(reconciled_set* base, node* rootA, node*
rootB, vec_ZZ_p& returnvalue);
+
+};
+
+// auxiliary procedures
+
+vec_ZZ_p difference_set(vec_ZZ_p set1, vec_ZZ_p set2);
+/*
+ R: 2 sets whose differences has to be found
+ E: Returns set2\set1
+ M:
+ Date: 28th Nov 2002
+*/
+#endif
Added: gnunet-java/consensus/socket.cpp
===================================================================
--- gnunet-java/consensus/socket.cpp (rev 0)
+++ gnunet-java/consensus/socket.cpp 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,225 @@
+// implements rudimentary sockets
+
+#include "socket.h"
+#include "reconciled_set.h"
+
+char genericBuf[MAXBUF]; // all purpose character buffer
+
+void sigchld_handler(int s)
+{
+ while(wait(NULL) > 0);
+}
+
+mySocket::mySocket(int thePort, int client) { // constructor
+ myPID = client;
+
+ // initialize vars
+ sizeMyBuf=0;
+
+ int sockDesc = socket(AF_INET, SOCK_STREAM, 0);
+ if (sockDesc==-1) {cout << "socket error" << endl; exit(-1); }
+
+ int yes=1;
+ if (setsockopt(sockDesc,SOL_SOCKET,SO_REUSEADDR,&yes,sizeof(int)) == -1) //
allow socket reuse
+ { cout << "setsockopt error" << endl; exit(-1); }
+
+ myAddr.sin_family = AF_INET;
+ myAddr.sin_port = htons(thePort);
+ myAddr.sin_addr.s_addr = INADDR_ANY; // i.e. my IP
+ memset(&myAddr.sin_zero,'\0',8); // this is extra padding
+
+ sa.sa_handler = sigchld_handler; // reap all dead processes
+ sigemptyset(&sa.sa_mask);
+ sa.sa_flags = SA_RESTART;
+ if (sigaction(SIGCHLD, &sa, NULL) == -1) { cout << "sigaction error" <<
endl; exit(-1); }
+
+ if (client==0) {
+ if (bind(sockDesc, (struct sockaddr *)&myAddr, sizeof(struct sockaddr)) ==
-1)
+ { cout << "bind error" << endl; exit(-1); }
+
+ if (listen(sockDesc,1) == -1) // only one one connection at a time
+ { cout << "listen error" << endl; exit(-1); }
+
+ // wait for connection
+ sin_size = sizeof(struct sockaddr_in);
+ if ((my_fd = accept(sockDesc, (struct sockaddr *)&otherAddr,
+
&sin_size)) == -1) { cout << "accept error" << endl; exit(-1); }
+ }
+ else {
+ otherAddr.sin_family = AF_INET;
+ otherAddr.sin_port = htons(thePort);
+ otherAddr.sin_addr.s_addr = INADDR_ANY;
+ memset(&otherAddr.sin_zero,'\0',8);
+ my_fd = sockDesc; // no new socket descriptors made
+ while
+ (connect(my_fd, (struct sockaddr *) &otherAddr,sizeof(struct sockaddr))
== -1) {
+ // wait a while
+ for (int ii=0; ii<10000; ii++) ;
+ }
+ }
+}
+
+mySocket::~mySocket() {
+ shutdown(my_fd,SHUT_RDWR);
+ close(my_fd); // close the socket
+}
+
+char *encode(const char *in) {
+ // return a compact encoding of the string "in"
+ // the current implementation is simple and very inefficient; a more
efficient
+ // implementation would pack two bytes at a time
+
+ int ii;
+
+ // change the input into a big number
+ ZZ inNum=ZZ_one; // need a place holder
+ for (ii=0; ii<strlen(in); ii++)
+ switch(in[ii]) {
+ case '0': case '1': case '2': case '3': case '4': case '5':
case '6': case '7': case '8': case '9':
+ inNum=14*inNum + (in[ii]-'0'); break;
+ case '[': inNum=14*inNum + 10; break;
+ case ']': inNum=14*inNum + 11; break;
+ case ',': inNum=14*inNum + 12; break;
+ case ' ': inNum=14*inNum + 13; break;
+ }
+
+ // convert inNum into a base 255 # (with 0 reservered for end of string)
+ int outLen = (int) ceil(log(inNum)/log(255.0));
+ char *out = new char[outLen+1];
+ int index=0;
+
+ while (inNum!=0) {
+ int nextChar = inNum % 255;
+ if (nextChar==128)
+ out[index]=127; // special shift to avoid conflict with
\0
+ else
+ out[index]=nextChar-128; // i.e. shift to range
-128..126
+ inNum=(inNum-nextChar)/255;
+ index++;
+ }
+ out[index]='\0'; // i.e. end of string
+
+ return out;
+}
+
+char *decode(const char *in) {
+ // return a decoding of 'in' (a string encoded with "encode") .. max
size is MAXBUF
+ // the current implementation is simple and very inefficient; a more
efficient
+ // implementation would unpack two bytes at a time
+
+ int ii, inLen = strlen(in);
+ char BUFFER[MAXBUF];
+ clock_t start = clock();// start timing
+
+ // convert input string into a number (it is output by "encode" in the
reverse order)
+ ZZ outNum=ZZ_zero;
+ for (ii=inLen-1; ii>=0; ii--)
+ if (in[ii]==127) // i.e. special code
+ outNum=outNum*255+128; // i.e. 127 maps to 0
+ else
+ outNum=outNum*255+in[ii]+128; // all other characters
map normally
+
+ int index=0;
+ while (outNum!=0) {
+ int nextChar = outNum % 14;
+ switch (nextChar) {
+ case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7:
case 8: case 9:
+ BUFFER[index++]=nextChar+'0'; break;
+ case 10: BUFFER[index++]='['; break;
+ case 11: BUFFER[index++]=']'; break;
+ case 12: BUFFER[index++]=','; break;
+ case 13: BUFFER[index++]=' '; break;
+ }
+ outNum=(outNum-nextChar)/14;
+ }
+ char *out = new char[index];
+ // reverse the buffer
+ for (ii=1; ii<index; ii++) // ignore the leading 1 which is a
placeholder
+ out[ii-1]=BUFFER[index-1-ii];
+ out[index-1]='\0'; // terminate properly
+
+ reconciled_set::time_comm += clock() - start; // compute elapsed time
+ return out;
+}
+
+const mySocket& mySocket::operator<< (const char *s) const {
+ clock_t start = clock(); // start timing
+
+ // encode the input
+ const char *toSend = encode(s);
+
+ int numSent, numBytes = strlen(toSend)+1; // +1 includes the trailing \0
+ if ((numSent=send(my_fd,toSend, numBytes*sizeof(char),0))==-1)
+ { cout << "send error on PID " << myPID << endl; exit(-1); }
+ if (numSent!=numBytes)
+ { cout << "Unhandled (send) packet fragmentation ... consult
programmer." << endl; exit(-1); }
+ reconciled_set::bytes_sent+=numSent;
+// cout << setw(6) << myPID << ": sent " << s << "(";
+// for (int ii=0; ii<strlen(toSend); ii++)
+// cout << (int) toSend[ii] << " ";
+// cout << ")" << " +" << numSent << " bytes = " <<
reconciled_set::bytes_sent << " bytes sent." << endl;
+
+ delete[] toSend; // i.e. reclaim memory
+ reconciled_set::time_comm += clock() - start; // compute elapsed time
+ return *this;
+}
+
+const mySocket& mySocket::operator>> (char *s) const {
+ clock_t start = clock(); // start timing
+
+ static char myBuf[MAXBUF];
+ static int sizeMyBuf=0; // number characters stored so far
+
+
+ int numReceived, numBytes;
+ if (sizeMyBuf==0) { // i.e. get more from the socket
+ if ((numReceived=recv(my_fd,myBuf,MAXBUF,0))==-1)
+ { cout << "receive error" << endl; exit(-1); }
+ sizeMyBuf=numReceived;
+ reconciled_set::bytes_received+=numReceived;
+ //cout << myPID << ": got " << myBuf << " (" << numReceived <<
")" << endl;
+ }
+
+ int bufSize = strlen(myBuf);
+ char *temp = decode(myBuf); // extract the string from the buffer
+ strcpy(s,temp);
+ delete[] temp; // i.e. deallocate the memory
+
+ memmove(myBuf,myBuf+bufSize+1,(MAXBUF-bufSize-1)*sizeof(char));// shift
down the buffer
+ sizeMyBuf-=(bufSize+1);
+
+// cout << setw(6) << myPID << "received " << s << "(";
+// for (int ii=0; ii<strlen(s); ii++)
+// cout << (int) s[ii] << " ";
+// cout << ")" << endl;
+
+
+ reconciled_set::time_comm += clock() - start; // compute elapsed time
+ return *this;
+}
+
+const vec_ZZ_p mySocket::getVec() {
+ // gets a vector from the socket
+ istrstream ii(genericBuf,MAXBUF);
+ vec_ZZ_p temp;
+
+ *this >> genericBuf; // get the string
+ ii >> temp; // convert it to a vector
+
+ return(temp); // return the vector
+}
+
+const void mySocket::pushVec(vec_ZZ_p vec) {
+ ostrstream oo(genericBuf,MAXBUF);
+ oo << vec; // convert the vector into a string
+ *this << genericBuf; // output the vector to the socket
+}
+
+// int main(void)
+// {
+// mySocket sock;
+// ZZ_p::init(to_ZZ("10"));
+
+// vec_ZZ_p temp=sock.getVec();
+// sock.pushVec(temp);
+// }
Added: gnunet-java/consensus/socket.h
===================================================================
--- gnunet-java/consensus/socket.h (rev 0)
+++ gnunet-java/consensus/socket.h 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,57 @@
+#ifndef SOCKETH
+#define SOCKETH
+// implements rudimentary sockets
+
+#include <cstdio>
+#include <cstdlib>
+#include <iostream>
+#include <strstream>
+#include <unistd.h>
+#include <errno.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/socket.h>
+#include <netinet/in.h>
+#include <arpa/inet.h>
+#include <sys/wait.h>
+#include <signal.h>
+#include <iomanip>
+#include <NTL/matrix.h>
+#include <NTL/mat_ZZ_p.h>
+#include <NTL/vec_ZZ.h>
+#include <NTL/ZZ.h>
+#include <NTL/ZZ_p.h>
+#include <NTL/vec_ZZ_p.h>
+#include <NTL/vec_vec_ZZ_p.h>
+#include <NTL/ZZ_pX.h>
+#include <NTL/ZZ_pXFactoring.h>
+#include "constants.h"
+
+using namespace std;
+
+extern void sigchld_handler(int s);
+const int MAXBUF = 500000;
+const int DEFAULT_PORT = 16041;
+
+class mySocket {
+public:
+ mySocket() {}; // default constructor
+ mySocket(int thePort, int client); // construct and listens for a
socket on thePort (client==0) or connects to thePort (client==1)
+ ~mySocket(); // destructor
+
+ const mySocket& operator<< ( const char *s) const; // push a string
onto the socket. string must consist only of 0-9 [ ] , and space
+ const mySocket& operator>> ( char *s) const; // get a string
from the socket. string must consist only of 0-9 [ ] , and space ... s should
be allocated
+ const vec_ZZ_p getVec(); // gets a vector
from the socket represented by at most MAXBUF characters
+
+ const void pushVec(vec_ZZ_p vec); // pushes a vector
onto the socket
+ int myPID; // the process ID of the process running this socket
+
+private:
+ int my_fd;
+ struct sockaddr_in myAddr, otherAddr;
+ struct sigaction sa;
+ socklen_t sin_size;
+ char myBuf[MAXBUF]; // the characters received so far
+ int sizeMyBuf; // number characters stored so far
+};
+#endif
Added: gnunet-java/consensus/usage.txt
===================================================================
--- gnunet-java/consensus/usage.txt (rev 0)
+++ gnunet-java/consensus/usage.txt 2012-11-08 09:50:08 UTC (rev 24832)
@@ -0,0 +1,90 @@
+NAME:
+ reconcile.exe - fast set reconciliation engine
+
+SYNOPSIS
+
+ reconcile.exe [-files | -static | -dynamic]
+ [-b <INT>] [-common <INT>] [-diff <INT>] [-p <INT>]
+ [-mbar <INT>] [-k <INT>] [-steps <INT>]
+ [-pA <FLOAT>] [-pB <FLOAT>] [-pR <FLOAT>]
+ [-fileA <STRING>] [-fileB <STRING>]
+
+ where <INT> is an integer, <FLOAT> is a floating point number, <STRING> is
a string.
+
+DESCRIPTION
+
+The various command-line options are described in the next section.
+This program has three modes of operations.
+
+-files: In this mode, the program reconciles sets in two files, wtih names
given by -fileA and
+ -fileB options. The user can also specify -b, -p, -mbar, and -k
options. Files are
+ assumed to be text files of the format:
+ [<el_1> <el_2> <el_3> ... <el_n>]
+ where elements el_i are space separated integers with number of bits
given by the
+ -b option.
+
+ EXAMPLE: the files "example_setA.txt" and "example_setB.txt" in the
source directory
+ can be reconciled with
+ reconcile.exe -files -fileA example_setA.txt -fileB example_setB.txt
+
+-static: (default) In this mode, the program reconciles two randomly
constructed sets. If
+ the -steps option is provided, then several different random
reconciliations are tried.
+ The user may specify the -b, -p, -mbar, -k, -steps, -common, and -diff
options.
+
+ EXAMPLE: The following example runs 10 different random reconciliations
+ reconcile.exe -static -steps 10 -confirm on
+
+-dynamic: In this mode, the program simulates a dynamic environment in which
changes are made
+ to two different sets in a dynamic setting. The sets are then
reconciled at random
+ intervals. This allows amortization of the computational complexity of
the
+ reconciliation algorithm over the various additions to the sets (rather
than all at
+ once, as in the -static case).
+
+ EXAMPLE: The following example tests a dynamic system in which both
sets initially
+ start as empty,a nd then setA is added elements with
probability 0.5 at each
+ iteration, set B with probability 0.3, and reconciliation
occurs in an
+ iteration with probability 0,1, for a total of 100 iterations:
+ reconcile.exe -dynamic -pA 0.5 -pB 0.3 -pR 0.1 -steps 100
+
+The various procedures can also be accessed directly through the C++ interface
in
+reconciled_set.h.
+
+OPTIONS
+
+The command-line options are:
+
+-b <bitsize>: determines the number of bits used to represent each element
in the set.
+-common <size>: the number of elements common to two random sets, by design.
+-diff <size>: max number of elements different between two random sets, by
design.
+-p <int>: the partition factor for the reconciliation; larger p use more
communication
+ bits but fewer communication rounds.
+-mbar <int>: the maximum number of differences on which to call the
underlying CPISync
+ algorithm; this affects the computation complexity of the
reconciliation
+ with higher numbers using to more computation time but
less communication.
+-k <int>: the redundancy factor affecting the probability of error of
the algorithm
+-steps <int>: the number of tests to perform (-static mode) or iterations
(-dynamic mode).
+-pA <FLOAT>: the probability of adding a random element to set A in a given
iteration.
+-pB <FLOAT>: the probability of adding a random element to set B in a given
iteration.
+-pR <FLOAT>: the probability of performing a reconciliation in a given
iteration.
+-fileA <STRING>:the name of the file containing the contents of set A.
+-fileB <STRING>:the name of the file containing the contents of set B.
+
+MEASUREMENT DATA
+
+The measurement data reported is:
+
+* Running time: Overall running time of the program.
+* setup: Running time for setup calculcations (e.g. sample polynomial
evals).
+* communication: Amount of time spend sending, encoding all data for
transmission, and
+ decoding all transmitted data (some overlap with
reconcilition time).
+* reconciliation:Amount of time for all of reconciliation, including
communication
+ time but excluding one-time setup costs.
+
+* Communication: Overall number of bytes communicated in the running of the
program.
+* transmitted: Number of bytes transmitted by one reconciling host.
+* received: NUmber of bytes received by the same reconciling host.
+
+---
+Practical Set Reconciliation. v Beta 0.998
+Initial implementation by Sachin Agarwal, Boston University (address@hidden)
+ Modifications by Ari Trachtenberg, Boston Unviersity (address@hidden)
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r24832 - in gnunet-java: . consensus,
gnunet <=