An Enhanced Distributed System to improve theTime Complexity of Binary Indexed Trees
Distributed Computing Systems are usually considered the most suitable model for practical solutions of many parallel algorithms. In this paper an enhanced distributed system is presented to improve the time complexity of Binary Indexed Trees (BIT). The proposed system uses multi-uniform processors with identical architectures and a specially designed distributed memory system. The analysis of this system has shown that it has reduced the time complexity of the read query to O(Log(Log(N))), and the update query to constant complexity, while the naive solution has a time complexity of O(Log(N)) for both queries. The system was implemented and simulated using VHDL and Verilog Hardware Description Languages, with xilinx ISE 10.1, as the development environment and ModelSim 6.1c, similarly as the simulation tool. The simulation has shown that the overhead resulting by the wiring and communication between the system fragments could be fairly neglected, which makes it applicable to practically reach the maximum speed up offered by the proposed model.
 XST User Guide, Xilinx Inc.
 The Algorithm Design Manual. TELOS, The Electronic Library of
 Digital Design: Principles and Practicese (4th Edition). Prentice Hall,
 Peter M. Fenwick. A new data structure for cumulative frequency tables.
SOFTWAREPRACTICE AND EXPERIENCE, 1994.
 Ralph C. Hilzer Helen D. Karatza. Performance analysis of parallel job
scheduling in distributed systems. Annual Simulation Symposium, 2003.
 TOPCODER Inc. Binary indexed trees
. http://www.topcoder.com/tc?module=Statices, December 2008.
 TOPCODER Inc. Range minimum query and lowest common ancestor.
http://www.topcoder.com/tc?module=Staticstor, January 2009.
 W. E. Johnston Q. M. Malluhi. Approaches for a reliable highperformance
distributed-parallel storage system. High Performance
Distributed Computing, 1996.
 Linda M.Wills Randall S. Janka. Specification and synthesis of real-time
embedded distributed and parallel multiprocessor-based signal processing
systems. International Conference on Compilers, Architecture and
Synthesis for Embedded Systems, 2000
 Vijay K. Naik Vinod G. J. Peris, Mark S. Squillante. Analysis of the
impact of memory in distributed parallel processing systems. Joint
International Conference on Measurement and Modeling of Computer