2002年趨勢百萬程式競賽 (初賽題目)

Introduction

Good Neighbors is a LAN-based groupware application. In the neighborhood, each user (neighbor) contributes a small amount of disk space to construct a collectively shared storage, which is globally accessible to all neighbors in the neighborhood. Neighbors can freely share files in this system, and the files are stored in a distributed way. This system has the following characteristics:

  1. Each user (neighbor) can access the neighborhood from any computer (a node) that physically resides on the LAN network with proper access rights.
  2. A shared file in the neighborhood is kept in pieces (fragments) on more than one node.
  3. A node does not have the ability to reconstruct the file just from its own fragment.
  4. A fault-tolerant mechanism should be provided so even if one or more machines are down, the file can still be correctly retrieved.

Architecture Overview

Global Directory Structure

All files in the neighborhood reside on a single level global directory, all the shared files are listed in this directory.

File Identification

A file is identified by its full name (file name with its path in the global directory) and its owner.  In other words, a "unique" file must have a unique combination of a full name and an owner. Therefore, two files with identical file names but different owners are treated as two unique files and can coexist in the global directory.

A file must have the following attributes:

Attribute Description
File Name The file name with an extension and path.  E.g. \pub\mystuff.doc

 

Creation time The time the file was put in the global directory (time according to the node that the user was on when he/she put the file in).

 

File Size The size of the file (not the fragments, or the size of a fragment).

 

Owner The user who put the file in the global directory.

 

Functional Requirements

Setup

The setup can either be an auto-installation script (a batch file or shell script) or an instruction to let users manually install the binaries. However, those who implement auto-installation scripts will earn more points based on the installation criteria.

The default installation path is:

For Windows: c:\Good_Neighbor

For Linux: /home/<current user>/Good_Neighbor

Application Behavior

After successful installation, the program should include a command line tool named gbn.exe (either in Windows or Linux) to support commands listed as the following:

(Note: All functions should behave similarly to the MS-DOS command line utility or Unix Shell commands; if there is any ambiguity, please refer to the MS-DOS command line utility or UNIX Shell commands.)

Function Parameter Example Description
start  user_name start  david  Starts the application. This function has to be called before all other functions can function properly.
setlocal  local_path local_path: local directory path setlocal  c:\my documents\ Sets the local directory.
put  local_filename local_filename: local file name

put public.doc

 Put a files from the local directory to the global directory.
get  [-o owner] remote_filename

[-o owner]: select owner

remote_filename: remote file name

 1. get -o David  homework.doc

2. get homework.doc

 Retrieves a file from the global directory to the local directory. If there are files with duplicate file names, the user can specify which file to get by specifying the owner using the -o flag. By default, the most current file will be retrieved.
ls  ls

 

 Shows all files in the global directory.

Displays all attributes of the file listed in File Identification.

exit   exit Leaves the neighborhood

 

File Manipulation Mechanism

Let N = all participants in the LAN (all nodes that have the program installed).

Let n = number of online neighbors in N (n <= N).

Let M = number of fragments of one file when putting the file (M <= n).

Let m = number of fragments in M that are accessible (m <= M).

 

Restrictions on  "ls", "put", "get":

"ls" and "del" must be operational when n >= 1.

Restrictions on "ls"

Only unique files are displayed. If there are duplicate files (with the same path and same owner), only the latest file should be displayed so that the file list is unambiguous.

Restrictions on "put"

When a file is "put" into the neighborhood, it is actually split into many fragments and each fragment is stored on one node.

Put is operational when n >= 3. In other words, min(M) = 3.

Restrictions on "get"

There are two restrictions on Get.

  1. The file is not salvageable when m = 1.

  2. The file must be salvageable when m >= (2/3)M.

Details are explained below.

M m Salvageable M m Salvageable
3 1 no 5 3 no restriction
2 yes 4 yes
3 yes 5 yes
4 1 no 6 1 no
2 no restriction 2 no restriction
3 yes 3 no restriction
4 yes 4 yes
5 1 no 5 yes
2 no restriction 6 yes

Click here for comprehensive use cases.

Sample Execution

PRE condition

There is one file, david6.doc in the local directory c:\my documents\.

Command Sample Output

start David 

 Entering neighborhood... Welcome!

setlocal c:\my documents\

 local directory is set to "c:\my documents\"
ls
david1.doc 2002/05/03 1:25pm 204,342 David
jenny2.txt 2002/02/04 11:50am 10,245 jenny
put david6.doc File put.
Get jenny2.txt File retrieved.
Exit Bye...

 

POST condition

The following files are present in c:\my documents\:

david6.doc

jenny2.txt

 

Test Environment

1.  At least six PCs will be used for testing.

Hardware specification: Intel Pentium III 600MHz, 128MB RAM, 20GB available hard disk space.

Operating System:

Contestants can choose any of the following environments to be designated as the test environments:

Microsoft Windows 2000 Professional (Service Pack 2), Windows XP Professional, Windows 98SE.

RedHat Linux 7.2 (full install) or Mandrake Linux 8.1 (full install).


2.  The testing environment is a closed, pure LAN environment, and each machine has an internal IP. All operating systems are installed with default protocols. No firewalls or routers are present in the environment.

Evaluation Process

  1. The contestants must inform Trend Micro of the desired test environment before July 14th.

  2. The contestants must email completed applications to contest@trend.com.tw before 11:50PM, July 15th.  Late applications will not be accepted. A complete application should contain the following items:

  1. Name of the team

  2. Source code

  3. The executable (binary) and any components the binary needs to run

  4. Installation guide, user manual or any documentation explaining the installation process

  5. Design documentation (all design decisions, implementation strategies, and system architecture must be documented here)

  6. Other documents if needed for explanatory purposes

  1. An email should not contain an attachment greater than 5MB. If the total size of the package is larger than 5MB, it should be divided into different pieces each less than 5MB and sent in separate emails.

  2. Testing and evaluation will commence July 16th.

  1.  Results will be announced on 6:00pm, July 22nd at http://www.trendmicro.com.tw/contest.

Evaluation Criteria

咀opyright 2002 Trend Micro Corporation. All Rights Reserved.