Gergely Ács Address: H-1521 Budapest Pf. 91., Hungary Office: Budapest, XI. Magyar tudósok körútja 2. Room I.E.429 Phone: + 36 1 463-2063,   Fax: + 36 1 463-3266 Curriculum Vitae   |   Publications   |   Miscellaneous

Miscellaneous items:

• Perl modules:
  • PinSketch (PinSketch-0.01.tar.gz): PinSketch provides an efficient way to find differences between two sets without having to communicate the sets, and with minimum information leakage. In particular, if we know that the size of the symmetric difference between two sets A and B is no greater than m, PinSketch can be used to recover the symmetric difference (i.e., A \ B U B \ A) knowing only the sketches of A and B (or a set from the two and the sketch of the other set), where a sketch has a size of m*b bits (b is the size of an element of the sets). Its computational complexity is O(m^2). This module is a simple perl interface for the PinSketch algorithm which has been implemented by Kevin Harmon and Leonid Reyzin in C++.
  • SetRecon (SetRecon-0.01.tar.gz): SetRecon is another algorithm to compute the differences between two sets. Similarly to PinSketch, it has near optimal communication complexity and minimal information leakage. Moreover, neither set needs to be maintained, it is enough to store their sketches, which can be incrementally updated. Similarly to PinSketch, the sizes of the sketches are independent of the sizes of A and B. SetRecon also allows to compute only the sizes of A \ B and B \ A without recovering their elements. In addition, if only the sketches of A and B are given, A \ B as well as B \ A can be separately recovered. On the other hand, compared to PinSketch, SetRecon has a computational complexity of O(m^3). This module is a perl interface for the stripped version of the original practical set reconciliation protocol which has been implemented by Sachin Agarwal and Ari Trachtenberg in C++.
  
  
• TinyOS 2.x modules:
  • GPSR (Ubisec&Sens download): GPSR (Greedy Perimeter Stateless Routing) is a geographic routing protocol proposed for wireless ad hoc and sensor networks that can be used to route data packets between any pair of nodes (i.e., it supports node-to-node communication). GPSR assumes that every sensor node is aware of its own location and the locations of its neighbors. In GPSR, nodes construct a planar subgraph based on the network topology in a distributive manner. This distributive planarization algorithm is GG (Gabriel Graph) in this current implementation. Forwarding a packet, each node first tries to select the next-hop towards the base station who is closest to the destination among all neighbors (greedy mode). If all neighbors are farther away from the destination than the forwarding node (i.e., there is a local minimum), then the forwarding node falls back to perimeter mode by using the planar subgraph to circumvent the local minimum. This module was only tested in TOSSIM.
  • PANEL (Ubisec&Sens download): PANEL is a Position-based Aggregator Node ELection protocol for wireless sensor networks. PANEL uses the geographical position information of the nodes to determine which of them should be the aggregators and ensures load balancing in the sense that each node is elected aggregator nearly equally frequently. The output of PANEL in case of every node is the knowledge of the aggregator's identifier and the next hop towards this aggregator. The motivation for the design of PANEL was to support TinyPEDS (Tiny Persistent Encrypted Data Storage), and other similar asynchronous sensor network applications.